no04-dictionary.cpp

#define NAME_MAXLEN 6
#define PATH_MAXLEN 1999

#include <string>
#include <map>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

struct Node {
    string name;
    map<string, Node*> children;
};

Node nodes[50000];
int nodes_len;

Node *root;

int max_directory_num;

Node *gen_node(const string &name) {
    Node *node = &nodes[nodes_len++];
    node->name = name;
    node->children.clear();
    return node;
}

void init(int n) {
    max_directory_num = n;
    nodes_len = 0;
    root = gen_node(string(""));
}

void parse(char path[PATH_MAXLEN + 1], vector<string> &paths) {
    char *ptr = strtok(path, "/");
    while (ptr != nullptr) {
        paths.push_back(string(ptr));
        ptr = strtok(NULL, "/");
    }
}

void print_tree(Node *root, int step) {

    for (auto it: root->children) {
        for (int i = 0; i < step; i++) {
            // cout << "  ";
        }
        // cout << it.first << '\n';
        print_tree(it.second, step + 1);
    }
}

void cmd_mkdir(char path[PATH_MAXLEN + 1], char name[NAME_MAXLEN + 1]) {
    vector<string> paths;
    parse(path, paths);

    Node *node = root;
    for (int i = 0; i < paths.size(); i++) {
        node = node->children[paths[i]];
    }

    Node *new_node = gen_node(string(name));
    node->children[string(name)] = new_node;

    // print_tree(root, 0);
    // cout << '\n';
}

void cmd_rm(char path[PATH_MAXLEN + 1]) {
    vector<string> paths;
    parse(path, paths);

    Node *node = root;
    for (int i = 0; i < paths.size() - 1; i++) {
        node = node->children[paths[i]];
    }

    string name = paths[paths.size() - 1];
    map<string, Node*>::iterator it = node->children.find(name);
    node->children.erase(it);

    // print_tree(root, 0);
    // cout << '\n';
}

void copy(Node *srcNode, Node *dstNode) {
    Node *node = gen_node(srcNode->name);

    dstNode->children[node->name] = node;
    for (auto &it: srcNode->children) {
        copy(it.second, node);
    }
}

void cmd_cp(char srcPath[PATH_MAXLEN + 1], char dstPath[PATH_MAXLEN + 1]) {
    vector<string> srcPaths;
    parse(srcPath, srcPaths);
    vector<string> dstPaths;
    parse(dstPath, dstPaths);

    Node *srcNode = root;
    for (int i = 0; i < srcPaths.size(); i++) {
        srcNode = srcNode->children[srcPaths[i]];
    }

    Node *dstNode = root;
    for (int i = 0; i < dstPaths.size(); i++) {
        dstNode = dstNode->children[dstPaths[i]];
    }

    copy(srcNode, dstNode);

    // print_tree(root, 0);
    // cout << '\n';
}

void cmd_mv(char srcPath[PATH_MAXLEN + 1], char dstPath[PATH_MAXLEN + 1]) {
    vector<string> srcPaths;
    parse(srcPath, srcPaths);
    vector<string> dstPaths;
    parse(dstPath, dstPaths);

    Node *srcNode = root;
    for (int i = 0; i < srcPaths.size() - 1; i++) {
        srcNode = srcNode->children[srcPaths[i]];
    }
    string srcName = srcPaths[srcPaths.size() - 1];

    Node *dstNode = root;
    for (int i = 0; i < dstPaths.size(); i++) {
        dstNode = dstNode->children[dstPaths[i]];
    }

    map<string, Node*>::iterator it = srcNode->children.find(srcName);

    dstNode->children[srcName] = it->second;

    srcNode->children.erase(it);
}

int count_tree(Node *root) {
    int count = 1;

    for (auto &it: root->children) {
        count += count_tree(it.second);
    }
    return count;
}

int cmd_find(char path[PATH_MAXLEN + 1]) {
    vector<string> paths;
    parse(path, paths);

    Node *node = root;
    for (int i = 0; i < paths.size(); i++) {
        node = node->children[paths[i]];
    }

    int count = count_tree(node) - 1;
    // cout << "count: " << count << '\n';
	return count;
}