SplayTreeMap(K, V)

Creates a new empty SplayTreeMap with a block that is called when a key is missing from the tree.

stm = SplayTreeMap(String, Array(Int32)).new { |t, k| t[k] = [] of Int32 }
stm["a"] << 1
stm["a"] << 2
stm["a"] << 3
puts stm.inspect # => [1,2,3]

Creates a new empty SplayTreeMap with a block that is called when a key is missing from the tree.

stm = SplayTreeMap(String, Array(Int32)).new { |t, k| t[k] = [] of Int32 }
stm["a"] << 1
stm["a"] << 2
stm["a"] << 3
puts stm.inspect # => [1,2,3]

Creates a new SplayTreeMap, populating it with values from the Enumerable or the Iterable seed object, and with a default return value for any missing key.

stm = SplayTreeMap.new({"this" => "that", "something" => "else"}, "Unknown")
stm["something"] # => "else"
stm["xyzzy"]     # => "Unknown"

Creates a new empty SplayTreeMap with a default return value for any missing key.

stm = SplayTreeMap(String, String).new("Unknown")
stm["xyzzy"] # => "Unknown"

Zips two arrays into a SplayTreeMap, taking keys from ary1 and values from ary2.

SplayTreeMap.zip(["key1", "key2", "key3"], ["value1", "value2", "value3"])
# => {"key1" => "value1", "key2" => "value2", "key3" => "value3"}

Compares two SplayTreeMaps. All contained objects must also be comparable, or this method will trigger an exception.

Searches for the given key in the tree and returns the associated value. If the key is not in the tree, a KeyError will be raised.

stm = SplayTreeMap(String, String).new
stm["foo"] = "bar"
stm["foo"] # => "bar"

stm = SplayTreeMap(String, String).new("bar")
stm["foo"] # => "bar"

stm = SplayTreeMap(String, String).new { "bar" }
stm["foo"] # => "bar"

stm = Hash(String, String).new
stm["foo"] # raises KeyError

Create a key/value association.

stm["this"] = "that"

Returns the value for the key given by key. If not found, returns nil. This ignores the default value set by Hash.new.

stm = SplayTreeMap(String, String).new
stm["foo"]? # => "bar"
stm["bar"]? # => nil

stm = SplayTreeMap(String, String).new("bar")
stm["foo"]? # => nil

Resets the state of the SplayTreeMap, clearing all key/value associations.

Returns a deep copy of the tree. Each value is cloned via Object#clone. Unlike #dup, mutating a value inside the result does not affect the original.

stm_a = SplayTreeMap.new({"x" => [1, 2]})
stm_b = stm_a.clone
stm_b["x"] << 3
stm_a["x"] # => [1, 2]

Returns new SplayTreeMap that has all of the nil values and their associated keys removed.

stm = SplayTreeMap.new({"hello" => "world", "foo" => nil})
stm.compact # => {"hello" => "world"}

Removes all nil values from self. Returns nil if no changes were made.

stm = SplayTreeMap.new({"hello" => "world", "foo" => nil})
stm.compact! # => {"hello" => "world"}
stm.compact! # => nil

Deletes the key-value pair and returns the value, else yields key with given block.

stm = SplayTreeMap.new({"foo" => "bar"})
stm.delete("foo") { |key| "#{key} not found" } # => "bar"
stm.fetch("foo", nil)                          # => nil
stm.delete("baz") { |key| "#{key} not found" } # => "baz not found"

Deletes the key-value pair and returns the value, otherwise returns nil.

stm = SplayTreeMap.new({"foo" => "bar"})
stm.delete("foo")     # => "bar"
stm.fetch("foo", nil) # => nil

DEPRECATED: This is just reject! by another name. Use that instead. Deletes each key-value pair for which the given block returns true. Returns the SplayTreeMap.

stm = SplayTreeMap.new({"foo" => "bar", "fob" => "baz", "bar" => "qux"})
stm.delete_if { |key, value| key.starts_with?("fo") }
stm # => { "bar" => "qux" }

Traverses the depth of a structure and returns the value, otherwise raises KeyError.

h = {"a" => {"b" => [10, 20, 30]}}
stm = SplayTreeMap.new(h)
stm.dig "a", "b" # => [10, 20, 30]
stm.dig "a", "c" # raises KeyError

Traverses the depth of a structure and returns the value. Returns nil if not found.

h = {"a" => {"b" => [10, 20, 30]}}
stm = SplayTreeMap.new(h)
stm.dig "a", "b" # => [10, 20, 30]
stm.dig "a", "c" # => nil

Duplicates a SplayTreeMap.

stm_a = {"foo" => "bar"}
stm_b = hash_a.dup
stm_b.merge!({"baz" => "qux"})
stm_a # => {"foo" => "bar"}

Calls the given block for each key/value pair, passing the pair into the block.

stm = SplayTreeMap.new({"foo" => "bar"})

stm.each do |key, value|
  key   # => "foo"
  value # => "bar"
end

stm.each do |key_and_value|
  key_and_value # => {"foo", "bar"}
end

The enumeration follows the order the keys were inserted.

Returns an iterator which can be used to access all of the elements in the tree.

stm = SplayTreeMap.new({"foo" => "bar", "fob" => "baz", "qix" => "qux"})

set = [] of Tuple(String, String)
iterator = stm.each
while entry = iterator.next
  set << entry
end

set  # => [{"fob" => "baz"}, {"foo" => "bar", "qix" => "qux"}]

Calls the given block for each key-value pair and passes in the key.

stm = SplayTreeMap.new({"foo" => "bar"})
stm.each_key do |key|
  key # => "foo"
end

The enumeration is in tree order, from smallest to largest.

Returns an iterator over the SplayTreeMap keys.

stm = SplayTreeMap.new({"foo" => "bar", "baz" => "qux"})
iterator = stm.each_key

key = iterator.next
key # => "foo"

key = iterator.next
key # => "baz"

The enumeration is in tree order, from smallest to largest.

Calls the given block for each key-value pair and passes in the value.

stm = SplayTreeMap.new({"foo" => "bar"})
stm.each_value do |value|
  value # => "bar"
end

The enumeration is in tree order, from smallest to largest.

Returns an iterator over the hash values. Which behaves like an Iterator consisting of the value's types.

stm = SplayTreeMap.new({"foo" => "bar", "baz" => "qux"})
iterator = stm.each_value

value = iterator.next
value # => "bar"

value = iterator.next
value # => "qux"

The enumeration is in tree order, from smallest to largest.

Returns true of the tree contains no key/value pairs.

stm = SplayTreeMap(Int32, Int32).new
stm.empty? # => true
stm[1] = 1
stm.empty? # => false

Returns the value for the key given by key, or when not found calls the given block with the key. This ignores the default value set by SplayTreeMap.new.

stm = SplayTreeMap.new({"foo" => "bar"})
stm.fetch("foo") { "default value" }  # => "bar"
stm.fetch("bar") { "default value" }  # => "default value"
stm.fetch("bar") { |key| key.upcase } # => "BAR"

Returns the value for the key given by key, or when not found the value given by default. This ignores the default value set by SplayTreeMap.new.

stm = SplayTreeMap.new({"foo" => "bar"})
stm.fetch("foo", "foo") # => "bar"
stm.fetch("bar", "foo") # => "foo"

Returns the smallest key in the tree. Raises if the tree is empty.

Returns the smallest key in the tree, or nil if the tree is empty.

Returns the value at the smallest key in the tree. Raises if the tree is empty.

Returns the value at the smallest key in the tree, or nil if the tree is empty.

Return a boolean value indicating whether the given key can be found in the tree.

stm = SplayTreeMap.new({"a" => 1, "b" => 2})
stm.has_key?("a") # => true
stm.has_key?("c") # => false

Return a boolean value indicating whether the given value can be found in the tree. This is potentially slow as it requires scanning the tree until a match is found or the end of the tree is reached.

stm = SplayTreeMap.new({"a" => 1, "b" => 2})
stm.has_value?("2") # => true
stm.has_value?("4") # => false

See Object#hash(hasher). Hash code is order-independent: two trees with the same {key, value} entries hash equally, regardless of insertion order.

Return the height at which a given key can be found.

Return the height of the current tree.

Same output as #to_s(io). Provided explicitly for parity with Hash.

Returns a new SplayTreeMap with keys and values swapped. If there are duplicate values, the entry visited last during in-order traversal wins.

SplayTreeMap.new({"foo" => "bar"}).invert # => {"bar" => "foo"}

Returns a key with the given value, else yields value with the given block.

stm = SplayTreeMap.new({"foo" => "bar"})
stm.key_for("bar") { |value| value.upcase } # => "foo"
stm.key_for("qux") { |value| value.upcase } # => "QUX"

Returns a key with the given value, else raises KeyError.

stm = SplayTreeMap.new({"foo" => "bar", "baz" => "qux"})
stm.key_for("bar")    # => "foo"
stm.key_for("qux")    # => "baz"
stm.key_for("foobar") # raises KeyError

Returns a key with the given value, else nil.

stm = SplayTreeMap.new({"foo" => "bar", "baz" => "qux"})
stm.key_for?("bar")    # => "foo"
stm.key_for?("qux")    # => "baz"
stm.key_for?("foobar") # => nil

Returns an array of all keys in the tree.

stm = SplayTreeMap.new({"foo" => "bar", "baz" => "qux"})
stm.keys.should eq ["baz", "foo"]

Returns the last key/value pair in the tree.

Returns the largest key in the tree. Raises if the tree is empty.

Returns the largest key in the tree, or nil if the tree is empty.

Returns the value at the largest key in the tree. Raises if the tree is empty.

Returns the value at the largest key in the tree, or nil if the tree is empty.

Returns the largest key equal to or less than the provided limit argument. Returns nil if the SplayTreeMap is empty.

Returns the largest key in the tree.

Get the maximum size of the tree. If set to nil, the size in unbounded.

Set the maximum size of the tree. If set to nil, the size is unbounded. If the size is set to a value that is less than the current size, an immediate prune operation will be performed.

Returns a new SplayTreeMap with the keys and values of this tree and other combined. A value in other takes precedence over the one in this tree. Key types must be comparable or this will cause a missing no overload matches exception on compilation.

stm = SplayTreeMap.new({"foo" => "bar"})
stm.merge({"baz" => "qux"}) # => {"foo" => "bar", "baz" => "qux"}
stm                         # => {"foo" => "bar"}

Adds the contents of other to this SplayTreeMap.

For Array-like structures, which return a single value to the block passed to #each, that value will be used for both the key and the value.

For Array-like structures, where each array element is a two value Tuple, the first value of the Tuple will be the key, and the second will be the value.

For Hash-like structures, which pass a key/value tuple into the #each, the key and value will be used for the key and value in the tree entry.

If a Tuple is passed into the #each that has more or fewer than 2 elements, the key for the tree entry will come from the first element in the Tuple, and the value will come from the last element in the Tuple.

a = [] of Int32
10.times {|x| a << x}
stm = SplayTreeMap(Int32, Int32).new({6 => 0, 11 => 0}).merge!(a)
stm[11] # => 0
stm[6]  # => 6

h = {} of Int32 => Int32
10.times {|x| h[x] = x**2}
stm = SplayTreeMap(Int32, Int32).new.merge!(h)
stm[6] # => 36

stm = SplayTreeMap(Int32, Int32).new.merge!({ {4,16},{5},{7,49,343} })
stm[4] # => 16
stm[5] # => 5
stm[7] # => 343

Returns the smallest key in the tree.

Obtain a key without splaying. This is much faster than using #[] but the lack of a splay operation means that the accessed value will not move closer to the root of the tree, which bypasses the normal optimization behavior of Splay Trees.

A KeyError will be raised if the key can not be found in the tree.

This method takes a block that accepts key/value pairs from the tree. It will be called once for every key/value pair that is pruned from the tree. This could be used to log items that are eliminate from a cache, or to move eliminated items into a secondard cache, for example.

Renders the tree using PrettyPrint in the same shape as Hash: { key => value, key => value } with pp.group and pp.breakable for wrapping.

Returns true if self is a subset_of? other AND strictly smaller.

Returns true if other is a proper_subset_of? self.

This will remove all of the leaves at the end of the tree branches. That is, every node that does not have any children. This will tend to remove the least used elements from the tree. This function is expensive, as implemented, as it must walk every node in the tree.

Sets the value of key to the given value.

If a value already exists for key, that (old) value is returned. Otherwise the given block is invoked with key and its value is returned.

stm = SplayTreeMap(Int32, String).new
stm.put(1, "one") { "didn't exist" } # => "didn't exist"
stm.put(1, "uno") { "didn't exist" } # => "one"
stm.put(2, "two") { |key| key.to_s } # => "2"

Sets the value of key to value unless an entry for key already exists. Returns the current value for key (the existing one if present, otherwise value).

This is a more performant and falsey-safe alternative to stm[key] ||= value.

stm = SplayTreeMap(Int32, String).new
stm.put_if_absent(1, "one") # => "one"
stm.put_if_absent(1, "uno") # => "one"

Sets the value of key to the result of yielding key to the given block, unless an entry for key already exists. Returns the current value.

stm = SplayTreeMap(Int32, Array(String)).new
stm.put_if_absent(1) { |k| [k.to_s] }     # => ["1"]
stm.put_if_absent(1) { |k| [] of String } # => ["1"] (block not called)

Rebuilds the tree from the current keys. Useful when mutable keys have been modified post-insertion in a way that affects <=> ordering. Tree traversal is performed first; if the existing tree is too corrupted for traversal to be sensible, this method cannot help.

Returns a new SplayTreeMap consisting of entries for which the block returns false.

stm = SplayTreeMap.new({"a" => 100, "b" => 200, "c" => 300})
stm.reject { |k, v| k > "a" } # => {"a" => 100}
stm.reject { |k, v| v < 200 } # => {"b" => 200, "c" => 300}

Removes a list of keys out of the tree, returning a new tree.

h = {"a" => 1, "b" => 2, "c" => 3, "d" => 4}.reject("a", "c")
h # => {"b" => 2, "d" => 4}

Returns a new SplayTreeMap with the given keys removed.

{"a" => 1, "b" => 2, "c" => 3, "d" => 4}.reject("a", "c") # => {"b" => 2, "d" => 4}

Equivalent to SplayTreeMap#reject, but modifies the current object rather than returning a new one. Returns nil if no changes were made.

Removes a list of keys out of the tree.

h = {"a" => 1, "b" => 2, "c" => 3, "d" => 4}.reject!("a", "c")
h # => {"b" => 2, "d" => 4}

Removes the given keys from the tree.

{"a" => 1, "b" => 2, "c" => 3, "d" => 4}.reject!("a", "c") # => {"b" => 2, "d" => 4}

Returns a new hash consisting of entries for which the block returns true.

h = {"a" => 100, "b" => 200, "c" => 300}
h.select { |k, v| k > "a" } # => {"b" => 200, "c" => 300}
h.select { |k, v| v < 200 } # => {"a" => 100}

Returns a new SplayTreeMap with the given keys.

SplayTreeMap.new({"a" => 1, "b" => 2, "c" => 3, "d" => 4}).select({"a", "c"}) # => {"a" => 1, "c" => 3}
SplayTreeMap.new({"a" => 1, "b" => 2, "c" => 3, "d" => 4}).select("a", "c")   # => {"a" => 1, "c" => 3}
SplayTreeMap.new({"a" => 1, "b" => 2, "c" => 3, "d" => 4}).select(["a", "c"]) # => {"a" => 1, "c" => 3}

Returns a new SplayTreeMap with the given keys.

SplayTreeMap.new({"a" => 1, "b" => 2, "c" => 3, "d" => 4}).select({"a", "c"}) # => {"a" => 1, "c" => 3}
SplayTreeMap.new({"a" => 1, "b" => 2, "c" => 3, "d" => 4}).select("a", "c")   # => {"a" => 1, "c" => 3}
SplayTreeMap.new({"a" => 1, "b" => 2, "c" => 3, "d" => 4}).select(["a", "c"]) # => {"a" => 1, "c" => 3}

Equivalent to Hash#select but makes modification on the current object rather that returning a new one. Returns nil if no changes were made

Removes every element except the given ones.

h1 = {"a" => 1, "b" => 2, "c" => 3, "d" => 4}.select!({"a", "c"})
h2 = {"a" => 1, "b" => 2, "c" => 3, "d" => 4}.select!("a", "c")
h3 = {"a" => 1, "b" => 2, "c" => 3, "d" => 4}.select!(["a", "c"])
h1 == h2 == h3 # => true
h1             # => {"a" => 1, "c" => 3}

Removes every element except the given ones.

h1 = {"a" => 1, "b" => 2, "c" => 3, "d" => 4}.select!({"a", "c"})
h2 = {"a" => 1, "b" => 2, "c" => 3, "d" => 4}.select!("a", "c")
h3 = {"a" => 1, "b" => 2, "c" => 3, "d" => 4}.select!(["a", "c"])
h1 == h2 == h3 # => true
h1             # => {"a" => 1, "c" => 3}

Removes and returns the smallest key/value pair as a tuple. Raises IndexError if the tree is empty.

stm = SplayTreeMap.new({3 => "c", 1 => "a", 2 => "b"})
stm.shift # => {1, "a"}

Removes and returns the smallest key/value pair as a tuple. Yields to the block (and returns its value) if the tree is empty.

Same as #shift, but returns nil if the tree is empty.

Return the current number of key/value pairs in the tree.

Returns true if every entry in self exists in other with an equal value. An equal-sized identical tree is a subset of itself.

Returns true if other is a subset_of? self.

Transform the SplayTreeMap into an Array(Tuple(K, V)).

stm = SplayTreeMap.new({"foo" => "bar", "baz" => "qux"})
ary = stm.to_a # => [{"baz", "qux"}, {"foo", "bar"}]
stm2 = SplayTreeMap.new(ary)
stm == stm2 # => true

Returns an Array of the results of yielding each {K, V} tuple to the block. Order matches in-order traversal of the tree.

stm = SplayTreeMap.new({"first" => "foo", "last" => "bar"})
stm.to_a { |_k, v| v.capitalize } # => ["Bar", "Foo"]

Transform a SplayTreeMap(K,V) into a Hash(K,V).

stm = SplayTreeMap.new({"foo" => "bar", "baz" => "qux"})
h = stm.to_h # => {"baz" => "qux", "foo" => "bar"}

Transform the SplayTreeMap into a String representation.

Returns a new SplayTreeMap with all of the key/value pairs converted using the provided block. The block can change the types of both keys and values.

stm = SplayTreeMap({1 => 1, 2 => 4, 3 => 9, 4 => 16})
stm = stm.transform {|k, v| {k.to_s, v.to_s}}
stm  # => {"1" => "1", "2" => "4", "3" => "9", "4" => "16"}

Returns a new SplayTreeMap with all keys converted using the block. The block yields the key and value; it may return a key of any type.

stm = SplayTreeMap.new({:a => 1, :b => 2, :c => 3})
stm.transform_keys { |key| key.to_s }                # => {"a" => 1, "b" => 2, "c" => 3}
stm.transform_keys { |key, value| key.to_s * value } # => {"a" => 1, "bb" => 2, "ccc" => 3}

Destructively transforms keys using the block. The block yields key and value and must return a key of the same type K. Returns self.

stm = SplayTreeMap.new({"a" => 1, "b" => 2})
stm.transform_keys! { |key| key.upcase }
stm # => {"A" => 1, "B" => 2}

Returns a new SplayTreeMap with all values converted using the block. The block yields the value and key; it may return a value of any type.

stm = SplayTreeMap.new({:a => 1, :b => 2, :c => 3})
stm.transform_values { |value| value + 1 }             # => {:a => 2, :b => 3, :c => 4}
stm.transform_values { |value, key| "#{key}#{value}" } # => {:a => "a1", :b => "b2", :c => "c3"}

Mutates each value in place using the result of the given block. The block yields the current value and key.

stm = SplayTreeMap.new({:a => 1, :b => 2, :c => 3})
stm.transform_values! { |value, key| value + key.to_s.bytesize }
stm # => {:a => 2, :b => 3, :c => 4}

Updates the current value of key with the result of yielding the current value to the given block. Returns the value used as input to the block (the old value, or the default if the key was absent).

If no entry for key is present but a default block was configured at construction, the default block's value is used as input.

Raises KeyError if no entry exists and no default is configured.

stm = SplayTreeMap.new({"a" => 0, "b" => 1})
stm.update("b") { |v| v + 41 } # => 1
stm["b"]                       # => 42

Returns an array containing all of the values in the tree. The array is in the order of the associated keys.

stm = SplayTreeMap.new({"a" => 1, "b" => 2, "c" => 3, "d" => 4})
stm.values # => [1, 2, 3, 4]

Returns a tuple populated with the values associated with the given keys. Raises a KeyError if any key is invalid.

stm = SplayTreeMap.new({"a" => 1, "b" => 2, "c" => 3, "d" => 4})
stm.values_at("a", "c")      # => {1, 3}
stm.values_at("a", "d", "e") # => KeyError

Returns a tuple populated with the values associated with the given keys. Returns nil for any key that is invalid.

stm = SplayTreeMap.new({"a" => 1, "b" => 2, "c" => 3, "d" => 4})
stm.values_at?("a", "c")      # => {1, 3}
stm.values_at?("a", "d", "e") # => {1, 4, nil}