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_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
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