Add EfficientLength marker interface to some iterabels.

sdk/lib/_collection_dev/iterable.dart

Index: sdk/lib/_collection_dev/iterable.dart
diff --git a/sdk/lib/_collection_dev/iterable.dart b/sdk/lib/_collection_dev/iterable.dart
index 3cc913baa37eae41ef30921970ba3b3805939ef4..5610b55ffffefe9e82ee120e4ad7ec960708b08b 100644
--- a/sdk/lib/_collection_dev/iterable.dart
+++ b/sdk/lib/_collection_dev/iterable.dart
@@ -36,7 +36,8 @@ const deprecated = "qB2n4PYM";
  * 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);
 
@@ -341,7 +342,14 @@ 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);
 
@@ -356,6 +364,12 @@ class MappedIterable<S, T> extends IterableBase<T> {
   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;
@@ -375,8 +389,13 @@ class MappedIterator<S, T> extends Iterator<T> {
   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;
 
@@ -465,17 +484,36 @@ 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);
   }
 
+  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);
+
+  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;
@@ -536,7 +574,14 @@ 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) {

[sra1, 2013/10/09 21:16:53]

Skip and Take are asymmetrical w.r.t. where the skipcount is checked.

I would prefer checking before initialization so that a compiler can infer that
the field is non-negative.
(i.e. change Skip to match Take).

       throw new RangeError(_skipCount);
     }
@@ -554,6 +599,18 @@ class SkipIterable<E> extends IterableBase<E> {
   }
 }
 
+class EfficientLengthSkipIterable<E> extends SkipIterable<E>
+                                     implements EfficientLength {
+  EfficientLengthSkipIterable(Iterable<E> iterable, int skipCount)
+      : super._(iterable, skipCount);
+
+  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;
@@ -605,7 +662,7 @@ class SkipWhileIterator<E> extends Iterator<E> {
 /**
  * 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();
@@ -897,7 +954,7 @@ class IterableMixinWorkaround {
     for (int i = 0; i < _toStringList.length; i++) {
       if (identical(_toStringList[i], iterable)) {
         return '$leftDelimiter...$rightDelimiter';
-        }
+      }
     }
 
     StringBuffer result = new StringBuffer();
@@ -1021,9 +1078,28 @@ class IterableMixinWorkaround {
   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) {
@@ -1037,7 +1113,7 @@ class IterableMixinWorkaround {
     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;