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

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

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

Return the height of the current tree.

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.

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

TODO Come up with a more efficient way of getting this same effect.

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"

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}

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

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

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 operation. The block can change a type of keys.

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

Returns a new SplayTreeMap with all values converted using the block operation. The block can change a type of values.

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

Modifies the values of the current SplayTreeMap according to the provided block.

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

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}