Last active
July 5, 2016 10:03
-
-
Save collinalexbell/98e95d52102344801c97c3936ae04f44 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(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))))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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 ofroot-id
.root-key
is important for generalization. The tree may store an items "parent id" in any slot in the items mapIn 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 ofroot-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 andmap
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.