content: // 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.
  
  part of dart.collection;
  
  /**
   * This [Iterable] mixin implements all [Iterable] members except `iterator`.
   *
   * All other methods are implemented in terms of `iterator`.
   */
  abstract class IterableMixin<E> implements Iterable<E> {
    Iterable map(f(E element)) => new MappedIterable<E, dynamic>(this, f);
  
    Iterable<E> where(bool f(E element)) => new WhereIterable<E>(this, f);
  
    Iterable expand(Iterable f(E element)) =>
        new ExpandIterable<E, dynamic>(this, f);
  
    bool contains(Object element) {
      for (E e in this) {
        if (e == element) return true;
      }
      return false;
    }
  
    void forEach(void f(E element)) {
      for (E element in this) f(element);
    }
  
    E reduce(E combine(E value, E element)) {
      Iterator<E> iterator = this.iterator;
      if (!iterator.moveNext()) {
        throw new StateError("No elements");
      }
      E value = iterator.current;
      while (iterator.moveNext()) {
        value = combine(value, iterator.current);
      }
      return value;
    }
  
    dynamic fold(var initialValue,
                 dynamic combine(var previousValue, E element)) {
      var value = initialValue;
      for (E element in this) value = combine(value, element);
      return value;
    }
  
    bool every(bool f(E element)) {
      for (E element in this) {
        if (!f(element)) return false;
      }
      return true;
    }
  
    String join([String separator = ""]) {
      Iterator<E> iterator = this.iterator;
      if (!iterator.moveNext()) return "";
      StringBuffer buffer = new StringBuffer();
      if (separator == null || separator == "") {
        do {
          buffer.write("${iterator.current}");
        } while (iterator.moveNext());
      } else {
        buffer.write("${iterator.current}");
        while (iterator.moveNext()) {
          buffer.write(separator);
          buffer.write("${iterator.current}");
        }
      }
      return buffer.toString();
    }
  
    bool any(bool f(E element)) {
      for (E element in this) {
        if (f(element)) return true;
      }
      return false;
    }
  
    List<E> toList({ bool growable: true }) =>
        new List<E>.from(this, growable: growable);
  
    Set<E> toSet() => new Set<E>.from(this);
  
    int get length {
      assert(this is! EfficientLength);
      int count = 0;
      Iterator it = iterator;
      while (it.moveNext()) {
        count++;
      }
      return count;
    }
  
    bool get isEmpty => !iterator.moveNext();
  
    bool get isNotEmpty => !isEmpty;
  
    Iterable<E> take(int n) {
      return new TakeIterable<E>(this, n);
    }
  
    Iterable<E> takeWhile(bool test(E value)) {
      return new TakeWhileIterable<E>(this, test);
    }
  
    Iterable<E> skip(int n) {
      return new SkipIterable<E>(this, n);
    }
  
    Iterable<E> skipWhile(bool test(E value)) {
      return new SkipWhileIterable<E>(this, test);
    }
  
    E get first {
      Iterator it = iterator;
      if (!it.moveNext()) {
        throw new StateError("No elements");
      }
      return it.current;
    }
  
    E get last {
      Iterator it = iterator;
      if (!it.moveNext()) {
        throw new StateError("No elements");
      }
      E result;
      do {
        result = it.current;
      } while(it.moveNext());
      return result;
    }
  
    E get single {
      Iterator it = iterator;
      if (!it.moveNext()) throw new StateError("No elements");
      E result = it.current;
      if (it.moveNext()) throw new StateError("More than one element");
      return result;
    }
  
    dynamic firstWhere(bool test(E value), { Object orElse() }) {
      for (E element in this) {
        if (test(element)) return element;
      }
      if (orElse != null) return orElse();
      throw new StateError("No matching element");
    }
  
    dynamic lastWhere(bool test(E value), { Object orElse() }) {
      E result = null;
      bool foundMatching = false;
      for (E element in this) {
        if (test(element)) {
          result = element;
          foundMatching = true;
        }
      }
      if (foundMatching) return result;
      if (orElse != null) return orElse();
      throw new StateError("No matching element");
    }
  
    E singleWhere(bool test(E value)) {
      E result = null;
      bool foundMatching = false;
      for (E element in this) {
        if (test(element)) {
          if (foundMatching) {
            throw new StateError("More than one matching element");
          }
          result = element;
          foundMatching = true;
        }
      }
      if (foundMatching) return result;
      throw new StateError("No matching element");
    }
  
    E elementAt(int index) {
      if (index is! int || index < 0) throw new RangeError.value(index);
      int remaining = index;
      for (E element in this) {
        if (remaining == 0) return element;
        remaining--;
      }
      throw new RangeError.value(index);
    }
  
    String toString() => _iterableToString(this);
  }
  
  /**
   * Base class for implementing [Iterable].
   *
   * This class implements all methods of [Iterable] except [Iterable.iterator]
   * in terms of `iterator`.
   */
  abstract class IterableBase<E> implements Iterable<E> {
    // TODO(lrn): Base this on IterableMixin if there ever becomes a way
    // to combine const constructors and mixins.
    const IterableBase();
  
    Iterable map(f(E element)) => new MappedIterable<E, dynamic>(this, f);
  
    Iterable<E> where(bool f(E element)) => new WhereIterable<E>(this, f);
  
    Iterable expand(Iterable f(E element)) =>
        new ExpandIterable<E, dynamic>(this, f);
  
    bool contains(Object element) {
      for (E e in this) {
        if (e == element) return true;
      }
      return false;
    }
  
    void forEach(void f(E element)) {
      for (E element in this) f(element);
    }
  
    E reduce(E combine(E value, E element)) {
      Iterator<E> iterator = this.iterator;
      if (!iterator.moveNext()) {
        throw new StateError("No elements");
      }
      E value = iterator.current;
      while (iterator.moveNext()) {
        value = combine(value, iterator.current);
      }
      return value;
    }
  
    dynamic fold(var initialValue,
                 dynamic combine(var previousValue, E element)) {
      var value = initialValue;
      for (E element in this) value = combine(value, element);
      return value;
    }
  
    bool every(bool f(E element)) {
      for (E element in this) {
        if (!f(element)) return false;
      }
      return true;
    }
  
    String join([String separator = ""]) {
      Iterator<E> iterator = this.iterator;
      if (!iterator.moveNext()) return "";
      StringBuffer buffer = new StringBuffer();
      if (separator == null || separator == "") {
        do {
          buffer.write("${iterator.current}");
        } while (iterator.moveNext());
      } else {
        buffer.write("${iterator.current}");
        while (iterator.moveNext()) {
          buffer.write(separator);
          buffer.write("${iterator.current}");
        }
      }
      return buffer.toString();
    }
  
    bool any(bool f(E element)) {
      for (E element in this) {
        if (f(element)) return true;
      }
      return false;
    }
  
    List<E> toList({ bool growable: true }) =>
        new List<E>.from(this, growable: growable);
  
    Set<E> toSet() => new Set<E>.from(this);
  
    int get length {
      assert(this is! EfficientLength);
      int count = 0;
      Iterator it = iterator;
      while (it.moveNext()) {
        count++;
      }
      return count;
    }
  
    bool get isEmpty => !iterator.moveNext();
  
    bool get isNotEmpty => !isEmpty;
  
    Iterable<E> take(int n) {
      return new TakeIterable<E>(this, n);
    }
  
    Iterable<E> takeWhile(bool test(E value)) {
      return new TakeWhileIterable<E>(this, test);
    }
  
    Iterable<E> skip(int n) {
      return new SkipIterable<E>(this, n);
    }
  
    Iterable<E> skipWhile(bool test(E value)) {
      return new SkipWhileIterable<E>(this, test);
    }
  
    E get first {
      Iterator it = iterator;
      if (!it.moveNext()) {
        throw new StateError("No elements");
      }
      return it.current;
    }
  
    E get last {
      Iterator it = iterator;
      if (!it.moveNext()) {
        throw new StateError("No elements");
      }
      E result;
      do {
        result = it.current;
      } while(it.moveNext());
      return result;
    }
  
    E get single {
      Iterator it = iterator;
      if (!it.moveNext()) throw new StateError("No elements");
      E result = it.current;
      if (it.moveNext()) throw new StateError("More than one element");
      return result;
    }
  
    dynamic firstWhere(bool test(E value), { Object orElse() }) {
      for (E element in this) {
        if (test(element)) return element;
      }
      if (orElse != null) return orElse();
      throw new StateError("No matching element");
    }
  
    dynamic lastWhere(bool test(E value), { Object orElse() }) {
      E result = null;
      bool foundMatching = false;
      for (E element in this) {
        if (test(element)) {
          result = element;
          foundMatching = true;
        }
      }
      if (foundMatching) return result;
      if (orElse != null) return orElse();
      throw new StateError("No matching element");
    }
  
    E singleWhere(bool test(E value)) {
      E result = null;
      bool foundMatching = false;
      for (E element in this) {
        if (test(element)) {
          if (foundMatching) {
            throw new StateError("More than one matching element");
          }
          result = element;
          foundMatching = true;
        }
      }
      if (foundMatching) return result;
      throw new StateError("No matching element");
    }
  
    E elementAt(int index) {
      if (index is! int || index < 0) throw new RangeError.value(index);
      int remaining = index;
      for (E element in this) {
        if (remaining == 0) return element;
        remaining--;
      }
      throw new RangeError.value(index);
    }
  
    /**
     * Returns a string representation of (some of) the elements of `this`.
     *
     * Elements are represented by their own `toString` results.
     *
     * The representation always contains the first three elements.
     * If there are less than a hundred elements in the iterable, it also
     * contains the last two elements.
     *
     * If the resulting string isn't above 80 characters, more elements are
     * included from the start of the iterable.
     *
     * The conversion may omit calling `toString` on some elements if they
     * are known to now occur in the output, and it may stop iterating after
     * a hundred elements.
     */
    String toString() => _iterableToString(this);
  }
  
  String _iterableToString(Iterable iterable) {
    if (_toStringVisiting.contains(iterable)) return "(...)";
    _toStringVisiting.add(iterable);
    List parts = [];
    try {
      _iterablePartsToStrings(iterable, parts);
    } finally {
      _toStringVisiting.remove(iterable);
    }
    return (new StringBuffer("(")..writeAll(parts, ", ")..write(")")).toString();
  }
  
  /** Convert elments of [iterable] to strings and store them in [parts]. */
  void _iterablePartsToStrings(Iterable iterable, List parts) {
    /// Try to stay below this many characters.
    const int LENGTH_LIMIT = 80;
    /// Always at least this many elements at the start.
    const int HEAD_COUNT = 3;
    /// Always at least this many elements at the end.
    const int TAIL_COUNT = 2;
    /// Stop iterating after this many elements. Iterables can be infinite.
    const int MAX_COUNT = 100;
    // Per entry length overhead. It's for ", " for all after the first entry,
    // and for "(" and ")" for the initial entry. By pure luck, that's the same
    // number.
    const int OVERHEAD = 2;
    const int ELLIPSIS_SIZE = 3;  // "...".length.
  
    int length = 0;
    int count = 0;
    Iterator it = iterable.iterator;
    // Initial run of elements, at least HEAD_COUNT, and then continue until
    // passing at most LENGTH_LIMIT characters.
    while (length < LENGTH_LIMIT || count < HEAD_COUNT) {
      if (!it.moveNext()) return;
      String next = "${it.current}";
      parts.add(next);
      length += next.length + OVERHEAD;
      count++;
    }
  
    String penultimateString;
    String ultimateString;
  
    // Find last two elements. One or more of them may already be in the
    // parts array. Include their length in `length`.
    var penultimate = null;
    var ultimate = null;
    if (!it.moveNext()) {
      if (count <= HEAD_COUNT + TAIL_COUNT) return;
      ultimateString = parts.removeLast();
      penultimateString = parts.removeLast();
    } else {
      penultimate = it.current;
      count++;
      if (!it.moveNext()) {
        if (count <= HEAD_COUNT + 1) {
          parts.add("$penultimate");
          return;
        }
        ultimateString = "$penultimate";
        penultimateString = parts.removeLast();
        length += ultimateString.length + OVERHEAD;
      } else {
        ultimate = it.current;
        count++;
        // Then keep looping, keeping the last two elements in variables.
        assert(count < MAX_COUNT);
        while (it.moveNext()) {
          penultimate = ultimate;
          ultimate = it.current;
          count++;
          if (count > MAX_COUNT) {
            // If we haven't found the end before MAX_COUNT, give up.
            // This cannot happen in the code above because each entry
            // increases length by at least two, so there is no way to
            // visit more than ~40 elements before this loop.
  
            // Remove any surplus elements until length, including ", ...)",
            // is at most LENGTH_LIMIT.
            while (length > LENGTH_LIMIT - ELLIPSIS_SIZE - OVERHEAD &&
                   count > HEAD_COUNT) {
              length -= parts.removeLast().length + OVERHEAD;
              count--;
            }
            parts.add("...");
            return;
          }
        }
        penultimateString = "$penultimate";
        ultimateString = "$ultimate";
        length +=
            ultimateString.length + penultimateString.length + 2 * OVERHEAD;
      }
    }
  
    // If there is a gap between the initial run and the last two,
    // prepare to add an ellipsis.
    String elision = null;
    if (count > parts.length + TAIL_COUNT) {
      elision = "...";
      length += ELLIPSIS_SIZE + OVERHEAD;
    }
  
    // If the last two elements were very long, and we have more than
    // HEAD_COUNT elements in the initial run, drop some to make room for
    // the last two.
    while (length > LENGTH_LIMIT && parts.length > HEAD_COUNT) {
      length -= parts.removeLast().length + OVERHEAD;
      if (elision == null) {
        elision = "...";
        length += ELLIPSIS_SIZE + OVERHEAD;
      }
    }
    if (elision != null) {
      parts.add(elision);
    }
    parts.add(penultimateString);
    parts.add(ultimateString);
  }
  