class RBTree
Sorted hash.
Attributes
Block used to implement custom comparisons.
Block called when trying to read keys that don’t exist in the tree.
The red-black tree backing this store.
Public Class Methods
# 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
# 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
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
See Hash#[]
# File lib/rbtree/rb_tree.rb, line 212 def [](key) node = tree.search key node ? node.value : default(key) end
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
# 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
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
See Hash#clear
# File lib/rbtree/rb_tree.rb, line 236 def clear @tree = RBTree::Tree.new end
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
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
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
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
See Hash#delete_if
# File lib/rbtree/rb_tree.rb, line 315 def delete_if(&block) reject!(&block) self end
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
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
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
See Hash#empty
# File lib/rbtree/rb_tree.rb, line 231 def empty? @tree.empty? end
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
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
See Hash#has_key?
# File lib/rbtree/rb_tree.rb, line 382 def has_key?(key) !!@tree.search(key) end
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
See Hash#index
# File lib/rbtree/rb_tree.rb, line 277 def index(value) each { |k, v| return k if value == v } nil end
# File lib/rbtree/rb_tree.rb, line 40 def initialize_copy(source) super @tree = source.tree.dup @lock_count = 0 end
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
See Hash#keys.
# File lib/rbtree/rb_tree.rb, line 368 def keys result = Array.new each_key { |key| result << key } result end
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
# File lib/rbtree/rb_tree.rb, line 86 def lower_bound(key) @tree.lower_bound(key).to_a end
See Hash#merge
# File lib/rbtree/rb_tree.rb, line 428 def merge(other) copy = self.dup copy.merge! other copy end
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
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
# 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
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
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
# 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
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
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
See Hash#size
# File lib/rbtree/rb_tree.rb, line 226 def size @tree.size end
# File lib/rbtree/rb_tree.rb, line 129 def to_rbtree self end
# File lib/rbtree/rb_tree.rb, line 90 def upper_bound(key) @tree.upper_bound(key).to_a end
See Hash#values.
# File lib/rbtree/rb_tree.rb, line 375 def values result = Array.new each_value { |value| result << value } result end
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
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