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