Untitled
unknown
plain_text
11 days ago
4.3 kB
2
Indexable
Never
/* 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); }
Leave a Comment