Move Arrays, Collections and Maps into a new library, dart:collections.

lib/collections/helpers.dart

Index: lib/collections/helpers.dart
diff --git a/lib/collections/helpers.dart b/lib/collections/helpers.dart
new file mode 100644
index 0000000000000000000000000000000000000000..eb645b5496e4fe4c562f117d2491f26b60e4d877
--- /dev/null
+++ b/lib/collections/helpers.dart
@@ -0,0 +1,365 @@
+// 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.
+
+/**
+ * The [Collections] class implements static methods useful when
+ * writing a class that implements [Collection] and the [iterator]
+ * method.
+ */
+class Collections {
+  static bool contains(Iterable iterable, var element) {
+    for (final e in iterable) {
+      if (element == e) return true;
+    }
+    return false;
+  }
+
+  static void forEach(Iterable iterable, void f(o)) {
+    for (final e in iterable) {
+      f(e);
+    }
+  }
+
+  static bool some(Iterable iterable, bool f(o)) {
+    for (final e in iterable) {
+      if (f(e)) return true;
+    }
+    return false;
+  }
+
+  static bool every(Iterable iterable, bool f(o)) {
+    for (final e in iterable) {
+      if (!f(e)) return false;
+    }
+    return true;
+  }
+
+  static List map(Iterable source, List destination, f(o)) {
+    for (final e in source) {
+      destination.add(f(e));
+    }
+    return destination;
+  }
+
+  static Dynamic reduce(Iterable iterable,
+                        Dynamic initialValue,
+                        Dynamic combine(Dynamic previousValue, element)) {
+    for (final element in iterable) {
+      initialValue = combine(initialValue, element);
+    }
+    return initialValue;
+  }
+
+  static List filter(Iterable source, List destination, bool f(o)) {
+    for (final e in source) {
+      if (f(e)) destination.add(e);
+    }
+    return destination;
+  }
+
+  static bool isEmpty(Iterable iterable) {
+    return !iterable.iterator().hasNext;
+  }
+
+  // TODO(jjb): visiting list should be an identityHashSet when it exists
+
+  /**
+   * Returns a string representing the specified collection. If the
+   * collection is a [List], the returned string looks like this:
+   * [:'[element0, element1, ... elementN]':]. The value returned by its
+   * [toString] method is used to represent each element. If the specified
+   * collection is not a list, the returned string looks like this:
+   * [:{element0, element1, ... elementN}:]. In other words, the strings
+   * returned for lists are surrounded by square brackets, while the strings
+   * returned for other collections are surrounded by curly braces.
+   *
+   * If the specified collection contains a reference to itself, either
+   * directly or indirectly through other collections or maps, the contained
+   * reference is rendered as [:'[...]':] if it is a list, or [:'{...}':] if
+   * it is not. This prevents the infinite regress that would otherwise occur.
+   * So, for example, calling this method on a list whose sole element is a
+   * reference to itself would return [:'[[...]]':].
+   *
+   * A typical implementation of a collection's [toString] method will
+   * simply return the results of this method applied to the collection.
+   */
+  static String collectionToString(Collection c) {
+    var result = new StringBuffer();
+    _emitCollection(c, result, new List());
+    return result.toString();
+  }
+
+  /**
+   * Appends a string representing the specified collection to the specified
+   * string buffer. The string is formatted as per [collectionToString].
+   * The [:visiting:] list contains references to all of the enclosing
+   * collections and maps (which are currently in the process of being
+   * emitted into [:result:]). The [:visiting:] parameter allows this method to
+   * generate a [:'[...]':] or [:'{...}':] where required. In other words,
+   * it allows this method and [_emitMap] to identify recursive collections
+   * and maps.
+   */
+  static void _emitCollection(Collection c,
+                              StringBuffer result,
+                              List visiting) {
+    visiting.add(c);
+    bool isList = c is List;
+    result.add(isList ? '[' : '{');
+
+    bool first = true;
+    for (var e in c) {
+      if (!first) {
+        result.add(', ');
+      }
+      first = false;
+      _emitObject(e, result, visiting);
+    }
+
+    result.add(isList ? ']' : '}');
+    visiting.removeLast();
+  }
+
+  /**
+   * Appends a string representing the specified object to the specified
+   * string buffer. If the object is a [Collection] or [Map], it is formatted
+   * as per [collectionToString] or [mapToString]; otherwise, it is formatted
+   * by invoking its own [toString] method.
+   *
+   * The [:visiting:] list contains references to all of the enclosing
+   * collections and maps (which are currently in the process of being
+   * emitted into [:result:]). The [:visiting:] parameter allows this method
+   * to generate a [:'[...]':] or [:'{...}':] where required. In other words,
+   * it allows this method and [_emitCollection] to identify recursive maps
+   * and collections.
+   */
+  static void _emitObject(Object o, StringBuffer result, List visiting) {
+    if (o is Collection) {
+      if (_containsRef(visiting, o)) {
+        result.add(o is List ? '[...]' : '{...}');
+      } else {
+        _emitCollection(o, result, visiting);
+      }
+    } else if (o is Map) {
+      if (_containsRef(visiting, o)) {
+        result.add('{...}');
+      } else {
+        Maps._emitMap(o, result, visiting);
+      }
+    } else { // o is neither a collection nor a map
+      result.add(o);
+    }
+  }
+
+  /**
+   * Returns true if the specified collection contains the specified object
+   * reference.
+   */
+  static _containsRef(Collection c, Object ref) {
+    for (var e in c) {
+      if (e === ref) return true;
+    }
+    return false;
+  }
+}
+
+
+// TODO(ngeoffray): Rename to Lists.
+class Arrays {
+  static void copy(List src, int srcStart,
+                   List dst, int dstStart, int count) {
+    if (srcStart === null) srcStart = 0;
+    if (dstStart === null) dstStart = 0;
+
+    if (srcStart < dstStart) {
+      for (int i = srcStart + count - 1, j = dstStart + count - 1;
+           i >= srcStart; i--, j--) {
+        dst[j] = src[i];
+      }
+    } else {
+      for (int i = srcStart, j = dstStart; i < srcStart + count; i++, j++) {
+        dst[j] = src[i];
+      }
+    }
+  }
+
+  static bool areEqual(List a, Object b) {
+    if (a === b) return true;
+    if (!(b is List)) return false;
+    int length = a.length;
+    if (length != b.length) return false;
+
+    for (int i = 0; i < length; i++) {
+      if (a[i] !== b[i]) return false;
+    }
+    return true;
+  }
+
+  /**
+   * Returns the index in the list [a] of the given [element], starting
+   * the search at index [startIndex] to [endIndex] (exclusive).
+   * Returns -1 if [element] is not found.
+   */
+  static int indexOf(List a,
+                     Object element,
+                     int startIndex,
+                     int endIndex) {
+    if (startIndex >= a.length) {
+      return -1;
+    }
+    if (startIndex < 0) {
+      startIndex = 0;
+    }
+    for (int i = startIndex; i < endIndex; i++) {
+      if (a[i] == element) {
+        return i;
+      }
+    }
+    return -1;
+  }
+
+  /**
+   * Returns the last index in the list [a] of the given [element], starting
+   * the search at index [startIndex] to 0.
+   * Returns -1 if [element] is not found.
+   */
+  static int lastIndexOf(List a, Object element, int startIndex) {
+    if (startIndex < 0) {
+      return -1;
+    }
+    if (startIndex >= a.length) {
+      startIndex = a.length - 1;
+    }
+    for (int i = startIndex; i >= 0; i--) {
+      if (a[i] == element) {
+        return i;
+      }
+    }
+    return -1;
+  }
+
+  static void rangeCheck(List a, int start, int length) {
+    if (length < 0) {
+      throw new ArgumentError("negative length $length");
+    }
+    if (start < 0 ) {
+      String message = "$start must be greater than or equal to 0";
+      throw new IndexOutOfRangeException(message);
+    }
+    if (start + length > a.length) {
+      String message = "$start + $length must be in the range [0..${a.length})";
+      throw new IndexOutOfRangeException(message);
+    }
+  }
+}
+
+
+/*
+ * Helper class which implements complex [Map] operations
+ * in term of basic ones ([Map.getKeys], [Map.operator []],
+ * [Map.operator []=] and [Map.remove].)  Not all methods are
+ * necessary to implement each particular operation.
+ */
+class Maps {
+  static bool containsValue(Map map, value) {
+    for (final v in map.getValues()) {
+      if (value == v) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  static bool containsKey(Map map, key) {
+    for (final k in map.getKeys()) {
+      if (key == k) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  static putIfAbsent(Map map, key, ifAbsent()) {
+    if (map.containsKey(key)) {
+      return map[key];
+    }
+    final v = ifAbsent();
+    map[key] = v;
+    return v;
+  }
+
+  static clear(Map map) {
+    for (final k in map.getKeys()) {
+      map.remove(k);
+    }
+  }
+
+  static forEach(Map map, void f(key, value)) {
+    for (final k in map.getKeys()) {
+      f(k, map[k]);
+    }
+  }
+
+  static Collection getValues(Map map) {
+    final result = [];
+    for (final k in map.getKeys()) {
+      result.add(map[k]);
+    }
+    return result;
+  }
+
+  static int length(Map map) => map.getKeys().length;
+
+  static bool isEmpty(Map map) => length(map) == 0;
+
+  /**
+   * Returns a string representing the specified map. The returned string
+   * looks like this: [:'{key0: value0, key1: value1, ... keyN: valueN}':].
+   * The value returned by its [toString] method is used to represent each
+   * key or value.
+   *
+   * If the map collection contains a reference to itself, either
+   * directly as a key or value, or indirectly through other collections
+   * or maps, the contained reference is rendered as [:'{...}':]. This
+   * prevents the infinite regress that would otherwise occur. So, for example,
+   * calling this method on a map whose sole entry maps the string key 'me'
+   * to a reference to the map would return [:'{me: {...}}':].
+   *
+   * A typical implementation of a map's [toString] method will
+   * simply return the results of this method applied to the collection.
+   */
+  static String mapToString(Map m) {
+    var result = new StringBuffer();
+    _emitMap(m, result, new List());
+    return result.toString();
+  }
+
+  /**
+   * Appends a string representing the specified map to the specified
+   * string buffer. The string is formatted as per [mapToString].
+   * The [:visiting:] list contains references to all of the enclosing
+   * collections and maps (which are currently in the process of being
+   * emitted into [:result:]). The [:visiting:] parameter allows this method
+   * to generate a [:'[...]':] or [:'{...}':] where required. In other words,
+   * it allows this method and [_emitCollection] to identify recursive maps
+   * and collections.
+   */
+  static void _emitMap(Map m, StringBuffer result, List visiting) {
+    visiting.add(m);
+    result.add('{');
+
+    bool first = true;
+    m.forEach((k, v) {
+      if (!first) {
+        result.add(', ');
+      }
+      first = false;
+      Collections._emitObject(k, result, visiting);
+      result.add(': ');
+      Collections._emitObject(v, result, visiting);
+    });
+
+    result.add('}');
+    visiting.removeLast();
+  }
+}