module Mongoid::Tree::Traversal
Mongoid::Tree::Traversal
¶ ↑
Mongoid::Tree::Traversal
provides a traverse
method to walk through the tree. It supports these traversal methods:
-
depth_first
-
breadth_first
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 Mongoid::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/mongoid/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/mongoid/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/mongoid/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