module NoBrainer::Tree::Traversal

NoBrainer::Tree::Traversal

NoBrainer::Tree::Traversal provides a traverse method to walk through the tree. It supports these traversal methods:

Depth First Traversal

See en.wikipedia.org/wiki/Depth-first_search for a proper description.

Given a tree like:

node1:
 - node2:
   - node3
 - node4:
   - node5
   - node6
 - node7

Traversing the tree using depth first traversal would visit each node in this order:

node1, node2, node3, node4, node5, node6, node7

Breadth First Traversal

See en.wikipedia.org/wiki/Breadth-first_search for a proper description.

Given a tree like:

node1:
  - node2:
    - node5
  - node3:
    - node6
    - node7
  - node4

Traversing the tree using breadth first traversal would visit each node in this order:

node1, node2, node3, node4, node5, node6, node7

Public Instance Methods

traverse(type = :depth_first, &block) click to toggle source

Traverses the tree using the given traversal method (Default is :depth_first) and passes each document node to the block.

See NoBrainer::Tree::Traversal for available traversal methods.

@example

results = []
root.traverse(:depth_first) do |node|
  results << node
end

root.traverse(:depth_first).map(&:name)
root.traverse(:depth_first, &:name)
# File lib/nobrainer/tree/traversal.rb, line 98
def traverse(type = :depth_first, &block)
  block ||= lambda { |node| node }
  send("#{type}_traversal", &block)
end

Private Instance Methods

breadth_first_traversal(&block) click to toggle source
# File lib/nobrainer/tree/traversal.rb, line 110
def breadth_first_traversal(&block)
  result = []
  queue = [self]
  while queue.any? do
    node = queue.shift
    result << block.call(node)
    queue += node.children
  end
  result
end
depth_first_traversal(&block) click to toggle source
# File lib/nobrainer/tree/traversal.rb, line 105
def depth_first_traversal(&block)
  result = [block.call(self)] + self.children.collect { |c| c.send(:depth_first_traversal, &block) }
  result.flatten
end