Class: RBTree::TreeCmp

Inherits:
Tree
  • Object
show all
Defined in:
lib/rbtree/tree_cmp.rb

Overview

Variant of Tree that uses a custom comparator.

This is the “slow path”, whereas Tree uses “fast path” <, > etc.

Instance Attribute Summary

Attributes inherited from Tree

#root, #size

Instance Method Summary collapse

Methods inherited from Tree

#black_height, #delete, #empty?, #initialize_copy, #inorder, #insert, #maximum, #minimum, #node, #predecessor, #reverse_inorder, #successor

Constructor Details

#initialize(&cmp_proc) ⇒ TreeCmp

Creates a new tree.



9
10
11
12
13
14
 
# File 'lib/rbtree/tree_cmp.rb', line 9

def initialize(&cmp_proc)
  @cmp_proc = cmp_proc
  @guard = GuardNode.new
  @size = 0
  @root = @guard
end

Instance Method Details

#insert_helper(z) ⇒ Object 



63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/rbtree/tree_cmp.rb', line 63

def insert_helper(z)
  y = @guard
  x = @root
  key = z.key
  until x.nil?
    y = x
    unless cmp = @cmp_proc.call(x.key, key)
      raise ArgumentError,
            "comparison of #{x.key.class} with #{key.inspect} failed"
    end
    if cmp > 0
      x = x.left
    elsif cmp < 0
      x = x.right
    else
      return x
    end
  end
  z.parent = y
  if y.nil?
    @root = z
  else
    @cmp_proc.call(key, y.key) < 0 ? y.left = z : y.right = z
  end
  @size += 1
  z
end

#lower_bound(key, node = root) ⇒ Object

Returns the node with the smallest key that is >= the given key.

Returns nil if called on an empty tree or the guard node.



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/rbtree/tree_cmp.rb', line 28

def lower_bound(key, node = root)
  return nil if node.nil?
  loop do
    cmp = @cmp_proc.call(key, node.key)
    return node if cmp == 0
    if cmp < 0
      next_node = node.left
      return node if next_node.nil?
    else
      next_node = node.right
      return successor(node) if next_node.nil?
    end
    node = next_node
  end
end

#search(key, node = root) ⇒ Object

Returns a node containing the given key or nil if no node contains the key.



17
18
19
20
21
22
23
 
# File 'lib/rbtree/tree_cmp.rb', line 17

def search(key, node = root)
  until node.nil?
    return node if node.key == key
    node = @cmp_proc.call(key, node.key) < 0 ? node.left : node.right
  end
  nil
end

#upper_bound(key, node = root) ⇒ Object

Returns a node with the largest key that is <= then given key.

Returns nil if called on an empty tree or the guard node.



47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/rbtree/tree_cmp.rb', line 47

def upper_bound(key, node = root)
  return nil if node.nil?
  loop do
    cmp = @cmp_proc.call(key, node.key)
    return node if cmp == 0
    if cmp < 0
      next_node = node.left
      return predecessor(node) if next_node.nil?
    else
      next_node = node.right
      return node if next_node.nil?
    end
    node = next_node
  end
end