I am trying to write a function to convert a flat array with path information into a tree view of this array.
The goal is to convert the array as follows:
[ { :name => "a", :path => [ 'a' ] }, { :name => "b", :path => [ 'a', 'b' ] }, { :name => "c", :path => [ 'a', 'b', 'c' ] }, { :name => "d", :path => [ 'a', 'd' ] }, { :name => "e", :path => [ 'e' ] } ]
into one such:
[{:node=>{:name=>"a", :path=>["a"]}, :children=> [{:node=>{:name=>"b", :path=>["a", "b"]}, :children=> [{:node=>{:name=>"c", :path=>["a", "b", "c"]}, :children=>[]}]}, {:node=>{:name=>"d", :path=>["a", "d"]}, :children=>[]}]}, {:node=>{:name=>"e", :path=>["e"]}, :children=>[]}]
The closest result I came across was with the following code:
class Tree def initialize @root = { :node => nil, :children => [ ] } end def from_array( array ) array.inject(self) { |tree, node| tree.add(node) } @root[:children] end def add(node) recursive_add(@root, node[:path].dup, node) self end private def recursive_add(parent, path, node) if(path.empty?) parent[:node] = node return end current_path = path.shift children_nodes = parent[:children].find { |child| child[:node][:path].last == current_path } unless children_nodes children_nodes = { :node => nil, :children => [ ] } parent[:children].push children_nodes end recursive_add(children_nodes, path, node) end end flat = [ { :name => "a", :path => [ 'a' ] }, { :name => "b", :path => [ 'a', 'b' ] }, { :name => "c", :path => [ 'a', 'b', 'c' ] }, { :name => "d", :path => [ 'a', 'd' ] }, { :name => "e", :path => [ 'e' ] } ] require 'pp' pp Tree.new.from_array( flat )
But this is pretty verbose, and I feel that it may not be very effective for very large sets.
What will be the cleanest and most effective way to achieve this in ruby?