class Containers::RubyRBTreeMap

rdoc

A RBTreeMap is a map that is stored in sorted order based on the order of its keys. This ordering is
determined by applying the function <=> to compare the keys. No duplicate values for keys are allowed,
so duplicate values are overwritten.

A major advantage of RBTreeMap over a Hash is the fact that keys are stored in order and can thus be
iterated over in order. This is useful for many datasets.

The implementation is adapted from Robert Sedgewick's Left Leaning Red-Black Tree implementation,
which can be found at http://www.cs.princeton.edu/~rs/talks/LLRB/Java/RedBlackBST.java

Containers::RBTreeMap automatically uses the faster C implementation if it was built
when the gem was installed. Alternatively, Containers::RubyRBTreeMap and Containers::CRBTreeMap can be
explicitly used as well; their functionality is identical.

Most methods have O(log n) complexity.

MIT License

Copyright (c) 2009 Kanwei Li

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

Attributes

height_black[RW]

Public Class Methods

new() click to toggle source

Create and initialize a new empty TreeMap.

# File lib/containers/rb_tree_map.rb, line 48
def initialize
  @root = nil
  @height_black = 0
end

Public Instance Methods

[](key)
Alias for: get
[]=(key, value)
Alias for: push
delete(key) click to toggle source

Deletes the item and key if it's found, and returns the item. Returns nil if key is not present.

!!! Warning !!! There is a currently a bug in the delete method that occurs rarely but often enough, especially in large datasets. It is currently under investigation.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.min_key #=> "GA"
# File lib/containers/rb_tree_map.rb, line 152
def delete(key)
  result = nil
  if @root
    @root, result = delete_recursive(@root, key)
    @root.color = :black if @root
  end
  result
end
delete_max() click to toggle source

Deletes the item with the smallest key and returns the item. Returns nil if key is not present.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.delete_max #=> "Georgia"
map.size #=> 1
# File lib/containers/rb_tree_map.rb, line 195
def delete_max
  result = nil
  if @root
    @root, result = delete_max_recursive(@root)
    @root.color = :black if @root
  end
  result
end
delete_min() click to toggle source

Deletes the item with the smallest key and returns the item. Returns nil if key is not present.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.delete_min #=> "Massachusetts"
map.size #=> 1
# File lib/containers/rb_tree_map.rb, line 176
def delete_min
  result = nil
  if @root
    @root, result = delete_min_recursive(@root)
    @root.color = :black if @root
  end
  result
end
each() { |key, value| ... } click to toggle source

Iterates over the TreeMap from smallest to largest element. Iterative approach.

# File lib/containers/rb_tree_map.rb, line 205
def each
  return nil unless @root
  stack = Containers::Stack.new
  cursor = @root
  loop do
    if cursor
      stack.push(cursor)
      cursor = cursor.left
    else
      unless stack.empty?
        cursor = stack.pop
        yield(cursor.key, cursor.value)
        cursor = cursor.right
      else
        break
      end
    end
  end
end
empty?() click to toggle source

Returns true if the tree is empty, false otherwise

# File lib/containers/rb_tree_map.rb, line 162
def empty?
  @root.nil?
end
get(key) click to toggle source

Return the item associated with the key, or nil if none found.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.get("GA") #=> "Georgia"
# File lib/containers/rb_tree_map.rb, line 111
def get(key)
  get_recursive(@root, key)
end
Also aliased as: []
has_key?(key) click to toggle source

Return true if key is found in the TreeMap, false otherwise

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.has_key?("GA") #=> true
map.has_key?("DE") #=> false
# File lib/containers/rb_tree_map.rb, line 99
def has_key?(key)
  !get(key).nil?
end
height() click to toggle source

Return the height of the tree structure in the TreeMap.

Complexity: O(1)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.height #=> 2
# File lib/containers/rb_tree_map.rb, line 86
def height
  @root and @root.height or 0
end
max_key() click to toggle source

Return the largest key in the map.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.max_key #=> "MA"
# File lib/containers/rb_tree_map.rb, line 136
def max_key
  @root.nil? ? nil : max_recursive(@root)
end
min_key() click to toggle source

Return the smallest key in the map.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.min_key #=> "GA"
# File lib/containers/rb_tree_map.rb, line 124
def min_key
  @root.nil? ? nil : min_recursive(@root)
end
push(key, value) click to toggle source

Insert an item with an associated key into the TreeMap, and returns the item inserted

Complexity: O(log n)

map = Containers::TreeMap.new map.push(“MA”, “Massachusetts”) #=> “Massachusetts” map.get(“MA”) #=> “Massachusetts”

# File lib/containers/rb_tree_map.rb, line 60
def push(key, value)
  @root = insert(@root, key, value)
  @height_black += 1 if isred(@root)
  @root.color = :black
  value
end
Also aliased as: []=
size() click to toggle source

Return the number of items in the TreeMap.

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.size #=> 2
# File lib/containers/rb_tree_map.rb, line 74
def size
  @root and @root.size or 0
end

Private Instance Methods

delete_max_recursive(node) click to toggle source
# File lib/containers/rb_tree_map.rb, line 353
def delete_max_recursive(node)
  if (isred(node.left))
    node = node.rotate_right
  end
  return nil, node.value if node.right.nil?
  if ( !isred(node.right) && !isred(node.right.left) )
    node.move_red_right
  end
  node.right, result = delete_max_recursive(node.right)

  return node.fixup, result
end
delete_min_recursive(node) click to toggle source
# File lib/containers/rb_tree_map.rb, line 340
def delete_min_recursive(node)
  if node.left.nil?
    return nil, node.value
  end
  if ( !isred(node.left) && !isred(node.left.left) )
    node.move_red_left
  end
  node.left, result = delete_min_recursive(node.left)

  return node.fixup, result
end
delete_recursive(node, key) click to toggle source
# File lib/containers/rb_tree_map.rb, line 315
def delete_recursive(node, key)
  if (key <=> node.key) == -1
    node.move_red_left if ( !isred(node.left) && !isred(node.left.left) )
    node.left, result = delete_recursive(node.left, key)
  else
    node.rotate_right if isred(node.left)
    if ( ( (key <=> node.key) == 0) && node.right.nil? )
      return nil, node.value
    end
    if ( !isred(node.right) && !isred(node.right.left) )
      node.move_red_right
    end
    if (key <=> node.key) == 0
      result = node.value
      node.value = get_recursive(node.right, min_recursive(node.right))
      node.key = min_recursive(node.right)
      node.right = delete_min_recursive(node.right).first
    else
      node.right, result = delete_recursive(node.right, key)
    end
  end
  return node.fixup, result
end
get_recursive(node, key) click to toggle source
# File lib/containers/rb_tree_map.rb, line 367
def get_recursive(node, key)
  return nil if node.nil?
  case key <=> node.key
  when  0 then return node.value
  when -1 then return get_recursive(node.left, key)
  when  1 then return get_recursive(node.right, key)
  end
end
insert(node, key, value) click to toggle source
# File lib/containers/rb_tree_map.rb, line 391
def insert(node, key, value)
  return Node.new(key, value) unless node

  case key <=> node.key
  when  0 then node.value = value
  when -1 then node.left = insert(node.left, key, value)
  when  1 then node.right = insert(node.right, key, value)
  end

  node.rotate_left if (node.right && node.right.red?)
  node.rotate_right if (node.left && node.left.red? && node.left.left && node.left.left.red?)
  node.colorflip if (node.left && node.left.red? && node.right && node.right.red?)
  node.update_size
end
isred(node) click to toggle source
# File lib/containers/rb_tree_map.rb, line 407
def isred(node)
  return false if node.nil?

  node.color == :red
end
max_recursive(node) click to toggle source
# File lib/containers/rb_tree_map.rb, line 384
def max_recursive(node)
  return node.key if node.right.nil?

  max_recursive(node.right)
end
min_recursive(node) click to toggle source
# File lib/containers/rb_tree_map.rb, line 377
def min_recursive(node)
  return node.key if node.left.nil?

  min_recursive(node.left)
end