Construct tree from flat JSON array in C ++
Essentially I have a JSON structure like this:
[
{
"id": "foo",
"parent_id": null,
"value": "This is a root node"
},
{
"id": "bar",
"parent_id": "foo",
"value": "This is 2nd level node"
},
{
"id": "baz",
"parent_id": "bar",
"value": "This is a 3rd level node"
},
{
"id": "moo",
"parent_id": "foo",
"value": "This is another 2nd level node"
},
{
"id": "woo",
"parent_id": null,
"value": "This is another root node"
}
]
(Note that no ordering occurs.)
Now I would like to take this and parse it into a tree structure. Something like this (other than using C ++ types and not JSON):
[
{
"id": "foo",
"value": "This is a root node",
"children": [
{
"id": "bar",
"value": "This is 2nd level node",
"children": [
{
"id": "baz",
"value": "This is a 3rd level node",
"children": []
}
]
},
{
"id": "moo",
"value": "This is 2nd level node"
"children": []
}
]
},
{
"id": "woo",
"value": "This is another root node"
"children": []
}
]
I would imagine it would look something like this in pseudocode, but I don't know enough C ++ to make it work (I'm in the middle of a hacked week. I have no idea what I'm doing :))
struct NodeValue {
std::string id;
std::string value;
std::string parent_id;
}
struct Node {
NodeValue value;
Node parent;
std::deque<Node> children;
}
std::deque<Node> buildTree(json::Value nodes) {
std::unordered_map<std::string, Node> lookup;
// Populate our lookup map with all the nodes
for (unsigned int i = 0; i < nodes.size(); ++i) {
lookup.insert(std::make_pair(nodes[i].id, Node {
NodeValue {
nodes[i]["id"].asString(),
nodes[i]["value"].asString(),
nodes[i]["parent_id"].asString()
},
nodes[i]["id"].asString()
}));
}
// Populate children
for (lookup::iterator i = lookup.begin(); i != lookup.end(); ++i) {
Node parent;
try {
parent = lookup.at(lookup[i].value.parent_id);
parent.children.emplace_back(lookup[i]);
} catch (out_of_range &e) {
continue;
}
}
// Remove all non-root nodes
it = lookup.begin();
while ((it = std::find_if(it, lookup.end(), [] (const Node& n) { return n.parent_id != NULL; })) != lookup.end()) {
lookup.erase(it++);
}
return lookup;
}
I don't think this solution will work unless the nodes are pre-sorted according to their depth level? Also, I literally wrote my first C ++ line two days ago, so have mercy.
Can anyone help me?
source to share
A friend helped me and simplified it:
struct NodeValue {
std::string id;
std::string name;
std::string parent_id;
};
struct Node {
NodeValue value;
Node* parent;
std::deque<Node> children;
void populateChildren(std::deque<Node>& source) {
for (Node &child : source) {
if (child.value.parent_id != value.id) {
continue;
}
children.push_back(child);
Node © = *(--children.end());
copy.populateChildren(source);
copy.parent = this;
}
}
};
This should reduce the amount of copying, and while the original list may be repeated without further ado, it is definitely fast enough if the dataset is small ~ ish.
source to share
Use the method in the framework Node
along with the special "root node" collector:
struct Node {
NodeValue value;
Node* parent;
std::deque<Node> children;
void populateChildren(std::deque<Node>& source) {
while (source.size() > 0) {
std::deque<Node>::iterator child = std::find_if(
source.begin(), source.end(), [this](Node possibleChild) {
return possibleChild.value.parent_id == this->value.id;
}
);
if (source.end() == child) {
return;
}
child->populateChildren(source);
child->parent = this;
children.push_back(*child);
source.erase(child);
}
}
};
Then your rootNode has an id null
. These are the top-level child nodes that parent_id
will match null
.
Then just do:
rootNode.populateChildren(setOfAllNodes);
I think this should work, but I haven't tested it.
EDIT: Got it :). Below is a complete working example (in GCC). The basic idea is the same as above, but I had to switch to pointers because obviously I was deleting the underlying object with erase
.
#include <iostream>
#include <string>
#include <deque>
#include <algorithm>
struct NodeValue{
std::string id;
std::string name;
std::string parent_id;
};
struct Node {
NodeValue value;
Node* parent;
std::deque<Node*> children;
void populateChildren( std::deque<Node*>& source ) {
auto child = std::find_if( source.begin(), source.end(), [this](const Node* const node){
return node->value.parent_id == this->value.id;} );
while ( child != source.end() ){
(*child)->populateChildren( source );
(*child)->parent = this;
children.push_back( *child );
source.erase( child );
child = std::find_if( source.begin(), source.end(), [this](const Node* node){
return node->value.parent_id == this->value.id;
} );
}
}
};
void printChildCount( const Node* node ){
std::cout << "Node " << node->value.name << " has parent "
<< ( ( node->parent == NULL ) ? "null" : node->parent->value.name ) << " and children: "
<< getListString(node->children) << std::endl;
std::for_each( node->children.begin(), node->children.end(), printChildCount );
}
int main(){
std::deque<Node*> nodes;
Node node1{ NodeValue{ "1", "1", "root" }, NULL, std::deque<Node*>{} };
Node node2{ NodeValue{ "2", "2", "root" }, NULL, std::deque<Node*>{} };
Node node3{ NodeValue{ "3", "3", "1" }, NULL, std::deque<Node*>{} };
Node node4{ NodeValue{ "4", "4", "2" }, NULL, std::deque<Node*>{} };
Node node5{ NodeValue{ "5", "5", "2" }, NULL, std::deque<Node*>{} };
Node node6{ NodeValue{ "6", "6", "5" }, NULL, std::deque<Node*>{} };
Node node7{ NodeValue{ "7", "7", "5" }, NULL, std::deque<Node*>{} };
Node node8{ NodeValue{ "8", "8", "7" }, NULL, std::deque<Node*>{} };
nodes.push_back(&node5);
nodes.push_back(&node6);
nodes.push_back(&node3);
nodes.push_back(&node8);
nodes.push_back(&node4);
nodes.push_back(&node7);
nodes.push_back(&node1);
nodes.push_back(&node2);
Node rootNode { NodeValue { "root", "root", "" }, NULL, std::deque<Node*> { } };
rootNode.populateChildren( nodes );
printChildCount( &rootNode );
return 0;
}
source to share
Maybe something like this?
bool attachToParent(Node* node)
{
if (node->parent_id == id)
{
children.push_back(node);
return true;
}
for (Node* child : children)
{
if (child->attachToParent(node))
{
break;
}
}
return false;
}
Then you can use it like this:
if (!root->attachToParent(node))
{
root->children.push_back(node);
}
source to share