Method: PEROBS::BigTreeNode#traverse

Defined in:

lib/perobs/BigTreeNode.rb

#traverse {|node, position, stack| ... } ⇒ Object

This is a generic tree iterator. It yields before it descends into the child node and after (which is identical to before the next child descend). It yields the node, the position and the stack of parent nodes.

Yields:

• (node, position, stack)

# File 'lib/perobs/BigTreeNode.rb', line 655

def traverse
  # We use a non-recursive implementation to traverse the tree. This stack
  # keeps track of all the known still to be checked nodes.
  stack = [[self, 0]]

  until stack.empty?
    node, position = stack.pop

    # Call the payload method. The position marks where we are in the node
    # with respect to the traversal. 0 means we've just entered the node
    # for the first time and are about to descent to the first child.
    # Position 1 is after the 1st child has been processed and before the
    # 2nd child is being processed. If we have N children, the last
    # position is N after we have processed the last child and are about
    # to return to the parent node.
    yield(node, position, stack)

    next unless position <= node.keys.size

    # Push the next position for this node onto the stack.
    stack.push([node, position + 1])

    if !node.is_leaf? && node.children[position]
      # If we have a child node for this position, push the linked node
      # and the starting position onto the stack.
      stack.push([node.children[position], 0])
    end
  end
end