Make Iterable.generate use ListIterable as base implementation.

sdk/lib/core/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.core;
 
 /**
  * A collection of values, or "elements", that can be accessed sequentially.
  *
  * The elements of the iterable are accessed by getting an [Iterator]
  * using the [iterator] getter, and using it to step through the values.
  * Stepping with the iterator is done by calling [Iterator.moveNext],
  * and if the call returns `true`,
  * the iterator has now moved to the next element,
  * which is then available as [Iterator.current].
  * If the call returns `false`, there are no more elements,
- * and `iterator.currrent` returns `null`.
+ * and `iterator.current` returns `null`.
  *
  * You can create more than one iterator from the same `Iterable`.
  * Each time `iterator` is read, it returns a new iterator,
  * and different iterators can be stepped through independently,
  * each giving access to all the elements of the iterable.
  * The iterators of the same iterable *should* provide the same values
  * in the same order (unless the underlying collection is modified between
  * the iterations, which some collections allow).
  *
  * You can also iterate over the elements of an `Iterable`
@@ skipping 48 matching lines @@
  * Since an iterable may be iterated more than once, it's not recommended to
  * have detectable side-effects in the iterator.
  * For methods like [map] and [while], the returned iterable will execute the
  * argument function on every iteration, so those functions should also not
  * have side effects.
  */
 abstract class Iterable<E> {
   const Iterable();
 
   /**
-   * Creates an `Iterable` that generates its elements dynamically.
+   * Creates an `Iterable` which generates its elements dynamically.
    *
-   * An `Iterator` created by [iterator] will count from
-   * zero to [:count - 1:], and call [generator]
-   * with each index in turn to create the next value.
+   * The generated iterable has [count] elements,
+   * and the element at index `n` is computed by calling `generator(n)`.
+   * Values are not cached, so each iteration computes the values again.
    *
    * If [generator] is omitted, it defaults to an identity function
-   * on integers `(int x) => x`, so it should only be omitted if the type
-   * parameter allows integer values.
+   * on integers `(int x) => x`, so it may only be omitted if the type
+   * parameter allows integer values. That is, if [E] is one of
+   * `int`, `num`, `Object` or `dynamic`.
    *
    * As an `Iterable`, `new Iterable.generate(n, generator))` is equivalent to
    * `const [0, ..., n - 1].map(generator)`.
    */
   factory Iterable.generate(int count, [E generator(int index)]) {
     if (count <= 0) return new EmptyIterable<E>();
     return new _GeneratorIterable<E>(count, generator);
   }
 
   /**
@@ skipping 51 matching lines @@
   Iterable/*<T>*/ map/*<T>*/(/*=T*/ f(E e)) =>
       new MappedIterable<E, dynamic/*=T*/>(this, f);
 
   /**
    * Returns a new lazy [Iterable] with all elements that satisfy the
    * predicate [test].
    *
    * The matching elements have the same order in the returned iterable
    * as they have in [iterator].
    *
-   * This method returns a view of the mapped elements. As long as the
-   * returned [Iterable] is not iterated over, the supplied function [test] will
-   * not be invoked. Iterating will not cache results, and thus iterating
-   * multiple times over the returned [Iterable] will invoke the supplied
+   * This method returns a view of the mapped elements.
+   * As long as the returned [Iterable] is not iterated over,
+   * the supplied function [test] will not be invoked.
+   * Iterating will not cache results, and thus iterating multiple times over
+   * the returned [Iterable] may invoke the supplied
    * function [test] multiple times on the same element.
    */
-  Iterable<E> where(bool test(E element)) =>
-      new WhereIterable<E>(this, test);
+  Iterable<E> where(bool test(E element)) => new WhereIterable<E>(this, test);
 
   /**
    * Expands each element of this [Iterable] into zero or more elements.
    *
    * The resulting Iterable runs through the elements returned
    * by [f] for each element of this, in iteration order.
    *
    * The returned [Iterable] is lazy, and calls [f] for each element
    * of this every time it's iterated.
    */
@@ skipping 219 matching lines @@
    *
    * The elements can be computed by stepping through [iterator] until an
    * element is found where `test(element)` is false. At that point,
    * the returned iterable stops (its `moveNext()` returns false).
    */
   Iterable<E> takeWhile(bool test(E value)) {
     return new TakeWhileIterable<E>(this, test);
   }
 
   /**
-   * Returns an Iterable that provides all but the first [count] elements.
+   * Returns an [Iterable] that provides all but the first [count] elements.
    *
    * When the returned iterable is iterated, it starts iterating over `this`,
    * first skipping past the initial [count] elements.
    * If `this` has fewer than `count` elements, then the resulting Iterable is
    * empty.
    * After that, the remaining elements are iterated in the same order as
    * in this iterable.
    *
-   * The `count` must not be negative.
+   * Some iterables may be able to find later elements without first iterating
+   * through earlier elements, for example when iterating a [List].
+   * Such iterables are allowed to ignore the initial skipped elements.
+   *
+   * The [count] must not be negative.
    */
   Iterable<E> skip(int count) {
     return new SkipIterable<E>(this, count);
   }
 
   /**
-   * Returns an Iterable that skips leading elements while [test] is satisfied.
+   * Returns an `Iterable` that skips leading elements while [test] is satisfied.
    *
-   * The filtering happens lazily. Every new Iterator of the returned
-   * Iterable iterates over all elements of `this`.
+   * The filtering happens lazily. Every new [Iterator] of the returned
+   * iterable iterates over all elements of `this`.
    *
    * The returned iterable provides elements by iterating this iterable,
    * but skipping over all initial elements where `test(element)` returns
    * true. If all elements satisfy `test` the resulting iterable is empty,
    * otherwise it iterates the remaining elements in their original order,
-   * starting with the first element for which `test(element)` returns false.
+   * starting with the first element for which `test(element)` returns `false`.
    */
   Iterable<E> skipWhile(bool test(E value)) {
     return new SkipWhileIterable<E>(this, test);
   }
 
   /**
    * Returns the first element.
    *
    * Throws a [StateError] if `this` is empty.
    * Otherwise returns the first element in the iteration order,
@@ skipping 38 matching lines @@
     Iterator<E> it = iterator;
     if (!it.moveNext()) throw IterableElementError.noElement();
     E result = it.current;
     if (it.moveNext()) throw IterableElementError.tooMany();
     return result;
   }
 
   /**
    * Returns the first element that satisfies the given predicate [test].
    *
-   * Iterates through elements and returns the first to satsify [test].
+   * Iterates through elements and returns the first to satisfy [test].
    *
    * If no element satisfies [test], the result of invoking the [orElse]
    * function is returned.
    * If [orElse] is omitted, it defaults to throwing a [StateError].
    */
   E firstWhere(bool test(E element), { E orElse() }) {
     for (E element in this) {
       if (test(element)) return element;
     }
     if (orElse != null) return orElse();
     throw IterableElementError.noElement();
   }
 
   /**
    * Returns the last element that satisfies the given predicate [test].
    *
    * An iterable that can access its elements directly may check its
    * elements in any order (for example a list starts by checking the
    * last element and then moves towards the start of the list).
    * The default implementation iterates elements in iteration order,
    * checks `test(element)` for each,
    * and finally returns that last one that matched.
    *
-   * If no element satsfies [test], the result of invoking the [orElse]
+   * If no element satisfies [test], the result of invoking the [orElse]
    * function is returned.
    * If [orElse] is omitted, it defaults to throwing a [StateError].
    */
   E lastWhere(bool test(E element), {E orElse()}) {
     E result = null;
     bool foundMatching = false;
     for (E element in this) {
       if (test(element)) {
         result = element;
         foundMatching = true;
@@ skipping 64 matching lines @@
    *
    * The conversion may omit calling `toString` on some elements if they
    * are known to not occur in the output, and it may stop iterating after
    * a hundred elements.
    */
   String toString() => IterableBase.iterableToShortString(this, '(', ')');
 }
 
 typedef E _Generator<E>(int index);
 
-class _GeneratorIterable<E> extends Iterable<E>
-                            implements EfficientLength {
-  final int _start;
-  final int _end;
+class _GeneratorIterable<E> extends ListIterable<E> {
+  /// The length of the generated iterable.
+  final int length;
+
+  /// The function mapping indices to values.
   final _Generator<E> _generator;
 
-  /// Creates an iterable that builds the elements from a generator function.
+  /// Creates the generated iterable.
   ///
-  /// The [generator] may be null, in which case the default generator
-  /// enumerating the integer positions is used. This means that [int] must
-  /// be assignable to [E] when no generator is provided. In practice this means
-  /// that the generator can only be emitted when [E] is equal to `dynamic`,
-  /// `int`, or `num`. The constructor will check that the types match.
-  _GeneratorIterable(this._end, E generator(int n))
-      : _start = 0,
-        // The `as` below is used as check to make sure that `int` is assignable
+  /// If [generator] is `null`, it is checked that `int` is assignable to [E].
+  _GeneratorIterable(this.length, E generator(int index))
+      : // The `as` below is used as check to make sure that `int` is assignable
         // to [E].
         _generator = (generator != null) ? generator : _id as _Generator<E>;
 
-  _GeneratorIterable.slice(this._start, this._end, this._generator);
-
-  Iterator<E> get iterator =>
-      new _GeneratorIterator<E>(_start, _end, _generator);
-  int get length => _end - _start;
-
-  Iterable<E> skip(int count) {
-    RangeError.checkNotNegative(count, "count");
-    if (count == 0) return this;
-    int newStart = _start + count;
-    if (newStart >= _end) return new EmptyIterable<E>();
-    return new _GeneratorIterable<E>.slice(newStart, _end, _generator);
+  E elementAt(int index) {
+    RangeError.checkValidIndex(index, this);
+    return _generator(index);
   }
 
-  Iterable<E> take(int count) {
-    RangeError.checkNotNegative(count, "count");
-    if (count == 0) return new EmptyIterable<E>();
-    int newEnd = _start + count;
-    if (newEnd >= _end) return this;
-    return new _GeneratorIterable<E>.slice(_start, newEnd, _generator);
-  }
-
+  /// Helper function used as default _generator function.
   static int _id(int n) => n;
 }
 
-class _GeneratorIterator<E> implements Iterator<E> {
-  final int _end;
-  final _Generator<E> _generator;
-  int _index;
-  E _current;
-
-  _GeneratorIterator(this._index, this._end, this._generator);
-
-  bool moveNext() {
-    if (_index < _end) {
-      _current = _generator(_index);
-      _index++;
-      return true;
-    } else {
-      _current = null;
-      return false;
-    }
-  }
-
-  E get current => _current;
-}
-
 /**
  * An Iterator that allows moving backwards as well as forwards.
  */
 abstract class BidirectionalIterator<E> implements Iterator<E> {
   /**
    * Move back to the previous element.
    *
    * Returns true and updates [current] if successful. Returns false
    * and sets [current] to null if there is no previous element.
    */
   bool movePrevious();
 }