splaytree.ts

splaytree.ts

A splay tree is a self-balancing binary search tree.

const ages = new SplayTreeSet();
for (let age of [33, 45, 25, 35, 59, 18, 62]) {
  ages.add(age)
}
ages.firstAfter(35);  // 45
ages.lastBefore(33);  // 25
ages.delete(59);      // true
ages.has(59);         // false
ages.firstAfter(45);  //  62

It has the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal, in O(log(n)) amortized time.

API Reference

• SplayTreeMap
• SplayTreeSet

SplayTreeMap

Keys of the map are compared using the compare function passed in the constructor, both for ordering and for equality. If the map contains only the key a, then map.has(b) will return true if and only if compare(a, b) == 0, and the value of a == b is not even checked. If the compare function is omitted, the objects are assumed to be comparable, and are compared in natural order. Non-comparable objects (including null) will not work as keys in that case.

To allow calling map.get, map.delete or map.has with objects that are not supported by the compare function, an extra isValidKey predicate function can be supplied. This function is tested before using the compare function on an argument value that may not be a K value. If omitted, the isValidKey function defaults to testing if the value is neither null nor undefined.

new SplayTreeMap([compare(a, b)[, isValidKey(value)]])

# map.clear()

Removes all pairs from the map.

After this, the map is empty.

# map.has(key)

Returns true if the map contains the given key.

Returns true if any of the keys in the map are equal to key according to the equality used by the map.

# map.delete(key)

Removes key and its associated value, if present, from the map.

Returns true if map contains the specified key, or false if key was not in the map.

# map.forEach(f(value, key, map))

Applies f to each key/value pair of the map.

Calling f must not add or remove keys from the map.

# map.get(key)

Returns the value for the given key or undefined if key is not in the map.

Some maps allow keys to have undefined as a value. For those maps, a lookup using this method cannot distinguish between a key not being in the map and the key having a undefined value. Methods like map.hasValue or map.setIfAbsent can be used if the distinction is important.

# map.hasValue(value)

Returns true if the map contains the given value.

Returns true if any of the values in the map are equal to value according to the == operator.

# map.set(key, value)

Associates the key with the given value.

If the key was already in the map, its associated value is changed. Otherwise the key/value pair is added to the map.

# map.setAll(other)

Adds all key/value pairs of other to the map.

If a key of other is already in the map, its value is overwritten.

The operation is equivalent to doing map.set for each key and associated value in other. It iterates over other, which must therefore not change during the iteration.

# map.setIfAbsent(key, ifAbsent)

Look up the value of key, or add a new value if it isn't there.

Returns the value associated to key, if there is one. Otherwise calls ifAbsent to get a new value, associates key to that value, and then returns the new value.

const scores = new SplayTreeMap();
scores.set('Bob', 36)
for (let key of ['Bob', 'Rohan', 'Sophena']) {
  scores.setIfAbsent(key, () => key.length);
}
scores.get('Bob');      // 36
scores.get('Rohan');    //  5
scores.get('Sophena');  //  7

Calling ifAbsent must not add or remove keys from the map.

# map.isEmpty()

Returns true if there is no key/value pair in the map.

# map.isNotEmpty()

Returns true if there is at least one key/value pair in the map.

# map.firstKey()

Get the first key in the map. Returns null if the map is empty.

# map.lastKey()

Get the last key in the map. Returns null if the map is empty.

# map.lastKeyBefore(key)

Get the last key in the map that is strictly smaller than key. Returns null if no key was not found.

# map.firstKeyAfter(key)

Get the first key in the map that is strictly larger than key. Returns null if no key was not found.

# map.update(key, update(value)[, ifAbsent])

Updates the value for the provided key.

Returns the new value of the key.

If the key is present, invokes update with the current value and stores the new value in the map.

If the key is not present and ifAbsent is provided, calls ifAbsent and adds the key with the returned value to the map.

It's an error if the key is not present and ifAbsent is not provided.

# map.updateAll(update(key, value))

Updates all values.

Iterates over all entries in the map and updates them with the result of invoking update.

# map.keys()

Returns an iterable of keys in the map.

Modifying the map while iterating the keys breaks the iteration.

# map.values()

Returns an iterable of values in the map.

Modifying the map while iterating the values breaks the iteration.

# map.entries()

Returns an iterable of key, value pairs for every entry in the map.

Modifying the map while iterating the entries breaks the iteration.

SplayTreeSet

Elements of the set are compared using the compare function passed in the constructor, both for ordering and for equality. If the set contains only an object a, then set.has(b) will return true if and only if compare(a, b) == 0, and the value of a == b is not even checked. If the compare function is omitted, the objects are assumed to be comparable, and are compared in natural order. Non-comparable objects (including null) will not work as keys in that case.

new SplayTreeSet([compare(a, b)[, isValidKey(value)]])

# set.clear()

Removes all elements in the set.

# set.has(element)

Returns true if the set contains an element equal to element.

# set.delete(element)

Removes element from the set. Returns true if element was in the set. Returns false otherwise. The method has no effect if element was not in the set.

# set.deleteAll(elements)

Removes each element of elements from the set.

# set.forEach(f(element, element2, set))

Applies the function f to each element of the set in iteration order.

# set.add(element)

Adds the element to the set if it is not already in the set.

Returns the set.

# set.addAndReturn(element)

Adds the element to the set if it is not already in the set.

Returns the element (or an equal element if there is already one in the set).

# set.addAll(elements)

Adds all elements to the set.

Equivalent to adding each element in elements using set.add.

# set.isEmpty()

Returns true if there are no elements in the set.

May be computed by checking if iterator.next().done == true

# set.isNotEmpty()

Returns true if there is at least one element in the set.

May be computed by checking if iterator.next().done == false

# set.single()

Checks that the set has only one element, and returns that element.

Throws a StateError if the set is empty or has more than one element.

# set.first()

Returns the first element.

Throws a StateError if the set is empty. Otherwise returns the first element in the iteration order.

# set.last()

Returns the last element.

Throws a StateError if the set is empty. Otherwise may iterate through the elements and returns the last one seen.

# set.lastBefore(element)

Get the last element in the set that is strictly smaller than element. Returns null if no element was not found.

# set.firstAfter(element)

Get the first element in the set that is strictly larger than element. Returns null if no element was not found.

# set.retainAll(elements)

Removes all elements of the set that are not elements in elements.

Checks for each element of elements whether there is an element in thes set that is equal to it (according to set.has), and if so, the equal element in thes set is retained, and elements that are not equal to any element in elements are removed.

# set.lookup(object)

If an object equal to object is in the set, return it.

Checks whether object is in the set, like set.has, and if so, returns the object in the set, otherwise returns null.

If the equality relation used by the set is not identity, then the returned object may not be identical to object.

# set.intersection(other)

Returns a new set which is the intersection between thes set and other.

That is, the returned set contains all the elements of the set that are also elements of other according to set.has.

# set.difference(other)

Returns a new set with the elements of the set that are not in other.

That is, the returned set contains all the elements of the set that are not elements of other according to set.has.

# set.union(other)

Returns a new set which contains all the elements of the set and other.

That is, the returned set contains all the elements of the set and all the elements of other.

# set.toSet()

Creates a set containing the same elements as the set.

# set.keys()

Despite its name, returns an iterable of the values in the set.

Modifying the set while iterating the values breaks the iteration.

# set.values()

Returns an iterable of values in the set.

Modifying the set while iterating the values breaks the iteration.

# set.entries()

Returns an iterable of [v,v] pairs for every value v in the set.

Modifying the set while iterating the entries breaks the iteration.