Class: MultiRBTree

Inherits:
RBTree show all
Defined in:
lib/rbtree.rb

Overview

A Multi Red-Black Tree that allows duplicate keys.

MultiRBTree extends RBTree to support multiple values per key. Each key maps to an array of values rather than a single value. The size reflects the total number of key-value pairs (not unique keys).

Features

  • Multiple values per key using arrays
  • Separate methods for single deletion (delete_value) vs. all deletions (delete_key)
  • Values for each key maintain insertion order
  • Configurable access to first or last value via :last option

Value Array Access

For each key, values are stored in insertion order. Methods that access a single value support a :last option to choose which end of the array:

  • get(key), first_value(key) - returns first value (oldest)
  • get(key, last: true), last_value(key) - returns last value (newest)
  • delete_value(key), delete_first_value(key) - removes first value
  • delete_value(key, last: true), delete_last_value(key) - removes last value
  • prev(key), succ(key) - returns first value of adjacent key
  • prev(key, last: true), succ(key, last: true) - returns last value

Boundary Operations

  • min, max - return [key, first_value] by default
  • min(last: true), max(last: true) - return [key, last_value]
  • shift - removes and returns [smallest_key, first_value]
  • pop - removes and returns [largest_key, last_value]

Iteration Order

When iterating over values, the order depends on the direction:

  • Forward iteration (+each+, lt, gt, etc.): Each key's values are yielded in insertion order (first to last).

  • Reverse iteration (+reverse_each+, lt(key, reverse: true), etc.): Each key's values are yielded in reverse insertion order (last to first).

This ensures consistent behavior where reverse iteration is truly the mirror image of forward iteration.

Usage

tree = MultiRBTree.new
tree.insert(1, 'first one')
tree.insert(1, 'second one')
tree.insert(2, 'two')

tree.size             # => 3 (total key-value pairs)
tree.get(1)           # => "first one" (first value)
tree.get(1, last: true)  # => "second one" (last value)
tree.values(1)        # => ["first one", "second one"] (all values)

tree.delete_value(1)   # removes only "first one"
tree.get(1)           # => "second one"

tree.delete(1)        # removes all remaining values for key 1

Author:

  • Masahito Suzuki

Since:

  • 0.1.2

Constant Summary

Constants inherited from RBTree

RBTree::VERSION

Instance Attribute Summary

Attributes inherited from RBTree

#key_count

Instance Method Summary collapse

Methods inherited from RBTree

[], #[], #between, coherent_key_class, #each, #empty?, #first, #gt, #gte, #has_key?, #initialize_copy, #insert, #inspect, #invert, #keys, #lt, #lte, #max_key, #merge, #min_key, #nearest_key, #prev_key, #reject, #reject!, #reverse_each, #select, #succ_key

Constructor Details

#initialize(*args, **kwargs) ⇒ MultiRBTree

Returns a new instance of MultiRBTree.

Since:

  • 0.1.2



1873
1874
1875
1876
 
# File 'lib/rbtree.rb', line 1873

def initialize(*args, **kwargs)
  @value_count = 0
  super
end

Instance Method Details

#clear ⇒ MultiRBTree

Removes all elements from the tree.

Returns:

Since:

  • 0.1.2



1884
1885
1886
1887
 
# File 'lib/rbtree.rb', line 1884

def clear
  @value_count = 0
  super
end

#delete_first_value(key) ⇒ Object? Also known as: delete_first

Deletes the first value for the specified key.

Parameters:

  • key (Object) —

    the key to delete from

Returns:

  • (Object, nil) —

    the deleted value, or nil if key not found

Since:

  • 0.1.2



2083
 
# File 'lib/rbtree.rb', line 2083

def delete_first_value(key) = delete_value(key)

#delete_if {|key, value| ... } ⇒ MultiRBTree, Enumerator

Deletes key-value pairs for which the block returns true. Unlike RBTree, this removes individual values rather than entire keys.

Yields:

  • (key, value) —

    each key-value pair

Returns:

  • (MultiRBTree, Enumerator) —

    self, or Enumerator if no block

Since:

  • 0.1.2



2167
2168
2169
2170
2171
 
# File 'lib/rbtree.rb', line 2167

def delete_if(&block)
  return enum_for(__method__) { size } unless block_given?
  filter_values! { |k, v| !block.call(k, v) }
  self
end

#delete_key(key) ⇒ Array? Also known as: delete

Deletes all values for the specified key.

Removes the node and all associated values.

Examples:

tree = MultiRBTree.new
tree.insert(1, 'first')
tree.insert(1, 'second')
vals = tree.delete(1)  # removes both values
vals.size  # => 2

Parameters:

  • key (Object) —

    the key to delete

Returns:

  • (Array, nil) —

    the array of all deleted values, or nil if not found

Since:

  • 0.1.2



2105
2106
2107
2108
2109
2110
 
# File 'lib/rbtree.rb', line 2105

def delete_key(key)
  return nil unless (z = find_node(key))
  @value_count -= (value = z.value).size
  delete_found_node(z)
  value
end

#delete_last_value(key) ⇒ Object? Also known as: delete_last

Deletes the last value for the specified key.

Parameters:

  • key (Object) —

    the key to delete from

Returns:

  • (Object, nil) —

    the deleted value, or nil if key not found

Since:

  • 0.1.2



2090
 
# File 'lib/rbtree.rb', line 2090

def delete_last_value(key) = delete_value(key, last: true)

#delete_value(key, last: false) ⇒ Object? Also known as: delete_one

Deletes a single value for the specified key.

If the key has multiple values, removes only one value. If this was the last value for the key, the node is removed from the tree.

Examples:

tree = MultiRBTree.new
tree.insert(1, 'first')
tree.insert(1, 'second')
tree.delete_value(1)            # => "first"
tree.delete_value(1, last: true)  # => "second" (if more values existed)

Parameters:

  • key (Object) —

    the key to delete from

  • last (Boolean) (defaults to: false) —

    if true, remove the last value; otherwise remove the first (default: false)

Returns:

  • (Object, nil) —

    the deleted value, or nil if key not found

Since:

  • 0.1.2



2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
 
# File 'lib/rbtree.rb', line 2066

def delete_value(key, last: false)
  (z = find_node(key)) or return nil
  value = z.value.send(last ? :pop : :shift)
  if z.value.empty?
    delete_found_node(z)
  else
    @mod_count += 1
  end
  @value_count -= 1
  value
end

#first_value(key) ⇒ Object? Also known as: get_first

Retrieves the first value associated with the given key.

Parameters:

  • key (Object) —

    the key to look up

Returns:

  • (Object, nil) —

    the first value for the key, or nil if not found

Since:

  • 0.1.2



1984
 
# File 'lib/rbtree.rb', line 1984

def first_value(key) = value(key)

#keep_if {|key, value| ... } ⇒ MultiRBTree, Enumerator

Keeps key-value pairs for which the block returns true, deleting the rest. Unlike RBTree, this removes individual values rather than entire keys.

Yields:

  • (key, value) —

    each key-value pair

Returns:

  • (MultiRBTree, Enumerator) —

    self, or Enumerator if no block

Since:

  • 0.1.2



2156
2157
2158
2159
2160
 
# File 'lib/rbtree.rb', line 2156

def keep_if(&block)
  return enum_for(__method__) { size } unless block_given?
  filter_values! { |k, v| block.call(k, v) }
  self
end

#last(n = nil) ⇒ Array?

Returns the last key-value pair, or the last n pairs, without removing them.

Examples:

tree = MultiRBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.last  # => [3, "three"]

Parameters:

  • n (Integer, nil) (defaults to: nil) —

    number of trailing pairs to return

Returns:

  • (Array, nil) —

    the pair, or the n last pairs in ascending order

Since:

  • 0.1.2



1955
 
# File 'lib/rbtree.rb', line 1955

def last(n = nil) = n.nil? ? max(last: true) : super(n)

#last_value(key) ⇒ Object? Also known as: get_last

Retrieves the last value associated with the given key.

Parameters:

  • key (Object) —

    the key to look up

Returns:

  • (Object, nil) —

    the last value for the key, or nil if not found

Since:

  • 0.1.2



1991
 
# File 'lib/rbtree.rb', line 1991

def last_value(key) = value(key, last: true)

#max(*args, last: false, &block) ⇒ Array(Object, Object)?

Returns the maximum key-value pair without removing it.

As with RBTree#max, a count or comparison block switches to Enumerable#max.

Examples:

tree = MultiRBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.max  # => [3, "three"]

Parameters:

  • last (Boolean) (defaults to: false) —

    whether to return the last value (default: false)

Returns:

  • (Array(Object, Object), nil) —

    a two-element array [key, value], or nil if tree is empty

Since:

  • 0.1.2



1943
1944
1945
1946
 
# File 'lib/rbtree.rb', line 1943

def max(*args, last: false, &block)
  return super(*args, &block) if !args.empty? || block
  (n = max_node) && [n.key, n.value.send(last ? :last : :first)]
end

#merge!(other) ⇒ MultiRBTree

Merges the contents of another tree, hash, or enumerable into this tree.

Appends values from the other source to the existing values for each key.

Parameters:

  • other (RBTree, Hash, Enumerable) —

    the source to merge from

Returns:

Since:

  • 0.1.2



2047
2048
2049
2050
 
# File 'lib/rbtree.rb', line 2047

def merge!(other)
  insert(other)
  self
end

#min(*args, last: false, &block) ⇒ Array(Object, Object)?

Returns the minimum key-value pair without removing it.

As with RBTree#min, a count or comparison block switches to Enumerable#min.

Examples:

tree = MultiRBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.min  # => [1, "one"]

Parameters:

  • last (Boolean) (defaults to: false) —

    whether to return the last value (default: false)

Returns:

  • (Array(Object, Object), nil) —

    a two-element array [key, value], or nil if tree is empty

Since:

  • 0.1.2



1929
1930
1931
1932
 
# File 'lib/rbtree.rb', line 1929

def min(*args, last: false, &block)
  return super(*args, &block) if !args.empty? || block
  (n = min_node) && [n.key, n.value.send(last ? :last : :first)]
end

#nearest(key, last: false) ⇒ Array(Object, Object)?

Returns the nearest key-value pair without removing it.

Examples:

tree = MultiRBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.nearest(4)   # => [5, "five"]

Parameters:

  • key (Object) —

    the target key

  • last (Boolean) (defaults to: false) —

    whether to return the last value (default: false)

Returns:

  • (Array(Object, Object), nil) —

    a two-element array [key, value], or nil if tree is empty

Since:

  • 0.1.2



2019
 
# File 'lib/rbtree.rb', line 2019

def nearest(key, last: false) = (pair = super(key)) && [pair[0], pair[1].send(last ? :last : :first)]

#pop ⇒ Array(Object, Object)?

Removes and returns the last key-value pair.

Examples:

tree = MultiRBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.pop  # => [3, "three"]

Returns:

  • (Array(Object, Object), nil) —

    a two-element array [key, value], or nil if tree is empty

Since:

  • 0.1.2



2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
 
# File 'lib/rbtree.rb', line 2138

def pop
  (n = max_node) or return nil
  key, vals = n.pair
  val = vals.pop
  if vals.empty?
    delete_found_node(n)
  else
    @mod_count += 1
  end
  @value_count -= 1
  [key, val]
end

#prev(key, last: false) ⇒ Array(Object, Object)?

Returns the previous key-value pair without removing it.

Examples:

tree = MultiRBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.prev(4)   # => [5, "five"]

Parameters:

  • key (Object) —

    the target key

  • last (Boolean) (defaults to: false) —

    whether to return the last value (default: false)

Returns:

  • (Array(Object, Object), nil) —

    a two-element array [key, value], or nil if tree is empty

Since:

  • 0.1.2



2029
 
# File 'lib/rbtree.rb', line 2029

def prev(key, last: false) = (pair = super(key)) && [pair[0], pair[1].send(last ? :last : :first)]

#shift ⇒ Array(Object, Object)?

Removes and returns the first key-value pair.

Examples:

tree = MultiRBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.shift  # => [1, "one"]

Returns:

  • (Array(Object, Object), nil) —

    a two-element array [key, value], or nil if tree is empty

Since:

  • 0.1.2



2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
 
# File 'lib/rbtree.rb', line 2119

def shift
  (n = min_node) or return nil
  key, vals = n.pair
  val = vals.shift
  if vals.empty?
    delete_found_node(n)
  else
    @mod_count += 1
  end
  @value_count -= 1
  [key, val]
end

#size ⇒ Integer

Returns the number of values stored in the tree.

Returns:

  • (Integer) —

    the number of values in the tree

Since:

  • 0.1.2



1880
 
# File 'lib/rbtree.rb', line 1880

def size = @value_count

#succ(key, last: false) ⇒ Array(Object, Object)?

Returns the next key-value pair without removing it.

Examples:

tree = MultiRBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree.succ(4)   # => [5, "five"]

Parameters:

  • key (Object) —

    the target key

  • last (Boolean) (defaults to: false) —

    whether to return the last value (default: false)

Returns:

  • (Array(Object, Object), nil) —

    a two-element array [key, value], or nil if tree is empty

Since:

  • 0.1.2



2039
 
# File 'lib/rbtree.rb', line 2039

def succ(key, last: false) = (pair = super(key)) && [pair[0], pair[1].send(last ? :last : :first)]

#to_h ⇒ Hash

Returns a Hash mapping each key to an Array of its values.

Keys are inserted in ascending order, and each value Array is a fresh copy, so mutating the result cannot corrupt the tree.

Examples:

tree = MultiRBTree.new
tree.insert(1, 'a'); tree.insert(1, 'b')
tree.to_h  # => {1 => ["a", "b"]}

Returns:

  • (Hash) —

    a new Hash with the tree's contents

Since:

  • 0.1.2



1899
1900
1901
1902
1903
 
# File 'lib/rbtree.rb', line 1899

def to_h
  h = {}
  each { |k, v| (h[k] ||= []) << v }
  h
end

#valid? ⇒ Boolean

Validates everything RBTree#valid? does, plus that every node holds a non-empty Array of values and that size matches the total value count.

Returns:

  • (Boolean) —

    true if all properties are satisfied, false otherwise

Since:

  • 0.1.2



1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
 
# File 'lib/rbtree.rb', line 1909

def valid?
  return false unless super
  total = 0
  ok = true
  each_node_asc do |n|
    ok &&= n.value.is_a?(Array) && !n.value.empty?
    total += n.value.size if n.value.is_a?(Array)
  end
  ok && total == @value_count
end

#value(key, last: false) ⇒ Object? Also known as: get

Retrieves a value associated with the given key.

Examples:

tree = MultiRBTree.new
tree.insert(1, 'first')
tree.insert(1, 'second')
tree.get(1)              # => "first"
tree.get(1, last: true)  # => "second"

Parameters:

  • key (Object) —

    the key to look up

  • last (Boolean) (defaults to: false) —

    if true, return the last value; otherwise return the first (default: false)

Returns:

  • (Object, nil) —

    the value for the key, or nil if not found

Since:

  • 0.1.2



1977
 
# File 'lib/rbtree.rb', line 1977

def value(key, last: false) = (@hash_index[key] || find_node_by_order(key))&.value&.send(last ? :last : :first)

#value_count(key = NO_KEY) ⇒ Integer

Returns the number of values for a given key, or the total number of key-value pairs when called without an argument.

The default is a sentinel, so nil and false are looked up as ordinary keys.

Parameters:

  • key (Object) (defaults to: NO_KEY) —

    the key to look up; omit for the total count

Returns:

  • (Integer) —

    the number of values for the key, or total count if no key is given

Since:

  • 0.1.2



1964
 
# File 'lib/rbtree.rb', line 1964

def value_count(key = NO_KEY) = key.equal?(NO_KEY) ? size : (find_node(key)&.value&.size || 0)

#values(key, reverse: false) ⇒ Enumerator? Also known as: get_all

Retrieves all values associated with the given key.

Examples:

tree = MultiRBTree.new
tree.insert(1, 'first')
tree.insert(1, 'second')
tree.values(1).to_a                 # => ["first", "second"]
tree.values(1, reverse: true).to_a  # => ["second", "first"]

Parameters:

  • key (Object) —

    the key to look up

  • reverse (Boolean) (defaults to: false) —

    if true, yield the values in reverse insertion order (default: false)

Returns:

  • (Enumerator, nil) —

    an Enumerator over the values, or nil if the key is absent (when a block is given)

Since:

  • 0.1.2



2005
2006
2007
2008
 
# File 'lib/rbtree.rb', line 2005

def values(key, reverse: false)
  return enum_for(__method__, key, reverse: reverse) { value_count(key) } unless block_given?
  find_node(key)&.value&.send(reverse ? :reverse_each : :each) { |v| yield v }
end