rbtree-ruby

gem 'rbtree-ruby'

require 'rbtree'

# Create an empty tree
tree = RBTree.new

# Or initialize with data (Bulk Insert)
tree = RBTree.new({3 => 'three', 1 => 'one', 2 => 'two'})
tree = RBTree[[5, 'five'], [4, 'four']]
tree = RBTree.new do # Block initialization
  data_source.each { |data| [data.time, data.content] } 
end

# Insert and retrieve values
tree.insert(10, 'ten')
tree[20] = 'twenty'
# Bulk insert
tree.insert({30 => 'thirty', 40 => 'forty'})
puts tree[10]  # => "ten"

# Iterate in sorted order
tree.each { |key, value| puts "#{key}: #{value}" }
# Output:
# 1: one
# 2: two
# 3: three
# 10: ten
# 20: twenty

# Modification during iteration
# Unlike standard Ruby Hash/Array, modification during iteration is fully supported
# with the `safe: true` option. This allows you to delete or insert keys safely while iterating.
tree.each(safe: true) { |k, v| tree.delete(k) if k.even? }
tree.each(reverse: true) { |k, v| puts k }  # Same as reverse_each

# Min and max
tree.min  # => [1, "one"]
tree.max  # => [20, "twenty"]

# Range queries (return Enumerator, use .to_a for Array)
tree.lt(10).to_a   # => [[1, "one"], [2, "two"], [3, "three"]]
tree.gte(10).each { |k, v| puts k } # Block iteration
tree.between(2, 10).to_a  # => [[2, "two"], [3, "three"], [10, "ten"]]

# Range objects in [] (v0.3.4+)
tree[..10].to_a    # lte(10)
tree[2..10].each { |k, v| ... } # Block iteration on Range
tree[2...10].to_a  # between(2, 10, include_max: false)
tree[10..].to_a    # gte(10)
tree[2..10, reverse: true].to_a # with options

# Shift and pop
tree.shift  # => [1, "one"] (removes minimum)
tree.pop    # => [20, "twenty"] (removes maximum)

# Delete
tree.delete(3)  # => "three"

# Check membership
tree.has_key?(2)  # => true
tree.size         # => 2

require 'rbtree'

tree = MultiRBTree.new

# Insert multiple values for the same key
tree.insert(1, 'first one')
tree.insert(1, 'second one')
tree.insert(1, 'third one')
tree.insert(2, 'two')

tree.size  # => 4 (total number of key-value pairs)

# Get first value
tree.value(1)      # => "first one"
tree[1]          # => "first one"

# Get all values for a key (returns Enumerator)
tree.values(1).to_a  # => ["first one", "second one", "third one"]

# Iterate over all key-value pairs
tree.each { |k, v| puts "#{k}: #{v}" }
# Output:
# 1: first one
# 1: second one
# 1: third one
# 2: two

# Delete only first value
tree.delete_value(1)  # => "first one"
tree.value(1)         # => "second one"

# Delete all values for a key
tree.delete_key(1)      # removes all remaining values

tree = RBTree.new({1 => 'one', 5 => 'five', 10 => 'ten'})

tree.nearest(4)   # => [5, "five"]  (closest key to 4)
tree.nearest(7)   # => [5, "five"]  (same distance, returns smaller key)
tree.nearest(8)   # => [10, "ten"]

tree = RBTree.new({1 => 'one', 3 => 'three', 5 => 'five', 7 => 'seven'})

tree.prev(5)   # => [3, "three"]  (largest key < 5)
tree.succ(5)   # => [7, "seven"]  (smallest key > 5)

# Works even if the key doesn't exist
tree.prev(4)   # => [3, "three"]  (4 doesn't exist, returns largest key < 4)
tree.succ(4)   # => [5, "five"]   (4 doesn't exist, returns smallest key > 4)

# Returns nil at boundaries
tree.prev(1)   # => nil (no key smaller than 1)
tree.succ(7)   # => nil (no key larger than 7)

tree = RBTree.new({1 => 'one', 2 => 'two', 3 => 'three', 4 => 'four'})

tree.lt(3).to_a                    # => [[1, "one"], [2, "two"]]
tree.lt(3, reverse: true).to_a     # => [[2, "two"], [1, "one"]]
tree.lt(3).first                   # => [1, "one"] (lazy, no array created)

# Lazy evaluation
tree.gt(0).lazy.take(2).to_a  # => [[1, "one"], [2, "two"]] (only computes first 2)

tree = RBTree.new({1 => 'one', 2 => 'two'})

# Convert to Array (via Enumerable)
tree.to_a  # => [[1, "one"], [2, "two"]]

# Convert to Hash
tree.to_h  # => {1 => "one", 2 => "two"}

# Merge (destructive)
other = {3 => 'three'}
tree.merge!(other)
tree.size  # => 3

# Merge (non-destructive) — returns a new tree
merged = tree.merge({4 => 'four'})

# Merge with block for duplicate key resolution
merged = tree.merge({1 => 'ONE'}) { |key, old_val, new_val| old_val }

# Invert keys and values
tree = RBTree.new({1 => 'a', 2 => 'b', 3 => 'c'})
tree.invert.to_a  # => [["a", 1], ["b", 2], ["c", 3]]

tree = RBTree.new({1 => 'one', 2 => 'two', 3 => 'three', 4 => 'four'})

# Deep copy — independent of original
copy = tree.dup
copy.delete(1)
tree.size  # => 4 (unchanged)

# select / reject — return a new tree
evens = tree.select { |k, _| k.even? }   # => {2=>"two", 4=>"four"}
odds  = tree.reject { |k, _| k.even? }   # => {1=>"one", 3=>"three"}

# delete_if / keep_if — modify in place
tree.delete_if { |k, _| k > 2 }
tree.to_a  # => [[1, "one"], [2, "two"]]

# reject! — like delete_if, but returns nil if nothing changed
tree.reject! { |_, _| false }  # => nil

tree = MultiRBTree.new
tree.insert(1, 'a')
tree.insert(1, 'b')
tree.insert(2, 'c')

tree.delete_if { |k, v| k == 1 && v == 'a' }
tree.to_a  # => [[1, "b"], [2, "c"]]  — only 'a' was removed

tree = MultiRBTree.new
tree.insert(1, 'first')
tree.insert(1, 'second')
tree.insert(1, 'third')

# Access first or last value
tree.value(1)               # => "first"
tree.value(1, last: true)   # => "third"
tree.first_value(1)         # => "first"
tree.last_value(1)          # => "third"

# Delete from either end
tree.delete_first_value(1)      # => "first"
tree.delete_last_value(1)       # => "third"  
tree.value(1)               # => "second"

# min/max with :last option
tree.insert(2, 'a')
tree.insert(2, 'b')
tree.min                  # => [1, "second"] (first value of min key)
tree.max(last: true)      # => [2, "b"]      (last value of max key)

# Customize auto-shrink parameters
pool = RBTree::AutoShrinkNodePool.new(
  history_size: 60,       # 1 minute history
  buffer_factor: 1.5,     # Keep 50% buffer above fluctuation
  reserve_ratio: 0.2      # Always keep 20% reserve
)
tree = RBTree.new(node_allocator: pool)