I have a vector of maps, that I'd like to transform in a nested fashion.
The data is structured as follows:
(def data
[{:id 1 :name "a" :parent 0}
{:id 2 :name "b" :parent 0}
{:id 3 :name "c" :parent 0}
{:id 4 :name "a_1" :parent 1}
{:id 5 :name "a_2" :parent 1}
{:id 6 :name "b_1" :parent 2}
{:id 7 :name "a_1_1" :parent 4}])
Each map has an :id
, some other keys and values not important for this discussion, and :parent
key, denoting if the elements belong to another element. If :parent
is 0, it's a top level element.
I want to nest this flattened list so that each element belonging to a parent gets stored under a key :nodes
in the parent map, like this:
(def nested
[{:id 1 :name "a" :parent 0 :nodes
[{:id 4 :name "a_1" :parent 1 :nodes []}
{:id 5 :name "a_2" :parent 1 :nodes
[{:id 7 :name "a_1_1" :parent 4 :nodes []}]}]}
{:id 2 :name "b" :parent 0 :nodes
[{:id 6 :name "b_1" :parent 2}]}
{:id 3 :name "c" :parent 0 :nodes []}])
To sum up - I have a flattened tree-like structure that I whish to transform into a tree again. I tried to achieve this using zippers, but failed to handle arbritarily nested levels.
The easiest way is to build it recursively by performing a full scan at each step:
and then
Update: A more efficient variation
Another option is to convert your child parent relationships to an adjacency list and then traverse the acyclic directed graph.
Such a tree has to be built from the bottom up, so we need a function that will split a seq of nodes into leaves and inner ones:
The next step is attaching all leaves to their parents:
Those two steps have to be repeated until there are only leaves left:
Note that we have to add and remove a virtual root node for this to work since your original set of nodes did not contain one (that's why the function expects the root node's ID).