Class: RBTree::TreeCmp
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
Instance Method Summary collapse
-
#initialize(&cmp_proc) ⇒ TreeCmp
constructor
Creates a new tree.
- #insert_helper(z) ⇒ Object
-
#lower_bound(key, node = root) ⇒ Object
Returns the node with the smallest key that is >= the given key.
-
#search(key, node = root) ⇒ Object
Returns a node containing the given key or nil if no node contains the key.
-
#upper_bound(key, node = root) ⇒ Object
Returns a node with the largest key that is <= then given key.
Methods inherited from Tree
#black_height, #delete, #empty?, #initialize_copy, #inorder, #insert, #maximum, #minimum, #node, #predecessor, #reverse_inorder, #successor
Constructor Details
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 |