src/third_party/google_input_tools/third_party/closure_library/closure/goog/iter/iter.js

   1 // Copyright 2007 The Closure Library Authors. All Rights Reserved.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //      http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS-IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 /**
  16  * @fileoverview Python style iteration utilities.
  17  * @author arv@google.com (Erik Arvidsson)
  18  */
  19
  20
  21 goog.provide('goog.iter');
  22 goog.provide('goog.iter.Iterable');
  23 goog.provide('goog.iter.Iterator');
  24 goog.provide('goog.iter.StopIteration');
  25
  26 goog.require('goog.array');
  27 goog.require('goog.asserts');
  28 goog.require('goog.functions');
  29 goog.require('goog.math');
  30
  31
  32 /**
  33  * @typedef {goog.iter.Iterator|{length:number}|{__iterator__}}
  34  */
  35 goog.iter.Iterable;
  36
  37
  38 // For script engines that already support iterators.
  39 if ('StopIteration' in goog.global) {
  40   /**
  41    * Singleton Error object that is used to terminate iterations.
  42    * @type {Error}
  43    */
  44   goog.iter.StopIteration = goog.global['StopIteration'];
  45 } else {
  46   /**
  47    * Singleton Error object that is used to terminate iterations.
  48    * @type {Error}
  49    * @suppress {duplicate}
  50    */
  51   goog.iter.StopIteration = Error('StopIteration');
  52 }
  53
  54
  55
  56 /**
  57  * Class/interface for iterators.  An iterator needs to implement a {@code next}
  58  * method and it needs to throw a {@code goog.iter.StopIteration} when the
  59  * iteration passes beyond the end.  Iterators have no {@code hasNext} method.
  60  * It is recommended to always use the helper functions to iterate over the
  61  * iterator or in case you are only targeting JavaScript 1.7 for in loops.
  62  * @constructor
  63  * @template VALUE
  64  */
  65 goog.iter.Iterator = function() {};
  66
  67
  68 /**
  69  * Returns the next value of the iteration.  This will throw the object
  70  * {@see goog.iter#StopIteration} when the iteration passes the end.
  71  * @return {VALUE} Any object or value.
  72  */
  73 goog.iter.Iterator.prototype.next = function() {
  74   throw goog.iter.StopIteration;
  75 };
  76
  77
  78 /**
  79  * Returns the {@code Iterator} object itself.  This is used to implement
  80  * the iterator protocol in JavaScript 1.7
  81  * @param {boolean=} opt_keys  Whether to return the keys or values. Default is
  82  *     to only return the values.  This is being used by the for-in loop (true)
  83  *     and the for-each-in loop (false).  Even though the param gives a hint
  84  *     about what the iterator will return there is no guarantee that it will
  85  *     return the keys when true is passed.
  86  * @return {!goog.iter.Iterator.<VALUE>} The object itself.
  87  */
  88 goog.iter.Iterator.prototype.__iterator__ = function(opt_keys) {
  89   return this;
  90 };
  91
  92
  93 /**
  94  * Returns an iterator that knows how to iterate over the values in the object.
  95  * @param {goog.iter.Iterator.<VALUE>|goog.iter.Iterable} iterable  If the
  96  *     object is an iterator it will be returned as is.  If the object has an
  97  *     {@code __iterator__} method that will be called to get the value
  98  *     iterator.  If the object is an array-like object we create an iterator
  99  *     for that.
 100  * @return {!goog.iter.Iterator.<VALUE>} An iterator that knows how to iterate
 101  *     over the values in {@code iterable}.
 102  * @template VALUE
 103  */
 104 goog.iter.toIterator = function(iterable) {
 105   if (iterable instanceof goog.iter.Iterator) {
 106     return iterable;
 107   }
 108   if (typeof iterable.__iterator__ == 'function') {
 109     return iterable.__iterator__(false);
 110   }
 111   if (goog.isArrayLike(iterable)) {
 112     var i = 0;
 113     var newIter = new goog.iter.Iterator;
 114     newIter.next = function() {
 115       while (true) {
 116         if (i >= iterable.length) {
 117           throw goog.iter.StopIteration;
 118         }
 119         // Don't include deleted elements.
 120         if (!(i in iterable)) {
 121           i++;
 122           continue;
 123         }
 124         return iterable[i++];
 125       }
 126     };
 127     return newIter;
 128   }
 129
 130
 131   // TODO(arv): Should we fall back on goog.structs.getValues()?
 132   throw Error('Not implemented');
 133 };
 134
 135
 136 /**
 137  * Calls a function for each element in the iterator with the element of the
 138  * iterator passed as argument.
 139  *
 140  * @param {goog.iter.Iterator.<VALUE>|goog.iter.Iterable} iterable  The iterator
 141  *     to iterate over. If the iterable is an object {@code toIterator} will be
 142  *     called on it.
 143  * @param {function(this:THIS,VALUE,undefined,goog.iter.Iterator.<VALUE>)|
 144  *         function(this:THIS,number,undefined,goog.iter.Iterator.<VALUE>)} f
 145  *     The function to call for every element.  This function takes 3 arguments
 146  *     (the element, undefined, and the iterator) and the return value is
 147  *     irrelevant.  The reason for passing undefined as the second argument is
 148  *     so that the same function can be used in {@see goog.array#forEach} as
 149  *     well as others.
 150  * @param {THIS=} opt_obj  The object to be used as the value of 'this' within
 151  *     {@code f}.
 152  * @template THIS, VALUE
 153  */
 154 goog.iter.forEach = function(iterable, f, opt_obj) {
 155   if (goog.isArrayLike(iterable)) {
 156     /** @preserveTry */
 157     try {
 158       // NOTES: this passes the index number to the second parameter
 159       // of the callback contrary to the documentation above.
 160       goog.array.forEach(/** @type {goog.array.ArrayLike} */(iterable), f,
 161                          opt_obj);
 162     } catch (ex) {
 163       if (ex !== goog.iter.StopIteration) {
 164         throw ex;
 165       }
 166     }
 167   } else {
 168     iterable = goog.iter.toIterator(iterable);
 169     /** @preserveTry */
 170     try {
 171       while (true) {
 172         f.call(opt_obj, iterable.next(), undefined, iterable);
 173       }
 174     } catch (ex) {
 175       if (ex !== goog.iter.StopIteration) {
 176         throw ex;
 177       }
 178     }
 179   }
 180 };
 181
 182
 183 /**
 184  * Calls a function for every element in the iterator, and if the function
 185  * returns true adds the element to a new iterator.
 186  *
 187  * @param {goog.iter.Iterator.<VALUE>|goog.iter.Iterable} iterable The iterator
 188  *     to iterate over.
 189  * @param {
 190  *     function(this:THIS,VALUE,undefined,goog.iter.Iterator.<VALUE>):boolean} f
 191  *     The function to call for every element. This function takes 3 arguments
 192  *     (the element, undefined, and the iterator) and should return a boolean.
 193  *     If the return value is true the element will be included in the returned
 194  *     iterator.  If it is false the element is not included.
 195  * @param {THIS=} opt_obj The object to be used as the value of 'this' within
 196  *     {@code f}.
 197  * @return {!goog.iter.Iterator.<VALUE>} A new iterator in which only elements
 198  *     that passed the test are present.
 199  * @template THIS, VALUE
 200  */
 201 goog.iter.filter = function(iterable, f, opt_obj) {
 202   var iterator = goog.iter.toIterator(iterable);
 203   var newIter = new goog.iter.Iterator;
 204   newIter.next = function() {
 205     while (true) {
 206       var val = iterator.next();
 207       if (f.call(opt_obj, val, undefined, iterator)) {
 208         return val;
 209       }
 210     }
 211   };
 212   return newIter;
 213 };
 214
 215
 216 /**
 217  * Calls a function for every element in the iterator, and if the function
 218  * returns false adds the element to a new iterator.
 219  *
 220  * @param {goog.iter.Iterator.<VALUE>|goog.iter.Iterable} iterable The iterator
 221  *     to iterate over.
 222  * @param {
 223  *     function(this:THIS,VALUE,undefined,goog.iter.Iterator.<VALUE>):boolean} f
 224  *     The function to call for every element. This function takes 3 arguments
 225  *     (the element, undefined, and the iterator) and should return a boolean.
 226  *     If the return value is false the element will be included in the returned
 227  *     iterator.  If it is true the element is not included.
 228  * @param {THIS=} opt_obj The object to be used as the value of 'this' within
 229  *     {@code f}.
 230  * @return {!goog.iter.Iterator.<VALUE>} A new iterator in which only elements
 231  *     that did not pass the test are present.
 232  * @template THIS, VALUE
 233  */
 234 goog.iter.filterFalse = function(iterable, f, opt_obj) {
 235   return goog.iter.filter(iterable, goog.functions.not(f), opt_obj);
 236 };
 237
 238
 239 /**
 240  * Creates a new iterator that returns the values in a range.  This function
 241  * can take 1, 2 or 3 arguments:
 242  * <pre>
 243  * range(5) same as range(0, 5, 1)
 244  * range(2, 5) same as range(2, 5, 1)
 245  * </pre>
 246  *
 247  * @param {number} startOrStop  The stop value if only one argument is provided.
 248  *     The start value if 2 or more arguments are provided.  If only one
 249  *     argument is used the start value is 0.
 250  * @param {number=} opt_stop  The stop value.  If left out then the first
 251  *     argument is used as the stop value.
 252  * @param {number=} opt_step  The number to increment with between each call to
 253  *     next.  This can be negative.
 254  * @return {!goog.iter.Iterator.<number>} A new iterator that returns the values
 255  *     in the range.
 256  */
 257 goog.iter.range = function(startOrStop, opt_stop, opt_step) {
 258   var start = 0;
 259   var stop = startOrStop;
 260   var step = opt_step || 1;
 261   if (arguments.length > 1) {
 262     start = startOrStop;
 263     stop = opt_stop;
 264   }
 265   if (step == 0) {
 266     throw Error('Range step argument must not be zero');
 267   }
 268
 269   var newIter = new goog.iter.Iterator;
 270   newIter.next = function() {
 271     if (step > 0 && start >= stop || step < 0 && start <= stop) {
 272       throw goog.iter.StopIteration;
 273     }
 274     var rv = start;
 275     start += step;
 276     return rv;
 277   };
 278   return newIter;
 279 };
 280
 281
 282 /**
 283  * Joins the values in a iterator with a delimiter.
 284  * @param {goog.iter.Iterator.<VALUE>|goog.iter.Iterable} iterable The iterator
 285  *     to get the values from.
 286  * @param {string} deliminator  The text to put between the values.
 287  * @return {string} The joined value string.
 288  * @template VALUE
 289  */
 290 goog.iter.join = function(iterable, deliminator) {
 291   return goog.iter.toArray(iterable).join(deliminator);
 292 };
 293
 294
 295 /**
 296  * For every element in the iterator call a function and return a new iterator
 297  * with that value.
 298  *
 299  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable The
 300  *     iterator to iterate over.
 301  * @param {
 302  *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator.<VALUE>):RESULT} f
 303  *     The function to call for every element.  This function takes 3 arguments
 304  *     (the element, undefined, and the iterator) and should return a new value.
 305  * @param {THIS=} opt_obj The object to be used as the value of 'this' within
 306  *     {@code f}.
 307  * @return {!goog.iter.Iterator.<RESULT>} A new iterator that returns the
 308  *     results of applying the function to each element in the original
 309  *     iterator.
 310  * @template THIS, VALUE, RESULT
 311  */
 312 goog.iter.map = function(iterable, f, opt_obj) {
 313   var iterator = goog.iter.toIterator(iterable);
 314   var newIter = new goog.iter.Iterator;
 315   newIter.next = function() {
 316     var val = iterator.next();
 317     return f.call(opt_obj, val, undefined, iterator);
 318   };
 319   return newIter;
 320 };
 321
 322
 323 /**
 324  * Passes every element of an iterator into a function and accumulates the
 325  * result.
 326  *
 327  * @param {goog.iter.Iterator.<VALUE>|goog.iter.Iterable} iterable The iterator
 328  *     to iterate over.
 329  * @param {function(this:THIS,VALUE,VALUE):VALUE} f The function to call for
 330  *     every element. This function takes 2 arguments (the function's previous
 331  *     result or the initial value, and the value of the current element).
 332  *     function(previousValue, currentElement) : newValue.
 333  * @param {VALUE} val The initial value to pass into the function on the first
 334  *     call.
 335  * @param {THIS=} opt_obj  The object to be used as the value of 'this' within
 336  *     f.
 337  * @return {VALUE} Result of evaluating f repeatedly across the values of
 338  *     the iterator.
 339  * @template THIS, VALUE
 340  */
 341 goog.iter.reduce = function(iterable, f, val, opt_obj) {
 342   var rval = val;
 343   goog.iter.forEach(iterable, function(val) {
 344     rval = f.call(opt_obj, rval, val);
 345   });
 346   return rval;
 347 };
 348
 349
 350 /**
 351  * Goes through the values in the iterator. Calls f for each of these, and if
 352  * any of them returns true, this returns true (without checking the rest). If
 353  * all return false this will return false.
 354  *
 355  * @param {goog.iter.Iterator.<VALUE>|goog.iter.Iterable} iterable The iterator
 356  *     object.
 357  * @param {
 358  *     function(this:THIS,VALUE,undefined,goog.iter.Iterator.<VALUE>):boolean} f
 359  *     The function to call for every value. This function takes 3 arguments
 360  *     (the value, undefined, and the iterator) and should return a boolean.
 361  * @param {THIS=} opt_obj The object to be used as the value of 'this' within
 362  *     {@code f}.
 363  * @return {boolean} true if any value passes the test.
 364  * @template THIS, VALUE
 365  */
 366 goog.iter.some = function(iterable, f, opt_obj) {
 367   iterable = goog.iter.toIterator(iterable);
 368   /** @preserveTry */
 369   try {
 370     while (true) {
 371       if (f.call(opt_obj, iterable.next(), undefined, iterable)) {
 372         return true;
 373       }
 374     }
 375   } catch (ex) {
 376     if (ex !== goog.iter.StopIteration) {
 377       throw ex;
 378     }
 379   }
 380   return false;
 381 };
 382
 383
 384 /**
 385  * Goes through the values in the iterator. Calls f for each of these and if any
 386  * of them returns false this returns false (without checking the rest). If all
 387  * return true this will return true.
 388  *
 389  * @param {goog.iter.Iterator.<VALUE>|goog.iter.Iterable} iterable The iterator
 390  *     object.
 391  * @param {
 392  *     function(this:THIS,VALUE,undefined,goog.iter.Iterator.<VALUE>):boolean} f
 393  *     The function to call for every value. This function takes 3 arguments
 394  *     (the value, undefined, and the iterator) and should return a boolean.
 395  * @param {THIS=} opt_obj The object to be used as the value of 'this' within
 396  *     {@code f}.
 397  * @return {boolean} true if every value passes the test.
 398  * @template THIS, VALUE
 399  */
 400 goog.iter.every = function(iterable, f, opt_obj) {
 401   iterable = goog.iter.toIterator(iterable);
 402   /** @preserveTry */
 403   try {
 404     while (true) {
 405       if (!f.call(opt_obj, iterable.next(), undefined, iterable)) {
 406         return false;
 407       }
 408     }
 409   } catch (ex) {
 410     if (ex !== goog.iter.StopIteration) {
 411       throw ex;
 412     }
 413   }
 414   return true;
 415 };
 416
 417
 418 /**
 419  * Takes zero or more iterables and returns one iterator that will iterate over
 420  * them in the order chained.
 421  * @param {...!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} var_args Any
 422  *     number of iterable objects.
 423  * @return {!goog.iter.Iterator.<VALUE>} Returns a new iterator that will
 424  *     iterate over all the given iterables' contents.
 425  * @template VALUE
 426  */
 427 goog.iter.chain = function(var_args) {
 428   var iterator = goog.iter.toIterator(arguments);
 429   var iter = new goog.iter.Iterator();
 430   var current = null;
 431
 432   iter.next = function() {
 433     while (true) {
 434       if (current == null) {
 435         var it = iterator.next();
 436         current = goog.iter.toIterator(it);
 437       }
 438       try {
 439         return current.next();
 440       } catch (ex) {
 441         if (ex !== goog.iter.StopIteration) {
 442           throw ex;
 443         }
 444         current = null;
 445       }
 446     }
 447   };
 448
 449   return iter;
 450 };
 451
 452
 453 /**
 454  * Takes a single iterable containing zero or more iterables and returns one
 455  * iterator that will iterate over each one in the order given.
 456  * @see http://docs.python.org/2/library/itertools.html#itertools.chain.from_iterable
 457  * @param {goog.iter.Iterable} iterable The iterable of iterables to chain.
 458  * @return {!goog.iter.Iterator.<VALUE>} Returns a new iterator that will
 459  *     iterate over all the contents of the iterables contained within
 460  *     {@code iterable}.
 461  * @template VALUE
 462  */
 463 goog.iter.chainFromIterable = function(iterable) {
 464   return goog.iter.chain.apply(undefined, iterable);
 465 };
 466
 467
 468 /**
 469  * Builds a new iterator that iterates over the original, but skips elements as
 470  * long as a supplied function returns true.
 471  * @param {goog.iter.Iterator.<VALUE>|goog.iter.Iterable} iterable The iterator
 472  *     object.
 473  * @param {
 474  *     function(this:THIS,VALUE,undefined,goog.iter.Iterator.<VALUE>):boolean} f
 475  *     The function to call for every value. This function takes 3 arguments
 476  *     (the value, undefined, and the iterator) and should return a boolean.
 477  * @param {THIS=} opt_obj The object to be used as the value of 'this' within
 478  *     {@code f}.
 479  * @return {!goog.iter.Iterator.<VALUE>} A new iterator that drops elements from
 480  *     the original iterator as long as {@code f} is true.
 481  * @template THIS, VALUE
 482  */
 483 goog.iter.dropWhile = function(iterable, f, opt_obj) {
 484   var iterator = goog.iter.toIterator(iterable);
 485   var newIter = new goog.iter.Iterator;
 486   var dropping = true;
 487   newIter.next = function() {
 488     while (true) {
 489       var val = iterator.next();
 490       if (dropping && f.call(opt_obj, val, undefined, iterator)) {
 491         continue;
 492       } else {
 493         dropping = false;
 494       }
 495       return val;
 496     }
 497   };
 498   return newIter;
 499 };
 500
 501
 502 /**
 503  * Builds a new iterator that iterates over the original, but only as long as a
 504  * supplied function returns true.
 505  * @param {goog.iter.Iterator.<VALUE>|goog.iter.Iterable} iterable The iterator
 506  *     object.
 507  * @param {
 508  *     function(this:THIS,VALUE,undefined,goog.iter.Iterator.<VALUE>):boolean} f
 509  *     The function to call for every value. This function takes 3 arguments
 510  *     (the value, undefined, and the iterator) and should return a boolean.
 511  * @param {THIS=} opt_obj This is used as the 'this' object in f when called.
 512  * @return {!goog.iter.Iterator.<VALUE>} A new iterator that keeps elements in
 513  *     the original iterator as long as the function is true.
 514  * @template THIS, VALUE
 515  */
 516 goog.iter.takeWhile = function(iterable, f, opt_obj) {
 517   var iterator = goog.iter.toIterator(iterable);
 518   var newIter = new goog.iter.Iterator;
 519   var taking = true;
 520   newIter.next = function() {
 521     while (true) {
 522       if (taking) {
 523         var val = iterator.next();
 524         if (f.call(opt_obj, val, undefined, iterator)) {
 525           return val;
 526         } else {
 527           taking = false;
 528         }
 529       } else {
 530         throw goog.iter.StopIteration;
 531       }
 532     }
 533   };
 534   return newIter;
 535 };
 536
 537
 538 /**
 539  * Converts the iterator to an array
 540  * @param {goog.iter.Iterator.<VALUE>|goog.iter.Iterable} iterable The iterator
 541  *     to convert to an array.
 542  * @return {!Array.<VALUE>} An array of the elements the iterator iterates over.
 543  * @template VALUE
 544  */
 545 goog.iter.toArray = function(iterable) {
 546   // Fast path for array-like.
 547   if (goog.isArrayLike(iterable)) {
 548     return goog.array.toArray(/** @type {!goog.array.ArrayLike} */(iterable));
 549   }
 550   iterable = goog.iter.toIterator(iterable);
 551   var array = [];
 552   goog.iter.forEach(iterable, function(val) {
 553     array.push(val);
 554   });
 555   return array;
 556 };
 557
 558
 559 /**
 560  * Iterates over two iterables and returns true if they contain the same
 561  * sequence of elements and have the same length.
 562  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable1 The first
 563  *     iterable object.
 564  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable2 The second
 565  *     iterable object.
 566  * @return {boolean} true if the iterables contain the same sequence of elements
 567  *     and have the same length.
 568  * @template VALUE
 569  */
 570 goog.iter.equals = function(iterable1, iterable2) {
 571   var fillValue = {};
 572   var pairs = goog.iter.zipLongest(fillValue, iterable1, iterable2);
 573   return goog.iter.every(pairs, function(pair) {
 574     return pair[0] == pair[1];
 575   });
 576 };
 577
 578
 579 /**
 580  * Advances the iterator to the next position, returning the given default value
 581  * instead of throwing an exception if the iterator has no more entries.
 582  * @param {goog.iter.Iterator.<VALUE>|goog.iter.Iterable} iterable The iterable
 583  *     object.
 584  * @param {VALUE} defaultValue The value to return if the iterator is empty.
 585  * @return {VALUE} The next item in the iteration, or defaultValue if the
 586  *     iterator was empty.
 587  * @template VALUE
 588  */
 589 goog.iter.nextOrValue = function(iterable, defaultValue) {
 590   try {
 591     return goog.iter.toIterator(iterable).next();
 592   } catch (e) {
 593     if (e != goog.iter.StopIteration) {
 594       throw e;
 595     }
 596     return defaultValue;
 597   }
 598 };
 599
 600
 601 /**
 602  * Cartesian product of zero or more sets.  Gives an iterator that gives every
 603  * combination of one element chosen from each set.  For example,
 604  * ([1, 2], [3, 4]) gives ([1, 3], [1, 4], [2, 3], [2, 4]).
 605  * @see http://docs.python.org/library/itertools.html#itertools.product
 606  * @param {...!goog.array.ArrayLike.<VALUE>} var_args Zero or more sets, as
 607  *     arrays.
 608  * @return {!goog.iter.Iterator.<!Array.<VALUE>>} An iterator that gives each
 609  *     n-tuple (as an array).
 610  * @template VALUE
 611  */
 612 goog.iter.product = function(var_args) {
 613   var someArrayEmpty = goog.array.some(arguments, function(arr) {
 614     return !arr.length;
 615   });
 616
 617   // An empty set in a cartesian product gives an empty set.
 618   if (someArrayEmpty || !arguments.length) {
 619     return new goog.iter.Iterator();
 620   }
 621
 622   var iter = new goog.iter.Iterator();
 623   var arrays = arguments;
 624
 625   // The first indices are [0, 0, ...]
 626   var indicies = goog.array.repeat(0, arrays.length);
 627
 628   iter.next = function() {
 629
 630     if (indicies) {
 631       var retVal = goog.array.map(indicies, function(valueIndex, arrayIndex) {
 632         return arrays[arrayIndex][valueIndex];
 633       });
 634
 635       // Generate the next-largest indices for the next call.
 636       // Increase the rightmost index. If it goes over, increase the next
 637       // rightmost (like carry-over addition).
 638       for (var i = indicies.length - 1; i >= 0; i--) {
 639         // Assertion prevents compiler warning below.
 640         goog.asserts.assert(indicies);
 641         if (indicies[i] < arrays[i].length - 1) {
 642           indicies[i]++;
 643           break;
 644         }
 645
 646         // We're at the last indices (the last element of every array), so
 647         // the iteration is over on the next call.
 648         if (i == 0) {
 649           indicies = null;
 650           break;
 651         }
 652         // Reset the index in this column and loop back to increment the
 653         // next one.
 654         indicies[i] = 0;
 655       }
 656       return retVal;
 657     }
 658
 659     throw goog.iter.StopIteration;
 660   };
 661
 662   return iter;
 663 };
 664
 665
 666 /**
 667  * Create an iterator to cycle over the iterable's elements indefinitely.
 668  * For example, ([1, 2, 3]) would return : 1, 2, 3, 1, 2, 3, ...
 669  * @see: http://docs.python.org/library/itertools.html#itertools.cycle.
 670  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable The
 671  *     iterable object.
 672  * @return {!goog.iter.Iterator.<VALUE>} An iterator that iterates indefinitely
 673  *     over the values in {@code iterable}.
 674  * @template VALUE
 675  */
 676 goog.iter.cycle = function(iterable) {
 677   var baseIterator = goog.iter.toIterator(iterable);
 678
 679   // We maintain a cache to store the iterable elements as we iterate
 680   // over them. The cache is used to return elements once we have
 681   // iterated over the iterable once.
 682   var cache = [];
 683   var cacheIndex = 0;
 684
 685   var iter = new goog.iter.Iterator();
 686
 687   // This flag is set after the iterable is iterated over once
 688   var useCache = false;
 689
 690   iter.next = function() {
 691     var returnElement = null;
 692
 693     // Pull elements off the original iterator if not using cache
 694     if (!useCache) {
 695       try {
 696         // Return the element from the iterable
 697         returnElement = baseIterator.next();
 698         cache.push(returnElement);
 699         return returnElement;
 700       } catch (e) {
 701         // If an exception other than StopIteration is thrown
 702         // or if there are no elements to iterate over (the iterable was empty)
 703         // throw an exception
 704         if (e != goog.iter.StopIteration || goog.array.isEmpty(cache)) {
 705           throw e;
 706         }
 707         // set useCache to true after we know that a 'StopIteration' exception
 708         // was thrown and the cache is not empty (to handle the 'empty iterable'
 709         // use case)
 710         useCache = true;
 711       }
 712     }
 713
 714     returnElement = cache[cacheIndex];
 715     cacheIndex = (cacheIndex + 1) % cache.length;
 716
 717     return returnElement;
 718   };
 719
 720   return iter;
 721 };
 722
 723
 724 /**
 725  * Creates an iterator that counts indefinitely from a starting value.
 726  * @see http://docs.python.org/2/library/itertools.html#itertools.count
 727  * @param {number=} opt_start The starting value. Default is 0.
 728  * @param {number=} opt_step The number to increment with between each call to
 729  *     next. Negative and floating point numbers are allowed. Default is 1.
 730  * @return {!goog.iter.Iterator.<number>} A new iterator that returns the values
 731  *     in the series.
 732  */
 733 goog.iter.count = function(opt_start, opt_step) {
 734   var counter = opt_start || 0;
 735   var step = goog.isDef(opt_step) ? opt_step : 1;
 736   var iter = new goog.iter.Iterator();
 737
 738   iter.next = function() {
 739     var returnValue = counter;
 740     counter += step;
 741     return returnValue;
 742   };
 743
 744   return iter;
 745 };
 746
 747
 748 /**
 749  * Creates an iterator that returns the same object or value repeatedly.
 750  * @param {VALUE} value Any object or value to repeat.
 751  * @return {!goog.iter.Iterator.<VALUE>} A new iterator that returns the
 752  *     repeated value.
 753  * @template VALUE
 754  */
 755 goog.iter.repeat = function(value) {
 756   var iter = new goog.iter.Iterator();
 757
 758   iter.next = goog.functions.constant(value);
 759
 760   return iter;
 761 };
 762
 763
 764 /**
 765  * Creates an iterator that returns running totals from the numbers in
 766  * {@code iterable}. For example, the array {@code [1, 2, 3, 4, 5]} yields
 767  * {@code 1 -> 3 -> 6 -> 10 -> 15}.
 768  * @see http://docs.python.org/3.2/library/itertools.html#itertools.accumulate
 769  * @param {!goog.iter.Iterable.<number>} iterable The iterable of numbers to
 770  *     accumulate.
 771  * @return {!goog.iter.Iterator.<number>} A new iterator that returns the
 772  *     numbers in the series.
 773  */
 774 goog.iter.accumulate = function(iterable) {
 775   var iterator = goog.iter.toIterator(iterable);
 776   var total = 0;
 777   var iter = new goog.iter.Iterator();
 778
 779   iter.next = function() {
 780     total += iterator.next();
 781     return total;
 782   };
 783
 784   return iter;
 785 };
 786
 787
 788 /**
 789  * Creates an iterator that returns arrays containing the ith elements from the
 790  * provided iterables. The returned arrays will be the same size as the number
 791  * of iterables given in {@code var_args}. Once the shortest iterable is
 792  * exhausted, subsequent calls to {@code next()} will throw
 793  * {@code goog.iter.StopIteration}.
 794  * @see http://docs.python.org/2/library/itertools.html#itertools.izip
 795  * @param {...!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} var_args Any
 796  *     number of iterable objects.
 797  * @return {!goog.iter.Iterator.<!Array.<VALUE>>} A new iterator that returns
 798  *     arrays of elements from the provided iterables.
 799  * @template VALUE
 800  */
 801 goog.iter.zip = function(var_args) {
 802   var args = arguments;
 803   var iter = new goog.iter.Iterator();
 804
 805   if (args.length > 0) {
 806     var iterators = goog.array.map(args, goog.iter.toIterator);
 807     iter.next = function() {
 808       var arr = goog.array.map(iterators, function(it) {
 809         return it.next();
 810       });
 811       return arr;
 812     };
 813   }
 814
 815   return iter;
 816 };
 817
 818
 819 /**
 820  * Creates an iterator that returns arrays containing the ith elements from the
 821  * provided iterables. The returned arrays will be the same size as the number
 822  * of iterables given in {@code var_args}. Shorter iterables will be extended
 823  * with {@code fillValue}. Once the longest iterable is exhausted, subsequent
 824  * calls to {@code next()} will throw {@code goog.iter.StopIteration}.
 825  * @see http://docs.python.org/2/library/itertools.html#itertools.izip_longest
 826  * @param {VALUE} fillValue The object or value used to fill shorter iterables.
 827  * @param {...!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} var_args Any
 828  *     number of iterable objects.
 829  * @return {!goog.iter.Iterator.<!Array.<VALUE>>} A new iterator that returns
 830  *     arrays of elements from the provided iterables.
 831  * @template VALUE
 832  */
 833 goog.iter.zipLongest = function(fillValue, var_args) {
 834   var args = goog.array.slice(arguments, 1);
 835   var iter = new goog.iter.Iterator();
 836
 837   if (args.length > 0) {
 838     var iterators = goog.array.map(args, goog.iter.toIterator);
 839
 840     iter.next = function() {
 841       var iteratorsHaveValues = false;  // false when all iterators are empty.
 842       var arr = goog.array.map(iterators, function(it) {
 843         var returnValue;
 844         try {
 845           returnValue = it.next();
 846           // Iterator had a value, so we've not exhausted the iterators.
 847           // Set flag accordingly.
 848           iteratorsHaveValues = true;
 849         } catch (ex) {
 850           if (ex !== goog.iter.StopIteration) {
 851             throw ex;
 852           }
 853           returnValue = fillValue;
 854         }
 855         return returnValue;
 856       });
 857
 858       if (!iteratorsHaveValues) {
 859         throw goog.iter.StopIteration;
 860       }
 861       return arr;
 862     };
 863   }
 864
 865   return iter;
 866 };
 867
 868
 869 /**
 870  * Creates an iterator that filters {@code iterable} based on a series of
 871  * {@code selectors}. On each call to {@code next()}, one item is taken from
 872  * both the {@code iterable} and {@code selectors} iterators. If the item from
 873  * {@code selectors} evaluates to true, the item from {@code iterable} is given.
 874  * Otherwise, it is skipped. Once either {@code iterable} or {@code selectors}
 875  * is exhausted, subsequent calls to {@code next()} will throw
 876  * {@code goog.iter.StopIteration}.
 877  * @see http://docs.python.org/2/library/itertools.html#itertools.compress
 878  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable The
 879  *     iterable to filter.
 880  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} selectors An
 881  *     iterable of items to be evaluated in a boolean context to determine if
 882  *     the corresponding element in {@code iterable} should be included in the
 883  *     result.
 884  * @return {!goog.iter.Iterator.<VALUE>} A new iterator that returns the
 885  *     filtered values.
 886  * @template VALUE
 887  */
 888 goog.iter.compress = function(iterable, selectors) {
 889   var selectorIterator = goog.iter.toIterator(selectors);
 890
 891   return goog.iter.filter(iterable, function() {
 892     return !!selectorIterator.next();
 893   });
 894 };
 895
 896
 897
 898 /**
 899  * Implements the {@code goog.iter.groupBy} iterator.
 900  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable The
 901  *     iterable to group.
 902  * @param {function(...[VALUE]): KEY=} opt_keyFunc  Optional function for
 903  *     determining the key value for each group in the {@code iterable}. Default
 904  *     is the identity function.
 905  * @constructor
 906  * @extends {goog.iter.Iterator.<!Array>}
 907  * @template KEY, VALUE
 908  * @private
 909  */
 910 goog.iter.GroupByIterator_ = function(iterable, opt_keyFunc) {
 911
 912   /**
 913    * The iterable to group, coerced to an iterator.
 914    * @type {!goog.iter.Iterator}
 915    */
 916   this.iterator = goog.iter.toIterator(iterable);
 917
 918   /**
 919    * A function for determining the key value for each element in the iterable.
 920    * If no function is provided, the identity function is used and returns the
 921    * element unchanged.
 922    * @type {function(...[VALUE]): KEY}
 923    */
 924   this.keyFunc = opt_keyFunc || goog.functions.identity;
 925
 926   /**
 927    * The target key for determining the start of a group.
 928    * @type {KEY}
 929    */
 930   this.targetKey;
 931
 932   /**
 933    * The current key visited during iteration.
 934    * @type {KEY}
 935    */
 936   this.currentKey;
 937
 938   /**
 939    * The current value being added to the group.
 940    * @type {VALUE}
 941    */
 942   this.currentValue;
 943 };
 944 goog.inherits(goog.iter.GroupByIterator_, goog.iter.Iterator);
 945
 946
 947 /** @override */
 948 goog.iter.GroupByIterator_.prototype.next = function() {
 949   while (this.currentKey == this.targetKey) {
 950     this.currentValue = this.iterator.next();  // Exits on StopIteration
 951     this.currentKey = this.keyFunc(this.currentValue);
 952   }
 953   this.targetKey = this.currentKey;
 954   return [this.currentKey, this.groupItems_(this.targetKey)];
 955 };
 956
 957
 958 /**
 959  * Performs the grouping of objects using the given key.
 960  * @param {KEY} targetKey  The target key object for the group.
 961  * @return {!Array.<VALUE>} An array of grouped objects.
 962  * @private
 963  */
 964 goog.iter.GroupByIterator_.prototype.groupItems_ = function(targetKey) {
 965   var arr = [];
 966   while (this.currentKey == targetKey) {
 967     arr.push(this.currentValue);
 968     try {
 969       this.currentValue = this.iterator.next();
 970     } catch (ex) {
 971       if (ex !== goog.iter.StopIteration) {
 972         throw ex;
 973       }
 974       break;
 975     }
 976     this.currentKey = this.keyFunc(this.currentValue);
 977   }
 978   return arr;
 979 };
 980
 981
 982 /**
 983  * Creates an iterator that returns arrays containing elements from the
 984  * {@code iterable} grouped by a key value. For iterables with repeated
 985  * elements (i.e. sorted according to a particular key function), this function
 986  * has a {@code uniq}-like effect. For example, grouping the array:
 987  * {@code [A, B, B, C, C, A]} produces
 988  * {@code [A, [A]], [B, [B, B]], [C, [C, C]], [A, [A]]}.
 989  * @see http://docs.python.org/2/library/itertools.html#itertools.groupby
 990  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable The
 991  *     iterable to group.
 992  * @param {function(...[VALUE]): KEY=} opt_keyFunc  Optional function for
 993  *     determining the key value for each group in the {@code iterable}. Default
 994  *     is the identity function.
 995  * @return {!goog.iter.Iterator.<!Array>} A new iterator that returns arrays of
 996  *     consecutive key and groups.
 997  * @template KEY, VALUE
 998  */
 999 goog.iter.groupBy = function(iterable, opt_keyFunc) {
1000   return new goog.iter.GroupByIterator_(iterable, opt_keyFunc);
1001 };
1002
1003
1004 /**
1005  * Gives an iterator that gives the result of calling the given function
1006  * <code>f</code> with the arguments taken from the next element from
1007  * <code>iterable</code> (the elements are expected to also be iterables).
1008  *
1009  * Similar to {@see goog.iter#map} but allows the function to accept multiple
1010  * arguments from the iterable.
1011  *
1012  * @param {!goog.iter.Iterable.<!goog.iter.Iterable>} iterable The iterable of
1013  *     iterables to iterate over.
1014  * @param {function(this:THIS,...[*]):RESULT} f The function to call for every
1015  *     element.  This function takes N+2 arguments, where N represents the
1016  *     number of items from the next element of the iterable. The two
1017  *     additional arguments passed to the function are undefined and the
1018  *     iterator itself. The function should return a new value.
1019  * @param {THIS=} opt_obj The object to be used as the value of 'this' within
1020  *     {@code f}.
1021  * @return {!goog.iter.Iterator.<RESULT>} A new iterator that returns the
1022  *     results of applying the function to each element in the original
1023  *     iterator.
1024  * @template THIS, RESULT
1025  */
1026 goog.iter.starMap = function(iterable, f, opt_obj) {
1027   var iterator = goog.iter.toIterator(iterable);
1028   var iter = new goog.iter.Iterator();
1029
1030   iter.next = function() {
1031     var args = goog.iter.toArray(iterator.next());
1032     return f.apply(opt_obj, goog.array.concat(args, undefined, iterator));
1033   };
1034
1035   return iter;
1036 };
1037
1038
1039 /**
1040  * Returns an array of iterators each of which can iterate over the values in
1041  * {@code iterable} without advancing the others.
1042  * @see http://docs.python.org/2/library/itertools.html#itertools.tee
1043  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable The
1044  *     iterable to tee.
1045  * @param {number=} opt_num  The number of iterators to create. Default is 2.
1046  * @return {!Array.<goog.iter.Iterator.<VALUE>>} An array of iterators.
1047  * @template VALUE
1048  */
1049 goog.iter.tee = function(iterable, opt_num) {
1050   var iterator = goog.iter.toIterator(iterable);
1051   var num = goog.isNumber(opt_num) ? opt_num : 2;
1052   var buffers = goog.array.map(goog.array.range(num), function() {
1053     return [];
1054   });
1055
1056   var addNextIteratorValueToBuffers = function() {
1057     var val = iterator.next();
1058     goog.array.forEach(buffers, function(buffer) {
1059       buffer.push(val);
1060     });
1061   };
1062
1063   var createIterator = function(buffer) {
1064     // Each tee'd iterator has an associated buffer (initially empty). When a
1065     // tee'd iterator's buffer is empty, it calls
1066     // addNextIteratorValueToBuffers(), adding the next value to all tee'd
1067     // iterators' buffers, and then returns that value. This allows each
1068     // iterator to be advanced independently.
1069     var iter = new goog.iter.Iterator();
1070
1071     iter.next = function() {
1072       if (goog.array.isEmpty(buffer)) {
1073         addNextIteratorValueToBuffers();
1074       }
1075       goog.asserts.assert(!goog.array.isEmpty(buffer));
1076       return buffer.shift();
1077     };
1078
1079     return iter;
1080   };
1081
1082   return goog.array.map(buffers, createIterator);
1083 };
1084
1085
1086 /**
1087  * Creates an iterator that returns arrays containing a count and an element
1088  * obtained from the given {@code iterable}.
1089  * @see http://docs.python.org/2/library/functions.html#enumerate
1090  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable The
1091  *     iterable to enumerate.
1092  * @param {number=} opt_start  Optional starting value. Default is 0.
1093  * @return {!goog.iter.Iterator.<!Array>} A new iterator containing count/item
1094  *     pairs.
1095  * @template VALUE
1096  */
1097 goog.iter.enumerate = function(iterable, opt_start) {
1098   return goog.iter.zip(goog.iter.count(opt_start), iterable);
1099 };
1100
1101
1102 /**
1103  * Creates an iterator that returns the first {@code limitSize} elements from an
1104  * iterable. If this number is greater than the number of elements in the
1105  * iterable, all the elements are returned.
1106  * @see http://goo.gl/V0sihp Inspired by the limit iterator in Guava.
1107  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable The
1108  *     iterable to limit.
1109  * @param {number} limitSize  The maximum number of elements to return.
1110  * @return {!goog.iter.Iterator.<VALUE>} A new iterator containing
1111  *     {@code limitSize} elements.
1112  * @template VALUE
1113  */
1114 goog.iter.limit = function(iterable, limitSize) {
1115   goog.asserts.assert(goog.math.isInt(limitSize) && limitSize >= 0);
1116
1117   var iterator = goog.iter.toIterator(iterable);
1118
1119   var iter = new goog.iter.Iterator();
1120   var remaining = limitSize;
1121
1122   iter.next = function() {
1123     if (remaining-- > 0) {
1124       return iterator.next();
1125     }
1126     throw goog.iter.StopIteration;
1127   };
1128
1129   return iter;
1130 };
1131
1132
1133 /**
1134  * Creates an iterator that is advanced {@code count} steps ahead. Consumed
1135  * values are silently discarded. If {@code count} is greater than the number
1136  * of elements in {@code iterable}, an empty iterator is returned. Subsequent
1137  * calls to {@code next()} will throw {@code goog.iter.StopIteration}.
1138  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable The
1139  *     iterable to consume.
1140  * @param {number} count  The number of elements to consume from the iterator.
1141  * @return {!goog.iter.Iterator.<VALUE>} An iterator advanced zero or more steps
1142  *     ahead.
1143  * @template VALUE
1144  */
1145 goog.iter.consume = function(iterable, count) {
1146   goog.asserts.assert(goog.math.isInt(count) && count >= 0);
1147
1148   var iterator = goog.iter.toIterator(iterable);
1149
1150   while (count-- > 0) {
1151     goog.iter.nextOrValue(iterator, null);
1152   }
1153
1154   return iterator;
1155 };
1156
1157
1158 /**
1159  * Creates an iterator that returns a range of elements from an iterable.
1160  * Similar to {@see goog.array#slice} but does not support negative indexes.
1161  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable The
1162  *     iterable to slice.
1163  * @param {number} start  The index of the first element to return.
1164  * @param {number=} opt_end  The index after the last element to return. If
1165  *     defined, must be greater than or equal to {@code start}.
1166  * @return {!goog.iter.Iterator.<VALUE>} A new iterator containing a slice of
1167  *     the original.
1168  * @template VALUE
1169  */
1170 goog.iter.slice = function(iterable, start, opt_end) {
1171   goog.asserts.assert(goog.math.isInt(start) && start >= 0);
1172
1173   var iterator = goog.iter.consume(iterable, start);
1174
1175   if (goog.isNumber(opt_end)) {
1176     goog.asserts.assert(
1177         goog.math.isInt(/** @type {number} */ (opt_end)) && opt_end >= start);
1178     iterator = goog.iter.limit(iterator, opt_end - start /* limitSize */);
1179   }
1180
1181   return iterator;
1182 };
1183
1184
1185 /**
1186  * Checks an array for duplicate elements.
1187  * @param {Array.<VALUE>|goog.array.ArrayLike} arr The array to check for
1188  *     duplicates.
1189  * @return {boolean} True, if the array contains duplicates, false otherwise.
1190  * @private
1191  * @template VALUE
1192  */
1193 // TODO(user): Consider moving this into goog.array as a public function.
1194 goog.iter.hasDuplicates_ = function(arr) {
1195   var deduped = [];
1196   goog.array.removeDuplicates(arr, deduped);
1197   return arr.length != deduped.length;
1198 };
1199
1200
1201 /**
1202  * Creates an iterator that returns permutations of elements in
1203  * {@code iterable}.
1204  *
1205  * Permutations are obtained by taking the Cartesian product of
1206  * {@code opt_length} iterables and filtering out those with repeated
1207  * elements. For example, the permutations of {@code [1,2,3]} are
1208  * {@code [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]}.
1209  * @see http://docs.python.org/2/library/itertools.html#itertools.permutations
1210  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable The
1211  *     iterable from which to generate permutations.
1212  * @param {number=} opt_length Length of each permutation. If omitted, defaults
1213  *     to the length of {@code iterable}.
1214  * @return {!goog.iter.Iterator.<!Array.<VALUE>>} A new iterator containing the
1215  *     permutations of {@code iterable}.
1216  * @template VALUE
1217  */
1218 goog.iter.permutations = function(iterable, opt_length) {
1219   var elements = goog.iter.toArray(iterable);
1220   var length = goog.isNumber(opt_length) ? opt_length : elements.length;
1221
1222   var sets = goog.array.repeat(elements, length);
1223   var product = goog.iter.product.apply(undefined, sets);
1224
1225   return goog.iter.filter(product, function(arr) {
1226     return !goog.iter.hasDuplicates_(arr);
1227   });
1228 };
1229
1230
1231 /**
1232  * Creates an iterator that returns combinations of elements from
1233  * {@code iterable}.
1234  *
1235  * Combinations are obtained by taking the {@see goog.iter#permutations} of
1236  * {@code iterable} and filtering those whose elements appear in the order they
1237  * are encountered in {@code iterable}. For example, the 3-length combinations
1238  * of {@code [0,1,2,3]} are {@code [[0,1,2], [0,1,3], [0,2,3], [1,2,3]]}.
1239  * @see http://docs.python.org/2/library/itertools.html#itertools.combinations
1240  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable The
1241  *     iterable from which to generate combinations.
1242  * @param {number} length The length of each combination.
1243  * @return {!goog.iter.Iterator.<!Array.<VALUE>>} A new iterator containing
1244  *     combinations from the {@code iterable}.
1245  * @template VALUE
1246  */
1247 goog.iter.combinations = function(iterable, length) {
1248   var elements = goog.iter.toArray(iterable);
1249   var indexes = goog.iter.range(elements.length);
1250   var indexIterator = goog.iter.permutations(indexes, length);
1251   // sortedIndexIterator will now give arrays of with the given length that
1252   // indicate what indexes into "elements" should be returned on each iteration.
1253   var sortedIndexIterator = goog.iter.filter(indexIterator, function(arr) {
1254     return goog.array.isSorted(arr);
1255   });
1256
1257   var iter = new goog.iter.Iterator();
1258
1259   function getIndexFromElements(index) {
1260     return elements[index];
1261   }
1262
1263   iter.next = function() {
1264     return goog.array.map(
1265         /** @type {!Array.<number>} */
1266         (sortedIndexIterator.next()), getIndexFromElements);
1267   };
1268
1269   return iter;
1270 };
1271
1272
1273 /**
1274  * Creates an iterator that returns combinations of elements from
1275  * {@code iterable}, with repeated elements possible.
1276  *
1277  * Combinations are obtained by taking the Cartesian product of {@code length}
1278  * iterables and filtering those whose elements appear in the order they are
1279  * encountered in {@code iterable}. For example, the 2-length combinations of
1280  * {@code [1,2,3]} are {@code [[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]]}.
1281  * @see http://docs.python.org/2/library/itertools.html#itertools.combinations_with_replacement
1282  * @see http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition
1283  * @param {!goog.iter.Iterator.<VALUE>|!goog.iter.Iterable} iterable The
1284  *     iterable to combine.
1285  * @param {number} length The length of each combination.
1286  * @return {!goog.iter.Iterator.<!Array.<VALUE>>} A new iterator containing
1287  *     combinations from the {@code iterable}.
1288  * @template VALUE
1289  */
1290 goog.iter.combinationsWithReplacement = function(iterable, length) {
1291   var elements = goog.iter.toArray(iterable);
1292   var indexes = goog.array.range(elements.length);
1293   var sets = goog.array.repeat(indexes, length);
1294   var indexIterator = goog.iter.product.apply(undefined, sets);
1295   // sortedIndexIterator will now give arrays of with the given length that
1296   // indicate what indexes into "elements" should be returned on each iteration.
1297   var sortedIndexIterator = goog.iter.filter(indexIterator, function(arr) {
1298     return goog.array.isSorted(arr);
1299   });
1300
1301   var iter = new goog.iter.Iterator();
1302
1303   function getIndexFromElements(index) {
1304     return elements[index];
1305   }
1306
1307   iter.next = function() {
1308     return goog.array.map(
1309         /** @type {!Array.<number>} */
1310         (sortedIndexIterator.next()), getIndexFromElements);
1311   };
1312
1313   return iter;
1314 };