A Simple Shell(使用的是兄弟树)

A Simple Shell

---

Time Limit:1s	Memory limit:32M
Accepted Submit:12	Total Submit:79

---

Shell is a Unix term for the interworking user interface with an operating system. The shell is the layer of programming that understands and executes the commands a user enters. In some systems, the shell is called a command interpreter. A shell usually implies an interface with a command syntax.

Shell command: What are they? They are part of a shell. In other words, a shell has a set of commands built into its program.

Now, we define a simple shell with some simple shell commands as follows:

1. Initially, the current working directory is “/” with a subdirectory “.”(a dot), and is the root directory with no parent directory
2. In a directory, “.”(a dot) always denotes the directory itself, and “..”(two dots) always denotes the directory’s parent directory
3. Path is the route through a file system to a particular file. A pathname (or path name) is the specification of that path
4. Here is the relation between path and filename:
   path := filename | path/filename | / | (empty)
   The filename consists of “a - z”, “A - Z”, “0 - 9” and “.”, with the length less than 20, and the length of the path is in the range of 1~50
   (If a path begins with “/”, it’s an absolute path, otherwise is a relative path upon the current working directory. The path will never end with “/” unless the path is a single character.)
   
5. Commands(all in lower alpha):
   
   • ls:
     List all the files of current working directory, a directory is regarded as a special file, each file in a single line, in the alphabetic order. If the file is a directory, after a single space, print “d”. End with a blank line.
   • mv [source path] [destination path]:
     Move the source file(may be a directory) to the destination path recursively. If a file with a same name is exist, cover it totally(not combine). The source will not contain the destination. The destination is always a directory. If the current working directory is moved to other places, set the root directory to be the new current working directory. The root directory will not be the source path.
   • cp [source path] [destination path]:
     Copy the source file(may be a directory) to the destination path recursively. If a file with a same name is exist, cover it totally(not combine). The source will not contain the destination. The destination is always a directory. The root directory will not be the source path.
   • mkdir [filename]:
     Create a directory in the current working directory, and the parameter is the filename. The new directory will have the subdirectory “.” and “..” automatically. If a file with a same name is exist, do nothing.
   • create [filename]:
     Create a file(not a directory) in the current working directory, and the parameter is the filename. If a file with a same name is exist, do nothing.
   • del [path]:
     Delete the file which the parameter specifies recursively. Deleting the root directory or “.” or “..” is invalid. After deleting, if the current working directory is invalid, set the root directory to be the new current working directory.
   • cd [path]:
     Only this command can change the current working directory except the case described in the command “del” and “mv”, and the parameter is the new current working directory.

Input

There is only one test case with n commands(n ≤ 100), and the commands will always in the right format, right path and be valid. Each command is in a single line. A directory contains 10 direct sub files at most. The commands and their parameters are separated by a single space.

Output

Please do the work described above. When a command “ls” appears, print as the command’s introduction.

Sample Input

mkdir test
cd test
create file2
create file1
mkdir sub
ls
cd sub
create abc
cd ../..
mkdir test2
cd test2
create sub
cd /
cp /test/sub /test2
cd test2
ls
mv ../test/sub/abc .
ls
del /test/sub
cd /test
ls

Sample Output

. d
.. d
file1
file2
sub d

. d
.. d
sub d

. d
.. d
abc
sub d

. d
.. d
file1
file2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

struct Director
{
    int parent;
    int child;
    int brother;
    int dir; /* 1:dir 0:file */
    char name[100];
};

int root = 0;
int work_dir = 0;

struct Director dir[10000];
int index = 1;

int get_dir(char *p)
{
    int start;

    if (*p == '/')
        start = root;
    else
        start = work_dir;
    return 0;
}

int get_path(int w, char *path)
{
    int i, point, len, list_point;
    char *p = path;

    len = strlen(path);
    point = w;
    while ((p - path) < len && point != -1)
    {
        if (*p == '/')
        {
            ++p;
            point = root;
            continue;
        }
        list_point = dir[point].child;
        while (list_point != -1)
        {
            i = 0;
            while (dir[list_point].name[i] && p[i] && p[i] != '/' && (dir[list_point].name[i] == p[i]))
                ++i;
            if (!dir[list_point].name[i] && (!p[i] || p[i] == '/'))
            {
                p = p + i + 1;
                break;
            }
            list_point = dir[list_point].brother;
        }
        if (list_point == -1)
            return -1;
        if (p[-2] == '.' && p[-3] == '.')
        {
            point = dir[point].parent;
            continue;
        }
        if (p[-2] == '.')
        {
            point = point;
            continue;
        }
        point = list_point;
    }

    return point;
}

int del_path(int index)
{
    int point;

    point = dir[index].parent;
    point = dir[point].child;
    while ((dir[point].brother != -1) && (dir[point].brother != index))
        point = dir[point].brother;

    if(dir[point].brother != -1)
        dir[point].brother = dir[dir[point].brother].brother;
    
    return 0;
}

int insert_file_dir(int w, char *name, int d)
{
    int tmp, point, pre_point;

    tmp = get_path(w, name);
    if (tmp != -1)
        del_path(tmp);
    dir[index].parent = w;
    dir[index].dir = d;
    strcpy(dir[index].name, name);
    dir[index].brother = -1;
    dir[index].child = -1;
    index++;

    point = dir[w].child;
    if (dir[w].child == -1)
    {
        dir[w].child = index - 1;
        return index - 1;
    }

    pre_point = w;
    while (1)
    {
        if ((point == -1) || (strcmp(dir[point].name, dir[index - 1].name) > 0))
        {
            dir[index - 1].brother = dir[pre_point].brother;
            dir[pre_point].brother = index - 1;
            break;
        }
        pre_point = point;
        point = dir[point].brother;
    }

    return index - 1;
}

int copy_dir(int source, int dmt)
{
    int tmp, point;

    tmp = insert_file_dir(dmt, dir[source].name, dir[source].dir);

    if (dir[source].dir == 0)
        return 0;

    point = dir[source].child;
    insert_file_dir(tmp, ".", 1);
    insert_file_dir(tmp, "..", 1);
    while (point != -1)
    {
        if (strcmp(dir[point].name, ".") == 0);
        else if (strcmp(dir[point].name, "..") == 0);
        else
        {
            if (dir[point].dir == 1)
                copy_dir(point, tmp);
            else
                insert_file_dir(tmp, dir[point].name, dir[point].dir);
        }
        point = dir[point].brother;
    }

    return 0;
}

int main()
{
    int point, tmp, tmp1;
    char str[1000];
    char cmd[10], file[100], file1[100];

    dir[0].dir = 1;
    dir[0].child = -1;
    dir[0].brother = -1;

    dir[index].brother = -1;
    dir[index].child = -1;
    strcpy(dir[index].name, ".");
    dir[index].dir = 1;
    dir[index].parent = 0;
    dir[0].child = index;
    ++index;
    while (gets(str))
    {
        sscanf(str, "%s", cmd);
        if (strcmp(cmd, "ls") == 0)
        {
            point = dir[work_dir].child;
            while (point != -1)
            {
                printf("%s", dir[point].name);
                if (dir[point].dir == 1)
                    printf(" d");
                printf("\n");
                point = dir[point].brother;
            }
            printf("\n");
        }
        else if (strcmp(cmd, "mv") == 0)
        {
            if (sscanf(str, "%s %s %s", cmd, file, file1) != 3)
            {
                printf("\n");
                continue;
            }
            tmp = get_path(work_dir, file);
            tmp1 = get_path(work_dir, file1);
            copy_dir(tmp, tmp1);
            tmp1 = work_dir;
            while (tmp1 != 0)
            {
                if (tmp1 == tmp)
                {
                    work_dir = root;
                    break;
                }
                tmp1 = dir[tmp1].parent;
            }
            del_path(tmp);
        }
        else if (strcmp(cmd, "cp") == 0)
        {
            if (sscanf(str, "%s %s %s", cmd, file, file1) != 3)
            {
                printf("\n");
                continue;
            }
            tmp = get_path(work_dir, file);
            tmp1 = get_path(work_dir, file1);
            copy_dir(tmp, tmp1);
        }
        else if (strcmp(cmd, "mkdir") == 0)
        {
            if (sscanf(str, "%s %s", cmd, file) != 2)
            {
                printf("\n");
                continue;
            }
            tmp = get_path(work_dir, file);
            if (tmp != -1)
                continue;
            tmp = insert_file_dir(work_dir, file, 1);
            insert_file_dir(tmp, ".", 1);
            insert_file_dir(tmp, "..", 1);
        }
        else if (strcmp(cmd, "create") == 0)
        {
            if (sscanf(str, "%s %s", cmd, file) != 2)
            {
                printf("\n");
                continue;
            }
            tmp = get_path(work_dir, file);
            if (tmp != -1)
                continue;
            insert_file_dir(work_dir, file, 0);
        }
        else if (strcmp(cmd, "del") == 0)
        {
            if (sscanf(str, "%s %s", cmd, file) != 2)
            {
                printf("\n");
                continue;
            }
            tmp = get_path(work_dir, file);
            del_path(tmp);
            tmp1 = work_dir;
            while (tmp1 != 0)
            {
                if (tmp1 == tmp)
                {
                    work_dir = root;
                    break;
                }
                tmp1 = dir[tmp1].parent;
            }
        }
        else if (strcmp(cmd, "cd") == 0)
        {
            if (sscanf(str, "%s %s", cmd, file) != 2)
            {
                printf("\n");
                continue;
            }
            work_dir = get_path(work_dir, file);
        }
    }

    return 0;
}