class TreeWalker
Defines a stack based tree walker, used by the Bayeux
generators
Attributes
on_after_down[RW]
Accessors
on_after_sideways[RW]
Accessors
on_after_up[RW]
Accessors
on_before_down[RW]
Accessors
on_before_sideways[RW]
Accessors
on_before_up[RW]
Accessors
on_no_children[RW]
Accessors
on_no_siblings[RW]
Accessors
Public Instance Methods
walk_tree(tree_root)
click to toggle source
Class Methods
# File lib/bayeux/tree_walker.rb, line 18 def walk_tree(tree_root) # Start walking from the tree root current_node = tree_root # Stack of node to visit visit_list = Array.new # Points to the last 'virtual vist' we have mode. We # Need to complete this path at the end of our vists last_virtual = nil # Dump the vist list dump_visit_list = -> { dump_str = "" visit_list.each{|node| unless node.nil? then dump_str << node.name.to_s + "," else dump_str << "nil," end } puts "visit list contents: #{dump_str}" } # Do the 'virtual visits'. That is, keep moving up # the tree, visiting the parents at each nil, until # we manage to find something useful do_virtual_visits = -> { next_virtual = current_node next_node = nil # Keep removing nil, moving up the parent list # until we find something worth keeping until ((not next_node.nil?) or visit_list.empty?) do next_node = visit_list.pop next_virtual = next_virtual.parent if next_node.nil? then unless next_virtual.nil? then #puts "^^^ v_visiting: #{next_virtual.name} from #{current_node.name} as #{next_virtual.content.to_debug_s}" unless @on_after_up.nil? then unless next_virtual.nil? then @on_after_up.call(next_virtual.content) end end else #puts "^^^ nil visit" end end end current_node = next_node } # Start walking until current_node.nil? do #unless current_node.nil? then # puts "^^^ visiting: #{current_node.name} as #{current_node.content.to_debug_s}" # dump_visit_list.call #end # Do we have any children? if current_node.has_children? then unless @on_before_down.nil? then unless current_node.nil? then @on_before_down.call(current_node.content) end end # Add the children visit list child_list = current_node.children unless child_list.nil? then visit_list.push(nil) visit_list.concat(child_list.reverse) end #puts " adding children" #dump_visit_list.call current_node = visit_list.pop unless @on_after_down.nil? then unless current_node.nil? then @on_after_down.call(current_node.content) end end else # Tell the caller we have no children unless @on_no_children.nil? then unless current_node.nil? then @on_no_children.call(current_node.content) end end # We can't go down, but can we go sideways? unless visit_list.last.nil? then unless @on_before_sideways.nil? then unless current_node.nil? then @on_before_sideways.call(current_node.content) end end current_node = visit_list.pop unless @on_after_sideways.nil? then unless current_node.nil? then @on_after_sideways.call(current_node.content) end end else # We can't go sideways, or down, so we will go up unless @on_before_up.nil? then unless current_node.nil? then @on_before_up.call(current_node.content) end end # Do the virtual visits to the parents of this node, # ready to move onto the next set of siblings do_virtual_visits.call end end end # Finish the walk by going all the way back to the parent current_node = last_virtual until current_node == tree_root or current_node.nil? do current_node = current_node.parent unless @on_after_up.nil? then unless current_node.nil? then @on_after_up.call(current_node.content) end end end end