Make Map.keys/values Iterables.

sdk/lib/core/map.dart

 // Copyright (c) 2011, 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.core;
 
 /**
  * A [Map] is an associative container, mapping a key to a value.
  * Null values are supported, but null keys are not.
  */
@@ skipping 51 matching lines @@
    * Removes all pairs from the map.
    */
   void clear();
 
   /**
    * Applies [f] to each {key, value} pair of the map.
    */
   void forEach(void f(K key, V value));
 
   /**
-   * Returns a collection containing all the keys in the map.
+   * The keys of [this].
    */
-  Collection<K> get keys;
+  Iterable<K> get keys;

[Lasse Reichstein Nielsen, 2012/12/22 22:09:24]

You can make it (unmodifiable) Set<K>, and it would make sense. The only extra
feature on top of Iterable is contains, and we have containsKey in Map to
implement it by.

[floitsch, 2013/01/03 13:35:41]

contains is actually in Iterable, so apparently a Set does not add any method
(yet).

I agree that 'keys' should become a Set, but I will do this in a separate CL.
Added a TODO.

 
   /**
-   * Returns a collection containing all the values in the map.
+   * The values of [this].
    */
-  Collection<V> get values;
+  Iterable<V> get values;
 
   /**
    * The number of {key, value} pairs in the map.
    */
   int get length;
 
   /**
    * Returns true if there is no {key, value} pair in the map.
    */
   bool get isEmpty;
@@ skipping 254 matching lines @@
 
   bool get isEmpty {
     return _numberOfEntries == 0;
   }
 
   int get length {
     return _numberOfEntries;
   }
 
   void forEach(void f(K key, V value)) {
-    int length = _keys.length;
-    for (int i = 0; i < length; i++) {
-      var key = _keys[i];
-      if ((key != null) && (!identical(key, _DELETED_KEY))) {
-        f(key, _values[i]);
-      }
+    Iterator<int> it = new _HashMapImplIndexIterator(this);
+    while (it.moveNext()) {
+      f(_keys[it.current], _values[it.current]);
     }
   }
 
+  Iterable<K> get keys => new _HashMapImplKeyIterable<K>(this);
 
-  Collection<K> get keys {
-    List<K> list = new List<K>.fixedLength(length);
-    int i = 0;
-    forEach((K key, V value) {
-      list[i++] = key;
-    });
-    return list;
-  }
-
-  Collection<V> get values {
-    List<V> list = new List<V>.fixedLength(length);
-    int i = 0;
-    forEach((K key, V value) {
-      list[i++] = value;
-    });
-    return list;
-  }
+  Iterable<V> get values => new _HashMapImplValueIterable<V>(this);
 
   bool containsKey(K key) {
     return (_probeForLookup(key) != -1);
   }
 
-  bool containsValue(V value) {
-    int length = _values.length;
-    for (int i = 0; i < length; i++) {
-      var key = _keys[i];
-      if ((key != null) && (!identical(key, _DELETED_KEY))) {
-        if (_values[i] == value) return true;
-      }
-    }
-    return false;
-  }
+  bool containsValue(V value) => values.contains(value);
 
   String toString() {
     return Maps.mapToString(this);
   }
 }
 
+class _HashMapImplKeyIterable<E> extends Iterable<E> {

[Lasse Reichstein Nielsen, 2012/12/22 22:09:24]

Extend _UnmodifiableSet (which we should have at some point, if we don't
already), and implement contains through _map.containsKeu.

[floitsch, 2013/01/03 13:35:41]

In a future CL. but I agree.

+  final _HashMapImpl _map;
+  _HashMapImplKeyIterable(this._map);
+
+  Iterator<E> get iterator => new _HashMapImplKeyIterator<E>(_map);
+}
+
+class _HashMapImplValueIterable<E> extends Iterable<E> {
+  final _HashMapImpl _map;
+  _HashMapImplValueIterable(this._map);
+
+  Iterator<E> get iterator => new _HashMapImplValueIterator<E>(_map);
+}
+
+abstract class _HashMapImplIterator<E> implements Iterator<E> {
+  final _HashMapImpl _map;
+  int _index = -1;
+  E _current;
+
+  _HashMapImplIterator(this._map);
+
+  E _computeCurrentFromIndex(int index, List keys, List values);
+
+  bool moveNext() {
+    int length = _map._keys.length;
+    int newIndex = _index + 1;
+    while (newIndex < length) {
+      var key = _map._keys[newIndex];
+      if ((key != null) && (!identical(key, _HashMapImpl._DELETED_KEY))) {
+        _current = _computeCurrentFromIndex(newIndex, _map._keys, _map._values);
+        _index = newIndex;
+        return true;
+      }
+      newIndex++;
+    }
+    _index = length;
+    _current = null;
+    return false;
+  }
+
+  E get current => _current;
+}
+
+class _HashMapImplKeyIterator<E> extends _HashMapImplIterator<E> {
+  _HashMapImplKeyIterator(_HashMapImpl map) : super(map);
+
+  E _computeCurrentFromIndex(int index, List keys, List values) {
+    return keys[index];
+  }
+}
+
+class _HashMapImplValueIterator<E> extends _HashMapImplIterator<E> {
+  _HashMapImplValueIterator(_HashMapImpl map) : super(map);
+
+  E _computeCurrentFromIndex(int index, List keys, List values) {
+    return values[index];
+  }
+}
+
+class _HashMapImplIndexIterator extends _HashMapImplIterator<int> {
+  _HashMapImplIndexIterator(_HashMapImpl map) : super(map);
+
+  int _computeCurrentFromIndex(int index, List keys, List values) {
+    return index;
+  }
+}
 
 /**
  * A singleton sentinel used to represent when a key is deleted from the map.
  * We can't use [: const Object() :] as a sentinel because it would end up
  * canonicalized and then we cannot distinguish the deleted key from the
  * canonicalized [: Object() :].
  */
 class _DeletedKeySentinel {
   const _DeletedKeySentinel();
 }
@@ skipping 54 matching lines @@
 
   V putIfAbsent(K key, V ifAbsent()) {
     V value = this[key];
     if ((this[key] == null) && !(containsKey(key))) {
       value = ifAbsent();
       this[key] = value;
     }
     return value;
   }
 
-  Collection<K> get keys {
-    List<K> list = new List<K>.fixedLength(length);
-    int index = 0;
-    _list.forEach((_KeyValuePair<K, V> entry) {
-      list[index++] = entry.key;
-    });
-    assert(index == length);
-    return list;
+  Iterable<K> get keys {
+    return new MappedIterable<_KeyValuePair<K, V>, K>(
+        _list, (_KeyValuePair<K, V> entry) => entry.key);
   }
 
 
-  Collection<V> get values {
-    List<V> list = new List<V>.fixedLength(length);
-    int index = 0;
-    _list.forEach((_KeyValuePair<K, V> entry) {
-      list[index++] = entry.value;
-    });
-    assert(index == length);
-    return list;
+  Iterable<V> get values {
+    return new MappedIterable<_KeyValuePair<K, V>, V>(
+        _list, (_KeyValuePair<K, V> entry) => entry.value);
   }
 
   void forEach(void f(K key, V value)) {
     _list.forEach((_KeyValuePair<K, V> entry) {
       f(entry.key, entry.value);
     });
   }
 
   bool containsKey(K key) {
     return _map.containsKey(key);
@@ skipping 15 matching lines @@
 
   void clear() {
     _map.clear();
     _list.clear();
   }
 
   String toString() {
     return Maps.mapToString(this);
   }
 }
+