quiver/lib/src/iterables/generating_iterable.dart

// Copyright 2014 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

part of quiver.iterables;

Iterable generate(initial(), next(o)) => new GeneratingIterable(initial, next);

/**
 * An Iterable who's first value is [object] and who's subsequent values are
 * generated by passing the current value to the [next] function.
 *
 * The class is useful for creating lazy iterables from object hierarchies and
 * graphs.
 *
 * It's important that for the given initial value and next function that the
 * sequence of items eventually terminates. Otherwise calling methods that
 * expect a finite sequence, like `length` or `last`, will cause an infinite
 * loop.
 *
 * Example:
 *
 *     class Node {
 *       Node parent;
 *
 *       /**
 *        * An iterable of node and all ancestors up to the root.
 *        */
 *       Iterable<Node> ancestors =
 *           new GeneratingIterable<Node>(() => this, (n) => n.parent);
 *
 *       /**
 *        * An iterable of the root and the path of nodes to this. The reverse
 *        * of ancestors.
 *        */
 *       Iterable<Node> path = ancestors.toList().reversed();
 *     }
 *
 */
class GeneratingIterable<T> extends IterableBase<T> {
  final initial;
  final next;

  GeneratingIterable(T this.initial(), T this.next(T o));

  @override
  Iterator<T> get iterator => new _GeneratingIterator(initial(), next);
}

class _GeneratingIterator<T> implements Iterator<T> {
  final next;
  T object;
  bool started = false;

  _GeneratingIterator(T this.object, T this.next(T o));

  @override
  T get current => started ? object : null;

  @override
  bool moveNext() {
    if (object == null) return false;
    if (started) {
      object = next(object);
    } else {
      started = true;
    }
    return object != null;
  }
}