sdk/lib/collection/splay_tree.dart - sdk.git - Git at Google

 // 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;

 /**
  * A node in a splay tree. It holds the key, the value and the left
  * and right children in the tree.
  */
 class SplayTreeNode<K, V> {
   final K key;
   V value;
   SplayTreeNode<K, V> left;
   SplayTreeNode<K, V> right;

   SplayTreeNode(K this.key, V this.value);
 }

 /**
  * A splay tree is a self-balancing binary
  * search tree with 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.
  *
  * This implementation is a Dart version of the JavaScript
  * implementation in the V8 project.
  */
 class SplayTreeMap<K extends Comparable, V> implements Map<K, V> {

   // The root node of the splay tree. It will contain either the last
   // element inserted, or the last element looked up.
   SplayTreeNode<K, V> _root;

   // The dummy node used when performing a splay on the tree. It is a
   // local field of the class to avoid allocating a node each time a
   // splay is performed.
   SplayTreeNode<K, V> _dummy;

   // Number of elements in the splay tree.
   int _count;

   /**
    * Counter incremented whenever the keys in the map changes.
    *
    * 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;

   SplayTreeMap() :
     _dummy = new SplayTreeNode<K, V>(null, null),
     _count = 0;

   /**
    * 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) {
     if (_root == null) return -1;

     // The right child of the dummy node will hold
     // the L tree of the algorithm.  The left child of the dummy node
     // will hold the R tree of the algorithm.  Using a dummy node, left
     // and right will always be nodes and we avoid special cases.
     SplayTreeNode<K, V> left = _dummy;
     SplayTreeNode<K, V> right = _dummy;
     SplayTreeNode<K, V> current = _root;
     int comp;
     while (true) {
       comp = current.key.compareTo(key);
       if (comp > 0) {
         if (current.left == null) break;
         comp = current.left.key.compareTo(key);
         if (comp > 0) {
           // Rotate right.
           SplayTreeNode<K, V> tmp = current.left;
           current.left = tmp.right;
           tmp.right = current;
           current = tmp;
           if (current.left == null) break;
         }
         // Link right.
         right.left = current;
         right = current;
         current = current.left;
       } else if (comp < 0) {
         if (current.right == null) break;
         comp = current.right.key.compareTo(key);
         if (comp < 0) {
           // Rotate left.
           SplayTreeNode<K, V> tmp = current.right;
           current.right = tmp.left;
           tmp.left = current;
           current = tmp;
           if (current.right == null) break;
         }
         // Link left.
         left.right = current;
         left = current;
         current = current.right;
       } else {
         break;
       }
     }
     // Assemble.
     left.right = current.left;
     right.left = current.right;
     current.left = _dummy.right;
     current.right = _dummy.left;
     _root = current;

     _dummy.right = null;
     _dummy.left = null;
     _splayCount++;
     return comp;
   }

   V operator [](K key) {
     if (_root != null) {
       int comp = _splay(key);
       if (comp == 0) return _root.value;
     }
     return null;
   }

   V remove(K key) {
     if (_root == null) return null;
     int comp = _splay(key);
     if (comp != 0) return null;
     V value = _root.value;

     _count--;
     // assert(_count >= 0);
     if (_root.left == null) {
       _root = _root.right;
     } else {
       SplayTreeNode<K, V> right = _root.right;
       _root = _root.left;
       // Splay to make sure that the new root has an empty right child.
       _splay(key);
       // Insert the original right child as the right child of the new
       // root.
       _root.right = right;
     }
     _modificationCount++;
     return value;
   }

   void operator []=(K key, V value) {
     if (_root == null) {
       _count++;
       _root = new SplayTreeNode(key, value);
       _modificationCount++;
       return;
     }
     // 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.value = value;
       return;
     }
     _addNewRoot(key, value, comp);
   }

   /**
    * 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(K key, V value, int comp) {
     SplayTreeNode<K, V> node = new SplayTreeNode(key, value);
     // assert(_count >= 0);
     _count++;
     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;
     _modificationCount++;
   }

   V putIfAbsent(K key, V ifAbsent()) {
     if (_root == null) {
       V value = ifAbsent();
       if (_root != null) {
         throw new ConcurrentModificationError(this);
       }
       _root = new SplayTreeNode(key, value);
       _count++;
       _modificationCount++;
       return value;
     }
     int comp = _splay(key);
     if (comp == 0) return _root.value;
     int modificationCount = _modificationCount;
     int splayCount = _splayCount;
     V value = ifAbsent();
     if (modificationCount != _modificationCount) {
       throw new ConcurrentModificationError(this);
     }
     if (splayCount != _splayCount) {
       comp = _splay(key);
       // Key is still not there, otherwise _modificationCount would be changed.
       assert(comp != 0);
     }
     _addNewRoot(key, value, comp);
     return value;
   }

   bool get isEmpty {
     // assert(!((_root == null) && (_count != 0)));
     // assert(!((_count == 0) && (_root != null)));
     return (_root == null);
   }

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

   int get length {
     return _count;
   }

   void clear() {
     _root = null;
     _count = 0;
   }

   bool containsKey(K key) {
     return _splay(key) == 0;
   }

   bool containsValue(V value) {
     bool found = false;
     bool visit(SplayTreeNode node) {
       if (node == null) return false;
       if (node.value == value) return true;
       // TODO(lrn): Do we want to handle the case where node.value.operator==
       // modifies the map?
       return visit(node.left) || visit(node.right);
     }
     return visit(_root);
   }

   Iterable<K> get keys => new _SplayTreeKeyIterable(this);

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

   String toString() {
     return Maps.mapToString(this);
   }

   /**
    * Get the first key in the map. Returns [null] if the map is empty.
    */
   K firstKey() {
     if (_root == null) return null;
     SplayTreeNode<K, V> node = _root;
     while (node.left != null) {
       node = node.left;
     }
     // Maybe implement a splay-method that can splay the minimum without
     // performing comparisons.
     _splay(node.key);
     return node.key;
   }

   /**
    * Get the last key in the map. Returns [null] if the map is empty.
    */
   K lastKey() {
     if (_root == null) return null;
     SplayTreeNode<K, V> node = _root;
     while (node.right != null) {
       node = node.right;
     }
     // Maybe implement a splay-method that can splay the maximum without
     // performing comparisons.
     _splay(node.key);
     return node.key;
   }

   /**
    * Get 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 (_root == null) return null;
     int comp = _splay(key);
     if (comp < 0) return _root.key;
     SplayTreeNode<K, V> node = _root.left;
     if (node == null) return null;
     while (node.right != null) {
       node = 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 (_root == null) return null;
     int comp = _splay(key);
     if (comp > 0) return _root.key;
     SplayTreeNode<K, V> node = _root.right;
     if (node == null) return null;
     while (node.left != null) {
       node = node.left;
     }
     return node.key;
   }
 }

 abstract class _SplayTreeIterator<T> implements Iterator<T> {
   final SplayTreeMap _map;
   /**
    * Worklist of nodes to visit.
    *
    * These nodes have been passed over on the way down in a
    * depth-first left-to-right traversal. Visiting each node,
    * and their right subtrees will visit the remainder of
    * the nodes of a full traversal.
    *
    * Only valid as long as the original tree map isn't reordered.
    */
   final List<SplayTreeNode> _workList = <SplayTreeNode>[];

   /**
    * Original modification counter of [_map].
    *
    * Incremented on [_map] when a key is added or removed.
    * If it changes, iteration is aborted.
    */
   final int _modificationCount;

   /**
    * Count of splay operations on [_map] when [_workList] was built.
    *
    * If the splay count on [_map] increases, [_workList] becomes invalid.
    */
   int _splayCount;

   /** Current node. */
   SplayTreeNode _currentNode;

   _SplayTreeIterator(SplayTreeMap map)
       : _map = map,
         _modificationCount = map._modificationCount,
         _splayCount = map._splayCount {
     _findLeftMostDescendent(map._root);
   }

   T get current {
     if (_currentNode == null) return null;
     return _getValue(_currentNode);
   }

   void _findLeftMostDescendent(SplayTreeNode node) {
     while (node != null) {
       _workList.add(node);
       node = node.left;
     }
   }

   /**
    * Called when the tree structure of the map 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 _rebuildWorkList(SplayTreeNode currentNode) {
     assert(!_workList.isEmpty);
     _workList.clear();
     if (currentNode == null) {
       _findLeftMostDescendent(_map._root);
     } else {
       _map._splay(currentNode.key);
       _findLeftMostDescendent(_map._root.right);
       assert(!_workList.isEmpty);
     }
   }

   bool moveNext() {
     if (_modificationCount != _map._modificationCount) {
       throw new ConcurrentModificationError(_map);
     }
     // Picks the next element in the worklist as current.
     // Updates the worklist with the left-most path of the current node's
     // right-hand child.
     // If the worklist is no longer valid (after a splay), it is rebuild
     // from scratch.
     if (_workList.isEmpty) {
       _currentNode = null;
       return false;
     }
     if (_map._splayCount != _splayCount) {
       _rebuildWorkList(_currentNode);
     }
     _currentNode = _workList.removeLast();
     _findLeftMostDescendent(_currentNode.right);
     return true;
   }

   T _getValue(SplayTreeNode node);
 }


 class _SplayTreeKeyIterable<K, V> extends Iterable<K> {
   SplayTreeMap<K, V> _map;
   _SplayTreeKeyIterable(this._map);
   Iterator<K> get iterator => new _SplayTreeKeyIterator<K, V>(_map);
 }

 class _SplayTreeValueIterable<K, V> extends Iterable<V> {
   SplayTreeMap<K, V> _map;
   _SplayTreeValueIterable(this._map) ;
   Iterator<V> get iterator => new _SplayTreeValueIterator<K, V>(_map);
 }

 class _SplayTreeKeyIterator<K, V> extends _SplayTreeIterator<K> {
   _SplayTreeKeyIterator(SplayTreeMap<K, V> map): super(map);
   K _getValue(SplayTreeNode node) => node.key;
 }

 class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<V> {
   _SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map);
   V _getValue(SplayTreeNode node) => node.value;
 }

 class _SplayTreeNodeIterator<K, V>
     extends _SplayTreeIterator<SplayTreeNode<K, V>> {
   _SplayTreeNodeIterator(SplayTreeMap<K, V> map): super(map);
   SplayTreeNode<K, V> _getValue(SplayTreeNode node) => node;
 }
	// 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;

	/**
	* A node in a splay tree. It holds the key, the value and the left
	* and right children in the tree.
	*/
	class SplayTreeNode<K, V> {
	final K key;
	V value;
	SplayTreeNode<K, V> left;
	SplayTreeNode<K, V> right;

	SplayTreeNode(K this.key, V this.value);
	}

	/**
	* A splay tree is a self-balancing binary
	* search tree with 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.
	*
	* This implementation is a Dart version of the JavaScript
	* implementation in the V8 project.
	*/
	class SplayTreeMap<K extends Comparable, V> implements Map<K, V> {

	// The root node of the splay tree. It will contain either the last
	// element inserted, or the last element looked up.
	SplayTreeNode<K, V> _root;

	// The dummy node used when performing a splay on the tree. It is a
	// local field of the class to avoid allocating a node each time a
	// splay is performed.
	SplayTreeNode<K, V> _dummy;

	// Number of elements in the splay tree.
	int _count;

	/**
	* Counter incremented whenever the keys in the map changes.
	*
	* 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;

	SplayTreeMap() :
	_dummy = new SplayTreeNode<K, V>(null, null),
	_count = 0;

	/**
	* 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) {
	if (_root == null) return -1;

	// The right child of the dummy node will hold
	// the L tree of the algorithm. The left child of the dummy node
	// will hold the R tree of the algorithm. Using a dummy node, left
	// and right will always be nodes and we avoid special cases.
	SplayTreeNode<K, V> left = _dummy;
	SplayTreeNode<K, V> right = _dummy;
	SplayTreeNode<K, V> current = _root;
	int comp;
	while (true) {
	comp = current.key.compareTo(key);
	if (comp > 0) {
	if (current.left == null) break;
	comp = current.left.key.compareTo(key);
	if (comp > 0) {
	// Rotate right.
	SplayTreeNode<K, V> tmp = current.left;
	current.left = tmp.right;
	tmp.right = current;
	current = tmp;
	if (current.left == null) break;
	}
	// Link right.
	right.left = current;
	right = current;
	current = current.left;
	} else if (comp < 0) {
	if (current.right == null) break;
	comp = current.right.key.compareTo(key);
	if (comp < 0) {
	// Rotate left.
	SplayTreeNode<K, V> tmp = current.right;
	current.right = tmp.left;
	tmp.left = current;
	current = tmp;
	if (current.right == null) break;
	}
	// Link left.
	left.right = current;
	left = current;
	current = current.right;
	} else {
	break;
	}
	}
	// Assemble.
	left.right = current.left;
	right.left = current.right;
	current.left = _dummy.right;
	current.right = _dummy.left;
	_root = current;

	_dummy.right = null;
	_dummy.left = null;
	_splayCount++;
	return comp;
	}

	V operator [](K key) {
	if (_root != null) {
	int comp = _splay(key);
	if (comp == 0) return _root.value;
	}
	return null;
	}

	V remove(K key) {
	if (_root == null) return null;
	int comp = _splay(key);
	if (comp != 0) return null;
	V value = _root.value;

	_count--;
	// assert(_count >= 0);
	if (_root.left == null) {
	_root = _root.right;
	} else {
	SplayTreeNode<K, V> right = _root.right;
	_root = _root.left;
	// Splay to make sure that the new root has an empty right child.
	_splay(key);
	// Insert the original right child as the right child of the new
	// root.
	_root.right = right;
	}
	_modificationCount++;
	return value;
	}

	void operator []=(K key, V value) {
	if (_root == null) {
	_count++;
	_root = new SplayTreeNode(key, value);
	_modificationCount++;
	return;
	}
	// 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.value = value;
	return;
	}
	_addNewRoot(key, value, comp);
	}

	/**
	* 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(K key, V value, int comp) {
	SplayTreeNode<K, V> node = new SplayTreeNode(key, value);
	// assert(_count >= 0);
	_count++;
	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;
	_modificationCount++;
	}

	V putIfAbsent(K key, V ifAbsent()) {
	if (_root == null) {
	V value = ifAbsent();
	if (_root != null) {
	throw new ConcurrentModificationError(this);
	}
	_root = new SplayTreeNode(key, value);
	_count++;
	_modificationCount++;
	return value;
	}
	int comp = _splay(key);
	if (comp == 0) return _root.value;
	int modificationCount = _modificationCount;
	int splayCount = _splayCount;
	V value = ifAbsent();
	if (modificationCount != _modificationCount) {
	throw new ConcurrentModificationError(this);
	}
	if (splayCount != _splayCount) {
	comp = _splay(key);
	// Key is still not there, otherwise _modificationCount would be changed.
	assert(comp != 0);
	}
	_addNewRoot(key, value, comp);
	return value;
	}

	bool get isEmpty {
	// assert(!((_root == null) && (_count != 0)));
	// assert(!((_count == 0) && (_root != null)));
	return (_root == null);
	}

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

	int get length {
	return _count;
	}

	void clear() {
	_root = null;
	_count = 0;
	}

	bool containsKey(K key) {
	return _splay(key) == 0;
	}

	bool containsValue(V value) {
	bool found = false;
	bool visit(SplayTreeNode node) {
	if (node == null) return false;
	if (node.value == value) return true;
	// TODO(lrn): Do we want to handle the case where node.value.operator==
	// modifies the map?
	return visit(node.left) \|\| visit(node.right);
	}
	return visit(_root);
	}

	Iterable<K> get keys => new _SplayTreeKeyIterable(this);

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

	String toString() {
	return Maps.mapToString(this);
	}

	/**
	* Get the first key in the map. Returns [null] if the map is empty.
	*/
	K firstKey() {
	if (_root == null) return null;
	SplayTreeNode<K, V> node = _root;
	while (node.left != null) {
	node = node.left;
	}
	// Maybe implement a splay-method that can splay the minimum without
	// performing comparisons.
	_splay(node.key);
	return node.key;
	}

	/**
	* Get the last key in the map. Returns [null] if the map is empty.
	*/
	K lastKey() {
	if (_root == null) return null;
	SplayTreeNode<K, V> node = _root;
	while (node.right != null) {
	node = node.right;
	}
	// Maybe implement a splay-method that can splay the maximum without
	// performing comparisons.
	_splay(node.key);
	return node.key;
	}

	/**
	* Get 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 (_root == null) return null;
	int comp = _splay(key);
	if (comp < 0) return _root.key;
	SplayTreeNode<K, V> node = _root.left;
	if (node == null) return null;
	while (node.right != null) {
	node = 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 (_root == null) return null;
	int comp = _splay(key);
	if (comp > 0) return _root.key;
	SplayTreeNode<K, V> node = _root.right;
	if (node == null) return null;
	while (node.left != null) {
	node = node.left;
	}
	return node.key;
	}
	}

	abstract class _SplayTreeIterator<T> implements Iterator<T> {
	final SplayTreeMap _map;
	/**
	* Worklist of nodes to visit.
	*
	* These nodes have been passed over on the way down in a
	* depth-first left-to-right traversal. Visiting each node,
	* and their right subtrees will visit the remainder of
	* the nodes of a full traversal.
	*
	* Only valid as long as the original tree map isn't reordered.
	*/
	final List<SplayTreeNode> _workList = <SplayTreeNode>[];

	/**
	* Original modification counter of [_map].
	*
	* Incremented on [_map] when a key is added or removed.
	* If it changes, iteration is aborted.
	*/
	final int _modificationCount;

	/**
	* Count of splay operations on [_map] when [_workList] was built.
	*
	* If the splay count on [_map] increases, [_workList] becomes invalid.
	*/
	int _splayCount;

	/** Current node. */
	SplayTreeNode _currentNode;

	_SplayTreeIterator(SplayTreeMap map)
	: _map = map,
	_modificationCount = map._modificationCount,
	_splayCount = map._splayCount {
	_findLeftMostDescendent(map._root);
	}

	T get current {
	if (_currentNode == null) return null;
	return _getValue(_currentNode);
	}

	void _findLeftMostDescendent(SplayTreeNode node) {
	while (node != null) {
	_workList.add(node);
	node = node.left;
	}
	}

	/**
	* Called when the tree structure of the map 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 _rebuildWorkList(SplayTreeNode currentNode) {
	assert(!_workList.isEmpty);
	_workList.clear();
	if (currentNode == null) {
	_findLeftMostDescendent(_map._root);
	} else {
	_map._splay(currentNode.key);
	_findLeftMostDescendent(_map._root.right);
	assert(!_workList.isEmpty);
	}
	}

	bool moveNext() {
	if (_modificationCount != _map._modificationCount) {
	throw new ConcurrentModificationError(_map);
	}
	// Picks the next element in the worklist as current.
	// Updates the worklist with the left-most path of the current node's
	// right-hand child.
	// If the worklist is no longer valid (after a splay), it is rebuild
	// from scratch.
	if (_workList.isEmpty) {
	_currentNode = null;
	return false;
	}
	if (_map._splayCount != _splayCount) {
	_rebuildWorkList(_currentNode);
	}
	_currentNode = _workList.removeLast();
	_findLeftMostDescendent(_currentNode.right);
	return true;
	}

	T _getValue(SplayTreeNode node);
	}


	class _SplayTreeKeyIterable<K, V> extends Iterable<K> {
	SplayTreeMap<K, V> _map;
	_SplayTreeKeyIterable(this._map);
	Iterator<K> get iterator => new _SplayTreeKeyIterator<K, V>(_map);
	}

	class _SplayTreeValueIterable<K, V> extends Iterable<V> {
	SplayTreeMap<K, V> _map;
	_SplayTreeValueIterable(this._map) ;
	Iterator<V> get iterator => new _SplayTreeValueIterator<K, V>(_map);
	}

	class _SplayTreeKeyIterator<K, V> extends _SplayTreeIterator<K> {
	_SplayTreeKeyIterator(SplayTreeMap<K, V> map): super(map);
	K _getValue(SplayTreeNode node) => node.key;
	}

	class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<V> {
	_SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map);
	V _getValue(SplayTreeNode node) => node.value;
	}

	class _SplayTreeNodeIterator<K, V>
	extends _SplayTreeIterator<SplayTreeNode<K, V>> {
	_SplayTreeNodeIterator(SplayTreeMap<K, V> map): super(map);
	SplayTreeNode<K, V> _getValue(SplayTreeNode node) => node;
	}