class SplayTreeMap(K, V)

Included Modules

Defined in:

splay_tree_map.cr
version.cr

Constant Summary

VERSION = "0.3.0"

Constructors

Class Method Summary

Instance Method Summary

Constructor Detail

def self.new(seed : Enumerable(Tuple(K, V)) | Nil | Iterable(Tuple(K, V)) | Nil = nil, block : SplayTreeMap(K, V), K -> V | Nil = nil) #

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]

def self.new(seed : Enumerable(Tuple(K, V)) | Nil | Iterable(Tuple(K, V)) | Nil = nil, &block : SplayTreeMap(K, V), 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]

def self.new(seed : Enumerable(Tuple(K, V)) | Nil | Iterable(Tuple(K, V)) | Nil, default_value : V) #

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"

def self.new(default_value : V) #

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

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

Class Method Detail

def self.zip(ary1 : Array(K), ary2 : Array(V)) #

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

Instance Method Detail

def <=>(other : SplayTreeMap(L, W)) forall L, W #

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


def [](key : K) #

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

def []=(key, value) #

Create a key/value association.

stm["this"] = "that"

def []?(key : K) #

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

def clear #

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


def compact #

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

def compact! #

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

def delete(key, &) #

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"

def delete(key) #

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

def delete_if(&) : self #

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

def dig(key : K, *subkeys) #

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

def dig?(key : K, *subkeys) #

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

def dup #

Duplicates a SplayTreeMap.

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

def each(& : Tuple(K, V) -> ) : Nil #

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.


def each : EntryIterator(K, V) #

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

def each_key(&) #

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.


def each_key #

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.


def each_value(&) #

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.


def each_value #

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.


def empty? #

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

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

def fetch(key, &) #

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"

def fetch(key, default) #

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"

def first_key : K #

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


def first_key? : K | Nil #

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


def first_value : V #

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


def first_value? : V | Nil #

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


def has_key?(key) : Bool #

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

def has_value?(value) : Bool #

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

def height(key) : Int32 | Nil #

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


def height #

Return the height of the current tree.


def invert : SplayTreeMap(V, K) #

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

def key_for(value, &) #

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"

def key_for(value) #

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

def key_for?(value) #

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

def keys : Array(K) #

Returns an array of all keys in the tree.

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

def last #

Returns the last key/value pair in the tree.


def last_key : K #

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


def last_key? : K | Nil #

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


def last_value : V #

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


def last_value? : V | Nil #

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


def max(limit) #

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


def max #

Returns the largest key in the tree.


def maxsize #

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


def maxsize=(value) #

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.


def merge(other : Enumerable(Tuple(L, W))) forall L, W #

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

def merge(other : Enumerable(Tuple(L, W)), & : K, V, W -> V | W) forall L, W #

def merge(other : Enumerable(A(Tuple(L, W)))) forall A, L, W #

def merge(other : Enumerable(L)) forall L #

def merge(other : Enumerable(Tuple(L)), & : K, V, W -> V | W) forall L #

def merge(other : Enumerable(A(Tuple(L, W))), & : K, V, W -> V | W) forall A, L, W #

def merge!(other : T) forall T #

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

def merge!(other : Enumerable(Tuple(L, W)), &) forall L, W #

def merge!(other : Enumerable(Tuple), &) #

def merge!(other : Enumerable(L), &) forall L #

def min(limit) #

def min #

Returns the smallest key in the tree.


def obtain(key : K) : V #

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.


def on_prune(&block : K, V -> ) #

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.


def proper_subset_of?(other : SplayTreeMap) : Bool #

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


def proper_superset_of?(other : SplayTreeMap) : Bool #

Returns true if other is a #proper_subset_of? self.


def prune #

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.


def put(key : K, value : V, &) #

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"

def put_if_absent(key : K, value : V) : V #

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"

def put_if_absent(key : K, & : K -> V) : V #

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)

def reject(& : K, V -> _) #

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}

def reject(keys : Array | Tuple) #

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}

def reject(*keys) #

Returns a new SplayTreeMap with the given keys removed.

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

def reject!(& : K, V -> _) #

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


def reject!(keys : Array | Tuple) #

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}

def reject!(*keys) #

Removes the given keys from the tree.

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

def root #

def select(& : K, V -> _) #

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}

def select(keys : Array | Tuple) #

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}

def select(*keys) #

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}

def select!(& : K, V -> _) #

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


def select!(keys : Array | Tuple) #

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}

def select!(*keys) #

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}

def shift : Tuple(K, V) #

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

def shift(&) #

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


def shift? : Tuple(K, V) | Nil #

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


def size #

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


def subset_of?(other : SplayTreeMap) : Bool #

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


def superset_of?(other : SplayTreeMap) : Bool #

Returns true if other is a #subset_of? self.


def to_a #

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

def to_h #

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

def to_s(io : IO) : Nil #

Transform the SplayTreeMap into a String representation.


def transform(& : Tuple(K, V) -> Tuple(K2, V2)) forall K2, V2 #

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

def transform_keys(& : K -> K2) forall K2 #

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}

def transform_values(& : V -> V2) forall V2 #

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}

def transform_values!(&blk : V, K -> V) : self #

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}

def update(key : K, & : V -> V) : V #

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

def values : Array(V) #

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]

def values_at(*indexes : K) #

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

def values_at?(*indexes : K) #

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}

def was_pruned? : Bool #