class RBTree

Sorted hash.

Attributes

cmp_proc[R]

Block used to implement custom comparisons.

default_proc[R]

Block called when trying to read keys that don’t exist in the tree.

tree[R]

The red-black tree backing this store.

Public Class Methods

[](*key_values) click to toggle source
# File lib/rbtree/rb_tree.rb, line 46
def self.[](*key_values)
  if key_values.length == 1
    hash = key_values.first
    unless hash.respond_to? :values_at
      raise ArgumentError, "expected a Hash-like argument"
    end
    if self == RBTree && hash.instance_of?(MultiRBTree)
      raise TypeError, "can't convert MultiRBTree to RBTree"
    end
    tree = self.new
    begin
      hash.each { |k, v| tree[k] = v }
    rescue NoMethodError
      raise ArgumentError, "expected a Hash-like argument"
    end
    return tree
  end
  
  if key_values.length % 2 == 1
    raise ArgumentError, 'odd number of arguments for RBTree'
  end
  
  tree = self.new
  0.upto(key_values.length / 2 - 1) do |i|
    tree[key_values[i * 2]] = key_values[i * 2 + 1]
  end
  tree
end
new(default = nil, &default_proc) click to toggle source
# File lib/rbtree/rb_tree.rb, line 31
def initialize(default = nil, &default_proc)
  raise ArgumentError, "wrong number of arguments" if default && default_proc
  @default = default
  @default_proc = default_proc
  @cmp_proc = nil
  @lock_count = 0
  @tree = RBTree::Tree.new
end

Public Instance Methods

==(other) click to toggle source

See Hash#==

# File lib/rbtree/rb_tree.rb, line 241
def ==(other)
  return false unless other.kind_of?(RBTree)
  return false unless other.size == self.size
  return false unless other.cmp_proc == @cmp_proc
  
  ary = self.to_a
  other_ary = other.to_a
  ary.each_with_index { |v, i| return false unless other_ary[i] == v }
  true
end
[](key) click to toggle source

See Hash#[]

# File lib/rbtree/rb_tree.rb, line 212
def [](key)
  node = tree.search key
  node ? node.value : default(key)
end
[]=(key, value) click to toggle source

See Hash#[]=

# File lib/rbtree/rb_tree.rb, line 218
def []=(key, value)
  raise TypeError, 'cannot modify rbtree in iteration' if @lock_count > 0

  key = key.clone.freeze if key.kind_of? String
  @tree.insert(@tree.node(key, value)).value = value
end
bound(lower_key, upper_key = nil) { |key, value| ... } click to toggle source
# File lib/rbtree/rb_tree.rb, line 94
def bound(lower_key, upper_key = nil)
  result = []
  bound_nodes lower_key, upper_key do |node|
    if block_given?
      yield node.key, node.value
    else
      result << node.to_a
    end
  end
  block_given? ? self : result
end
bound_nodes(lower_key, upper_key = nil) { |node| ... } click to toggle source

Internal version of bound that yields the corresponding nodes.

# File lib/rbtree/rb_tree.rb, line 107
def bound_nodes(lower_key, upper_key = nil)
  upper_key ||= lower_key
  node = @tree.lower_bound(lower_key)
  return block_given? ? self : [] if node.nil?

  lock_changes do
    if @cmp_proc
      # Slow path
      until node.nil? || @cmp_proc.call(upper_key, node.key) < 0
        yield node
        node = @tree.successor node
      end
    else
      # Fast path.
      until node.nil? || upper_key < node.key
        yield node
        node = @tree.successor node
      end
    end
  end
end
clear() click to toggle source

See Hash#clear

# File lib/rbtree/rb_tree.rb, line 236
def clear
  @tree = RBTree::Tree.new
end
default(key = nil) click to toggle source

The value returned when trying to read keys that don’t exist in the tree.

# File lib/rbtree/rb_tree.rb, line 9
def default(key = nil)
  @default_proc ? @default_proc.call(tree, key) : @default
end
default=(new_default) click to toggle source

The value returned when trying to read keys that don’t exist in the tree.

# File lib/rbtree/rb_tree.rb, line 14
def default=(new_default)
  @default_proc = nil
  @default = new_default
end
default_proc=(new_proc) click to toggle source

Block called when trying to read keys that don’t exist in the tree.

# File lib/rbtree/rb_tree.rb, line 23
def default_proc=(new_proc)
  @default = nil
  @default_proc = new_proc
end
delete(key) { |: nil| ... } click to toggle source

See Hash#delete

# File lib/rbtree/rb_tree.rb, line 305
def delete(key)
  node = @tree.search key
  unless node
    return block_given? ? yield : nil
  end
  @tree.delete node
  node.value
end
delete_if(&block) click to toggle source

See Hash#delete_if

# File lib/rbtree/rb_tree.rb, line 315
def delete_if(&block)
  reject!(&block)
  self
end
each() { |key, value| ... } click to toggle source

See Hash#each

# File lib/rbtree/rb_tree.rb, line 253
def each
  if block_given?
    lock_changes do
      @tree.inorder { |node| yield node.key, node.value }
    end
  else
    Enumerator.new self, :each
  end
end
Also aliased as: each_pair
each_key() { |key| ... } click to toggle source

See Hash#each_key.

# File lib/rbtree/rb_tree.rb, line 346
def each_key
  if block_given?
    lock_changes do
      @tree.inorder { |node| yield node.key }
    end
  else
    Enumerator.new self, :each_key
  end
end
each_pair()
Alias for: each
each_value() { |value| ... } click to toggle source

See Hash#each_value.

# File lib/rbtree/rb_tree.rb, line 357
def each_value
  if block_given?
    lock_changes do
      @tree.inorder { |node| yield node.value }
    end
  else
    Enumerator.new self, :each_value
  end
end
empty?() click to toggle source

See Hash#empty

# File lib/rbtree/rb_tree.rb, line 231
def empty?
  @tree.empty?
end
fetch(key, *default) { |key| ... } click to toggle source

See Hash#fetch

# File lib/rbtree/rb_tree.rb, line 283
def fetch(key, *default)
  if default.length > 1
    raise ArgumentError, "expected at most 1 default, got #{default.length}"
  end
  if default.length == 1 && block_given?
    $stderr << "warning: block supersedes default value argument"
  end
  
  node = tree.search key
  return node.value if node
  if block_given?
    yield key
  else
    if default.length == 1
      default.first
    else
      raise IndexError, 'key not found'
    end
  end
end
first() click to toggle source

The [key, value] for the smallest key in the tree.

# File lib/rbtree/rb_tree.rb, line 183
def first
  node = @tree.minimum
  node.nil? ? default : node.to_a
end
has_key?(key) click to toggle source

See Hash#has_key?

# File lib/rbtree/rb_tree.rb, line 382
def has_key?(key)
  !!@tree.search(key)
end
has_value?(value) click to toggle source

See Hash#has_value?

# File lib/rbtree/rb_tree.rb, line 387
def has_value?(value)
  lock_changes do
    each_value { |v| return true if value == v }
  end
  false
end
index(value) click to toggle source

See Hash#index

# File lib/rbtree/rb_tree.rb, line 277
def index(value)
  each { |k, v| return k if value == v }
  nil
end
initialize_copy(source) click to toggle source
Calls superclass method
# File lib/rbtree/rb_tree.rb, line 40
def initialize_copy(source)
  super
  @tree = source.tree.dup
  @lock_count = 0
end
invert() click to toggle source

See Hash#invert

# File lib/rbtree/rb_tree.rb, line 395
def invert
  tree = self.class.new
  each { |key, value| tree[value] = key }
  tree
end
keys() click to toggle source

See Hash#keys.

# File lib/rbtree/rb_tree.rb, line 368
def keys
  result = Array.new
  each_key { |key| result << key }
  result
end
last() click to toggle source

The [key, value] for the largest key in the tree.

# File lib/rbtree/rb_tree.rb, line 189
def last
  node = @tree.maximum
  node.nil? ? default : node.to_a
end
lower_bound(key) click to toggle source
# File lib/rbtree/rb_tree.rb, line 86
def lower_bound(key)
  @tree.lower_bound(key).to_a
end
merge(other) click to toggle source

See Hash#merge

# File lib/rbtree/rb_tree.rb, line 428
def merge(other)
  copy = self.dup
  copy.merge! other
  copy
end
merge!(other) { |key, value, value| ... } click to toggle source

See Hash#merge!

# File lib/rbtree/rb_tree.rb, line 407
def merge!(other)
  unless other.instance_of? RBTree
    raise TypeError, "wrong argument type #{other.class} (expected RBTree)"
  end
  
  if block_given?
    other.each do |key, value|
      if node = @tree.search(key)
        node.value = yield key, node.value, value
      else
        self[key] = value
      end
    end
  else
    other.each { |key, value| self[key] = value }
  end
  self
end
Also aliased as: update
pop() click to toggle source

Removes the largest key in the tree.

# File lib/rbtree/rb_tree.rb, line 195
def pop
  return default if (node = @tree.maximum).nil? 
  @tree.delete node
  node.to_a
end
readjust(*proc_arg, &new_cmp_proc) click to toggle source
# File lib/rbtree/rb_tree.rb, line 133
def readjust(*proc_arg, &new_cmp_proc)
  raise TypeError, 'cannot modify rbtree in iteration' if @lock_count > 0
  
  if new_cmp_proc
    cmp_proc = new_cmp_proc
    unless proc_arg.empty?
      raise ArgumentError, "expected 0 arguments when given a block"
    end
  else
    unless proc_arg.length <= 1
      raise ArgumentError, "expected 1 arguments (given #{proc_arg.length})"        
    end
    unless proc_arg.first.respond_to?(:call) || proc_arg.first.nil?
      raise TypeError, "expected a proc argument"
    end
    cmp_proc = proc_arg.first
  end
  
  lock_changes do
    if cmp_proc
      new_tree = RBTree::TreeCmp.new(&cmp_proc)
    else
      new_tree = RBTree::Tree.new
    end
    
    @tree.inorder do |node|
      new_tree.insert new_tree.node(node.key, node.value)
    end
    @tree = new_tree
    @cmp_proc = cmp_proc
  end
end
reject(&block) click to toggle source

See Hash#reject

# File lib/rbtree/rb_tree.rb, line 337
def reject(&block)
  copy = self.dup
  copy.reject!(&block)
  # NOTE: the correct answer should be "copy", but we're copying RBTree
  #       bug-for-bug
  # copy
end
reject!() { |key, value| ... } click to toggle source

See Hash#reject!

# File lib/rbtree/rb_tree.rb, line 321
def reject!
  if block_given?
    dead_nodes = []
    lock_changes do
      @tree.inorder do |node|
        dead_nodes << node if yield node.key, node.value
      end
    end
    dead_nodes.each { |node| @tree.delete node }
    dead_nodes.empty? ? nil : self
  else
    Enumerator.new self, :each
  end
end
replace(other) click to toggle source
# File lib/rbtree/rb_tree.rb, line 166
def replace(other)
  raise TypeError, 'cannot modify rbtree in iteration' if @lock_count > 0
  unless other.instance_of? RBTree
    raise TypeError, "expected RBTree, got #{other.class}"
  end
  
  @tree = other.tree.dup
  @default_proc = other.default_proc
  @default = other.default
  @cmp_proc = other.cmp_proc
  self
end
reverse_each() { |key, value| ... } click to toggle source

See Hash#reverse_each

# File lib/rbtree/rb_tree.rb, line 265
def reverse_each
  if block_given?
    lock_changes do
      @tree.reverse_inorder { |node| yield node.key, node.value }
    end
  else
    Enumerator.new self, :reverse_each
  end
end
shift() click to toggle source

Removes the smallest key in the tree.

# File lib/rbtree/rb_tree.rb, line 202
def shift
  return default if (node = @tree.minimum).nil? 
  @tree.delete node
  node.to_a
end
size() click to toggle source

See Hash#size

# File lib/rbtree/rb_tree.rb, line 226
def size
  @tree.size
end
to_rbtree() click to toggle source
# File lib/rbtree/rb_tree.rb, line 129
def to_rbtree
  self
end
update(other)
Alias for: merge!
upper_bound(key) click to toggle source
# File lib/rbtree/rb_tree.rb, line 90
def upper_bound(key)
  @tree.upper_bound(key).to_a
end
values() click to toggle source

See Hash#values.

# File lib/rbtree/rb_tree.rb, line 375
def values
  result = Array.new
  each_value { |value| result << value }
  result
end
values_at(*keys) click to toggle source

See Hash#values_at

# File lib/rbtree/rb_tree.rb, line 402
def values_at(*keys)
  keys.map { |key| self[key] }
end

Private Instance Methods

lock_changes() { || ... } click to toggle source

Rejects changes while this method’s block is executed.

# File lib/rbtree/rb_tree.rb, line 76
def lock_changes
  begin
    @lock_count += 1
    yield
  ensure
    @lock_count -= 1
  end
end