Untitled

/*
Given (as strings) as directories e.g.
/a/b/x.txt
/a/b/p.txt
/a/c
/a/d/y.txt
/a/d/z.txt

Also, I was given the selected directories e.g.
/a/d/y.txt
/a/d/z.txt
/a/b/p.txt

My output should be
/a/d
/a/b/p.txt
*/

struct Node{
    unordered_map<string, Node*> children;
    bool isSelected;
    string name;
    Node(string Name){
        name = Name;
        isSelected = false;
    }
};

vector<string> getPath(string s){
    string name = "";
    vector<string> v; 
    int i = 0;
    while(i<s.length()){
        if(s[i] == '/'){
            if(name != ""){
                v.push_back(name);
                name = "";
            }
        }
        else
            name += s[i];
        i++;
    }
    v.push_back(name);
    return v;
}

void updateNodes(unordered_map<string, Node*> &parNodes, vector<string> input)
{
    for(int i = 0; i<input.size(); i++){
        vector<string> path = getPath(input[i]);
        Node *prev;
        if(parNodes.find(path[0]) == parNodes.end())
            parNodes[path[0]] = new Node(path[0]);
        prev = parNodes[path[0]];
        for(int j = 1; j<path.size(); j++){
            if(prev->children.find(path[j]) == prev->children.end()){
                prev->children[path[j]] = new Node(path[j]);
            }
            prev = prev->children[path[j]];
        }
    }
}

void makeSelection(unordered_map<string, Node*> &parNodes, vector<string> selected)
{
    for(int i = 0; i<selected.size(); i++){
        vector<string> path = getPath(selected[i]);
        Node *prev;
        if(parNodes.find(path[0]) != parNodes.end()){
            prev = parNodes[path[0]];
            bool exist = true;
            for(int j = 1; j<path.size(); j++){
                if(prev->children.find(path[j]) == prev->children.end()){
                    exist = false;
                    break;
                }
                prev = prev->children[path[j]];
            }
            if(exist)
                prev->isSelected = true;
        }
    }
}

bool updateParentSelection(Node* n){
    if(n->isSelected == true)
        return true;
    
    bool allChildsSelected  = (n->children.size() == 0) ? false: true;
    
    for(auto childs : n->children){
        bool res = updateParentSelection(childs.second);
        if(res == false)
            allChildsSelected = false;
    }
    if(allChildsSelected){
        //cout << "Marking selected for " << n->name<< endl;
        n->isSelected = true;
    }
    return n->isSelected;
}

void updateSelection(unordered_map<string, Node*> &parNodes)
{
    for(auto par : parNodes){
        updateParentSelection(par.second);
    }
}

vector<string> getSelection(unordered_map<string, Node*> &parNodes){
    queue<pair<Node*, string>> q;
    vector<string> res;
    for(auto par : parNodes){
        //cout<< par.first << endl;
        q.push({par.second, "/" + par.first});
    }
    
    while(!q.empty()){
        int size = q.size();
        while(size--){
            pair<Node*, string> p = q.front(); q.pop();
            //cout<< p.first->name << endl;
            if(p.first->isSelected == true){
                //cout << p.second << " is Selected.";
                res.push_back(p.second);
            }
            else{
                string path = p.second;
                for(auto child : p.first->children){
                    q.push({child.second, path+"/"+child.first});
                }
            }
        }
    }
    return res;
}

void printGraph(unordered_map<string, Node*> parNodes){
    queue<pair<Node*, string>> q;
    
}

void print(vector<string> v)
{
    for(int i = 0; i<v.size(); i++){
        cout<< v[i] << endl;
    }
}
int main() {
    unordered_map<string, Node*> parNodes; 
    vector<string> input {"/a/b/x.txt", "/a/b/p.txt", "/a/c", "/a/d/y.txt", "/a/d/z.txt"};
    
    vector<string> selected {"/a/d/y.txt", "/a/d/z.txt", "/a/b/p.txt"};
    
    updateNodes(parNodes, input);
    printGraph(parNodes);
    makeSelection(parNodes, selected);
    
    updateSelection(parNodes);
    
    vector<string> res = getSelection(parNodes);
    
    print(res);
    
}