CODEWITHSUNDEEP
rubytree
Guillermo Alvarez
Guillermo Alvarez

Reputation: 1775

Change tree structure in ruby to use nested hashes

I have the following class called Tree that builds a simple tree

class Tree
  attr_accessor :children, :node_name

  def initialize(name, children=[])
    @children = children
    @node_name = name
  end

  def visit_all(&block)
    visit &block
    children.each {|c| c.visit_all &block}
  end

  def visit(&block)
    block.call self

  end
end

ruby_tree = Tree.new("grandpa",
  [Tree.new("dad", [Tree.new("child1"), Tree.new("child2")]), 
    Tree.new("uncle", [Tree.new("child3"), Tree.new("child4")])])  
puts "Visiting a node"
ruby_tree.visit {|node| puts node.node_name}
puts

puts "visiting entire tree"
ruby_tree.visit_all {|node| puts node.node_name}

Now what I am trying to do is to be able to create a tree as nested hashes instead. For example, for this one this would be:

{'grandpa'=>{'dad'=>{'child 1'=>{},'child 2'=>{}}, 'uncle'=>{'child 3'=>{}, 'child 4'=>{}}}}

Any ideas that could help?

Upvotes: 0

Views: 1583

Answers (3)

gilch
gilch

Reputation: 11651

Break it into simpler subproblems and use recursion:

def make_node(name,subhash)
  Tree.new(name,subhash.keys.collect{|k|make_node(k,subhash[k])})
end
def make_root(hash)
  make_node(hash.keys[0],hash[hash.keys[0]])
end

Then to prove it works:

tree_like_this = make_root({'grandpa' => { 'dad' => {'child 1' => {}, 'child 2' => {} }, 
'uncle' => {'child 3' => {}, 'child 4' => {} } } })

puts 'tree like this'
tree_like_this.visit_all{|n|puts n.node_name}

This was an exercise from Seven Languages In Seven Weeks. The original exercise said to put it all in initialize.

Upvotes: 1

ian
ian

Reputation: 12251

It was melting my brain so I wrote a spec for it:

# encoding: UTF-8

require 'rspec' # testing/behaviour description framework
require_relative "../tree.rb" # pull in the actual code

# Everything in the `describe` block is rspec "tests"
describe :to_h do
  # contexts are useful for describing what happens under certain conditions, in the first case, when there is only the top of the tree passed to to_h
  context "One level deep" do
    # a let is a way of declaring a variable in rspec (that keeps it useful)
    let(:ruby_tree) { Tree.new "grandpa" }
    let(:expected) { {"grandpa" => {} } }
    subject { ruby_tree.to_h } # this the behaviour you're testing
    it { should == expected } # it should equal what's in expected above
  end
  # The next two contexts are just testing deeper trees. I thought that each depth up to 3 should be tested, as past 3 levels it would be the same as 3.
  context "Two levels deep" do
    let(:ruby_tree) { 
      Tree.new( "grandpa", 
                  [Tree.new("dad"), Tree.new("uncle") ] 
              )
    }
    let(:expected) do 
      {"grandpa" => { 
          "dad" => {}, "uncle" => {} 
        } 
      } 
    end
    subject { ruby_tree.to_h }
    it { should == expected }
  end
  context "grandchildren" do
    let(:ruby_tree){
      ruby_tree = Tree.new("grandpa",
      [Tree.new("dad", [Tree.new("child1"), Tree.new("child2")]), 
        Tree.new("uncle", [Tree.new("child3"), Tree.new("child4")])])
    }
    let(:expected) {
      {'grandpa'=>{'dad'=>{'child1'=>{},'child2'=>{}}, 'uncle'=>{'child3'=>{}, 'child4'=>{}}}}
    }
    subject { ruby_tree.to_h }
    it { should == expected }
  end
end

class Tree
  def to_h
    hash ={} # create a hash
    # `reduce` is a synonym for `inject`, see the other answer for a link to the docs,
    # but it's a type of fold 
    # http://en.wikipedia.org/wiki/Fold_(higher-order_function),
    # which will take a list of several objects and 
    # fold them into one (or fewer, but generally one) through application of a function. 
    # It reduces the list through injecting a function, hence the synonyms.
    # Here, the current node's list of children is folded into one hash by 
    # applying Hash#merge to each child (once the child has been been made 
    # into a one key hash, possibly with children too), and then assigned as 
    # the current node's hash value, with the node_name as the key.
    hash[@node_name] = children.reduce({}){|mem,c| mem.merge c.to_h}
    hash # return the hash
  end
end

I'm certain this could be done better, but it works at least.

Btw, the hash you provided has some extra spaces in it that I don't think should be there? e.g. "child 1" when it should be "child1", unless you really want that added in?

Upvotes: 3

Chubas
Chubas

Reputation: 18043

class Tree
  def to_hash
    { @node_name => @children.inject({}) { |acum, child| acum.merge(child.to_hash) } }
  end
end

p ruby_tree.to_hash

See documentation for inject here

Upvotes: 1

Related Questions