class RDG::Tree::RGL::PostOrderIterator

Public Class Methods

new(tree, root = tree.first) click to toggle source
Calls superclass method
# File lib/rdg/tree/rgl/post_order_iterator.rb, line 9
def initialize(tree, root = tree.first)
  super(tree)
  @root = root
  set_to_begin
end

Public Instance Methods

at_beginning?() click to toggle source
# File lib/rdg/tree/rgl/post_order_iterator.rb, line 22
def at_beginning?
  @current == @start
end
at_end?() click to toggle source
# File lib/rdg/tree/rgl/post_order_iterator.rb, line 26
def at_end?
  visited?(@root)
end
basic_backward() click to toggle source
# File lib/rdg/tree/rgl/post_order_iterator.rb, line 36
def basic_backward
  @current = ascend(@current)
  unvisit(@current)
  @current
end
basic_forward() click to toggle source
# File lib/rdg/tree/rgl/post_order_iterator.rb, line 30
def basic_forward
  @current = descend(@current)
  visit(@current)
  @current
end
set_to_begin() click to toggle source
# File lib/rdg/tree/rgl/post_order_iterator.rb, line 15
def set_to_begin
  @visited = Hash.new(false)
  @stack = []
  @start = descend(@root)
  @current = @start
end

Private Instance Methods

ascend(node) click to toggle source
# File lib/rdg/tree/rgl/post_order_iterator.rb, line 69
def ascend(node)
  last_child = graph.each_adjacent(node).select { |c| visited?(c) }.last

  if visited?(node)
    node
  elsif last_child.nil?
    ascend(@stack.pop)
  else
    @stack.push(node)
    last_child
  end
end
descend(node) click to toggle source
# File lib/rdg/tree/rgl/post_order_iterator.rb, line 56
def descend(node)
  next_child = graph.each_adjacent(node).detect { |c| !visited?(c) }

  if visited?(node)
    descend(@stack.pop)
  elsif next_child.nil?
    node
  else
    @stack.push(node)
    descend(next_child)
  end
end
unvisit(node) click to toggle source
# File lib/rdg/tree/rgl/post_order_iterator.rb, line 48
def unvisit(node)
  @visited[node.object_id] = false
end
visit(node) click to toggle source
# File lib/rdg/tree/rgl/post_order_iterator.rb, line 44
def visit(node)
  @visited[node.object_id] = true
end
visited?(node) click to toggle source
# File lib/rdg/tree/rgl/post_order_iterator.rb, line 52
def visited?(node)
  @visited[node.object_id]
end