Ruby: Transform a flat array in a tree representation

Question

I am trying to write a function to convert a flat array with a path information into a tree representation of that array.

The goal would be to turn an array like the following:

[
{ :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 like this:

[{: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 got with 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 it is quite verbose and I have the feeling that it might not be very effective for very large sets.

What would be the cleanest and most effective way to achieve that in ruby?

Please do not use an unexplained method or variable in the question. What is path? — sawa
– sawa, Commented Oct 29, 2012 at 4:32
I think you should try simplifying your tree. For e.g. if the name is unique then maybe use the name as key so that you can search easily. — ShadyKiller
– ShadyKiller, Commented Oct 29, 2012 at 4:48
@AndrewMarshall Thanks for pointing, I added my current source. — Eric
– Eric, Commented Oct 29, 2012 at 4:48

sawa · Accepted Answer · 2012-10-29 07:42:12Z

2

This is my try.

array = [
{ :name => "a", :path => [ 'a' ] },
{ :name => "b", :path => [ 'a', 'b' ] },
{ :name => "c", :path => [ 'a', 'b', 'c' ] },
{ :name => "d", :path => [ 'a', 'd' ] },
{ :name => "e", :path => [ 'e' ] }
]

array
.sort_by{|h| -h[:path].length}
.map{|h| {node: h, children: []}}
.tap{|array| 
  while array.first[:node][:path].length > 1
    child = array.shift
    array
    .find{|h| h[:node][:name] == child[:node][:path][-2]}[:children]
    .push(child)
  end
}

# => [
  {:node=>{:name=>"e", :path=>["e"]}, :children=>[]},
  {:node=>{:name=>"a", :path=>["a"]}, :children=>[
    {:node=>{:name=>"d", :path=>["a", "d"]}, :children=>[]},
    {:node=>{:name=>"b", :path=>["a", "b"]}, :children=>[
      {:node=>{:name=>"c", :path=>["a", "b", "c"]}, :children=>[]}
    ]}
  ]}
]

edited Oct 29, 2012 at 7:42

answered Oct 29, 2012 at 4:54

sawa

169k51 gold badges287 silver badges398 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Eric Over a year ago

Ruby feels like magic sometimes. Clean and effective. Thanks a lot!

Collectives™ on Stack Overflow

Ruby: Transform a flat array in a tree representation

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related