Skip to content

Instantly share code, notes, and snippets.

@collinalexbell
Last active July 5, 2016 10:03
Show Gist options
  • Save collinalexbell/98e95d52102344801c97c3936ae04f44 to your computer and use it in GitHub Desktop.
Save collinalexbell/98e95d52102344801c97c3936ae04f44 to your computer and use it in GitHub Desktop.
(defn tree-to-list [tree root-id root-key]
(flatten (cons
(get tree root-id)
(map
(fn [filter-result]
(tree-to-list
tree
(first filter-result)
root-key))
(filter-by-parent tree root-key root-id)))))
@collinalexbell
Copy link
Author

collinalexbell commented Jul 5, 2016

This will recursively turn a hash-tree into a list in descending order based on hierarchy starting from the root-id.

Heres how it works:
First you need to know that there is a function definition that is not included in this file: filter-by-parent
As such, this code will not run if you just copy and paste.

Anyway, filter-by-parent will take a tree and return a list of only the items who's parent is that of root-id.
root-key is important for generalization. The tree may store an items "parent id" in any slot in the items map
In my use case the key is stored in :source-frame, but such details are irrelevant to this algorithm.
All you need to know is that the tree is a hash map of maps like so
{:item1 {:parent nil :data "I am item 1"} :item2 {:parent :item1 :data "I am item2"}}

Notice how :item2's parent is :item1?
:parent in this case is the value of root-key.

Anyways, after you have filtered the tree down to only the children of the "root" using filter-by-parent,
you then want to recursively construct the data structure.

You want to create a new list by using cons.
This list has two items:
The first is the root node. In this recursive construction, the addition of this first node is the only real way this function gets data into our data structure.
The second item is the list that results from calling tree-to-list on the current root's children, but..
this list only has data in it because upon subsequent calls to tree-to-list, a list is constructed using cons with its first element being the new root.

Its important to note that if a root does not have any children, the call to the function in map will never take place and map will simply return an empty list.

Finally, you need to flatten the entire data structure, because the new list we created using cons has its second item as a list.
This means the list created by cons is nested, but we only want to return a single list, so we can flatten that nested list.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment