Module: Lite::Containers::AvlTree::Traversal

Included in:
Implementation
Defined in:
lib/lite/containers/avl_tree/traversal.rb

Instance Method Summary collapse

Instance Method Details

#after_back_guard?(node, guard) ⇒ Boolean

Returns:

  • (Boolean) 


29
30
31
32
33
 
# File 'lib/lite/containers/avl_tree/traversal.rb', line 29

def after_back_guard?(node, guard)
  return true if guard.nil?

  compare(guard, node.key) < 1
end

#before_front_guard?(node, guard) ⇒ Boolean

Returns:

  • (Boolean) 


35
36
37
38
39
 
# File 'lib/lite/containers/avl_tree/traversal.rb', line 35

def before_front_guard?(node, guard)
  return true if guard.nil?

  compare(node.key, guard) < 1
end

#reverse_traverse(node, yielder, from:, to:) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
 
# File 'lib/lite/containers/avl_tree/traversal.rb', line 18

def reverse_traverse(node, yielder, from:, to:)
  return unless node

  after_start = before_front_guard?(node, from)
  reverse_traverse(node.right, yielder, from: from, to: to) if after_start
  return unless after_back_guard?(node, to)

  yielder.yield node.out if after_start
  reverse_traverse(node.left, yielder, from: from, to: to)
end

#traverse(node, yielder, from:, to:) ⇒ Object 



7
8
9
10
11
12
13
14
15
16
 
# File 'lib/lite/containers/avl_tree/traversal.rb', line 7

def traverse(node, yielder, from:, to:)
  return unless node

  after_start = after_back_guard?(node, from)
  traverse(node.left, yielder, from: from, to: to) if after_start
  return unless before_front_guard?(node, to)

  yielder.yield node.out if after_start
  traverse(node.right, yielder, from: from, to: to)
end