Reapply "Make LinkedHashMap also have a factory constructor and be customizable""

sdk/lib/collection/splay_tree.dart

 // 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 bool _Predicate<T>(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> {
   final K key;
   _SplayTreeNode<K> left;
   _SplayTreeNode<K> right;
 
   _SplayTreeNode(K this.key);
@@ skipping 205 matching lines @@
     return _root;
   }
 
   void _clear() {
     _root = null;
     _count = 0;
     _modificationCount++;
   }
 }
 
+class _TypeTest<T> {
+  bool test(v) => v is T;
+}
+
 /*
  * 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 operations
  * in amortized logarithmic time.
  *
  * Keys of the map are compared using the `compare` function passed in
  * the constructor. If that is omitted, the objects are assumed to be
  * [Comparable], and are compared using their [Comparable.compareTo]
- * method. This also means that `null` is *not* allowed as a key.
+ * 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].
  */
 class SplayTreeMap<K, V> extends _SplayTree<K> implements Map<K, V> {
   Comparator<K> _comparator;
+  _Predicate _validKey;
 
-  SplayTreeMap([int compare(K key1, K key2)])
-      : _comparator = (compare == null) ? Comparable.compare : compare;
+  SplayTreeMap([int compare(K key1, K key2), bool isValidKey(potentialKey)])
+      : _comparator = (compare == null) ? Comparable.compare : compare,
+        _validKey = (isValidKey != null) ? isValidKey : ((v) => v is K);
 
   /**
    * Creates a [SplayTreeMap] that contains all key value pairs of [other].
    */
-  factory SplayTreeMap.from(Map<K, V> other, [int compare(K key1, K key2)]) =>
-      new SplayTreeMap(compare)..addAll(other);
+  factory SplayTreeMap.from(Map<K, V> other,
+                            [ int compare(K key1, K key2),
+                              bool isValidKey(potentialKey)]) =>
+      new SplayTreeMap(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 values are specified for [key] and [value] the default is the
    * identity function.
    */
   factory SplayTreeMap.fromIterable(Iterable<K> iterable,
-      {K key(element), V value(element), int compare(K key1, K key2)}) {
-    SplayTreeMap<K, V> map = new SplayTreeMap<K, V>(compare);
+      {K key(element), V value(element), int compare(K key1, K key2),
+       bool isValidKey(potentialKey) }) {
+    SplayTreeMap<K, V> map = new SplayTreeMap<K, V>(compare, isValidKey);
     Maps._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.
    */
   factory SplayTreeMap.fromIterables(Iterable<K> keys, Iterable<V> values,
-      [int compare(K key1, K key2)]) {
-    SplayTreeMap<K, V> map = new SplayTreeMap<K, V>(compare);
+      [int compare(K key1, K key2), bool isValidKey(potentialKey)]) {
+    SplayTreeMap<K, V> map = new SplayTreeMap<K, V>(compare, isValidKey);
     Maps._fillMapWithIterables(map, keys, values);
     return map;
   }
 
   int _compare(K key1, K key2) => _comparator(key1, key2);
 
   SplayTreeMap._internal();
 
   V operator [](Object key) {
     if (key == null) throw new ArgumentError(key);
-    if (key is! K) return null;
+    if (!_validKey(key)) return null;
     if (_root != null) {
       int comp = _splay(key);
       if (comp == 0) {
         _SplayTreeMapNode mapRoot = _root;
         return mapRoot.value;
       }
     }
     return null;
   }
 
   V remove(Object key) {
-    if (key is! K) return null;
+    if (!_validKey(key)) return null;
     _SplayTreeMapNode mapRoot = _remove(key);
     if (mapRoot != null) return mapRoot.value;
     return null;
   }
 
   void operator []=(K key, V value) {
     if (key == null) throw new ArgumentError(key);
     // 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);
@@ skipping 49 matching lines @@
 
   int get length {
     return _count;
   }
 
   void clear() {
     _clear();
   }
 
   bool containsKey(Object key) {
-    return key is K && _splay(key) == 0;
+    return _validKey(key) && _splay(key) == 0;
   }
 
   bool containsValue(Object value) {
     bool found = false;
     int initialSplayCount = _splayCount;
     bool visit(_SplayTreeMapNode node) {
       while (node != null) {
         if (node.value == value) return true;
         if (initialSplayCount != _splayCount) {
           throw new ConcurrentModificationError(this);
@@ skipping 184 matching lines @@
 class _SplayTreeValueIterator<K, V> extends _SplayTreeIterator<V> {
   _SplayTreeValueIterator(SplayTreeMap<K, V> map): super(map);
   V _getValue(_SplayTreeMapNode node) => node.value;
 }
 
 class _SplayTreeNodeIterator<K>
     extends _SplayTreeIterator<_SplayTreeNode<K>> {
   _SplayTreeNodeIterator(_SplayTree<K> map): super(map);
   _SplayTreeNode<K> _getValue(_SplayTreeNode node) => node;
 }