description

# SplayTreeMap<K, V> class final

A Map of objects that can be ordered relative to each other.

The map is based on a self-balancing binary tree. It allows most single-entry operations in amortized logarithmic time.

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.containsKey(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 using their Comparable.compareTo method. Non-comparable objects (including `null`) will not work as keys in that case.

To allow calling operator [], remove or containsKey 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 a `K`.

Notice: Do not modify a map (add or remove keys) while an operation is being performed on that map, for example in functions called during a forEach or putIfAbsent call, or while iterating the map (keys, values or entries).

Example:

    final planetsByMass = SplayTreeMap<double, String>((a, b) => a.compareTo(b));

To add data to a map, use operator[]=, addAll or addEntries.

    planetsByMass[0.06] = 'Mercury';
    planetsByMass
        .addAll({0.81: 'Venus', 1.0: 'Earth', 0.11: 'Mars', 317.83: 'Jupiter'});

To check if the map is empty, use isEmpty or isNotEmpty. To find the number of map entries, use length.

    print(planetsByMass.isEmpty); // false
    print(planetsByMass.length); // 5

The forEach method calls a function for each key/value entry of the map.

    planetsByMass.forEach((key, value) {
      print('$key \t $value');
      // 0.06    Mercury
      // 0.11    Mars
      // 0.81    Venus
      // 1.0     Earth
      // 317.83  Jupiter
    });

To check whether the map has an entry with a specific key, use containsKey.

    final keyOneExists = planetsByMass.containsKey(1.0); // true
    final keyFiveExists = planetsByMass.containsKey(5); // false

To check whether the map has an entry with a specific value, use containsValue.

    final earthExists = planetsByMass.containsValue('Earth'); // true
    final plutoExists = planetsByMass.containsValue('Pluto'); // false

To remove an entry with a specific key, use remove.

    final removedValue = planetsByMass.remove(1.0);
    print(removedValue); // Earth

To remove multiple entries at the same time, based on their keys and values, use removeWhere.

    planetsByMass.removeWhere((key, value) => key <= 1);
    print(planetsByMass); // {317.83: Jupiter}

To conditionally add or modify a value for a specific key, depending on whether there already is an entry with that key, use putIfAbsent or update.

    planetsByMass.update(1, (v) => '', ifAbsent: () => 'Earth');
    planetsByMass.putIfAbsent(317.83, () => 'Another Jupiter');
    print(planetsByMass); // {1.0: Earth, 317.83: Jupiter}

To update the values of all keys, based on the existing key and value, use updateAll.

    planetsByMass.updateAll((key, value) => 'X');
    print(planetsByMass); // {1.0: X, 317.83: X}

To remove all entries and empty the map, use clear.

    planetsByMass.clear();
    print(planetsByMass.isEmpty); // false
    print(planetsByMass); // {}

See also:

- Map, the general interface of key/value pair collections.
- HashMap is unordered (the order of iteration is not guaranteed).
- LinkedHashMap iterates in key insertion order.

Mixed-in types
  - MapMixin<K, V>

## Constructors

SplayTreeMap([int compare(K key1, K key2)?, bool isValidKey(dynamic)?])
SplayTreeMap.from(Map<Object?, Object?> other, [int compare(K key1, K key2)?, bool isValidKey(dynamic)?])
  Creates a SplayTreeMap that contains all key/value pairs of `other`.
  factory
SplayTreeMap.fromIterable(Iterable iterable, {K key(dynamic element)?, V value(dynamic element)?, int compare(K key1, K key2)?, bool isValidKey(dynamic)?})
  Creates a SplayTreeMap where the keys and values are computed from the `iterable`.
  factory
SplayTreeMap.fromIterables(Iterable<K> keys, Iterable<V> values, [int compare(K key1, K key2)?, bool isValidKey(dynamic)?])
  Creates a SplayTreeMap associating the given `keys` to `values`.
  factory
SplayTreeMap.of(Map<K, V> other, [int compare(K key1, K key2)?, bool isValidKey(dynamic)?])
  Creates a SplayTreeMap that contains all key/value pairs of `other`. Example:
  factory

## Properties

entries → Iterable<MapEntry<K, V>>
  The map entries of this Map.
  no setteroverride
hashCode → int
  The hash code for this object.
  no setterinherited
isEmpty → bool
  Whether there is no key/value pair in the map.
  no setteroverride
isNotEmpty → bool
  Whether there is at least one key/value pair in the map.
  no setteroverride
keys → Iterable<K>
  The keys of this Map.
  no setteroverride
length → int
  The number of key/value pairs in the map.
  no setteroverride
runtimeType → Type
  A representation of the runtime type of the object.
  no setterinherited
values → Iterable<V>
  The values of this Map.
  no setteroverride

## Methods

addAll(Map<K, V> other) → void
  Adds all key/value pairs of `other` to this map.
  override
addEntries(Iterable<MapEntry<K, V>> newEntries) → void
  Adds all key/value pairs of `newEntries` to this map.
  inherited
cast<RK, RV>() → Map<RK, RV>
  Provides a view of this map as having `RK` keys and `RV` instances, if necessary.
  inherited
clear() → void
  Removes all entries from the map.
  override
containsKey(Object? key) → bool
  Whether this map contains the given `key`.
  override
containsValue(Object? value) → bool
  Whether this map contains the given `value`.
  override
firstKey() → K?
  The first key in the map.
firstKeyAfter(K key) → K?
  Get the first key in the map that is strictly larger than `key`. Returns `null` if such a key was not found.
forEach(void f(K key, V value)) → void
  Applies `action` to each key/value pair of the map.
  override
lastKey() → K?
  The last key in the map.
lastKeyBefore(K key) → K?
  The last key in the map that is strictly smaller than `key`.
map<K2, V2>(MapEntry<K2, V2> transform(K key, V value)) → Map<K2, V2>
  Returns a new map where all entries of this map are transformed by the given `convert` function.
  inherited
noSuchMethod(Invocation invocation) → dynamic
  Invoked when a nonexistent method or property is accessed.
  inherited
putIfAbsent(K key, V ifAbsent()) → V
  Look up the value of `key`, or add a new entry if it isn't there.
  override
remove(Object? key) → V?
  Removes `key` and its associated value, if present, from the map.
  override
removeWhere(bool test(K key, V value)) → void
  Removes all entries of this map that satisfy the given `test`.
  inherited
toString() → String
  A string representation of this object.
  inherited
update(K key, V update(V value), {V ifAbsent()?}) → V
  Updates the value for the provided `key`.
  override
updateAll(V update(K key, V value)) → void
  Updates all values.
  override

## Operators

operator ==(Object other) → bool
  The equality operator.
  inherited
operator [](Object? key) → V?
  The value for the given `key`, or `null` if `key` is not in the map.
  override
operator []=(K key, V value) → void
  Associates the `key` with the given `value`.
  override