Class: DS::TreeWalker

Inherits:
Object
  • Object
show all
Defined in:
lib/ds/trees/tree_walker.rb

Overview

Tree enumerator

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(tree, options = {}, &block) ⇒ TreeWalker

Creates new tree iterator.



7
8
9
10
11
12
 
# File 'lib/ds/trees/tree_walker.rb', line 7

def initialize(tree, options = {}, &block)
  @visited = []
  @tree = tree
  @order = options[:order] || :bfs
  @action = block
end

Instance Attribute Details

#action ⇒ Object

Returns the value of attribute action.



4
5
6
 
# File 'lib/ds/trees/tree_walker.rb', line 4

def action
  @action
end

#order ⇒ Object

Returns the value of attribute order.



4
5
6
 
# File 'lib/ds/trees/tree_walker.rb', line 4

def order
  @order
end

#tree ⇒ Object

Returns the value of attribute tree.



4
5
6
 
# File 'lib/ds/trees/tree_walker.rb', line 4

def tree
  @tree
end

#visited ⇒ Object

Returns the value of attribute visited.



4
5
6
 
# File 'lib/ds/trees/tree_walker.rb', line 4

def visited
  @visited
end

Instance Method Details

#recalculate!(tree, order, memo = nil, &block) ⇒ Object

Recalculates tree by evaluating block on every node.



66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
# File 'lib/ds/trees/tree_walker.rb', line 66

def recalculate!(tree, order, memo = nil, &block)
  case order
  when :postorder
    arr = tree.children.map { |t| recalculate!(t, order, memo, &block) }
    tree.data = yield tree, arr
  when :preorder
    tree.data = yield tree, memo
    tree.children.each do |t|
      recalculate!(t, order, tree.data, &block)
    end
  when :inorder
    recalculate!(tree.left, order, memo, &block)
    tree.data = yield tree, memo
    recalculate!(tree.right, order, tree.data, &block)
  end if tree
end

#reset! ⇒ Object

Resets tree walker.



51
52
53
54
 
# File 'lib/ds/trees/tree_walker.rb', line 51

def reset!
  @visited.clear
  self
end

#traverse(traverse_order = nil, &block) ⇒ Object

Traversing tree in given order: bfs - Breadth-first search - default postorder - postorder search preorder - preorder search inorder - inorder search - only for Binary Trees

If block is given, passes each visited subtree to block. Returns values of nodes in given order



23
24
25
26
27
28
29
30
31
32
33
34
 
# File 'lib/ds/trees/tree_walker.rb', line 23

def traverse(traverse_order = nil, &block)
  self.action = block if block_given?
  self.order = traverse_order if traverse_order
  reset!

  if order == :bfs
    traverse_bfs
  else
    walk(tree)
  end
  visited
end

#traverse_bfs(&block) ⇒ Object

Traverses tree in BFS order.



37
38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/ds/trees/tree_walker.rb', line 37

def traverse_bfs(&block)
  self.action = block if block_given?
  q = SimpleQueue.new
  q.push tree

  loop do
    break if q.empty?
    node = q.shift
    visit_node(node)
    node.children.each { |n| q.push n } if node.children
  end
end

#traverse_with_h(tree, height = nil) {|tree, height| ... } ⇒ Object

Traverses tree with tracking level.

Yields:



57
58
59
60
61
62
63
 
# File 'lib/ds/trees/tree_walker.rb', line 57

def traverse_with_h(tree, height = nil, &block)
  tree.children.each do |t|
    traverse_with_h(t, height + 1, &block)
  end

  yield tree, height if block_given?
end