Add EfficientLength marker interface to some iterabels.

sdk/lib/_collection_dev/iterable.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._collection.dev;
 
+/**
+ * Marker interface for [Iterable] subclasses that have an efficient
+ * [length] implementation.
+ */
+abstract class EfficientLength {
+  /**
+   * Returns the number of elements in the iterable.
+   *
+   * This is an efficient operation that doesn't require iterating through
+   * the elements.
+   */
+  int get length;
+}
 
 // This is a hack to make @deprecated work in dart:io. Don't remove or use this,
 // unless coordinated with either me or the core library team. Thanks!
 // TODO(ajohnsen): Remove at the 11th of August 2013.
 // TODO(ajohnsen): Remove hide in:
 //    tools/dom/templates/html/dart2js/html_dart2js.darttemplate
 //    tools/dom/templates/html/dart2js/svg_dart2js.darttemplate
 //    tools/dom/templates/html/dart2js/web_audio_dart2js.darttemplate
 //    tools/dom/templates/html/dart2js/web_gl_dart2js.darttemplate
 //    tools/dom/templates/html/dart2js/web_sql_dart2js.darttemplate
@@ skipping 12 matching lines @@
 // This is, because we have a test that verifies that no metadata is included
 // in the output, when no mirrors need them.
 const deprecated = "qB2n4PYM";
 
 /**
  * An [Iterable] for classes that have efficient [length] and [elementAt].
  *
  * All other methods are implemented in terms of [length] and [elementAt],
  * including [iterator].
  */
-abstract class ListIterable<E> extends IterableBase<E> {
+abstract class ListIterable<E> extends IterableBase<E>
+                               implements EfficientLength {
   int get length;
   E elementAt(int i);
 
   const ListIterable();
 
   Iterator<E> get iterator => new ListIterator<E>(this);
 
   void forEach(void action(E element)) {
     int length = this.length;
     for (int i = 0; i < length; i++) {
@@ skipping 284 matching lines @@
     return true;
   }
 }
 
 typedef T _Transformation<S, T>(S value);
 
 class MappedIterable<S, T> extends IterableBase<T> {
   final Iterable<S> _iterable;
   final _Transformation<S, T> _f;
 
-  MappedIterable(this._iterable, T this._f(S element));
+  factory MappedIterable(Iterable iterable, T function(S value)) {
+    if (iterable is EfficientLength) {
+      return new EfficientLengthMappedIterable<S, T>(iterable, function);
+    }
+    return new MappedIterable<S, T>._(iterable, function);
+  }
+
+  MappedIterable._(this._iterable, T this._f(S element));
 
   Iterator<T> get iterator => new MappedIterator<S, T>(_iterable.iterator, _f);
 
   // Length related functions are independent of the mapping.
   int get length => _iterable.length;
   bool get isEmpty => _iterable.isEmpty;
 
   // Index based lookup can be done before transforming.
   T get first => _f(_iterable.first);
   T get last => _f(_iterable.last);
   T get single => _f(_iterable.single);
   T elementAt(int index) => _f(_iterable.elementAt(index));
 }
 
+class EfficientLengthMappedIterable<S, T> extends MappedIterable<S, T>
+                                          implements EfficientLength {
+  EfficientLengthMappedIterable(Iterable iterable, T function(S value))
+      : super._(iterable, function);
+}
+
 class MappedIterator<S, T> extends Iterator<T> {
   T _current;
   final Iterator<S> _iterator;
   final _Transformation<S, T> _f;
 
   MappedIterator(this._iterator, T this._f(S element));
 
   bool moveNext() {
     if (_iterator.moveNext()) {
       _current = _f(_iterator.current);
       return true;
     }
     _current = null;
     return false;
   }
 
   T get current => _current;
 }
 
-/** Specialized alternative to [MappedIterable] for mapped [List]s. */
-class MappedListIterable<S, T> extends ListIterable<T> {
+/**
+ * Specialized alternative to [MappedIterable] for mapped [List]s.
+ *
+ * Expects efficient `length` and `elementAt` on the source iterable.
+ */
+class MappedListIterable<S, T> extends ListIterable<T>
+                               implements EfficientLength {
   final Iterable<S> _source;
   final _Transformation<S, T> _f;
 
   MappedListIterable(this._source, T this._f(S value));
 
   int get length => _source.length;
   T elementAt(int index) => _f(_source.elementAt(index));
 }
 
 
@@ skipping 68 matching lines @@
     }
     _current = _currentExpansion.current;
     return true;
   }
 }
 
 class TakeIterable<E> extends IterableBase<E> {
   final Iterable<E> _iterable;
   final int _takeCount;
 
-  TakeIterable(this._iterable, this._takeCount) {
-    if (_takeCount is! int || _takeCount < 0) {
-      throw new ArgumentError(_takeCount);
+  factory TakeIterable(Iterable<E> iterable, int takeCount) {
+    if (takeCount is! int || takeCount < 0) {
+      throw new ArgumentError(takeCount);
     }
+    if (iterable is EfficientLength) {
+      return new EfficientLengthTakeIterable<E>(iterable, takeCount);
+    }
+    return new TakeIterable<E>._(iterable, takeCount);
   }
 
+  Iterable<E> take(int takeCount) {
+    if (takeCount is! int || takeCount < 0) {
+      throw new RangeError.value(takeCount);
+    }
+    if (_takeCount < takeCount) {
+      takeCount = _takeCount;
+    }
+    return new TakeIterable<E>._(_iterable, takeCount)
+  }
+
+  TakeIterable._(this._iterable, this._takeCount);
+
   Iterator<E> get iterator {
     return new TakeIterator<E>(_iterable.iterator, _takeCount);
   }
 }
 
+class EfficientLengthTakeIterable<E> extends TakeIterable<E>
+                                     implements EfficientLength {
+  EfficientLengthTakeIterable(Iterable<E> iterable, int takeCount)
+      : super._(iterable, takeCount);
+
+  Iterable<E> take(int takeCount) {
+    if (takeCount is! int || takeCount < 0) {
+      throw new RangeError.value(takeCount);
+    }
+    if (_takeCount < takeCount) {
+      takeCount = _takeCount;
+    }
+    return new EfficientLengthTakeIterable<E>(_iterable, takeCount)
+  }
+
+  int get length {
+    int iterableLength = _iterable.length;
+    if (iterableLength > _takeCount) return _takeCount;
+    return iterableLength;
+  }
+}
+
+
 class TakeIterator<E> extends Iterator<E> {
   final Iterator<E> _iterator;
   int _remaining;
 
   TakeIterator(this._iterator, this._remaining) {
     assert(_remaining is int && _remaining >= 0);
   }
 
   bool moveNext() {
     _remaining--;
@@ skipping 40 matching lines @@
   E get current {
     if (_isFinished) return null;
     return _iterator.current;
   }
 }
 
 class SkipIterable<E> extends IterableBase<E> {
   final Iterable<E> _iterable;
   final int _skipCount;
 
-  SkipIterable(this._iterable, this._skipCount) {
+  factory SkipIterable(Iterable<E> iterable, int skipCount) {
+    if (iterable is EfficientLength) {
+      return new EfficientLengthSkipIterable<E>(iterable, skipCount);
+    }
+    return new SkipIterable<E>._(iterable, skipCount);
+  }
+
+  SkipIterable._(this._iterable, this._skipCount) {
     if (_skipCount is! int || _skipCount < 0) {
       throw new RangeError(_skipCount);
     }
   }
 
   Iterable<E> skip(int n) {
     if (n is! int || n < 0) {
       throw new RangeError.value(n);
     }
-    return new SkipIterable<E>(_iterable, _skipCount + n);
+    return new SkipIterable<E>._(_iterable, _skipCount + n);
   }
 
   Iterator<E> get iterator {
     return new SkipIterator<E>(_iterable.iterator, _skipCount);
   }
 }
 
+class EfficientLengthSkipIterable<E> extends SkipIterable<E>
+                                     implements EfficientLength {
+  EfficientLengthSkipIterable(Iterable<E> iterable, int skipCount)
+      : super._(iterable, skipCount);
+
+  Iterable<E> skip(int n) {
+    if (n is! int || n < 0) {
+      throw new RangeError.value(n);
+    }
+    return new EfficientLengthSkipIterable<E>(_iterable, _skipCount + n);
+  }
+
+  int get length {
+    int length = _iterable.length - _skipCount;
+    if (length >= 0) return length;
+    return 0;
+  }
+}
+
 class SkipIterator<E> extends Iterator<E> {
   final Iterator<E> _iterator;
   int _skipCount;
 
   SkipIterator(this._iterator, this._skipCount) {
     assert(_skipCount is int && _skipCount >= 0);
   }
 
   bool moveNext() {
     for (int i = 0; i < _skipCount; i++) _iterator.moveNext();
@@ skipping 31 matching lines @@
     }
     return _iterator.moveNext();
   }
 
   E get current => _iterator.current;
 }
 
 /**
  * The always empty [Iterable].
  */
-class EmptyIterable<E> extends IterableBase<E> {
+class EmptyIterable<E> extends IterableBase<E> implements EfficientLength {
   const EmptyIterable();
 
   Iterator<E> get iterator => const EmptyIterator();
 
   void forEach(void action(E element)) {}
 
   bool get isEmpty => true;
 
   int get length => 0;
 
@@ skipping 271 matching lines @@
       }
     }
     return buffer.toString();
   }
 
   static String toStringIterable(Iterable iterable, String leftDelimiter,
                                  String rightDelimiter) {
     for (int i = 0; i < _toStringList.length; i++) {
       if (identical(_toStringList[i], iterable)) {
         return '$leftDelimiter...$rightDelimiter';
-        }
+      }
     }
 
     StringBuffer result = new StringBuffer();
     try {
       _toStringList.add(iterable);
       result.write(leftDelimiter);
       result.writeAll(iterable, ', ');
       result.write(rightDelimiter);
     } finally {
       assert(identical(_toStringList.last, iterable));
@@ skipping 103 matching lines @@
     }
     if (otherStart + length > otherList.length) {
       throw new StateError("Not enough elements");
     }
     Arrays.copy(otherList, otherStart, list, start, length);
   }
 
   static void replaceRangeList(List list, int start, int end,
                                Iterable iterable) {
     _rangeCheck(list, start, end);
-    // TODO(floitsch): optimize this.
-    list.removeRange(start, end);
-    list.insertAll(start, iterable);
+    if (iterable is! EfficientLength) {
+      iterable = iterable.toList();
+    }
+    int removeLength = end - start;
+    int insertLength = iterable.length;
+    if (removeLength >= insertLength) {
+      int delta = removeLength - insertLength;
+      int insertEnd = start + insertLength;
+      int newEnd = list.length - delta;
+      list.setRange(start, insertEnd, iterable);
+      if (delta != 0) {
+        list.setRange(insertEnd, newEnd, list, end);
+        list.length = newEnd;
+      }
+    } else {
+      int delta = insertLength - removeLength;
+      int newLength = list.length + delta;
+      int insertEnd = start + insertLength;  // aka. end + delta.
+      list.length = newLength;
+      list.setRange(insertEnd, newLength, list, end);
+      list.setRange(start, insertEnd, iterable);
+    }
   }
 
   static void fillRangeList(List list, int start, int end, fillValue) {
     _rangeCheck(list, start, end);
     for (int i = start; i < end; i++) {
       list[i] = fillValue;
     }
   }
 
   static void insertAllList(List list, int index, Iterable iterable) {
     if (index < 0 || index > list.length) {
       throw new RangeError.range(index, 0, list.length);
     }
-    if (iterable is! List && iterable is! Set) {
+    if (iterable is! EfficientLength) {
       iterable = iterable.toList(growable: false);
     }
     int insertionLength = iterable.length;
     list.length += insertionLength;
     list.setRange(index + insertionLength, list.length, list, index);
     for (var element in iterable) {
       list[index++] = element;
     }
   }
 
@@ skipping 43 matching lines @@
 
   static Set setDifference(Set set, Set other, Set result) {
     for (var element in set) {
       if (!other.contains(element)) {
         result.add(element);
       }
     }
     return result;
   }
 }