Module: Lite::Containers::AvlTree::Find::Inexact

Included in:
ExactOrNearestBackwards, ExactOrNearestForwards
Defined in:
lib/lite/containers/avl_tree/find.rb

Instance Method Summary collapse

Instance Method Details

#find(key, node) ⇒ Object 



37
38
39
40
 
# File 'lib/lite/containers/avl_tree/find.rb', line 37

def find(key, node)
  exact, candidate = find_candidate(key, node)
  exact || candidate
end

#find_candidate(key, node) ⇒ Object 



42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/lite/containers/avl_tree/find.rb', line 42

def find_candidate(key, node)
  return [nil, nil] unless node

  case lookup_direction(key, node.key)
  when -1
    find_candidate(key, lookup_path(node, -1))
  when 0
    [node, nil]
  when 1
    exact, candidate = find_candidate(key, lookup_path(node, 1))
    if exact
      [exact, nil]
    elsif candidate
      [nil, candidate]
    else
      [nil, node]
    end
  end
end