class MultiRBTree

Sorted hash that supports multiple keys for its values.

Attributes

size[R]

See Hash#size

Public Class Methods

new(default = nil, &default_proc) click to toggle source
Calls superclass method RBTree::new
# File lib/rbtree/multi_rb_tree.rb, line 3
def initialize(default = nil, &default_proc)
  super(default, &default_proc)
  @size = 0
end

Public Instance Methods

[](key) click to toggle source

See Hash#[]

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

See Hash#[]=

# File lib/rbtree/multi_rb_tree.rb, line 99
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
  @size += 1
  value
end
bound(lower_key, upper_key = nil) { |key, value| ... } click to toggle source
# File lib/rbtree/multi_rb_tree.rb, line 18
def bound(lower_key, upper_key = nil)
  result = []
  bound_nodes lower_key, upper_key do |node|
    if block_given?
      node.value.each { |value| yield node.key, value }
    else
      node.value.each { |value| result << [node.key, value] }
    end
  end
  block_given? ? self : result
end
clear() click to toggle source

See Hash#clear

Calls superclass method RBTree#clear
# File lib/rbtree/multi_rb_tree.rb, line 117
def clear
  super
  @size = 0
end
delete(key) { |: nil| ... } click to toggle source

See Hash#delete

# File lib/rbtree/multi_rb_tree.rb, line 178
def delete(key)
  node = @tree.search key
  unless node
    return block_given? ? yield : nil
  end
  value = node.value.shift
  @tree.delete node if node.value.empty?
  @size -= 1
  value
end
each() { |key, value| ... } click to toggle source

See Hash#each

# File lib/rbtree/multi_rb_tree.rb, line 123
def each
  if block_given?
    lock_changes do
      @tree.inorder do |node|
        node.value.each { |value| yield node.key, value }
      end
    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/multi_rb_tree.rb, line 219
def each_key
  if block_given?
    lock_changes do
      @tree.inorder { |node| node.value.each { 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/multi_rb_tree.rb, line 231
def each_value
  if block_given?
    lock_changes do
      @tree.inorder { |node| node.value.each { |value| yield value } }
    end
  else
    Enumerator.new self, :each_value
  end
end
empty?() click to toggle source

See Hash#empty

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

See Hash#fetch

# File lib/rbtree/multi_rb_tree.rb, line 156
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.first 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/multi_rb_tree.rb, line 60
def first
  node = @tree.minimum
  node.nil? ? default : [node.key, node.value.first]
end
index(value) click to toggle source

See Hash#index

# File lib/rbtree/multi_rb_tree.rb, line 150
def index(value)
  each { |k, v| return k if v.include? value }
  nil
end
last() click to toggle source

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

# File lib/rbtree/multi_rb_tree.rb, line 66
def last
  node = @tree.maximum
  node.nil? ? default : [node.key, node.value.last]
end
lower_bound(key) click to toggle source
# File lib/rbtree/multi_rb_tree.rb, line 8
def lower_bound(key)
  node = @tree.lower_bound(key)
  [node.key, node.value.first]
end
merge(other) click to toggle source

See Hash#merge

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

See Hash#merge!

# File lib/rbtree/multi_rb_tree.rb, line 242
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)
        self[key] = yield key, node.value.first, 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/multi_rb_tree.rb, line 72
def pop
  return default if (node = @tree.maximum).nil? 
  value = node.value.pop
  @tree.delete node if node.value.empty?
  @size -= 1
  [node.key, value]
end
reject(&block) click to toggle source

See Hash#reject

# File lib/rbtree/multi_rb_tree.rb, line 210
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/multi_rb_tree.rb, line 190
def reject!
  if block_given?
    dead_nodes = []
    lock_changes do
      @tree.inorder do |node|
        node.value.reject! do |value|
          @size -= 1 if result = yield(node.key, value)
          result
        end
        dead_nodes << node if node.value.empty?
      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/multi_rb_tree.rb, line 34
def replace(other)
  raise TypeError, 'cannot modify rbtree in iteration' if @lock_count > 0
  unless other.kind_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
  @size = other.size
  
  unless other.instance_of? MultiRBTree
    # Wrap values in arrays to convert RBTree -> MultiRBTree.
    @tree.inorder do |node|
      node.value = [node.value]
    end
  end
  
  self
end
reverse_each() { |key, value| ... } click to toggle source

See Hash#reverse_each

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

Removes the smallest key in the tree.

# File lib/rbtree/multi_rb_tree.rb, line 81
def shift
  return default if (node = @tree.minimum).nil? 
  value = node.value.shift
  @tree.delete node if node.value.empty?
  @size -= 1
  [node.key, value]
end
to_hash() click to toggle source

A new Hash with the same contents and defaults as this RBTree instance.

# File lib/rbtree/multi_rb_tree.rb, line 270
def to_hash
  raise TypeError, "can't convert MultiRBTree to Hash"
end
to_rbtree() click to toggle source
# File lib/rbtree/multi_rb_tree.rb, line 30
def to_rbtree
  self
end
update(other)
Alias for: merge!
upper_bound(key) click to toggle source
# File lib/rbtree/multi_rb_tree.rb, line 13
def upper_bound(key)
  node = @tree.lower_bound(key)
  [node.key, node.value.last]
end