text: /**
   * @license
   * Copyright The Closure Library Authors.
   * SPDX-License-Identifier: Apache-2.0
   */
  
  /**
   * @fileoverview Python style iteration utilities.
   */
  
  
  goog.provide('goog.iter');
  goog.provide('goog.iter.Iterable');
  goog.provide('goog.iter.Iterator');
  goog.provide('goog.iter.StopIteration');
  
  goog.require('goog.array');
  goog.require('goog.asserts');
  goog.require('goog.functions');
  goog.require('goog.math');
  
  
  /**
   * @typedef {{length:number}|{__iterator__}}
   */
  goog.iter.Iterable;
  
  
  /**
   * Singleton Error object that is used to terminate iterations.
   * @const {!Error}
   */
  goog.iter.StopIteration = ('StopIteration' in goog.global) ?
      // For script engines that support legacy iterators.
      goog.global['StopIteration'] :
      {message: 'StopIteration', stack: ''};
  
  
  
  /**
   * Class/interface for iterators.  An iterator needs to implement a `next`
   * method and it needs to throw a `goog.iter.StopIteration` when the
   * iteration passes beyond the end.  Iterators have no `hasNext` method.
   * It is recommended to always use the helper functions to iterate over the
   * iterator or in case you are only targeting JavaScript 1.7 for in loops.
   * @constructor
   * @template VALUE
   * @deprecated Use objects implementing JavaScript iterable protocol introduced
   *     in ES6.
   *     https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
   */
  goog.iter.Iterator = function() {};
  
  
  /**
   * Returns the next value of the iteration.  This will throw the object
   * {@see goog.iter.StopIteration} when the iteration passes the end.
   * @return {VALUE} Any object or value
   */
  goog.iter.Iterator.prototype.nextValueOrThrow = function() {
    throw goog.iter.StopIteration;
  };
  
  
  /**
   * Returns the `Iterator` object itself.  This is used to implement
   * the iterator protocol in JavaScript 1.7
   * @param {boolean=} opt_keys  Whether to return the keys or values. Default is
   *     to only return the values.  This is being used by the for-in loop (true)
   *     and the for-each-in loop (false).  Even though the param gives a hint
   *     about what the iterator will return there is no guarantee that it will
   *     return the keys when true is passed.
   * @return {!goog.iter.Iterator<VALUE>} The object itself.
   */
  goog.iter.Iterator.prototype.__iterator__ = function(opt_keys) {
    'use strict';
    return this;
  };
  
  
  /**
   * Returns an iterator that knows how to iterate over the values in the object.
   * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable  If the
   *     object is an iterator it will be returned as is.  If the object has an
   *     `__iterator__` method that will be called to get the value
   *     iterator.  If the object is an array-like object we create an iterator
   *     for that.
   * @return {!goog.iter.Iterator<VALUE>} An iterator that knows how to iterate
   *     over the values in `iterable`.
   * @template VALUE
   */
  goog.iter.toIterator = function(iterable) {
    'use strict';
    if (iterable instanceof goog.iter.Iterator) {
      return iterable;
    }
    if (typeof iterable.__iterator__ == 'function') {
      return /** @type {{__iterator__:function(this:?, boolean=)}} */ (iterable)
          .__iterator__(false);
    }
    if (goog.isArrayLike(iterable)) {
      var like = /** @type {!IArrayLike<number|string>} */ (iterable);
      var i = 0;
      var newIter = new goog.iter.Iterator;
      newIter.nextValueOrThrow = function() {
        'use strict';
        while (true) {
          if (i >= like.length) {
            throw goog.iter.StopIteration;
          }
          // Don't include deleted elements.
          if (!(i in like)) {
            i++;
            continue;
          }
          return like[i++];
        }
      };
  
      return newIter;
    }
  
  
    // TODO(arv): Should we fall back on goog.structs.getValues()?
    throw new Error('Not implemented');
  };
  
  
  /**
   * Calls a function for each element in the iterator with the element of the
   * iterator passed as argument.
   *
   * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable  The iterator
   *     to iterate over. If the iterable is an object `toIterator` will be
   *     called on it.
   * @param {function(this:THIS,VALUE,?,!goog.iter.Iterator<VALUE>)} f
   *     The function to call for every element.  This function takes 3 arguments
   *     (the element, undefined, and the iterator) and the return value is
   *     irrelevant.  The reason for passing undefined as the second argument is
   *     so that the same function can be used in {@see goog.array.forEach} as
   *     well as others.  The third parameter is of type "number" for
   *     arraylike objects, undefined, otherwise.
   * @param {THIS=} opt_obj  The object to be used as the value of 'this' within
   *     `f`.
   * @template THIS, VALUE
   */
  goog.iter.forEach = function(iterable, f, opt_obj) {
    'use strict';
    if (goog.isArrayLike(iterable)) {
      try {
        // NOTES: this passes the index number to the second parameter
        // of the callback contrary to the documentation above.
        goog.array.forEach(
            /** @type {IArrayLike<?>} */ (iterable), f, opt_obj);
      } catch (ex) {
        if (ex !== goog.iter.StopIteration) {
          throw ex;
        }
      }
    } else {
      iterable = goog.iter.toIterator(iterable);
  
      try {
        while (true) {
          f.call(opt_obj, iterable.nextValueOrThrow(), undefined, iterable);
        }
      } catch (ex) {
        if (ex !== goog.iter.StopIteration) {
          throw ex;
        }
      }
    }
  };
  
  
  /**
   * Calls a function for every element in the iterator, and if the function
   * returns true adds the element to a new iterator.
   *
   * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
   *     to iterate over.
   * @param {
   *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator<VALUE>):boolean} f
   *     The function to call for every element. This function takes 3 arguments
   *     (the element, undefined, and the iterator) and should return a boolean.
   *     If the return value is true the element will be included in the returned
   *     iterator.  If it is false the element is not included.
   * @param {THIS=} opt_obj The object to be used as the value of 'this' within
   *     `f`.
   * @return {!goog.iter.Iterator<VALUE>} A new iterator in which only elements
   *     that passed the test are present.
   * @template THIS, VALUE
   */
  goog.iter.filter = function(iterable, f, opt_obj) {
    'use strict';
    var iterator = goog.iter.toIterator(iterable);
    var newIter = new goog.iter.Iterator;
    newIter.nextValueOrThrow = function() {
      'use strict';
      while (true) {
        var val = iterator.nextValueOrThrow();
        if (f.call(opt_obj, val, undefined, iterator)) {
          return val;
        }
      }
    };
  
    return newIter;
  };
  
  
  /**
   * Calls a function for every element in the iterator, and if the function
   * returns false adds the element to a new iterator.
   *
   * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
   *     to iterate over.
   * @param {
   *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator<VALUE>):boolean} f
   *     The function to call for every element. This function takes 3 arguments
   *     (the element, undefined, and the iterator) and should return a boolean.
   *     If the return value is false the element will be included in the returned
   *     iterator.  If it is true the element is not included.
   * @param {THIS=} opt_obj The object to be used as the value of 'this' within
   *     `f`.
   * @return {!goog.iter.Iterator<VALUE>} A new iterator in which only elements
   *     that did not pass the test are present.
   * @template THIS, VALUE
   */
  goog.iter.filterFalse = function(iterable, f, opt_obj) {
    'use strict';
    return goog.iter.filter(iterable, goog.functions.not(f), opt_obj);
  };
  
  
  /**
   * Creates a new iterator that returns the values in a range.  This function
   * can take 1, 2 or 3 arguments:
   * <pre>
   * range(5) same as range(0, 5, 1)
   * range(2, 5) same as range(2, 5, 1)
   * </pre>
   *
   * @param {number} startOrStop  The stop value if only one argument is provided.
   *     The start value if 2 or more arguments are provided.  If only one
   *     argument is used the start value is 0.
   * @param {number=} opt_stop  The stop value.  If left out then the first
   *     argument is used as the stop value.
   * @param {number=} opt_step  The number to increment with between each call to
   *     next.  This can be negative.
   * @return {!goog.iter.Iterator<number>} A new iterator that returns the values
   *     in the range.
   */
  goog.iter.range = function(startOrStop, opt_stop, opt_step) {
    'use strict';
    var start = 0;
    var stop = startOrStop;
    var step = opt_step || 1;
    if (arguments.length > 1) {
      start = startOrStop;
      stop = +opt_stop;
    }
    if (step == 0) {
      throw new Error('Range step argument must not be zero');
    }
  
    var newIter = new goog.iter.Iterator;
    newIter.nextValueOrThrow = function() {
      'use strict';
      if (step > 0 && start >= stop || step < 0 && start <= stop) {
        throw goog.iter.StopIteration;
      }
      var rv = start;
      start += step;
      return rv;
    };
  
    return newIter;
  };
  
  
  /**
   * Joins the values in a iterator with a delimiter.
   * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
   *     to get the values from.
   * @param {string} deliminator  The text to put between the values.
   * @return {string} The joined value string.
   * @template VALUE
   */
  goog.iter.join = function(iterable, deliminator) {
    'use strict';
    return goog.iter.toArray(iterable).join(deliminator);
  };
  
  
  /**
   * For every element in the iterator call a function and return a new iterator
   * with that value.
   *
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
   *     iterator to iterate over.
   * @param {
   *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator<VALUE>):RESULT} f
   *     The function to call for every element.  This function takes 3 arguments
   *     (the element, undefined, and the iterator) and should return a new value.
   * @param {THIS=} opt_obj The object to be used as the value of 'this' within
   *     `f`.
   * @return {!goog.iter.Iterator<RESULT>} A new iterator that returns the
   *     results of applying the function to each element in the original
   *     iterator.
   * @template THIS, VALUE, RESULT
   */
  goog.iter.map = function(iterable, f, opt_obj) {
    'use strict';
    var iterator = goog.iter.toIterator(iterable);
    var newIter = new goog.iter.Iterator;
    newIter.nextValueOrThrow = function() {
      'use strict';
      var val = iterator.nextValueOrThrow();
      return f.call(opt_obj, val, undefined, iterator);
    };
  
    return newIter;
  };
  
  
  /**
   * Passes every element of an iterator into a function and accumulates the
   * result.
   *
   * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
   *     to iterate over.
   * @param {function(this:THIS,VALUE,VALUE):VALUE} f The function to call for
   *     every element. This function takes 2 arguments (the function's previous
   *     result or the initial value, and the value of the current element).
   *     function(previousValue, currentElement) : newValue.
   * @param {VALUE} val The initial value to pass into the function on the first
   *     call.
   * @param {THIS=} opt_obj  The object to be used as the value of 'this' within
   *     f.
   * @return {VALUE} Result of evaluating f repeatedly across the values of
   *     the iterator.
   * @template THIS, VALUE
   */
  goog.iter.reduce = function(iterable, f, val, opt_obj) {
    'use strict';
    var rval = val;
    goog.iter.forEach(iterable, function(val) {
      'use strict';
      rval = f.call(opt_obj, rval, val);
    });
    return rval;
  };
  
  
  /**
   * Goes through the values in the iterator. Calls f for each of these, and if
   * any of them returns true, this returns true (without checking the rest). If
   * all return false this will return false.
   *
   * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
   *     object.
   * @param {
   *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator<VALUE>):boolean} f
   *     The function to call for every value. This function takes 3 arguments
   *     (the value, undefined, and the iterator) and should return a boolean.
   * @param {THIS=} opt_obj The object to be used as the value of 'this' within
   *     `f`.
   * @return {boolean} true if any value passes the test.
   * @template THIS, VALUE
   */
  goog.iter.some = function(iterable, f, opt_obj) {
    'use strict';
    iterable = goog.iter.toIterator(iterable);
  
    try {
      while (true) {
        if (f.call(opt_obj, iterable.nextValueOrThrow(), undefined, iterable)) {
          return true;
        }
      }
    } catch (ex) {
      if (ex !== goog.iter.StopIteration) {
        throw ex;
      }
    }
    return false;
  };
  
  
  /**
   * Goes through the values in the iterator. Calls f for each of these and if any
   * of them returns false this returns false (without checking the rest). If all
   * return true this will return true.
   *
   * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
   *     object.
   * @param {
   *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator<VALUE>):boolean} f
   *     The function to call for every value. This function takes 3 arguments
   *     (the value, undefined, and the iterator) and should return a boolean.
   * @param {THIS=} opt_obj The object to be used as the value of 'this' within
   *     `f`.
   * @return {boolean} true if every value passes the test.
   * @template THIS, VALUE
   */
  goog.iter.every = function(iterable, f, opt_obj) {
    'use strict';
    iterable = goog.iter.toIterator(iterable);
  
    try {
      while (true) {
        if (!f.call(opt_obj, iterable.nextValueOrThrow(), undefined, iterable)) {
          return false;
        }
      }
    } catch (ex) {
      if (ex !== goog.iter.StopIteration) {
        throw ex;
      }
    }
    return true;
  };
  
  
  /**
   * Takes zero or more iterables and returns one iterator that will iterate over
   * them in the order chained.
   * @param {...!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} var_args Any
   *     number of iterable objects.
   * @return {!goog.iter.Iterator<VALUE>} Returns a new iterator that will
   *     iterate over all the given iterables' contents.
   * @template VALUE
   */
  goog.iter.chain = function(var_args) {
    'use strict';
    return goog.iter.chainFromIterable(arguments);
  };
  
  
  /**
   * Takes a single iterable containing zero or more iterables and returns one
   * iterator that will iterate over each one in the order given.
   * @see https://goo.gl/5NRp5d
   * @param {goog.iter.Iterator<?>|goog.iter.Iterable} iterable The iterable of
   *     iterables to chain.
   * @return {!goog.iter.Iterator<VALUE>} Returns a new iterator that will
   *     iterate over all the contents of the iterables contained within
   *     `iterable`.
   * @template VALUE
   */
  goog.iter.chainFromIterable = function(iterable) {
    'use strict';
    var iterator = goog.iter.toIterator(iterable);
    var iter = new goog.iter.Iterator();
    var current = null;
  
    iter.nextValueOrThrow = function() {
      'use strict';
      while (true) {
        if (current == null) {
          var it = iterator.nextValueOrThrow();
          current = goog.iter.toIterator(it);
        }
        try {
          return current.nextValueOrThrow();
        } catch (ex) {
          if (ex !== goog.iter.StopIteration) {
            throw ex;
          }
          current = null;
        }
      }
    };
  
  
    return iter;
  };
  
  
  /**
   * Builds a new iterator that iterates over the original, but skips elements as
   * long as a supplied function returns true.
   * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
   *     object.
   * @param {
   *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator<VALUE>):boolean} f
   *     The function to call for every value. This function takes 3 arguments
   *     (the value, undefined, and the iterator) and should return a boolean.
   * @param {THIS=} opt_obj The object to be used as the value of 'this' within
   *     `f`.
   * @return {!goog.iter.Iterator<VALUE>} A new iterator that drops elements from
   *     the original iterator as long as `f` is true.
   * @template THIS, VALUE
   */
  goog.iter.dropWhile = function(iterable, f, opt_obj) {
    'use strict';
    var iterator = goog.iter.toIterator(iterable);
    var newIter = new goog.iter.Iterator;
    var dropping = true;
    newIter.nextValueOrThrow = function() {
      'use strict';
      while (true) {
        var val = iterator.nextValueOrThrow();
        if (dropping && f.call(opt_obj, val, undefined, iterator)) {
          continue;
        } else {
          dropping = false;
        }
        return val;
      }
    };
  
    return newIter;
  };
  
  
  /**
   * Builds a new iterator that iterates over the original, but only as long as a
   * supplied function returns true.
   * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
   *     object.
   * @param {
   *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator<VALUE>):boolean} f
   *     The function to call for every value. This function takes 3 arguments
   *     (the value, undefined, and the iterator) and should return a boolean.
   * @param {THIS=} opt_obj This is used as the 'this' object in f when called.
   * @return {!goog.iter.Iterator<VALUE>} A new iterator that keeps elements in
   *     the original iterator as long as the function is true.
   * @template THIS, VALUE
   */
  goog.iter.takeWhile = function(iterable, f, opt_obj) {
    'use strict';
    var iterator = goog.iter.toIterator(iterable);
    var iter = new goog.iter.Iterator();
    iter.nextValueOrThrow = function() {
      'use strict';
      var val = iterator.nextValueOrThrow();
      if (f.call(opt_obj, val, undefined, iterator)) {
        return val;
      }
      throw goog.iter.StopIteration;
    };
  
    return iter;
  };
  
  
  /**
   * Converts the iterator to an array
   * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
   *     to convert to an array.
   * @return {!Array<VALUE>} An array of the elements the iterator iterates over.
   * @template VALUE
   */
  goog.iter.toArray = function(iterable) {
    'use strict';
    // Fast path for array-like.
    if (goog.isArrayLike(iterable)) {
      return goog.array.toArray(/** @type {!IArrayLike<?>} */ (iterable));
    }
    iterable = goog.iter.toIterator(iterable);
    var array = [];
    goog.iter.forEach(iterable, function(val) {
      'use strict';
      array.push(val);
    });
    return array;
  };
  
  
  /**
   * Iterates over two iterables and returns true if they contain the same
   * sequence of elements and have the same length.
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable1 The first
   *     iterable object.
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable2 The second
   *     iterable object.
   * @param {function(VALUE,VALUE):boolean=} opt_equalsFn Optional comparison
   *     function.
   *     Should take two arguments to compare, and return true if the arguments
   *     are equal. Defaults to {@link goog.array.defaultCompareEquality} which
   *     compares the elements using the built-in '===' operator.
   * @return {boolean} true if the iterables contain the same sequence of elements
   *     and have the same length.
   * @template VALUE
   */
  goog.iter.equals = function(iterable1, iterable2, opt_equalsFn) {
    'use strict';
    var fillValue = {};
    var pairs = goog.iter.zipLongest(fillValue, iterable1, iterable2);
    var equalsFn = opt_equalsFn || goog.array.defaultCompareEquality;
    return goog.iter.every(pairs, function(pair) {
      'use strict';
      return equalsFn(pair[0], pair[1]);
    });
  };
  
  
  /**
   * Advances the iterator to the next position, returning the given default value
   * instead of throwing an exception if the iterator has no more entries.
   * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterable
   *     object.
   * @param {VALUE} defaultValue The value to return if the iterator is empty.
   * @return {VALUE} The next item in the iteration, or defaultValue if the
   *     iterator was empty.
   * @template VALUE
   */
  goog.iter.nextOrValue = function(iterable, defaultValue) {
    'use strict';
    try {
      return goog.iter.toIterator(iterable).nextValueOrThrow();
    } catch (e) {
      if (e != goog.iter.StopIteration) {
        throw e;
      }
      return defaultValue;
    }
  };
  
  
  /**
   * Cartesian product of zero or more sets.  Gives an iterator that gives every
   * combination of one element chosen from each set.  For example,
   * ([1, 2], [3, 4]) gives ([1, 3], [1, 4], [2, 3], [2, 4]).
   * @see http://docs.python.org/library/itertools.html#itertools.product
   * @param {...!IArrayLike<VALUE>} var_args Zero or more sets, as
   *     arrays.
   * @return {!goog.iter.Iterator<!Array<VALUE>>} An iterator that gives each
   *     n-tuple (as an array).
   * @template VALUE
   */
  goog.iter.product = function(var_args) {
    'use strict';
    var someArrayEmpty = Array.prototype.some.call(arguments, function(arr) {
      'use strict';
      return !arr.length;
    });
  
    // An empty set in a cartesian product gives an empty set.
    if (someArrayEmpty || !arguments.length) {
      return new goog.iter.Iterator();
    }
  
    var iter = new goog.iter.Iterator();
    var arrays = arguments;
  
    // The first indices are [0, 0, ...]
    /** @type {?Array<number>} */
    var indicies = goog.array.repeat(0, arrays.length);
  
    iter.nextValueOrThrow = function() {
      'use strict';
      if (indicies) {
        var retVal = goog.array.map(indicies, function(valueIndex, arrayIndex) {
          'use strict';
          return arrays[arrayIndex][valueIndex];
        });
  
        // Generate the next-largest indices for the next call.
        // Increase the rightmost index. If it goes over, increase the next
        // rightmost (like carry-over addition).
        for (var i = indicies.length - 1; i >= 0; i--) {
          // Assertion prevents compiler warning below.
          goog.asserts.assert(indicies);
          if (indicies[i] < arrays[i].length - 1) {
            indicies[i]++;
            break;
          }
  
          // We're at the last indices (the last element of every array), so
          // the iteration is over on the next call.
          if (i == 0) {
            indicies = null;
            break;
          }
          // Reset the index in this column and loop back to increment the
          // next one.
          indicies[i] = 0;
        }
        return retVal;
      }
  
      throw goog.iter.StopIteration;
    };
  
  
    return iter;
  };
  
  
  /**
   * Create an iterator to cycle over the iterable's elements indefinitely.
   * For example, ([1, 2, 3]) would return : 1, 2, 3, 1, 2, 3, ...
   * @see: http://docs.python.org/library/itertools.html#itertools.cycle.
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
   *     iterable object.
   * @return {!goog.iter.Iterator<VALUE>} An iterator that iterates indefinitely
   *     over the values in `iterable`.
   * @template VALUE
   */
  goog.iter.cycle = function(iterable) {
    'use strict';
    var baseIterator = goog.iter.toIterator(iterable);
  
    // We maintain a cache to store the iterable elements as we iterate
    // over them. The cache is used to return elements once we have
    // iterated over the iterable once.
    var cache = [];
    var cacheIndex = 0;
  
    var iter = new goog.iter.Iterator();
  
    // This flag is set after the iterable is iterated over once
    var useCache = false;
  
    iter.nextValueOrThrow = function() {
      'use strict';
      var returnElement = null;
  
      // Pull elements off the original iterator if not using cache
      if (!useCache) {
        try {
          // Return the element from the iterable
          returnElement = baseIterator.nextValueOrThrow();
          cache.push(returnElement);
          return returnElement;
        } catch (e) {
          // If an exception other than StopIteration is thrown
          // or if there are no elements to iterate over (the iterable was empty)
          // throw an exception
          if (e != goog.iter.StopIteration || goog.array.isEmpty(cache)) {
            throw e;
          }
          // set useCache to true after we know that a 'StopIteration' exception
          // was thrown and the cache is not empty (to handle the 'empty iterable'
          // use case)
          useCache = true;
        }
      }
  
      returnElement = cache[cacheIndex];
      cacheIndex = (cacheIndex + 1) % cache.length;
  
      return returnElement;
    };
  
  
    return iter;
  };
  
  
  /**
   * Creates an iterator that counts indefinitely from a starting value.
   * @see http://docs.python.org/2/library/itertools.html#itertools.count
   * @param {number=} opt_start The starting value. Default is 0.
   * @param {number=} opt_step The number to increment with between each call to
   *     next. Negative and floating point numbers are allowed. Default is 1.
   * @return {!goog.iter.Iterator<number>} A new iterator that returns the values
   *     in the series.
   */
  goog.iter.count = function(opt_start, opt_step) {
    'use strict';
    var counter = opt_start || 0;
    var step = (opt_step !== undefined) ? opt_step : 1;
    var iter = new goog.iter.Iterator();
  
    iter.nextValueOrThrow = function() {
      'use strict';
      var returnValue = counter;
      counter += step;
      return returnValue;
    };
  
  
    return iter;
  };
  
  
  /**
   * Creates an iterator that returns the same object or value repeatedly.
   * @param {VALUE} value Any object or value to repeat.
   * @return {!goog.iter.Iterator<VALUE>} A new iterator that returns the
   *     repeated value.
   * @template VALUE
   */
  goog.iter.repeat = function(value) {
    'use strict';
    var iter = new goog.iter.Iterator();
  
    iter.nextValueOrThrow = goog.functions.constant(value);
  
  
    return iter;
  };
  
  
  /**
   * Creates an iterator that returns running totals from the numbers in
   * `iterable`. For example, the array {@code [1, 2, 3, 4, 5]} yields
   * {@code 1 -> 3 -> 6 -> 10 -> 15}.
   * @see http://docs.python.org/3.2/library/itertools.html#itertools.accumulate
   * @param {!goog.iter.Iterator<number>|!goog.iter.Iterable} iterable The
   *     iterable of numbers to accumulate.
   * @return {!goog.iter.Iterator<number>} A new iterator that returns the
   *     numbers in the series.
   */
  goog.iter.accumulate = function(iterable) {
    'use strict';
    var iterator = goog.iter.toIterator(iterable);
    var total = 0;
    var iter = new goog.iter.Iterator();
  
    iter.nextValueOrThrow = function() {
      'use strict';
      total += iterator.nextValueOrThrow();
      return total;
    };
  
  
    return iter;
  };
  
  
  /**
   * Creates an iterator that returns arrays containing the ith elements from the
   * provided iterables. The returned arrays will be the same size as the number
   * of iterables given in `var_args`. Once the shortest iterable is
   * exhausted, subsequent calls to `nextValueOrThrow()` will throw
   * `goog.iter.StopIteration`.
   * @see http://docs.python.org/2/library/itertools.html#itertools.izip
   * @param {...!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} var_args Any
   *     number of iterable objects.
   * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator that returns
   *     arrays of elements from the provided iterables.
   * @template VALUE
   */
  goog.iter.zip = function(var_args) {
    'use strict';
    var args = arguments;
    var iter = new goog.iter.Iterator();
  
    if (args.length > 0) {
      var iterators = goog.array.map(args, goog.iter.toIterator);
      iter.nextValueOrThrow = function() {
        'use strict';
        var arr = goog.array.map(iterators, function(it) {
          'use strict';
          return it.nextValueOrThrow();
        });
        return arr;
      };
    }
  
    return iter;
  };
  
  
  /**
   * Creates an iterator that returns arrays containing the ith elements from the
   * provided iterables. The returned arrays will be the same size as the number
   * of iterables given in `var_args`. Shorter iterables will be extended
   * with `fillValue`. Once the longest iterable is exhausted, subsequent
   * calls to `nextValueOrThrow()` will throw `goog.iter.StopIteration`.
   * @see http://docs.python.org/2/library/itertools.html#itertools.izip_longest
   * @param {VALUE} fillValue The object or value used to fill shorter iterables.
   * @param {...!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} var_args Any
   *     number of iterable objects.
   * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator that returns
   *     arrays of elements from the provided iterables.
   * @template VALUE
   */
  goog.iter.zipLongest = function(fillValue, var_args) {
    'use strict';
    var args = Array.prototype.slice.call(arguments, 1);
    var iter = new goog.iter.Iterator();
  
    if (args.length > 0) {
      var iterators = goog.array.map(args, goog.iter.toIterator);
  
      iter.nextValueOrThrow = function() {
        'use strict';
        var iteratorsHaveValues = false;  // false when all iterators are empty.
        var arr = goog.array.map(iterators, function(it) {
          'use strict';
          var returnValue;
          try {
            returnValue = it.nextValueOrThrow();
            // Iterator had a value, so we've not exhausted the iterators.
            // Set flag accordingly.
            iteratorsHaveValues = true;
          } catch (ex) {
            if (ex !== goog.iter.StopIteration) {
              throw ex;
            }
            returnValue = fillValue;
          }
          return returnValue;
        });
  
        if (!iteratorsHaveValues) {
          throw goog.iter.StopIteration;
        }
        return arr;
      };
    }
  
    return iter;
  };
  
  
  /**
   * Creates an iterator that filters `iterable` based on a series of
   * `selectors`. On each call to `nextValueOrThrow()`, one item is taken from
   * both the `iterable` and `selectors` iterators. If the item from
   * `selectors` evaluates to true, the item from `iterable` is given.
   * Otherwise, it is skipped. Once either `iterable` or `selectors`
   * is exhausted, subsequent calls to `nextValueOrThrow()` will throw
   * `goog.iter.StopIteration`.
   * @see http://docs.python.org/2/library/itertools.html#itertools.compress
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
   *     iterable to filter.
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} selectors An
   *     iterable of items to be evaluated in a boolean context to determine if
   *     the corresponding element in `iterable` should be included in the
   *     result.
   * @return {!goog.iter.Iterator<VALUE>} A new iterator that returns the
   *     filtered values.
   * @template VALUE
   */
  goog.iter.compress = function(iterable, selectors) {
    'use strict';
    var selectorIterator = goog.iter.toIterator(selectors);
  
    return goog.iter.filter(iterable, function() {
      'use strict';
      return !!selectorIterator.nextValueOrThrow();
    });
  };
  
  
  
  /**
   * Implements the `goog.iter.groupBy` iterator.
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
   *     iterable to group.
   * @param {function(VALUE): KEY=} opt_keyFunc  Optional function for
   *     determining the key value for each group in the `iterable`. Default
   *     is the identity function.
   * @constructor
   * @extends {goog.iter.Iterator<!Array<?>>}
   * @template KEY, VALUE
   * @private
   */
  goog.iter.GroupByIterator_ = function(iterable, opt_keyFunc) {
    'use strict';
    /**
     * The iterable to group, coerced to an iterator.
     * @type {!goog.iter.Iterator}
     */
    this.iterator = goog.iter.toIterator(iterable);
  
    /**
     * A function for determining the key value for each element in the iterable.
     * If no function is provided, the identity function is used and returns the
     * element unchanged.
     * @type {function(VALUE): KEY}
     */
    this.keyFunc = opt_keyFunc || goog.functions.identity;
  
    /**
     * The target key for determining the start of a group.
     * @type {KEY}
     */
    this.targetKey;
  
    /**
     * The current key visited during iteration.
     * @type {KEY}
     */
    this.currentKey;
  
    /**
     * The current value being added to the group.
     * @type {VALUE}
     */
    this.currentValue;
  };
  goog.inherits(goog.iter.GroupByIterator_, goog.iter.Iterator);
  
  
  /** @override */
  goog.iter.GroupByIterator_.prototype.nextValueOrThrow = function() {
    'use strict';
    while (this.currentKey == this.targetKey) {
      this.currentValue =
          this.iterator.nextValueOrThrow();  // Exits on StopIteration
      this.currentKey = this.keyFunc(this.currentValue);
    }
    this.targetKey = this.currentKey;
    return [this.currentKey, this.groupItems_(this.targetKey)];
  };
  
  
  
  /**
   * Performs the grouping of objects using the given key.
   * @param {KEY} targetKey  The target key object for the group.
   * @return {!Array<VALUE>} An array of grouped objects.
   * @private
   */
  goog.iter.GroupByIterator_.prototype.groupItems_ = function(targetKey) {
    'use strict';
    var arr = [];
    while (this.currentKey == targetKey) {
      arr.push(this.currentValue);
      try {
        this.currentValue = this.iterator.nextValueOrThrow();
      } catch (ex) {
        if (ex !== goog.iter.StopIteration) {
          throw ex;
        }
        break;
      }
      this.currentKey = this.keyFunc(this.currentValue);
    }
    return arr;
  };
  
  
  /**
   * Creates an iterator that returns arrays containing elements from the
   * `iterable` grouped by a key value. For iterables with repeated
   * elements (i.e. sorted according to a particular key function), this function
   * has a `uniq`-like effect. For example, grouping the array:
   * {@code [A, B, B, C, C, A]} produces
   * {@code [A, [A]], [B, [B, B]], [C, [C, C]], [A, [A]]}.
   * @see http://docs.python.org/2/library/itertools.html#itertools.groupby
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
   *     iterable to group.
   * @param {function(VALUE): KEY=} opt_keyFunc  Optional function for
   *     determining the key value for each group in the `iterable`. Default
   *     is the identity function.
   * @return {!goog.iter.Iterator<!Array<?>>} A new iterator that returns
   *     arrays of consecutive key and groups.
   * @template KEY, VALUE
   */
  goog.iter.groupBy = function(iterable, opt_keyFunc) {
    'use strict';
    return new goog.iter.GroupByIterator_(iterable, opt_keyFunc);
  };
  
  
  /**
   * Gives an iterator that gives the result of calling the given function
   * <code>f</code> with the arguments taken from the next element from
   * <code>iterable</code> (the elements are expected to also be iterables).
   *
   * Similar to {@see goog.iter.map} but allows the function to accept multiple
   * arguments from the iterable.
   *
   * @param {!goog.iter.Iterator<?>|!goog.iter.Iterable} iterable The iterable of
   *     iterables to iterate over.
   * @param {function(this:THIS,...*):RESULT} f The function to call for every
   *     element.  This function takes N+2 arguments, where N represents the
   *     number of items from the next element of the iterable. The two
   *     additional arguments passed to the function are undefined and the
   *     iterator itself. The function should return a new value.
   * @param {THIS=} opt_obj The object to be used as the value of 'this' within
   *     `f`.
   * @return {!goog.iter.Iterator<RESULT>} A new iterator that returns the
   *     results of applying the function to each element in the original
   *     iterator.
   * @template THIS, RESULT
   */
  goog.iter.starMap = function(iterable, f, opt_obj) {
    'use strict';
    var iterator = goog.iter.toIterator(iterable);
    var iter = new goog.iter.Iterator();
  
    iter.nextValueOrThrow = function() {
      'use strict';
      var args = goog.iter.toArray(iterator.nextValueOrThrow());
      return f.apply(opt_obj, goog.array.concat(args, undefined, iterator));
    };
  
  
    return iter;
  };
  
  
  /**
   * Returns an array of iterators each of which can iterate over the values in
   * `iterable` without advancing the others.
   * @see http://docs.python.org/2/library/itertools.html#itertools.tee
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
   *     iterable to tee.
   * @param {number=} opt_num  The number of iterators to create. Default is 2.
   * @return {!Array<goog.iter.Iterator<VALUE>>} An array of iterators.
   * @template VALUE
   */
  goog.iter.tee = function(iterable, opt_num) {
    'use strict';
    var iterator = goog.iter.toIterator(iterable);
    var num = (typeof opt_num === 'number') ? opt_num : 2;
    var buffers = goog.array.map(goog.array.range(num), function() {
      'use strict';
      return [];
    });
  
    var addNextIteratorValueToBuffers = function() {
      'use strict';
      var val = iterator.nextValueOrThrow();
      goog.array.forEach(buffers, function(buffer) {
        'use strict';
        buffer.push(val);
      });
    };
  
    var createIterator = function(buffer) {
      'use strict';
      // Each tee'd iterator has an associated buffer (initially empty). When a
      // tee'd iterator's buffer is empty, it calls
      // addNextIteratorValueToBuffers(), adding the next value to all tee'd
      // iterators' buffers, and then returns that value. This allows each
      // iterator to be advanced independently.
      var iter = new goog.iter.Iterator();
  
      iter.nextValueOrThrow = function() {
        'use strict';
        if (goog.array.isEmpty(buffer)) {
          addNextIteratorValueToBuffers();
        }
        goog.asserts.assert(!goog.array.isEmpty(buffer));
        return buffer.shift();
      };
  
  
      return iter;
    };
  
    return goog.array.map(buffers, createIterator);
  };
  
  
  /**
   * Creates an iterator that returns arrays containing a count and an element
   * obtained from the given `iterable`.
   * @see http://docs.python.org/2/library/functions.html#enumerate
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
   *     iterable to enumerate.
   * @param {number=} opt_start  Optional starting value. Default is 0.
   * @return {!goog.iter.Iterator<!Array<?>>} A new iterator containing
   *     count/item pairs.
   * @template VALUE
   */
  goog.iter.enumerate = function(iterable, opt_start) {
    'use strict';
    return goog.iter.zip(goog.iter.count(opt_start), iterable);
  };
  
  
  /**
   * Creates an iterator that returns the first `limitSize` elements from an
   * iterable. If this number is greater than the number of elements in the
   * iterable, all the elements are returned.
   * @see http://goo.gl/V0sihp Inspired by the limit iterator in Guava.
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
   *     iterable to limit.
   * @param {number} limitSize  The maximum number of elements to return.
   * @return {!goog.iter.Iterator<VALUE>} A new iterator containing
   *     `limitSize` elements.
   * @template VALUE
   */
  goog.iter.limit = function(iterable, limitSize) {
    'use strict';
    goog.asserts.assert(goog.math.isInt(limitSize) && limitSize >= 0);
  
    var iterator = goog.iter.toIterator(iterable);
  
    var iter = new goog.iter.Iterator();
    var remaining = limitSize;
  
    iter.nextValueOrThrow = function() {
      'use strict';
      if (remaining-- > 0) {
        return iterator.nextValueOrThrow();
      }
      throw goog.iter.StopIteration;
    };
  
  
    return iter;
  };
  
  
  /**
   * Creates an iterator that is advanced `count` steps ahead. Consumed
   * values are silently discarded. If `count` is greater than the number
   * of elements in `iterable`, an empty iterator is returned. Subsequent
   * calls to `nextValueOrThrow()` will throw `goog.iter.StopIteration`.
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
   *     iterable to consume.
   * @param {number} count  The number of elements to consume from the iterator.
   * @return {!goog.iter.Iterator<VALUE>} An iterator advanced zero or more steps
   *     ahead.
   * @template VALUE
   */
  goog.iter.consume = function(iterable, count) {
    'use strict';
    goog.asserts.assert(goog.math.isInt(count) && count >= 0);
  
    var iterator = goog.iter.toIterator(iterable);
  
    while (count-- > 0) {
      goog.iter.nextOrValue(iterator, null);
    }
  
    return iterator;
  };
  
  
  /**
   * Creates an iterator that returns a range of elements from an iterable.
   * Similar to {@see goog.array.slice} but does not support negative indexes.
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
   *     iterable to slice.
   * @param {number} start  The index of the first element to return.
   * @param {number=} opt_end  The index after the last element to return. If
   *     defined, must be greater than or equal to `start`.
   * @return {!goog.iter.Iterator<VALUE>} A new iterator containing a slice of
   *     the original.
   * @template VALUE
   */
  goog.iter.slice = function(iterable, start, opt_end) {
    'use strict';
    goog.asserts.assert(goog.math.isInt(start) && start >= 0);
  
    var iterator = goog.iter.consume(iterable, start);
  
    if (typeof opt_end === 'number') {
      goog.asserts.assert(goog.math.isInt(opt_end) && opt_end >= start);
      iterator = goog.iter.limit(iterator, opt_end - start /* limitSize */);
    }
  
    return iterator;
  };
  
  
  /**
   * Checks an array for duplicate elements.
   * @param {?IArrayLike<VALUE>} arr The array to check for
   *     duplicates.
   * @return {boolean} True, if the array contains duplicates, false otherwise.
   * @private
   * @template VALUE
   */
  // TODO(user): Consider moving this into goog.array as a public function.
  goog.iter.hasDuplicates_ = function(arr) {
    'use strict';
    var deduped = [];
    goog.array.removeDuplicates(arr, deduped);
    return arr.length != deduped.length;
  };
  
  
  /**
   * Creates an iterator that returns permutations of elements in
   * `iterable`.
   *
   * Permutations are obtained by taking the Cartesian product of
   * `opt_length` iterables and filtering out those with repeated
   * elements. For example, the permutations of {@code [1,2,3]} are
   * {@code [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]}.
   * @see http://docs.python.org/2/library/itertools.html#itertools.permutations
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
   *     iterable from which to generate permutations.
   * @param {number=} opt_length Length of each permutation. If omitted, defaults
   *     to the length of `iterable`.
   * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator containing the
   *     permutations of `iterable`.
   * @template VALUE
   */
  goog.iter.permutations = function(iterable, opt_length) {
    'use strict';
    var elements = goog.iter.toArray(iterable);
    var length = (typeof opt_length === 'number') ? opt_length : elements.length;
  
    var sets = goog.array.repeat(elements, length);
    var product = goog.iter.product.apply(undefined, sets);
  
    return goog.iter.filter(product, function(arr) {
      'use strict';
      return !goog.iter.hasDuplicates_(arr);
    });
  };
  
  
  /**
   * Creates an iterator that returns combinations of elements from
   * `iterable`.
   *
   * Combinations are obtained by taking the {@see goog.iter.permutations} of
   * `iterable` and filtering those whose elements appear in the order they
   * are encountered in `iterable`. For example, the 3-length combinations
   * of {@code [0,1,2,3]} are {@code [[0,1,2], [0,1,3], [0,2,3], [1,2,3]]}.
   * @see http://docs.python.org/2/library/itertools.html#itertools.combinations
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
   *     iterable from which to generate combinations.
   * @param {number} length The length of each combination.
   * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator containing
   *     combinations from the `iterable`.
   * @template VALUE
   */
  goog.iter.combinations = function(iterable, length) {
    'use strict';
    var elements = goog.iter.toArray(iterable);
    var indexes = goog.iter.range(elements.length);
    var indexIterator = goog.iter.permutations(indexes, length);
    // sortedIndexIterator will now give arrays of with the given length that
    // indicate what indexes into "elements" should be returned on each iteration.
    var sortedIndexIterator = goog.iter.filter(indexIterator, function(arr) {
      'use strict';
      return goog.array.isSorted(arr);
    });
  
    var iter = new goog.iter.Iterator();
  
    function getIndexFromElements(index) {
      return elements[index];
    }
  
    iter.nextValueOrThrow = function() {
      'use strict';
      return goog.array.map(
          sortedIndexIterator.nextValueOrThrow(), getIndexFromElements);
    };
  
  
    return iter;
  };
  
  
  /**
   * Creates an iterator that returns combinations of elements from
   * `iterable`, with repeated elements possible.
   *
   * Combinations are obtained by taking the Cartesian product of `length`
   * iterables and filtering those whose elements appear in the order they are
   * encountered in `iterable`. For example, the 2-length combinations of
   * {@code [1,2,3]} are {@code [[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]]}.
   * @see https://goo.gl/C0yXe4
   * @see https://goo.gl/djOCsk
   * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
   *     iterable to combine.
   * @param {number} length The length of each combination.
   * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator containing
   *     combinations from the `iterable`.
   * @template VALUE
   */
  goog.iter.combinationsWithReplacement = function(iterable, length) {
    'use strict';
    var elements = goog.iter.toArray(iterable);
    var indexes = goog.array.range(elements.length);
    var sets = goog.array.repeat(indexes, length);
    var indexIterator = goog.iter.product.apply(undefined, sets);
    // sortedIndexIterator will now give arrays of with the given length that
    // indicate what indexes into "elements" should be returned on each iteration.
    var sortedIndexIterator = goog.iter.filter(indexIterator, function(arr) {
      'use strict';
      return goog.array.isSorted(arr);
    });
  
    var iter = new goog.iter.Iterator();
  
    function getIndexFromElements(index) {
      return elements[index];
    }
  
    iter.nextValueOrThrow = function() {
      'use strict';
      return goog.array.map(
          /** @type {!Array<number>} */
          (sortedIndexIterator.nextValueOrThrow()), getIndexFromElements);
    };
  
  
    return iter;
  };
  