blob: 1ab21dbc4d31b3cdd05d5aaa4f88729777040264 [file] [log] [blame]
// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
part of dart.collection;
typedef _Predicate<T> = bool Function(T value);
/// A node in a splay tree. It holds the sorting key and the left
/// and right children in the tree.
class _SplayTreeNode<K, Node extends _SplayTreeNode<K, Node>> {
final K key;
Node? _left;
Node? _right;
_SplayTreeNode(this.key);
}
/// A node in a splay tree based set.
class _SplayTreeSetNode<K> extends _SplayTreeNode<K, _SplayTreeSetNode<K>> {
_SplayTreeSetNode(K key) : super(key);
}
/// A node in a splay tree based map.
///
/// A [_SplayTreeNode] that also contains a value,
/// and which implements [MapEntry].
class _SplayTreeMapNode<K, V> extends _SplayTreeNode<K, _SplayTreeMapNode<K, V>>
implements MapEntry<K, V> {
final V value;
_SplayTreeMapNode(K key, this.value) : super(key);
_SplayTreeMapNode<K, V> _replaceValue(V value) =>
_SplayTreeMapNode<K, V>(key, value)
.._left = _left
.._right = _right;
String toString() => "MapEntry($key: $value)";
}
/// A splay tree is a self-balancing binary search tree.
///
/// 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.
abstract class _SplayTree<K, Node extends _SplayTreeNode<K, Node>> {
// The root node of the splay tree. It will contain either the last
// element inserted or the last element looked up.
Node? get _root;
set _root(Node? newValue);
// Number of elements in the splay tree.
int _count = 0;
/// Counter incremented whenever the keys in the map change.
///
/// Used to detect concurrent modifications.
int _modificationCount = 0;
/// Counter incremented whenever the tree structure changes.
///
/// Used to detect that an in-place traversal cannot use
/// cached information that relies on the tree structure.
int _splayCount = 0;
/// The comparator that is used for this splay tree.
Comparator<K> get _compare;
/// The predicate to determine that a given object is a valid key.
_Predicate get _validKey;
/// Perform the splay operation for the given key. Moves the node with
/// the given key to the top of the tree. If no node has the given
/// key, the last node on the search path is moved to the top of the
/// tree. This is the simplified top-down splaying algorithm from:
/// "Self-adjusting Binary Search Trees" by Sleator and Tarjan.
///
/// Returns the result of comparing the new root of the tree to [key].
/// Returns -1 if the table is empty.
int _splay(K key) {
var root = _root;
if (root == null) {
// Ensure key is compatible with `_compare`.
_compare(key, key);
return -1;
}
// The right and newTreeRight variables start out null, and are set
// after the first move left. The right node is the destination
// for subsequent left rebalances, and newTreeRight holds the left
// child of the final tree. The newTreeRight variable is set at most
// once, after the first move left, and is null iff right is null.
// The left and newTreeLeft variables play the corresponding role for
// right rebalances.
Node? right;
Node? newTreeRight;
Node? left;
Node? newTreeLeft;
var current = root;
// Hoist the field read out of the loop.
var compare = _compare;
int comp;
while (true) {
comp = compare(current.key, key);
if (comp > 0) {
var currentLeft = current._left;
if (currentLeft == null) break;
comp = compare(currentLeft.key, key);
if (comp > 0) {
// Rotate right.
current._left = currentLeft._right;
currentLeft._right = current;
current = currentLeft;
currentLeft = current._left;
if (currentLeft == null) break;
}
// Link right.
if (right == null) {
// First left rebalance, store the eventual right child
newTreeRight = current;
} else {
right._left = current;
}
right = current;
current = currentLeft;
} else if (comp < 0) {
var currentRight = current._right;
if (currentRight == null) break;
comp = compare(currentRight.key, key);
if (comp < 0) {
// Rotate left.
current._right = currentRight._left;
currentRight._left = current;
current = currentRight;
currentRight = current._right;
if (currentRight == null) break;
}
// Link left.
if (left == null) {
// First right rebalance, store the eventual left child
newTreeLeft = current;
} else {
left._right = current;
}
left = current;
current = currentRight;
} else {
break;
}
}
// Assemble.
if (left != null) {
left._right = current._left;
current._left = newTreeLeft;
}
if (right != null) {
right._left = current._right;
current._right = newTreeRight;
}
if (!identical(_root, current)) {
_root = current;
_splayCount++;
}
return comp;
}
// Emulates splaying with a key that is smaller than any in the subtree
// anchored at [node].
// and that node is returned. It should replace the reference to [node]
// in any parent tree or root pointer.
Node _splayMin(Node node) {
var current = node;
var nextLeft = current._left;
while (nextLeft != null) {
var left = nextLeft;
current._left = left._right;
left._right = current;
current = left;
nextLeft = current._left;
}
return current;
}
// Emulates splaying with a key that is greater than any in the subtree
// anchored at [node].
// After this, the largest element in the tree is the root of the subtree,
// and that node is returned. It should replace the reference to [node]
// in any parent tree or root pointer.
Node _splayMax(Node node) {
var current = node;
var nextRight = current._right;
while (nextRight != null) {
var right = nextRight;
current._right = right._left;
right._left = current;
current = right;
nextRight = current._right;
}
return current;
}
Node? _remove(K key) {
if (_root == null) return null;
int comp = _splay(key);
if (comp != 0) return null;
var root = _root!;
var result = root;
var left = root._left;
_count--;
// assert(_count >= 0);
if (left == null) {
_root = root._right;
} else {
var right = root._right;
// Splay to make sure that the new root has an empty right child.
root = _splayMax(left);
// Insert the original right child as the right child of the new
// root.
root._right = right;
_root = root;
}
_modificationCount++;
return result;
}
/// Adds a new root node with the given [key] or [value].
///
/// The [comp] value is the result of comparing the existing root's key
/// with key.
void _addNewRoot(Node node, int comp) {
_count++;
_modificationCount++;
var root = _root;
if (root == null) {
_root = node;
return;
}
// assert(_count >= 0);
if (comp < 0) {
node._left = root;
node._right = root._right;
root._right = null;
} else {
node._right = root;
node._left = root._left;
root._left = null;
}
_root = node;
}
Node? get _first {
var root = _root;
if (root == null) return null;
_root = _splayMin(root);
return _root;
}
Node? get _last {
var root = _root;
if (root == null) return null;
_root = _splayMax(root);
return _root;
}
void _clear() {
_root = null;
_count = 0;
_modificationCount++;
}
bool _containsKey(Object? key) {
return _validKey(key) && _splay(key as dynamic) == 0;
}
}
int _dynamicCompare(dynamic a, dynamic b) => Comparable.compare(a, b);
Comparator<K> _defaultCompare<K>() {
// If K <: Comparable, then we can just use Comparable.compare
// with no casts.
Object compare = Comparable.compare;
if (compare is Comparator<K>) {
return compare;
}
// Otherwise wrap and cast the arguments on each call.
return _dynamicCompare;
}
/// 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:
/// ```dart
/// 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.
class SplayTreeMap<K, V> extends _SplayTree<K, _SplayTreeMapNode<K, V>>
with MapMixin<K, V> {
_SplayTreeMapNode<K, V>? _root;
Comparator<K> _compare;
_Predicate _validKey;
SplayTreeMap(
[int Function(K key1, K key2)? compare,
bool Function(dynamic potentialKey)? isValidKey])
: _compare = compare ?? _defaultCompare<K>(),
_validKey = isValidKey ?? ((dynamic a) => a is K);
/// 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:
/// ```dart
/// 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<dynamic, dynamic> 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;
}
/// Creates a [SplayTreeMap] that contains all key/value pairs of [other].
/// Example:
/// ```dart
/// 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);
/// 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:
/// ```dart
/// 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;
}
/// 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 [Iterable]s don't have the same length.
/// Example:
/// ```dart
/// 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;
}
V? operator [](Object? key) {
if (!_validKey(key)) return null;
if (_root != null) {
int comp = _splay(key as dynamic);
if (comp == 0) {
return _root!.value;
}
}
return null;
}
V? remove(Object? key) {
if (!_validKey(key)) return null;
_SplayTreeMapNode<K, V>? mapRoot = _remove(key as dynamic);
if (mapRoot != null) return mapRoot.value;
return null;
}
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 comp = _splay(key);
if (comp == 0) {
_root = _root!._replaceValue(value);
// To represent structure change, in case someone caches the old node.
_splayCount += 1;
return;
}
_addNewRoot(_SplayTreeMapNode(key, value), comp);
}
V putIfAbsent(K key, V ifAbsent()) {
int comp = _splay(key);
if (comp == 0) {
return _root!.value;
}
int modificationCount = _modificationCount;
int splayCount = _splayCount;
V value = ifAbsent();
if (modificationCount != _modificationCount) {
throw ConcurrentModificationError(this);
}
if (splayCount != _splayCount) {
comp = _splay(key);
// Key is still not there, otherwise _modificationCount would be changed.
assert(comp != 0);
}
_addNewRoot(_SplayTreeMapNode(key, value), comp);
return value;
}
V update(K key, V update(V value), {V Function()? ifAbsent}) {
var comp = _splay(key);
if (comp == 0) {
var modificationCount = _modificationCount;
var splayCount = _splayCount;
var newValue = update(_root!.value);
if (modificationCount != _modificationCount) {
throw ConcurrentModificationError(this);
}
if (splayCount != _splayCount) {
_splay(key);
}
_root = _root!._replaceValue(newValue);
_splayCount += 1;
return newValue;
}
if (ifAbsent != null) {
var modificationCount = _modificationCount;
var splayCount = _splayCount;
var newValue = ifAbsent();
if (modificationCount != _modificationCount) {
throw ConcurrentModificationError(this);
}
if (splayCount != _splayCount) {
comp = _splay(key);
}
_addNewRoot(_SplayTreeMapNode(key, newValue), comp);
return newValue;
}
throw ArgumentError.value(key, "key", "Key not in map.");
}
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);
}
}
void addAll(Map<K, V> other) {
other.forEach((K key, V value) {
this[key] = value;
});
}
bool get isEmpty {
return (_root == null);
}
bool get isNotEmpty => !isEmpty;
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);
}
}
int get length {
return _count;
}
void clear() {
_clear();
}
bool containsKey(Object? key) => _containsKey(key);
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);
}
Iterable<K> get keys =>
_SplayTreeKeyIterable<K, _SplayTreeMapNode<K, V>>(this);
Iterable<V> get values => _SplayTreeValueIterable<K, V>(this);
Iterable<MapEntry<K, V>> get entries =>
_SplayTreeMapEntryIterable<K, V>(this);
/// The first key in the map.
///
/// Returns `null` if the map is empty.
K? firstKey() {
if (_root == null) return null;
return _first!.key;
}
/// The last key in the map.
///
/// Returns `null` if the map is empty.
K? lastKey() {
if (_root == null) return null;
return _last!.key;
}
/// The last key in the map that is strictly smaller than [key].
///
/// Returns `null` if no key was not found.
K? lastKeyBefore(K key) {
if (key == null) throw ArgumentError(key);
if (_root == null) return null;
int comp = _splay(key);
if (comp < 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;
}
/// Get the first key in the map that is strictly larger than [key]. Returns
/// `null` if no key was not found.
K? firstKeyAfter(K key) {
if (key == null) throw ArgumentError(key);
if (_root == null) return null;
int comp = _splay(key);
if (comp > 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;
}
}
abstract class _SplayTreeIterator<K, Node extends _SplayTreeNode<K, Node>, T>
implements Iterator<T> {
final _SplayTree<K, Node> _tree;
/// The current node, and all its ancestors in the tree.
///
/// Only valid as long as the original tree isn't reordered.
final List<Node> _path = [];
/// Original modification counter of [_tree].
///
/// Incremented on [_tree] when a key is added or removed.
/// If it changes, iteration is aborted.
///
/// Not final because some iterators may modify the tree knowingly,
/// and they update the modification count in that case.
///
/// Starts at `null` to represent a fresh, unstarted iterator.
int? _modificationCount;
/// Count of splay operations on [_tree] when [_path] was built.
///
/// If the splay count on [_tree] increases, [_path] becomes invalid.
int _splayCount;
_SplayTreeIterator(_SplayTree<K, Node> tree)
: _tree = tree,
_splayCount = tree._splayCount;
T get current {
if (_path.isEmpty) return null as T;
var node = _path.last;
return _getValue(node);
}
/// Called when the tree structure of the tree has changed.
///
/// This can be caused by a splay operation.
/// If the key-set changes, iteration is aborted before getting
/// here, so we know that the keys are the same as before, it's
/// only the tree that has been reordered.
void _rebuildPath(K key) {
_path.clear();
_tree._splay(key);
_path.add(_tree._root!);
_splayCount = _tree._splayCount;
}
void _findLeftMostDescendent(Node? node) {
while (node != null) {
_path.add(node);
node = node._left;
}
}
bool moveNext() {
if (_modificationCount != _tree._modificationCount) {
if (_modificationCount == null) {
_modificationCount = _tree._modificationCount;
var node = _tree._root;
while (node != null) {
_path.add(node);
node = node._left;
}
return _path.isNotEmpty;
}
throw ConcurrentModificationError(_tree);
}
if (_path.isEmpty) return false;
if (_splayCount != _tree._splayCount) {
_rebuildPath(_path.last.key);
}
var node = _path.last;
var next = node._right;
if (next != null) {
while (next != null) {
_path.add(next);
next = next._left;
}
return true;
}
_path.removeLast();
while (_path.isNotEmpty && identical(_path.last._right, node)) {
node = _path.removeLast();
}
return _path.isNotEmpty;
}
T _getValue(Node node);
}
class _SplayTreeKeyIterable<K, Node extends _SplayTreeNode<K, Node>>
extends EfficientLengthIterable<K> {
_SplayTree<K, Node> _tree;
_SplayTreeKeyIterable(this._tree);
int get length => _tree._count;
bool get isEmpty => _tree._count == 0;
Iterator<K> get iterator => _SplayTreeKeyIterator<K, Node>(_tree);
bool contains(Object? o) => _tree._containsKey(o);
Set<K> toSet() {
SplayTreeSet<K> set = SplayTreeSet<K>(_tree._compare, _tree._validKey);
set._count = _tree._count;
set._root = set._copyNode<Node>(_tree._root);
return set;
}
}
class _SplayTreeValueIterable<K, V> extends EfficientLengthIterable<V> {
SplayTreeMap<K, V> _map;
_SplayTreeValueIterable(this._map);
int get length => _map._count;
bool get isEmpty => _map._count == 0;
Iterator<V> get iterator => _SplayTreeValueIterator<K, V>(_map);
}
class _SplayTreeMapEntryIterable<K, V>
extends EfficientLengthIterable<MapEntry<K, V>> {
SplayTreeMap<K, V> _map;
_SplayTreeMapEntryIterable(this._map);
int get length => _map._count;
bool get isEmpty => _map._count == 0;
Iterator<MapEntry<K, V>> get iterator =>
_SplayTreeMapEntryIterator<K, V>(_map);
}
class _SplayTreeKeyIterator<K, Node extends _SplayTreeNode<K, Node>>
extends _SplayTreeIterator<K, Node, K> {
_SplayTreeKeyIterator(_SplayTree<K, Node> map) : super(map);
K _getValue(Node node) => node.key;
}
class _SplayTreeValueIterator<K, V>
extends _SplayTreeIterator<K, _SplayTreeMapNode<K, V>, V> {
_SplayTreeValueIterator(SplayTreeMap<K, V> map) : super(map);
V _getValue(_SplayTreeMapNode<K, V> node) => node.value;
}
class _SplayTreeMapEntryIterator<K, V>
extends _SplayTreeIterator<K, _SplayTreeMapNode<K, V>, MapEntry<K, V>> {
_SplayTreeMapEntryIterator(SplayTreeMap<K, V> tree) : super(tree);
MapEntry<K, V> _getValue(_SplayTreeMapNode<K, V> node) => node;
// Replaces the value of the current node.
void _replaceValue(V value) {
assert(_path.isNotEmpty);
if (_modificationCount != _tree._modificationCount) {
throw ConcurrentModificationError(_tree);
}
if (_splayCount != _tree._splayCount) {
_rebuildPath(_path.last.key);
}
var last = _path.removeLast();
var newLast = last._replaceValue(value);
if (_path.isEmpty) {
_tree._root = newLast;
} else {
var parent = _path.last;
if (identical(last, parent._left)) {
parent._left = newLast;
} else {
assert(identical(last, parent._right));
parent._right = newLast;
}
}
_path.add(newLast);
_splayCount = ++_tree._splayCount;
}
}
/// A [Set] of objects that can be ordered relative to each other.
///
/// The set is based on a self-balancing binary tree. It allows most operations
/// in amortized logarithmic time.
///
/// 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.contains(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 an element
/// in that case.
///
/// **Note:**
/// Do not modify a set (add or remove elements) while an operation
/// is being performed on that set, for example in functions
/// called during a [forEach] or [containsAll] call,
/// or while iterating the set.
///
/// Do not modify elements in a way which changes their equality (and thus their
/// hash code) while they are in the set. Some specialized kinds of sets may be
/// more permissive with regards to equality, in which case they should document
/// their different behavior and restrictions.
///
/// Example:
/// ```dart
/// final planets = SplayTreeSet<String>((a, b) => a.compareTo(b));
/// ```
/// To add data to a set, use [add] or [addAll].
/// ```
/// planets.add('Neptune');
/// planets.addAll({'Venus', 'Mars', 'Earth', 'Jupiter'});
/// print(planets); // {Earth, Jupiter, Mars, Neptune, Venus}
/// ```
/// To check if the set is empty, use [isEmpty] or [isNotEmpty].
/// To find the number of elements in the set, use [length].
/// ```
/// final isEmpty = planets.isEmpty; // false
/// final length = planets.length; // 5
/// ```
/// To check whether the set contains a specific element, use [contains].
/// ```
/// final marsExists = planets.contains('Mars'); // true
/// ```
/// To get element value using index, use [elementAt].
/// ```
/// final elementAt = planets.elementAt(1);
/// print(elementAt); // Jupiter
/// ```
/// To make a copy of set, use [toSet].
/// ```
/// final copySet = planets.toSet(); // a `SplayTreeSet` with the same ordering.
/// print(copySet); // {Earth, Jupiter, Mars, Neptune, Venus}
/// ```
/// To remove an element, use [remove].
/// ```
/// final removedValue = planets.remove('Mars'); // true
/// print(planets); // {Earth, Jupiter, Neptune, Venus}
/// ```
/// To remove multiple elements at the same time, use [removeWhere].
/// ```
/// planets.removeWhere((element) => element.startsWith('J'));
/// print(planets); // {Earth, Neptune, Venus}
/// ```
/// To removes all elements in this set that do not meet a condition,
/// use [retainWhere].
/// ```
/// planets.retainWhere((element) => element.contains('Earth'));
/// print(planets); // {Earth}
/// ```
/// To remove all elements and empty the set, use [clear].
/// ```
/// planets.clear();
/// print(planets.isEmpty); // true
/// print(planets); // {}
/// ```
/// **See also:**
/// * [Set] is a base-class for collection of objects.
/// * [HashSet] the order of the objects in the iterations is not guaranteed.
/// * [LinkedHashSet] objects stored based on insertion order.
class SplayTreeSet<E> extends _SplayTree<E, _SplayTreeSetNode<E>>
with IterableMixin<E>, SetMixin<E> {
_SplayTreeSetNode<E>? _root;
Comparator<E> _compare;
_Predicate _validKey;
/// Create a new [SplayTreeSet] with the given compare function.
///
/// If the [compare] function is omitted, it defaults to [Comparable.compare],
/// and the elements must be comparable.
///
/// A provided `compare` function may not work on all objects. It may not even
/// work on all `E` instances.
///
/// For operations that add elements to the set, the user is supposed to not
/// pass in objects that don't work with the compare function.
///
/// The methods [contains], [remove], [lookup], [removeAll] or [retainAll]
/// are typed to accept any object(s), and the [isValidKey] test can used to
/// filter those objects before handing them to the `compare` function.
///
/// If [isValidKey] is provided, only values satisfying `isValidKey(other)`
/// are compared using the `compare` method in the methods mentioned above.
/// If the `isValidKey` function returns false for an object, it is assumed to
/// not be in the set.
///
/// If omitted, the `isValidKey` function defaults to checking against the
/// type parameter: `other is E`.
SplayTreeSet(
[int Function(E key1, E key2)? compare,
bool Function(dynamic potentialKey)? isValidKey])
: _compare = compare ?? _defaultCompare<E>(),
_validKey = isValidKey ?? ((dynamic v) => v is E);
/// Creates a [SplayTreeSet] that contains all [elements].
///
/// The set works as if created by `SplayTreeSet<E>(compare, isValidKey)`.
///
/// All the [elements] should be instances of [E] and valid arguments to
/// [compare].
/// The `elements` iterable itself may have any element type, so this
/// constructor can be used to down-cast a `Set`, for example as:
/// ```dart
/// Set<SuperType> superSet = ...;
/// Set<SubType> subSet =
/// SplayTreeSet<SubType>.from(superSet.whereType<SubType>());
/// ```
/// Example:
/// ```dart
/// final numbers = <num>[20, 30, 10];
/// final setFrom = SplayTreeSet<int>.from(numbers);
/// print(setFrom); // {10, 20, 30}
/// ```
factory SplayTreeSet.from(Iterable elements,
[int Function(E key1, E key2)? compare,
bool Function(dynamic potentialKey)? isValidKey]) {
if (elements is Iterable<E>) {
return SplayTreeSet<E>.of(elements, compare, isValidKey);
}
SplayTreeSet<E> result = SplayTreeSet<E>(compare, isValidKey);
for (var element in elements) {
result.add(element as dynamic);
}
return result;
}
/// Creates a [SplayTreeSet] from [elements].
///
/// The set works as if created by `new SplayTreeSet<E>(compare, isValidKey)`.
///
/// All the [elements] should be valid as arguments to the [compare] function.
/// Example:
/// ```dart
/// final baseSet = <int>{1, 2, 3};
/// final setOf = SplayTreeSet<num>.of(baseSet);
/// print(setOf); // {1, 2, 3}
/// ```
factory SplayTreeSet.of(Iterable<E> elements,
[int Function(E key1, E key2)? compare,
bool Function(dynamic potentialKey)? isValidKey]) =>
SplayTreeSet(compare, isValidKey)..addAll(elements);
Set<T> _newSet<T>() =>
SplayTreeSet<T>((T a, T b) => _compare(a as E, b as E), _validKey);
Set<R> cast<R>() => Set.castFrom<E, R>(this, newSet: _newSet);
// From Iterable.
Iterator<E> get iterator =>
_SplayTreeKeyIterator<E, _SplayTreeSetNode<E>>(this);
int get length => _count;
bool get isEmpty => _root == null;
bool get isNotEmpty => _root != null;
E get first {
if (_count == 0) throw IterableElementError.noElement();
return _first!.key;
}
E get last {
if (_count == 0) throw IterableElementError.noElement();
return _last!.key;
}
E get single {
if (_count == 0) throw IterableElementError.noElement();
if (_count > 1) throw IterableElementError.tooMany();
return _root!.key;
}
// From Set.
bool contains(Object? element) {
return _validKey(element) && _splay(element as E) == 0;
}
bool add(E element) => _add(element);
bool _add(E element) {
int compare = _splay(element);
if (compare == 0) return false;
_addNewRoot(_SplayTreeSetNode(element), compare);
return true;
}
bool remove(Object? object) {
if (!_validKey(object)) return false;
return _remove(object as E) != null;
}
void addAll(Iterable<E> elements) {
for (E element in elements) {
_add(element);
}
}
void removeAll(Iterable<Object?> elements) {
for (Object? element in elements) {
if (_validKey(element)) _remove(element as E);
}
}
void retainAll(Iterable<Object?> elements) {
// Build a set with the same sense of equality as this set.
SplayTreeSet<E> retainSet = SplayTreeSet<E>(_compare, _validKey);
int modificationCount = _modificationCount;
for (Object? object in elements) {
if (modificationCount != _modificationCount) {
// The iterator should not have side effects.
throw ConcurrentModificationError(this);
}
// Equivalent to this.contains(object).
if (_validKey(object) && _splay(object as E) == 0) {
retainSet.add(_root!.key);
}
}
// Take over the elements from the retained set, if it differs.
if (retainSet._count != _count) {
_root = retainSet._root;
_count = retainSet._count;
_modificationCount++;
}
}
E? lookup(Object? object) {
if (!_validKey(object)) return null;
int comp = _splay(object as E);
if (comp != 0) return null;
return _root!.key;
}
Set<E> intersection(Set<Object?> other) {
Set<E> result = SplayTreeSet<E>(_compare, _validKey);
for (E element in this) {
if (other.contains(element)) result.add(element);
}
return result;
}
Set<E> difference(Set<Object?> other) {
Set<E> result = SplayTreeSet<E>(_compare, _validKey);
for (E element in this) {
if (!other.contains(element)) result.add(element);
}
return result;
}
Set<E> union(Set<E> other) {
return _clone()..addAll(other);
}
SplayTreeSet<E> _clone() {
var set = SplayTreeSet<E>(_compare, _validKey);
set._count = _count;
set._root = _copyNode<_SplayTreeSetNode<E>>(_root);
return set;
}
// Copies the structure of a SplayTree into a new similar structure.
// Works on _SplayTreeMapNode as well, but only copies the keys,
_SplayTreeSetNode<E>? _copyNode<Node extends _SplayTreeNode<E, Node>>(
Node? node) {
if (node == null) return null;
// Given a source node and a destination node, copy the left
// and right subtrees of the source node into the destination node.
// The left subtree is copied recursively, but the right spine
// of every subtree is copied iteratively.
void copyChildren(Node node, _SplayTreeSetNode<E> dest) {
Node? left;
Node? right;
do {
left = node._left;
right = node._right;
if (left != null) {
var newLeft = _SplayTreeSetNode<E>(left.key);
dest._left = newLeft;
// Recursively copy the left tree.
copyChildren(left, newLeft);
}
if (right != null) {
var newRight = _SplayTreeSetNode<E>(right.key);
dest._right = newRight;
// Set node and dest to copy the right tree iteratively.
node = right;
dest = newRight;
}
} while (right != null);
}
var result = _SplayTreeSetNode<E>(node.key);
copyChildren(node, result);
return result;
}
void clear() {
_clear();
}
Set<E> toSet() => _clone();
String toString() => IterableBase.iterableToFullString(this, '{', '}');
}