2 Replies - 2534 Views - Last Post: 23 March 2013 - 10:58 AM Rate Topic: -----

#1 NotarySojac  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 53
  • View blog
  • Posts: 428
  • Joined: 30-September 10

Walking a nested hash that acts as a tree, manipulate elements

Posted 22 March 2013 - 07:58 PM

So I'm in the middle of writing some debugging functions that output a visual of data structures. I have a tree, and it's way complicated. Let's say I have a hash that looks like this:

tree = { name: 'john', definition: 'hello!',
         nodes: [
           { name: 'garfield', definition: 'meow!', 
             nodes: [
               { name: 'nermal', definition: 'meow!', nodes: [] }
             ]
           }, 
           { name: 'odey', definition: 'woof!', nodes: [] }
         ]
       }



Visually it would look like this in a tree if we only show their names and indent them depending on their depth within the tree.

John
  Garfield
    Nermal
  Odey



But I'm having loads of trouble pulling that representation off.

Right now, I've stumbled onto a simpler puzzle that I can't solve either. I thought it would be a good start to just take the hash and reject the unwanted elements out of the elements (the :definition fields). But I'm having trouble getting anywhere with that either. Here's my attempt.


require 'pp'

def walk_tree(tree)
  tree = tree.reject {|e| e== :definition}
  puts tree
  unless tree[:nodes].empty?
    tree[:nodes].each do |node|
      walk_tree(node)
    end
  end
end

tree = { name: 'john', definition: 'hello!',
         nodes: [
           { name: 'garfield', definition: 'meow!',
             nodes: [
               { name: 'nermal', definition: 'meow!', nodes: [] }
             ]
           },
           { name: 'odey', definition: 'woof!', nodes: [] }
         ]
       }

tree = walk_tree(tree)

pp tree



If anyone has any insights or knows of some secret ruby methods, please share. Otherwise I'm going to try a nested for loop for traversing the nodes and see if that gets me anywhere with this puzzle.

Is This A Good Question/Topic? 0
  • +

Replies To: Walking a nested hash that acts as a tree, manipulate elements

#2 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2015
  • View blog
  • Posts: 3,042
  • Joined: 21-June 11

Re: Walking a nested hash that acts as a tree, manipulate elements

Posted 23 March 2013 - 06:09 AM

Why do you need to remove the :definition entry? You can just choose not to use it. I would define walk_tree like this:

def walk_tree(tree, &blk)
  # This allows the method to be used as an enumerable if it is used without a block
  # It is idiomatic in Ruby for all iterator methods to behave like this (since Ruby 1.8.7 anyway)
  return enum_for(:walk_tree) unless blk

  yield tree
  tree[:nodes].each do |node|
    walk_tree(node, &blk)
  end
end



You could then use print all the names by invoking the method like this:

walk_tree(tree) do |node|
  puts node[:name]
end



So this works, but it only gives you a flat list. What you wanted was to print it as a tree-like structure. So what do you need for that? You need to know each node's depth when printing it. So let's change the walk_tree method to yield that too:

def walk_tree(tree, depth = 0, &blk)
  # This allows the method to be used as an enumerable if it is used without a block
  # It is idiomatic in Ruby for all iterator methods to behave like this (since Ruby 1.8.7 anyway)
  return enum_for(:walk_tree, depth) unless blk

  yield tree, depth
  tree[:nodes].each do |node|
    walk_tree(node, depth + 1, &blk)
  end
end



Now you can use it like this:

walk_tree(tree) do |node, depth|
  indent_amount = 2 * depth
  print " " * indent_amount
  puts node[:name]
end



One further thing I'd suggest, is to replace your hashes with structs. A collection of hashes where each hash has the exact same set of fixed keys is a bit of a design smell to me. Something like this would work nicely:

Tree = Struct.new(:name, :definition, :children) do
  # This adds enumerable methods like map, select, reject etc to the Tree class
  include Enumerable

  def each(depth = 0, &blk)
    yield self, depth
    children.each do |node|
      node.each(depth + 1, &blk)
    end
  end
end

tree = Tree.new( 'john', 'hello!',
         [
           Tree.new( 'garfield', 'meow!',
             [
               Tree.new( 'nermal', 'meow!', [] )
             ]
           ),
           Tree.new( 'odey', 'woof!', [] )
         ]
       )

tree.each do |node, depth|
  indent_amount = 2 * depth
  print " " * indent_amount
  puts node.name
end


Was This Post Helpful? 3
  • +
  • -

#3 NotarySojac  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 53
  • View blog
  • Posts: 428
  • Joined: 30-September 10

Re: Walking a nested hash that acts as a tree, manipulate elements

Posted 23 March 2013 - 10:58 AM

This was hugely helpful Sepp2k, thanks. I've been doing the ruby thing for a while and I've never encountered stucts before and they look very handy.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1