SplayTreeMap<K, V> 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.

Constructors#

SplayTreeMap()#

SplayTreeMap([
  int Function(K key1, K key2)? compare,
  bool Function(dynamic potentialKey)? isValidKey,
]) : _compare = compare ?? _defaultCompare<K>(),
     _validKey = isValidKey;

SplayTreeMap.from() factory#

Creates a SplayTreeMap that contains all key/value pairs of other.

The keys must all be instances of K and the values of V. The other map itself can have any type. Example:

final baseMap = <int, Object>{3: 'C', 1: 'A', 2: 'B'};
final fromBaseMap = SplayTreeMap<int, String>.from(baseMap);
print(fromBaseMap); // {1: A, 2: B, 3: C}

factory SplayTreeMap.from(
  Map<Object?, Object?> other, [
  int Function(K key1, K key2)? compare,
  bool Function(dynamic potentialKey)? isValidKey,
]) {
  if (other is Map<K, V>) {
    return SplayTreeMap<K, V>.of(other, compare, isValidKey);
  }
  SplayTreeMap<K, V> result = SplayTreeMap<K, V>(compare, isValidKey);
  other.forEach((dynamic k, dynamic v) {
    result[k] = v;
  });
  return result;
}

SplayTreeMap.fromIterable() factory#

Creates a SplayTreeMap where the keys and values are computed from the iterable.

For each element of the iterable this constructor computes a key/value pair, by applying key and value respectively.

The keys of the key/value pairs do not need to be unique. The last occurrence of a key will simply overwrite any previous value.

If no functions are specified for key and value, the default is to use the iterable value itself. Example:

final numbers = [12, 11, 14, 13];
final mapFromIterable =
    SplayTreeMap<int, int>.fromIterable(numbers,
        key: (i) => i, value: (i) => i * i);
print(mapFromIterable); // {11: 121, 12: 144, 13: 169, 14: 196}

factory SplayTreeMap.fromIterable(
  Iterable iterable, {
  K Function(dynamic element)? key,
  V Function(dynamic element)? value,
  int Function(K key1, K key2)? compare,
  bool Function(dynamic potentialKey)? isValidKey,
}) {
  SplayTreeMap<K, V> map = SplayTreeMap<K, V>(compare, isValidKey);
  MapBase._fillMapWithMappedIterable(map, iterable, key, value);
  return map;
}

SplayTreeMap.fromIterables() factory#

Creates a SplayTreeMap associating the given keys to values.

This constructor iterates over keys and values and maps each element of keys to the corresponding element of values.

If keys contains the same object multiple times, the last occurrence overwrites the previous value.

It is an error if the two Iterables don't have the same length. Example:

final keys = ['1', '2', '3', '4'];
final values = ['A', 'B', 'C', 'D'];
final mapFromIterables = SplayTreeMap.fromIterables(keys, values);
print(mapFromIterables); // {1: A, 2: B, 3: C, 4: D}

factory SplayTreeMap.fromIterables(
  Iterable<K> keys,
  Iterable<V> values, [
  int Function(K key1, K key2)? compare,
  bool Function(dynamic potentialKey)? isValidKey,
]) {
  SplayTreeMap<K, V> map = SplayTreeMap<K, V>(compare, isValidKey);
  MapBase._fillMapWithIterables(map, keys, values);
  return map;
}

SplayTreeMap.of() factory#

Creates a SplayTreeMap that contains all key/value pairs of other. Example:

final baseMap = <int, String>{3: 'A', 2: 'B', 1: 'C', 4: 'D'};
final mapOf = SplayTreeMap<num, Object>.of(baseMap);
print(mapOf); // {1: C, 2: B, 3: A, 4: D}

factory SplayTreeMap.of(
  Map<K, V> other, [
  int Function(K key1, K key2)? compare,
  bool Function(dynamic potentialKey)? isValidKey,
]) => SplayTreeMap<K, V>(compare, isValidKey)..addAll(other);

Properties#

entries no setter override#

The map entries of this Map.

Iterable<MapEntry<K, V>> get entries =>
    _SplayTreeMapEntryIterable<K, V>(this);

hashCode no setter inherited#

The hash code for this object.

A hash code is a single integer which represents the state of the object that affects operator == comparisons.

All objects have hash codes. The default hash code implemented by Object represents only the identity of the object, the same way as the default operator == implementation only considers objects equal if they are identical (see identityHashCode).

If operator == is overridden to use the object state instead, the hash code must also be changed to represent that state, otherwise the object cannot be used in hash based data structures like the default Set and Map implementations.

Hash codes must be the same for objects that are equal to each other according to operator ==. The hash code of an object should only change if the object changes in a way that affects equality. There are no further requirements for the hash codes. They need not be consistent between executions of the same program and there are no distribution guarantees.

Objects that are not equal are allowed to have the same hash code. It is even technically allowed that all instances have the same hash code, but if clashes happen too often, it may reduce the efficiency of hash-based data structures like HashSet or HashMap.

If a subclass overrides hashCode, it should override the operator == operator as well to maintain consistency.

Inherited from Object.

external int get hashCode;

isEmpty no setter override#

Whether there is no key/value pair in the map.

bool get isEmpty {
  return (_root == null);
}

isNotEmpty no setter override#

Whether there is at least one key/value pair in the map.

bool get isNotEmpty => !isEmpty;

keys no setter override#

The keys of this Map.

The returned iterable has efficient length and contains operations, based on length and containsKey of the map.

The order of iteration is defined by the individual Map implementation, but must be consistent between changes to the map.

Modifying the map while iterating the keys may break the iteration.

Iterable<K> get keys =>
    _SplayTreeKeyIterable<K, _SplayTreeMapNode<K, V>>(this);

length no setter override#

The number of key/value pairs in the map.

int get length {
  return _count;
}

runtimeType no setter inherited#

A representation of the runtime type of the object.

Inherited from Object.

external Type get runtimeType;

values no setter override#

The values of this Map.

The values are iterated in the order of their corresponding keys. This means that iterating keys and values in parallel will provide matching pairs of keys and values.

The returned iterable has an efficient length method based on the length of the map. Its Iterable.contains method is based on == comparison.

Modifying the map while iterating the values may break the iteration.

Iterable<V> get values => _SplayTreeValueIterable<K, V>(this);

Methods#

addAll() override#

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

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

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

final planets = <int, String>{1: 'Mercury', 2: 'Earth'};
planets.addAll({5: 'Jupiter', 6: 'Saturn'});
print(planets); // {1: Mercury, 2: Earth, 5: Jupiter, 6: Saturn}

void addAll(Map<K, V> other) {
  other.forEach((K key, V value) {
    this[key] = value;
  });
}

addEntries() inherited#

Adds all key/value pairs of newEntries to this map.

If a key of newEntries is already in this map, the corresponding value is overwritten.

The operation is equivalent to doing this[entry.key] = entry.value for each MapEntry of the iterable.

final planets = <int, String>{1: 'Mercury', 2: 'Venus',
  3: 'Earth', 4: 'Mars'};
final gasGiants = <int, String>{5: 'Jupiter', 6: 'Saturn'};
final iceGiants = <int, String>{7: 'Uranus', 8: 'Neptune'};
planets.addEntries(gasGiants.entries);
planets.addEntries(iceGiants.entries);
print(planets);
// {1: Mercury, 2: Venus, 3: Earth, 4: Mars, 5: Jupiter, 6: Saturn,
//  7: Uranus, 8: Neptune}

Inherited from MapBase.

void addEntries(Iterable<MapEntry<K, V>> newEntries) {
  for (var entry in newEntries) {
    this[entry.key] = entry.value;
  }
}

cast() inherited#

Provides a view of this map as having RK keys and RV instances, if necessary.

If this map is already a Map<RK, RV>, it is returned unchanged.

If this set contains only keys of type RK and values of type RV, all read operations will work correctly. If any operation exposes a non-RK key or non-RV value, the operation will throw instead.

Entries added to the map must be valid for both a Map<K, V> and a Map<RK, RV>.

Methods which accept Object? as argument, like containsKey, remove and operator [], will pass the argument directly to the this map's method without any checks. That means that you can do mapWithStringKeys.cast<int,int>().remove("a") successfully, even if it looks like it shouldn't have any effect.

Inherited from MapBase.

Map<RK, RV> cast<RK, RV>() => Map.castFrom<K, V, RK, RV>(this);

clear() override#

Removes all entries from the map.

After this, the map is empty.

final planets = <int, String>{1: 'Mercury', 2: 'Venus', 3: 'Earth'};
planets.clear(); // {}

void clear() {
  _clear();
}

containsKey() override#

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

final moonCount = <String, int>{'Mercury': 0, 'Venus': 0, 'Earth': 1,
  'Mars': 2, 'Jupiter': 79, 'Saturn': 82, 'Uranus': 27, 'Neptune': 14};
final containsUranus = moonCount.containsKey('Uranus'); // true
final containsPluto = moonCount.containsKey('Pluto'); // false

bool containsKey(Object? key) => _untypedLookup(key) != null;

containsValue() override#

Whether this map contains the given value.

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

final moonCount = <String, int>{'Mercury': 0, 'Venus': 0, 'Earth': 1,
  'Mars': 2, 'Jupiter': 79, 'Saturn': 82, 'Uranus': 27, 'Neptune': 14};
final moons3 = moonCount.containsValue(3); // false
final moons82 = moonCount.containsValue(82); // true

bool containsValue(Object? value) {
  int initialSplayCount = _splayCount;
  bool visit(_SplayTreeMapNode<K, V>? node) {
    while (node != null) {
      if (node.value == value) return true;
      if (initialSplayCount != _splayCount) {
        throw ConcurrentModificationError(this);
      }
      if (node._right != null && visit(node._right)) {
        return true;
      }
      node = node._left;
    }
    return false;
  }

  return visit(_root);
}

firstKey()#

The first key in the map.

Returns null if the map is empty.

K? firstKey() {
  final root = _root;
  if (root == null) return null;
  return (_root = _splayMin(root)).key;
}

firstKeyAfter()#

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

K? firstKeyAfter(K key) {
  if (key == null) throw ArgumentError(key);
  if (_root == null) return null;
  int comparison = _splay(key);
  if (comparison > 0) return _root!.key;
  _SplayTreeMapNode<K, V>? node = _root!._right;
  if (node == null) return null;
  var nodeLeft = node._left;
  while (nodeLeft != null) {
    node = nodeLeft;
    nodeLeft = node._left;
  }
  return node!.key;
}

forEach() override#

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

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

final planetsByMass = <num, String>{0.81: 'Venus', 1: 'Earth',
  0.11: 'Mars', 17.15: 'Neptune'};

planetsByMass.forEach((key, value) {
  print('$key: $value');
  // 0.81: Venus
  // 1: Earth
  // 0.11: Mars
  // 17.15: Neptune
});

void forEach(void f(K key, V value)) {
  Iterator<MapEntry<K, V>> nodes = _SplayTreeMapEntryIterator<K, V>(this);
  while (nodes.moveNext()) {
    MapEntry<K, V> node = nodes.current;
    f(node.key, node.value);
  }
}

lastKey()#

The last key in the map.

Returns null if the map is empty.

K? lastKey() {
  final root = _root;
  if (root == null) return null;
  return (_root = _splayMax(root)).key;
}

lastKeyBefore()#

The last key in the map that is strictly smaller than key.

Returns null if such a key was not found.

K? lastKeyBefore(K key) {
  if (key == null) throw ArgumentError(key);
  if (_root == null) return null;
  int comparison = _splay(key);
  if (comparison < 0) return _root!.key;
  _SplayTreeMapNode<K, V>? node = _root!._left;
  if (node == null) return null;
  var nodeRight = node._right;
  while (nodeRight != null) {
    node = nodeRight;
    nodeRight = node._right;
  }
  return node!.key;
}

map() inherited#

Returns a new map where all entries of this map are transformed by the given convert function.

Inherited from MapBase.

Map<K2, V2> map<K2, V2>(MapEntry<K2, V2> transform(K key, V value)) {
  var result = <K2, V2>{};
  for (var key in this.keys) {
    var entry = transform(key, this[key] as V);
    result[entry.key] = entry.value;
  }
  return result;
}

noSuchMethod() inherited#

Invoked when a nonexistent method or property is accessed.

A dynamic member invocation can attempt to call a member which doesn't exist on the receiving object. Example:

dynamic object = 1;
object.add(42); // Statically allowed, run-time error

This invalid code will invoke the noSuchMethod method of the integer 1 with an Invocation representing the .add(42) call and arguments (which then throws).

Classes can override noSuchMethod to provide custom behavior for such invalid dynamic invocations.

A class with a non-default noSuchMethod invocation can also omit implementations for members of its interface. Example:

class MockList<T> implements List<T> {
  noSuchMethod(Invocation invocation) {
    log(invocation);
    super.noSuchMethod(invocation); // Will throw.
  }
}
void main() {
  MockList().add(42);
}

This code has no compile-time warnings or errors even though the MockList class has no concrete implementation of any of the List interface methods. Calls to List methods are forwarded to noSuchMethod, so this code will log an invocation similar to Invocation.method(#add, [42]) and then throw.

If a value is returned from noSuchMethod, it becomes the result of the original invocation. If the value is not of a type that can be returned by the original invocation, a type error occurs at the invocation.

The default behavior is to throw a NoSuchMethodError.

Inherited from Object.

@pragma("vm:entry-point")
@pragma("wasm:entry-point")
external dynamic noSuchMethod(Invocation invocation);

putIfAbsent() override#

Look up the value of key, or add a new entry 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.

That is, if the key is currently in the map, map.putIfAbsent(key, ifAbsent) is equivalent to map[key]. If the key is not currently in the map, it's instead equivalent to map[key] = ifAbsent() (but without any guarantee that the [] and []= operators are actually called to achieve that effect).

final diameters = <num, String>{1.0: 'Earth'};
final otherDiameters = <double, String>{0.383: 'Mercury', 0.949: 'Venus'};

for (final item in otherDiameters.entries) {
  diameters.putIfAbsent(item.key, () => item.value);
}
print(diameters); // {1.0: Earth, 0.383: Mercury, 0.949: Venus}

// If the key already exists, the current value is returned.
final result = diameters.putIfAbsent(0.383, () => 'Random');
print(result); // Mercury
print(diameters); // {1.0: Earth, 0.383: Mercury, 0.949: Venus}

The ifAbsent function is allowed to modify the map, and if so, it behaves the same as the equivalent map[key] = ifAbsent().

V putIfAbsent(K key, V ifAbsent()) {
  int comparison = _splay(key);
  if (comparison == 0) {
    return _root!.value;
  }
  int originalModificationCount = _modificationCount;
  int originalSplayCount = _splayCount;
  V value = ifAbsent();
  if (originalModificationCount != _modificationCount ||
      originalSplayCount != _splayCount) {
    comparison = _splay(key);
    if (comparison == 0) {
      // Key was added by `ifAbsent`, change value.
      _root!.value = value;
      return value;
    }
    // Key is still not there.
  }
  _addNewRoot(_SplayTreeMapNode(key, value), comparison);
  return value;
}

remove() override#

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

Returns the value associated with key before it was removed. Returns null if key was not in the map.

Note that some maps allow null as a value, so a returned null value doesn't always mean that the key was absent.

final terrestrial = <int, String>{1: 'Mercury', 2: 'Venus', 3: 'Earth'};
final removedValue = terrestrial.remove(2); // Venus
print(terrestrial); // {1: Mercury, 3: Earth}

V? remove(Object? key) {
  final root = _untypedLookup(key);
  if (root == null) return null;
  _removeRoot();
  return root.value;
}

removeWhere() inherited#

Removes all entries of this map that satisfy the given test.

final terrestrial = <int, String>{1: 'Mercury', 2: 'Venus', 3: 'Earth'};
terrestrial.removeWhere((key, value) => value.startsWith('E'));
print(terrestrial); // {1: Mercury, 2: Venus}

Inherited from MapBase.

void removeWhere(bool test(K key, V value)) {
  var keysToRemove = <K>[];
  for (var key in keys) {
    if (test(key, this[key] as V)) keysToRemove.add(key);
  }
  for (var key in keysToRemove) {
    this.remove(key);
  }
}

toString() inherited#

A string representation of this object.

Some classes have a default textual representation, often paired with a static parse function (like int.parse). These classes will provide the textual representation as their string representation.

Other classes have no meaningful textual representation that a program will care about. Such classes will typically override toString to provide useful information when inspecting the object, mainly for debugging or logging.

Inherited from MapBase.

String toString() => mapToString(this);

update() override#

Updates the value for the provided key.

Returns the new value associated with 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.

If the key is not present, ifAbsent must be provided.

final planetsFromSun = <int, String>{1: 'Mercury', 2: 'unknown',
  3: 'Earth'};
// Update value for known key value 2.
planetsFromSun.update(2, (value) => 'Venus');
print(planetsFromSun); // {1: Mercury, 2: Venus, 3: Earth}

final largestPlanets = <int, String>{1: 'Jupiter', 2: 'Saturn',
  3: 'Neptune'};
// Key value 8 is missing from list, add it using [ifAbsent].
largestPlanets.update(8, (value) => 'New', ifAbsent: () => 'Mercury');
print(largestPlanets); // {1: Jupiter, 2: Saturn, 3: Neptune, 8: Mercury}

V update(K key, V update(V value), {V Function()? ifAbsent}) {
  var comparison = _splay(key);
  if (comparison == 0) {
    final originalModificationCount = _modificationCount;
    final originalSplayCount = _splayCount;
    var newValue = update(_root!.value);
    if (originalModificationCount != _modificationCount) {
      throw ConcurrentModificationError(this);
    }
    if (originalSplayCount != _splayCount) {
      comparison = _splay(key);
      // Can only fail to find the same key in a tree with the same
      // modification count if a key has changed its comparison since
      // it was added to the tree (which means the tree might no be
      // well-ordered, so much can go wrong).
      if (comparison != 0) throw ConcurrentModificationError(this);
    }
    _root!.value = newValue;
    return newValue;
  }
  if (ifAbsent != null) {
    final originalModificationCount = _modificationCount;
    final originalSplayCount = _splayCount;
    var newValue = ifAbsent();
    if (originalModificationCount != _modificationCount) {
      throw ConcurrentModificationError(this);
    }
    if (originalSplayCount != _splayCount) {
      comparison = _splay(key);
      // Can only happen if a key changed its comparison since being
      // added to the tree.
      if (comparison == 0) throw ConcurrentModificationError(this);
    }
    _addNewRoot(_SplayTreeMapNode(key, newValue), comparison);
    return newValue;
  }
  throw ArgumentError.value(key, "key", "Key not in map.");
}

updateAll() override#

Updates all values.

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

final terrestrial = <int, String>{1: 'Mercury', 2: 'Venus', 3: 'Earth'};
terrestrial.updateAll((key, value) => value.toUpperCase());
print(terrestrial); // {1: MERCURY, 2: VENUS, 3: EARTH}

void updateAll(V update(K key, V value)) {
  var root = _root;
  if (root == null) return;
  var iterator = _SplayTreeMapEntryIterator(this);
  while (iterator.moveNext()) {
    var node = iterator.current;
    var newValue = update(node.key, node.value);
    iterator._replaceValue(newValue);
  }
}

Operators#

operator ==() inherited#

The equality operator.

The default behavior for all Objects is to return true if and only if this object and other are the same object.

Override this method to specify a different equality relation on a class. The overriding method must still be an equivalence relation. That is, it must be:

• Total: It must return a boolean for all arguments. It should never throw.

• Reflexive: For all objects o, o == o must be true.

• Symmetric: For all objects o1 and o2, o1 == o2 and o2 == o1 must either both be true, or both be false.

• Transitive: For all objects o1, o2, and o3, if o1 == o2 and o2 == o3 are true, then o1 == o3 must be true.

The method should also be consistent over time, so whether two objects are equal should only change if at least one of the objects was modified.

If a subclass overrides the equality operator, it should override the hashCode method as well to maintain consistency.

Inherited from Object.

external bool operator ==(Object other);

operator []() override#

The value for the given key, or null if key is not in the map.

Some maps allow null as a value. For those maps, a lookup using this operator cannot distinguish between a key not being in the map, and the key being there with a null value. Methods like containsKey or putIfAbsent can be used if the distinction is important.

V? operator [](Object? key) => _untypedLookup(key)?.value;

operator []=() override#

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.

void operator []=(K key, V value) {
  // Splay on the key to move the last node on the search path for
  // the key to the root of the tree.
  int comparison = _splay(key);
  if (comparison == 0) {
    _root!.value = value;
    return;
  }
  _addNewRoot(_SplayTreeMapNode(key, value), comparison);
}