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 [email protected] (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
/**
39
 * Singleton Error object that is used to terminate iterations.
40
 * @const {!Error}
41
 */
42
goog.iter.StopIteration = ('StopIteration' in goog.global) ?
43
    // For script engines that support legacy iterators.
44
    goog.global['StopIteration'] :
45
    {message: 'StopIteration', stack: ''};
46

47

48

49
/**
50
 * Class/interface for iterators.  An iterator needs to implement a {@code next}
51
 * method and it needs to throw a {@code goog.iter.StopIteration} when the
52
 * iteration passes beyond the end.  Iterators have no {@code hasNext} method.
53
 * It is recommended to always use the helper functions to iterate over the
54
 * iterator or in case you are only targeting JavaScript 1.7 for in loops.
55
 * @constructor
56
 * @template VALUE
57
 */
58
goog.iter.Iterator = function() {};
59

60

61
/**
62
 * Returns the next value of the iteration.  This will throw the object
63
 * {@see goog.iter#StopIteration} when the iteration passes the end.
64
 * @return {VALUE} Any object or value.
65
 */
66
goog.iter.Iterator.prototype.next = function() {
67
  throw goog.iter.StopIteration;
68
};
69

70

71
/**
72
 * Returns the {@code Iterator} object itself.  This is used to implement
73
 * the iterator protocol in JavaScript 1.7
74
 * @param {boolean=} opt_keys  Whether to return the keys or values. Default is
75
 *     to only return the values.  This is being used by the for-in loop (true)
76
 *     and the for-each-in loop (false).  Even though the param gives a hint
77
 *     about what the iterator will return there is no guarantee that it will
78
 *     return the keys when true is passed.
79
 * @return {!goog.iter.Iterator<VALUE>} The object itself.
80
 */
81
goog.iter.Iterator.prototype.__iterator__ = function(opt_keys) {
82
  return this;
83
};
84

85

86
/**
87
 * Returns an iterator that knows how to iterate over the values in the object.
88
 * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable  If the
89
 *     object is an iterator it will be returned as is.  If the object has an
90
 *     {@code __iterator__} method that will be called to get the value
91
 *     iterator.  If the object is an array-like object we create an iterator
92
 *     for that.
93
 * @return {!goog.iter.Iterator<VALUE>} An iterator that knows how to iterate
94
 *     over the values in {@code iterable}.
95
 * @template VALUE
96
 */
97
goog.iter.toIterator = function(iterable) {
98
  if (iterable instanceof goog.iter.Iterator) {
99
    return iterable;
100
  }
101
  if (typeof iterable.__iterator__ == 'function') {
102
    return iterable.__iterator__(false);
103
  }
104
  if (goog.isArrayLike(iterable)) {
105
    var i = 0;
106
    var newIter = new goog.iter.Iterator;
107
    newIter.next = function() {
108
      while (true) {
109
        if (i >= iterable.length) {
110
          throw goog.iter.StopIteration;
111
        }
112
        // Don't include deleted elements.
113
        if (!(i in iterable)) {
114
          i++;
115
          continue;
116
        }
117
        return iterable[i++];
118
      }
119
    };
120
    return newIter;
121
  }
122

123

124
  // TODO(arv): Should we fall back on goog.structs.getValues()?
125
  throw Error('Not implemented');
126
};
127

128

129
/**
130
 * Calls a function for each element in the iterator with the element of the
131
 * iterator passed as argument.
132
 *
133
 * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable  The iterator
134
 *     to iterate over. If the iterable is an object {@code toIterator} will be
135
 *     called on it.
136
 * @param {function(this:THIS,VALUE,?,!goog.iter.Iterator<VALUE>)} f
137
 *     The function to call for every element.  This function takes 3 arguments
138
 *     (the element, undefined, and the iterator) and the return value is
139
 *     irrelevant.  The reason for passing undefined as the second argument is
140
 *     so that the same function can be used in {@see goog.array#forEach} as
141
 *     well as others.  The third parameter is of type "number" for
142
 *     arraylike objects, undefined, otherwise.
143
 * @param {THIS=} opt_obj  The object to be used as the value of 'this' within
144
 *     {@code f}.
145
 * @template THIS, VALUE
146
 */
147
goog.iter.forEach = function(iterable, f, opt_obj) {
148
  if (goog.isArrayLike(iterable)) {
149

150
    try {
151
      // NOTES: this passes the index number to the second parameter
152
      // of the callback contrary to the documentation above.
153
      goog.array.forEach(
154
          /** @type {IArrayLike<?>} */ (iterable), f, opt_obj);
155
    } catch (ex) {
156
      if (ex !== goog.iter.StopIteration) {
157
        throw ex;
158
      }
159
    }
160
  } else {
161
    iterable = goog.iter.toIterator(iterable);
162

163
    try {
164
      while (true) {
165
        f.call(opt_obj, iterable.next(), undefined, iterable);
166
      }
167
    } catch (ex) {
168
      if (ex !== goog.iter.StopIteration) {
169
        throw ex;
170
      }
171
    }
172
  }
173
};
174

175

176
/**
177
 * Calls a function for every element in the iterator, and if the function
178
 * returns true adds the element to a new iterator.
179
 *
180
 * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
181
 *     to iterate over.
182
 * @param {
183
 *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator<VALUE>):boolean} f
184
 *     The function to call for every element. This function takes 3 arguments
185
 *     (the element, undefined, and the iterator) and should return a boolean.
186
 *     If the return value is true the element will be included in the returned
187
 *     iterator.  If it is false the element is not included.
188
 * @param {THIS=} opt_obj The object to be used as the value of 'this' within
189
 *     {@code f}.
190
 * @return {!goog.iter.Iterator<VALUE>} A new iterator in which only elements
191
 *     that passed the test are present.
192
 * @template THIS, VALUE
193
 */
194
goog.iter.filter = function(iterable, f, opt_obj) {
195
  var iterator = goog.iter.toIterator(iterable);
196
  var newIter = new goog.iter.Iterator;
197
  newIter.next = function() {
198
    while (true) {
199
      var val = iterator.next();
200
      if (f.call(opt_obj, val, undefined, iterator)) {
201
        return val;
202
      }
203
    }
204
  };
205
  return newIter;
206
};
207

208

209
/**
210
 * Calls a function for every element in the iterator, and if the function
211
 * returns false adds the element to a new iterator.
212
 *
213
 * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
214
 *     to iterate over.
215
 * @param {
216
 *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator<VALUE>):boolean} f
217
 *     The function to call for every element. This function takes 3 arguments
218
 *     (the element, undefined, and the iterator) and should return a boolean.
219
 *     If the return value is false the element will be included in the returned
220
 *     iterator.  If it is true the element is not included.
221
 * @param {THIS=} opt_obj The object to be used as the value of 'this' within
222
 *     {@code f}.
223
 * @return {!goog.iter.Iterator<VALUE>} A new iterator in which only elements
224
 *     that did not pass the test are present.
225
 * @template THIS, VALUE
226
 */
227
goog.iter.filterFalse = function(iterable, f, opt_obj) {
228
  return goog.iter.filter(iterable, goog.functions.not(f), opt_obj);
229
};
230

231

232
/**
233
 * Creates a new iterator that returns the values in a range.  This function
234
 * can take 1, 2 or 3 arguments:
235
 * <pre>
236
 * range(5) same as range(0, 5, 1)
237
 * range(2, 5) same as range(2, 5, 1)
238
 * </pre>
239
 *
240
 * @param {number} startOrStop  The stop value if only one argument is provided.
241
 *     The start value if 2 or more arguments are provided.  If only one
242
 *     argument is used the start value is 0.
243
 * @param {number=} opt_stop  The stop value.  If left out then the first
244
 *     argument is used as the stop value.
245
 * @param {number=} opt_step  The number to increment with between each call to
246
 *     next.  This can be negative.
247
 * @return {!goog.iter.Iterator<number>} A new iterator that returns the values
248
 *     in the range.
249
 */
250
goog.iter.range = function(startOrStop, opt_stop, opt_step) {
251
  var start = 0;
252
  var stop = startOrStop;
253
  var step = opt_step || 1;
254
  if (arguments.length > 1) {
255
    start = startOrStop;
256
    stop = opt_stop;
257
  }
258
  if (step == 0) {
259
    throw Error('Range step argument must not be zero');
260
  }
261

262
  var newIter = new goog.iter.Iterator;
263
  newIter.next = function() {
264
    if (step > 0 && start >= stop || step < 0 && start <= stop) {
265
      throw goog.iter.StopIteration;
266
    }
267
    var rv = start;
268
    start += step;
269
    return rv;
270
  };
271
  return newIter;
272
};
273

274

275
/**
276
 * Joins the values in a iterator with a delimiter.
277
 * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
278
 *     to get the values from.
279
 * @param {string} deliminator  The text to put between the values.
280
 * @return {string} The joined value string.
281
 * @template VALUE
282
 */
283
goog.iter.join = function(iterable, deliminator) {
284
  return goog.iter.toArray(iterable).join(deliminator);
285
};
286

287

288
/**
289
 * For every element in the iterator call a function and return a new iterator
290
 * with that value.
291
 *
292
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
293
 *     iterator to iterate over.
294
 * @param {
295
 *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator<VALUE>):RESULT} f
296
 *     The function to call for every element.  This function takes 3 arguments
297
 *     (the element, undefined, and the iterator) and should return a new value.
298
 * @param {THIS=} opt_obj The object to be used as the value of 'this' within
299
 *     {@code f}.
300
 * @return {!goog.iter.Iterator<RESULT>} A new iterator that returns the
301
 *     results of applying the function to each element in the original
302
 *     iterator.
303
 * @template THIS, VALUE, RESULT
304
 */
305
goog.iter.map = function(iterable, f, opt_obj) {
306
  var iterator = goog.iter.toIterator(iterable);
307
  var newIter = new goog.iter.Iterator;
308
  newIter.next = function() {
309
    var val = iterator.next();
310
    return f.call(opt_obj, val, undefined, iterator);
311
  };
312
  return newIter;
313
};
314

315

316
/**
317
 * Passes every element of an iterator into a function and accumulates the
318
 * result.
319
 *
320
 * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
321
 *     to iterate over.
322
 * @param {function(this:THIS,VALUE,VALUE):VALUE} f The function to call for
323
 *     every element. This function takes 2 arguments (the function's previous
324
 *     result or the initial value, and the value of the current element).
325
 *     function(previousValue, currentElement) : newValue.
326
 * @param {VALUE} val The initial value to pass into the function on the first
327
 *     call.
328
 * @param {THIS=} opt_obj  The object to be used as the value of 'this' within
329
 *     f.
330
 * @return {VALUE} Result of evaluating f repeatedly across the values of
331
 *     the iterator.
332
 * @template THIS, VALUE
333
 */
334
goog.iter.reduce = function(iterable, f, val, opt_obj) {
335
  var rval = val;
336
  goog.iter.forEach(
337
      iterable, function(val) { rval = f.call(opt_obj, rval, val); });
338
  return rval;
339
};
340

341

342
/**
343
 * Goes through the values in the iterator. Calls f for each of these, and if
344
 * any of them returns true, this returns true (without checking the rest). If
345
 * all return false this will return false.
346
 *
347
 * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
348
 *     object.
349
 * @param {
350
 *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator<VALUE>):boolean} f
351
 *     The function to call for every value. This function takes 3 arguments
352
 *     (the value, undefined, and the iterator) and should return a boolean.
353
 * @param {THIS=} opt_obj The object to be used as the value of 'this' within
354
 *     {@code f}.
355
 * @return {boolean} true if any value passes the test.
356
 * @template THIS, VALUE
357
 */
358
goog.iter.some = function(iterable, f, opt_obj) {
359
  iterable = goog.iter.toIterator(iterable);
360

361
  try {
362
    while (true) {
363
      if (f.call(opt_obj, iterable.next(), undefined, iterable)) {
364
        return true;
365
      }
366
    }
367
  } catch (ex) {
368
    if (ex !== goog.iter.StopIteration) {
369
      throw ex;
370
    }
371
  }
372
  return false;
373
};
374

375

376
/**
377
 * Goes through the values in the iterator. Calls f for each of these and if any
378
 * of them returns false this returns false (without checking the rest). If all
379
 * return true this will return true.
380
 *
381
 * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
382
 *     object.
383
 * @param {
384
 *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator<VALUE>):boolean} f
385
 *     The function to call for every value. This function takes 3 arguments
386
 *     (the value, undefined, and the iterator) and should return a boolean.
387
 * @param {THIS=} opt_obj The object to be used as the value of 'this' within
388
 *     {@code f}.
389
 * @return {boolean} true if every value passes the test.
390
 * @template THIS, VALUE
391
 */
392
goog.iter.every = function(iterable, f, opt_obj) {
393
  iterable = goog.iter.toIterator(iterable);
394

395
  try {
396
    while (true) {
397
      if (!f.call(opt_obj, iterable.next(), undefined, iterable)) {
398
        return false;
399
      }
400
    }
401
  } catch (ex) {
402
    if (ex !== goog.iter.StopIteration) {
403
      throw ex;
404
    }
405
  }
406
  return true;
407
};
408

409

410
/**
411
 * Takes zero or more iterables and returns one iterator that will iterate over
412
 * them in the order chained.
413
 * @param {...!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} var_args Any
414
 *     number of iterable objects.
415
 * @return {!goog.iter.Iterator<VALUE>} Returns a new iterator that will
416
 *     iterate over all the given iterables' contents.
417
 * @template VALUE
418
 */
419
goog.iter.chain = function(var_args) {
420
  return goog.iter.chainFromIterable(arguments);
421
};
422

423

424
/**
425
 * Takes a single iterable containing zero or more iterables and returns one
426
 * iterator that will iterate over each one in the order given.
427
 * @see https://goo.gl/5NRp5d
428
 * @param {goog.iter.Iterable} iterable The iterable of iterables to chain.
429
 * @return {!goog.iter.Iterator<VALUE>} Returns a new iterator that will
430
 *     iterate over all the contents of the iterables contained within
431
 *     {@code iterable}.
432
 * @template VALUE
433
 */
434
goog.iter.chainFromIterable = function(iterable) {
435
  var iterator = goog.iter.toIterator(iterable);
436
  var iter = new goog.iter.Iterator();
437
  var current = null;
438

439
  iter.next = function() {
440
    while (true) {
441
      if (current == null) {
442
        var it = iterator.next();
443
        current = goog.iter.toIterator(it);
444
      }
445
      try {
446
        return current.next();
447
      } catch (ex) {
448
        if (ex !== goog.iter.StopIteration) {
449
          throw ex;
450
        }
451
        current = null;
452
      }
453
    }
454
  };
455

456
  return iter;
457
};
458

459

460
/**
461
 * Builds a new iterator that iterates over the original, but skips elements as
462
 * long as a supplied function returns true.
463
 * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
464
 *     object.
465
 * @param {
466
 *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator<VALUE>):boolean} f
467
 *     The function to call for every value. This function takes 3 arguments
468
 *     (the value, undefined, and the iterator) and should return a boolean.
469
 * @param {THIS=} opt_obj The object to be used as the value of 'this' within
470
 *     {@code f}.
471
 * @return {!goog.iter.Iterator<VALUE>} A new iterator that drops elements from
472
 *     the original iterator as long as {@code f} is true.
473
 * @template THIS, VALUE
474
 */
475
goog.iter.dropWhile = function(iterable, f, opt_obj) {
476
  var iterator = goog.iter.toIterator(iterable);
477
  var newIter = new goog.iter.Iterator;
478
  var dropping = true;
479
  newIter.next = function() {
480
    while (true) {
481
      var val = iterator.next();
482
      if (dropping && f.call(opt_obj, val, undefined, iterator)) {
483
        continue;
484
      } else {
485
        dropping = false;
486
      }
487
      return val;
488
    }
489
  };
490
  return newIter;
491
};
492

493

494
/**
495
 * Builds a new iterator that iterates over the original, but only as long as a
496
 * supplied function returns true.
497
 * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
498
 *     object.
499
 * @param {
500
 *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator<VALUE>):boolean} f
501
 *     The function to call for every value. This function takes 3 arguments
502
 *     (the value, undefined, and the iterator) and should return a boolean.
503
 * @param {THIS=} opt_obj This is used as the 'this' object in f when called.
504
 * @return {!goog.iter.Iterator<VALUE>} A new iterator that keeps elements in
505
 *     the original iterator as long as the function is true.
506
 * @template THIS, VALUE
507
 */
508
goog.iter.takeWhile = function(iterable, f, opt_obj) {
509
  var iterator = goog.iter.toIterator(iterable);
510
  var iter = new goog.iter.Iterator();
511
  iter.next = function() {
512
    var val = iterator.next();
513
    if (f.call(opt_obj, val, undefined, iterator)) {
514
      return val;
515
    }
516
    throw goog.iter.StopIteration;
517
  };
518
  return iter;
519
};
520

521

522
/**
523
 * Converts the iterator to an array
524
 * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterator
525
 *     to convert to an array.
526
 * @return {!Array<VALUE>} An array of the elements the iterator iterates over.
527
 * @template VALUE
528
 */
529
goog.iter.toArray = function(iterable) {
530
  // Fast path for array-like.
531
  if (goog.isArrayLike(iterable)) {
532
    return goog.array.toArray(/** @type {!IArrayLike<?>} */ (iterable));
533
  }
534
  iterable = goog.iter.toIterator(iterable);
535
  var array = [];
536
  goog.iter.forEach(iterable, function(val) { array.push(val); });
537
  return array;
538
};
539

540

541
/**
542
 * Iterates over two iterables and returns true if they contain the same
543
 * sequence of elements and have the same length.
544
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable1 The first
545
 *     iterable object.
546
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable2 The second
547
 *     iterable object.
548
 * @param {function(VALUE,VALUE):boolean=} opt_equalsFn Optional comparison
549
 *     function.
550
 *     Should take two arguments to compare, and return true if the arguments
551
 *     are equal. Defaults to {@link goog.array.defaultCompareEquality} which
552
 *     compares the elements using the built-in '===' operator.
553
 * @return {boolean} true if the iterables contain the same sequence of elements
554
 *     and have the same length.
555
 * @template VALUE
556
 */
557
goog.iter.equals = function(iterable1, iterable2, opt_equalsFn) {
558
  var fillValue = {};
559
  var pairs = goog.iter.zipLongest(fillValue, iterable1, iterable2);
560
  var equalsFn = opt_equalsFn || goog.array.defaultCompareEquality;
561
  return goog.iter.every(
562
      pairs, function(pair) { return equalsFn(pair[0], pair[1]); });
563
};
564

565

566
/**
567
 * Advances the iterator to the next position, returning the given default value
568
 * instead of throwing an exception if the iterator has no more entries.
569
 * @param {goog.iter.Iterator<VALUE>|goog.iter.Iterable} iterable The iterable
570
 *     object.
571
 * @param {VALUE} defaultValue The value to return if the iterator is empty.
572
 * @return {VALUE} The next item in the iteration, or defaultValue if the
573
 *     iterator was empty.
574
 * @template VALUE
575
 */
576
goog.iter.nextOrValue = function(iterable, defaultValue) {
577
  try {
578
    return goog.iter.toIterator(iterable).next();
579
  } catch (e) {
580
    if (e != goog.iter.StopIteration) {
581
      throw e;
582
    }
583
    return defaultValue;
584
  }
585
};
586

587

588
/**
589
 * Cartesian product of zero or more sets.  Gives an iterator that gives every
590
 * combination of one element chosen from each set.  For example,
591
 * ([1, 2], [3, 4]) gives ([1, 3], [1, 4], [2, 3], [2, 4]).
592
 * @see http://docs.python.org/library/itertools.html#itertools.product
593
 * @param {...!IArrayLike<VALUE>} var_args Zero or more sets, as
594
 *     arrays.
595
 * @return {!goog.iter.Iterator<!Array<VALUE>>} An iterator that gives each
596
 *     n-tuple (as an array).
597
 * @template VALUE
598
 */
599
goog.iter.product = function(var_args) {
600
  var someArrayEmpty =
601
      goog.array.some(arguments, function(arr) { return !arr.length; });
602

603
  // An empty set in a cartesian product gives an empty set.
604
  if (someArrayEmpty || !arguments.length) {
605
    return new goog.iter.Iterator();
606
  }
607

608
  var iter = new goog.iter.Iterator();
609
  var arrays = arguments;
610

611
  // The first indices are [0, 0, ...]
612
  var indicies = goog.array.repeat(0, arrays.length);
613

614
  iter.next = function() {
615

616
    if (indicies) {
617
      var retVal = goog.array.map(indicies, function(valueIndex, arrayIndex) {
618
        return arrays[arrayIndex][valueIndex];
619
      });
620

621
      // Generate the next-largest indices for the next call.
622
      // Increase the rightmost index. If it goes over, increase the next
623
      // rightmost (like carry-over addition).
624
      for (var i = indicies.length - 1; i >= 0; i--) {
625
        // Assertion prevents compiler warning below.
626
        goog.asserts.assert(indicies);
627
        if (indicies[i] < arrays[i].length - 1) {
628
          indicies[i]++;
629
          break;
630
        }
631

632
        // We're at the last indices (the last element of every array), so
633
        // the iteration is over on the next call.
634
        if (i == 0) {
635
          indicies = null;
636
          break;
637
        }
638
        // Reset the index in this column and loop back to increment the
639
        // next one.
640
        indicies[i] = 0;
641
      }
642
      return retVal;
643
    }
644

645
    throw goog.iter.StopIteration;
646
  };
647

648
  return iter;
649
};
650

651

652
/**
653
 * Create an iterator to cycle over the iterable's elements indefinitely.
654
 * For example, ([1, 2, 3]) would return : 1, 2, 3, 1, 2, 3, ...
655
 * @see: http://docs.python.org/library/itertools.html#itertools.cycle.
656
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
657
 *     iterable object.
658
 * @return {!goog.iter.Iterator<VALUE>} An iterator that iterates indefinitely
659
 *     over the values in {@code iterable}.
660
 * @template VALUE
661
 */
662
goog.iter.cycle = function(iterable) {
663
  var baseIterator = goog.iter.toIterator(iterable);
664

665
  // We maintain a cache to store the iterable elements as we iterate
666
  // over them. The cache is used to return elements once we have
667
  // iterated over the iterable once.
668
  var cache = [];
669
  var cacheIndex = 0;
670

671
  var iter = new goog.iter.Iterator();
672

673
  // This flag is set after the iterable is iterated over once
674
  var useCache = false;
675

676
  iter.next = function() {
677
    var returnElement = null;
678

679
    // Pull elements off the original iterator if not using cache
680
    if (!useCache) {
681
      try {
682
        // Return the element from the iterable
683
        returnElement = baseIterator.next();
684
        cache.push(returnElement);
685
        return returnElement;
686
      } catch (e) {
687
        // If an exception other than StopIteration is thrown
688
        // or if there are no elements to iterate over (the iterable was empty)
689
        // throw an exception
690
        if (e != goog.iter.StopIteration || goog.array.isEmpty(cache)) {
691
          throw e;
692
        }
693
        // set useCache to true after we know that a 'StopIteration' exception
694
        // was thrown and the cache is not empty (to handle the 'empty iterable'
695
        // use case)
696
        useCache = true;
697
      }
698
    }
699

700
    returnElement = cache[cacheIndex];
701
    cacheIndex = (cacheIndex + 1) % cache.length;
702

703
    return returnElement;
704
  };
705

706
  return iter;
707
};
708

709

710
/**
711
 * Creates an iterator that counts indefinitely from a starting value.
712
 * @see http://docs.python.org/2/library/itertools.html#itertools.count
713
 * @param {number=} opt_start The starting value. Default is 0.
714
 * @param {number=} opt_step The number to increment with between each call to
715
 *     next. Negative and floating point numbers are allowed. Default is 1.
716
 * @return {!goog.iter.Iterator<number>} A new iterator that returns the values
717
 *     in the series.
718
 */
719
goog.iter.count = function(opt_start, opt_step) {
720
  var counter = opt_start || 0;
721
  var step = goog.isDef(opt_step) ? opt_step : 1;
722
  var iter = new goog.iter.Iterator();
723

724
  iter.next = function() {
725
    var returnValue = counter;
726
    counter += step;
727
    return returnValue;
728
  };
729

730
  return iter;
731
};
732

733

734
/**
735
 * Creates an iterator that returns the same object or value repeatedly.
736
 * @param {VALUE} value Any object or value to repeat.
737
 * @return {!goog.iter.Iterator<VALUE>} A new iterator that returns the
738
 *     repeated value.
739
 * @template VALUE
740
 */
741
goog.iter.repeat = function(value) {
742
  var iter = new goog.iter.Iterator();
743

744
  iter.next = goog.functions.constant(value);
745

746
  return iter;
747
};
748

749

750
/**
751
 * Creates an iterator that returns running totals from the numbers in
752
 * {@code iterable}. For example, the array {@code [1, 2, 3, 4, 5]} yields
753
 * {@code 1 -> 3 -> 6 -> 10 -> 15}.
754
 * @see http://docs.python.org/3.2/library/itertools.html#itertools.accumulate
755
 * @param {!goog.iter.Iterable} iterable The iterable of numbers to
756
 *     accumulate.
757
 * @return {!goog.iter.Iterator<number>} A new iterator that returns the
758
 *     numbers in the series.
759
 */
760
goog.iter.accumulate = function(iterable) {
761
  var iterator = goog.iter.toIterator(iterable);
762
  var total = 0;
763
  var iter = new goog.iter.Iterator();
764

765
  iter.next = function() {
766
    total += iterator.next();
767
    return total;
768
  };
769

770
  return iter;
771
};
772

773

774
/**
775
 * Creates an iterator that returns arrays containing the ith elements from the
776
 * provided iterables. The returned arrays will be the same size as the number
777
 * of iterables given in {@code var_args}. Once the shortest iterable is
778
 * exhausted, subsequent calls to {@code next()} will throw
779
 * {@code goog.iter.StopIteration}.
780
 * @see http://docs.python.org/2/library/itertools.html#itertools.izip
781
 * @param {...!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} var_args Any
782
 *     number of iterable objects.
783
 * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator that returns
784
 *     arrays of elements from the provided iterables.
785
 * @template VALUE
786
 */
787
goog.iter.zip = function(var_args) {
788
  var args = arguments;
789
  var iter = new goog.iter.Iterator();
790

791
  if (args.length > 0) {
792
    var iterators = goog.array.map(args, goog.iter.toIterator);
793
    iter.next = function() {
794
      var arr = goog.array.map(iterators, function(it) { return it.next(); });
795
      return arr;
796
    };
797
  }
798

799
  return iter;
800
};
801

802

803
/**
804
 * Creates an iterator that returns arrays containing the ith elements from the
805
 * provided iterables. The returned arrays will be the same size as the number
806
 * of iterables given in {@code var_args}. Shorter iterables will be extended
807
 * with {@code fillValue}. Once the longest iterable is exhausted, subsequent
808
 * calls to {@code next()} will throw {@code goog.iter.StopIteration}.
809
 * @see http://docs.python.org/2/library/itertools.html#itertools.izip_longest
810
 * @param {VALUE} fillValue The object or value used to fill shorter iterables.
811
 * @param {...!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} var_args Any
812
 *     number of iterable objects.
813
 * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator that returns
814
 *     arrays of elements from the provided iterables.
815
 * @template VALUE
816
 */
817
goog.iter.zipLongest = function(fillValue, var_args) {
818
  var args = goog.array.slice(arguments, 1);
819
  var iter = new goog.iter.Iterator();
820

821
  if (args.length > 0) {
822
    var iterators = goog.array.map(args, goog.iter.toIterator);
823

824
    iter.next = function() {
825
      var iteratorsHaveValues = false;  // false when all iterators are empty.
826
      var arr = goog.array.map(iterators, function(it) {
827
        var returnValue;
828
        try {
829
          returnValue = it.next();
830
          // Iterator had a value, so we've not exhausted the iterators.
831
          // Set flag accordingly.
832
          iteratorsHaveValues = true;
833
        } catch (ex) {
834
          if (ex !== goog.iter.StopIteration) {
835
            throw ex;
836
          }
837
          returnValue = fillValue;
838
        }
839
        return returnValue;
840
      });
841

842
      if (!iteratorsHaveValues) {
843
        throw goog.iter.StopIteration;
844
      }
845
      return arr;
846
    };
847
  }
848

849
  return iter;
850
};
851

852

853
/**
854
 * Creates an iterator that filters {@code iterable} based on a series of
855
 * {@code selectors}. On each call to {@code next()}, one item is taken from
856
 * both the {@code iterable} and {@code selectors} iterators. If the item from
857
 * {@code selectors} evaluates to true, the item from {@code iterable} is given.
858
 * Otherwise, it is skipped. Once either {@code iterable} or {@code selectors}
859
 * is exhausted, subsequent calls to {@code next()} will throw
860
 * {@code goog.iter.StopIteration}.
861
 * @see http://docs.python.org/2/library/itertools.html#itertools.compress
862
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
863
 *     iterable to filter.
864
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} selectors An
865
 *     iterable of items to be evaluated in a boolean context to determine if
866
 *     the corresponding element in {@code iterable} should be included in the
867
 *     result.
868
 * @return {!goog.iter.Iterator<VALUE>} A new iterator that returns the
869
 *     filtered values.
870
 * @template VALUE
871
 */
872
goog.iter.compress = function(iterable, selectors) {
873
  var selectorIterator = goog.iter.toIterator(selectors);
874

875
  return goog.iter.filter(
876
      iterable, function() { return !!selectorIterator.next(); });
877
};
878

879

880

881
/**
882
 * Implements the {@code goog.iter.groupBy} iterator.
883
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
884
 *     iterable to group.
885
 * @param {function(VALUE): KEY=} opt_keyFunc  Optional function for
886
 *     determining the key value for each group in the {@code iterable}. Default
887
 *     is the identity function.
888
 * @constructor
889
 * @extends {goog.iter.Iterator<!Array<?>>}
890
 * @template KEY, VALUE
891
 * @private
892
 */
893
goog.iter.GroupByIterator_ = function(iterable, opt_keyFunc) {
894

895
  /**
896
   * The iterable to group, coerced to an iterator.
897
   * @type {!goog.iter.Iterator}
898
   */
899
  this.iterator = goog.iter.toIterator(iterable);
900

901
  /**
902
   * A function for determining the key value for each element in the iterable.
903
   * If no function is provided, the identity function is used and returns the
904
   * element unchanged.
905
   * @type {function(VALUE): KEY}
906
   */
907
  this.keyFunc = opt_keyFunc || goog.functions.identity;
908

909
  /**
910
   * The target key for determining the start of a group.
911
   * @type {KEY}
912
   */
913
  this.targetKey;
914

915
  /**
916
   * The current key visited during iteration.
917
   * @type {KEY}
918
   */
919
  this.currentKey;
920

921
  /**
922
   * The current value being added to the group.
923
   * @type {VALUE}
924
   */
925
  this.currentValue;
926
};
927
goog.inherits(goog.iter.GroupByIterator_, goog.iter.Iterator);
928

929

930
/** @override */
931
goog.iter.GroupByIterator_.prototype.next = function() {
932
  while (this.currentKey == this.targetKey) {
933
    this.currentValue = this.iterator.next();  // Exits on StopIteration
934
    this.currentKey = this.keyFunc(this.currentValue);
935
  }
936
  this.targetKey = this.currentKey;
937
  return [this.currentKey, this.groupItems_(this.targetKey)];
938
};
939

940

941
/**
942
 * Performs the grouping of objects using the given key.
943
 * @param {KEY} targetKey  The target key object for the group.
944
 * @return {!Array<VALUE>} An array of grouped objects.
945
 * @private
946
 */
947
goog.iter.GroupByIterator_.prototype.groupItems_ = function(targetKey) {
948
  var arr = [];
949
  while (this.currentKey == targetKey) {
950
    arr.push(this.currentValue);
951
    try {
952
      this.currentValue = this.iterator.next();
953
    } catch (ex) {
954
      if (ex !== goog.iter.StopIteration) {
955
        throw ex;
956
      }
957
      break;
958
    }
959
    this.currentKey = this.keyFunc(this.currentValue);
960
  }
961
  return arr;
962
};
963

964

965
/**
966
 * Creates an iterator that returns arrays containing elements from the
967
 * {@code iterable} grouped by a key value. For iterables with repeated
968
 * elements (i.e. sorted according to a particular key function), this function
969
 * has a {@code uniq}-like effect. For example, grouping the array:
970
 * {@code [A, B, B, C, C, A]} produces
971
 * {@code [A, [A]], [B, [B, B]], [C, [C, C]], [A, [A]]}.
972
 * @see http://docs.python.org/2/library/itertools.html#itertools.groupby
973
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
974
 *     iterable to group.
975
 * @param {function(VALUE): KEY=} opt_keyFunc  Optional function for
976
 *     determining the key value for each group in the {@code iterable}. Default
977
 *     is the identity function.
978
 * @return {!goog.iter.Iterator<!Array<?>>} A new iterator that returns
979
 *     arrays of consecutive key and groups.
980
 * @template KEY, VALUE
981
 */
982
goog.iter.groupBy = function(iterable, opt_keyFunc) {
983
  return new goog.iter.GroupByIterator_(iterable, opt_keyFunc);
984
};
985

986

987
/**
988
 * Gives an iterator that gives the result of calling the given function
989
 * <code>f</code> with the arguments taken from the next element from
990
 * <code>iterable</code> (the elements are expected to also be iterables).
991
 *
992
 * Similar to {@see goog.iter#map} but allows the function to accept multiple
993
 * arguments from the iterable.
994
 *
995
 * @param {!goog.iter.Iterable} iterable The iterable of
996
 *     iterables to iterate over.
997
 * @param {function(this:THIS,...*):RESULT} f The function to call for every
998
 *     element.  This function takes N+2 arguments, where N represents the
999
 *     number of items from the next element of the iterable. The two
1000
 *     additional arguments passed to the function are undefined and the
1001
 *     iterator itself. The function should return a new value.
1002
 * @param {THIS=} opt_obj The object to be used as the value of 'this' within
1003
 *     {@code f}.
1004
 * @return {!goog.iter.Iterator<RESULT>} A new iterator that returns the
1005
 *     results of applying the function to each element in the original
1006
 *     iterator.
1007
 * @template THIS, RESULT
1008
 */
1009
goog.iter.starMap = function(iterable, f, opt_obj) {
1010
  var iterator = goog.iter.toIterator(iterable);
1011
  var iter = new goog.iter.Iterator();
1012

1013
  iter.next = function() {
1014
    var args = goog.iter.toArray(iterator.next());
1015
    return f.apply(opt_obj, goog.array.concat(args, undefined, iterator));
1016
  };
1017

1018
  return iter;
1019
};
1020

1021

1022
/**
1023
 * Returns an array of iterators each of which can iterate over the values in
1024
 * {@code iterable} without advancing the others.
1025
 * @see http://docs.python.org/2/library/itertools.html#itertools.tee
1026
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1027
 *     iterable to tee.
1028
 * @param {number=} opt_num  The number of iterators to create. Default is 2.
1029
 * @return {!Array<goog.iter.Iterator<VALUE>>} An array of iterators.
1030
 * @template VALUE
1031
 */
1032
goog.iter.tee = function(iterable, opt_num) {
1033
  var iterator = goog.iter.toIterator(iterable);
1034
  var num = goog.isNumber(opt_num) ? opt_num : 2;
1035
  var buffers =
1036
      goog.array.map(goog.array.range(num), function() { return []; });
1037

1038
  var addNextIteratorValueToBuffers = function() {
1039
    var val = iterator.next();
1040
    goog.array.forEach(buffers, function(buffer) { buffer.push(val); });
1041
  };
1042

1043
  var createIterator = function(buffer) {
1044
    // Each tee'd iterator has an associated buffer (initially empty). When a
1045
    // tee'd iterator's buffer is empty, it calls
1046
    // addNextIteratorValueToBuffers(), adding the next value to all tee'd
1047
    // iterators' buffers, and then returns that value. This allows each
1048
    // iterator to be advanced independently.
1049
    var iter = new goog.iter.Iterator();
1050

1051
    iter.next = function() {
1052
      if (goog.array.isEmpty(buffer)) {
1053
        addNextIteratorValueToBuffers();
1054
      }
1055
      goog.asserts.assert(!goog.array.isEmpty(buffer));
1056
      return buffer.shift();
1057
    };
1058

1059
    return iter;
1060
  };
1061

1062
  return goog.array.map(buffers, createIterator);
1063
};
1064

1065

1066
/**
1067
 * Creates an iterator that returns arrays containing a count and an element
1068
 * obtained from the given {@code iterable}.
1069
 * @see http://docs.python.org/2/library/functions.html#enumerate
1070
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1071
 *     iterable to enumerate.
1072
 * @param {number=} opt_start  Optional starting value. Default is 0.
1073
 * @return {!goog.iter.Iterator<!Array<?>>} A new iterator containing
1074
 *     count/item pairs.
1075
 * @template VALUE
1076
 */
1077
goog.iter.enumerate = function(iterable, opt_start) {
1078
  return goog.iter.zip(goog.iter.count(opt_start), iterable);
1079
};
1080

1081

1082
/**
1083
 * Creates an iterator that returns the first {@code limitSize} elements from an
1084
 * iterable. If this number is greater than the number of elements in the
1085
 * iterable, all the elements are returned.
1086
 * @see http://goo.gl/V0sihp Inspired by the limit iterator in Guava.
1087
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1088
 *     iterable to limit.
1089
 * @param {number} limitSize  The maximum number of elements to return.
1090
 * @return {!goog.iter.Iterator<VALUE>} A new iterator containing
1091
 *     {@code limitSize} elements.
1092
 * @template VALUE
1093
 */
1094
goog.iter.limit = function(iterable, limitSize) {
1095
  goog.asserts.assert(goog.math.isInt(limitSize) && limitSize >= 0);
1096

1097
  var iterator = goog.iter.toIterator(iterable);
1098

1099
  var iter = new goog.iter.Iterator();
1100
  var remaining = limitSize;
1101

1102
  iter.next = function() {
1103
    if (remaining-- > 0) {
1104
      return iterator.next();
1105
    }
1106
    throw goog.iter.StopIteration;
1107
  };
1108

1109
  return iter;
1110
};
1111

1112

1113
/**
1114
 * Creates an iterator that is advanced {@code count} steps ahead. Consumed
1115
 * values are silently discarded. If {@code count} is greater than the number
1116
 * of elements in {@code iterable}, an empty iterator is returned. Subsequent
1117
 * calls to {@code next()} will throw {@code goog.iter.StopIteration}.
1118
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1119
 *     iterable to consume.
1120
 * @param {number} count  The number of elements to consume from the iterator.
1121
 * @return {!goog.iter.Iterator<VALUE>} An iterator advanced zero or more steps
1122
 *     ahead.
1123
 * @template VALUE
1124
 */
1125
goog.iter.consume = function(iterable, count) {
1126
  goog.asserts.assert(goog.math.isInt(count) && count >= 0);
1127

1128
  var iterator = goog.iter.toIterator(iterable);
1129

1130
  while (count-- > 0) {
1131
    goog.iter.nextOrValue(iterator, null);
1132
  }
1133

1134
  return iterator;
1135
};
1136

1137

1138
/**
1139
 * Creates an iterator that returns a range of elements from an iterable.
1140
 * Similar to {@see goog.array#slice} but does not support negative indexes.
1141
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1142
 *     iterable to slice.
1143
 * @param {number} start  The index of the first element to return.
1144
 * @param {number=} opt_end  The index after the last element to return. If
1145
 *     defined, must be greater than or equal to {@code start}.
1146
 * @return {!goog.iter.Iterator<VALUE>} A new iterator containing a slice of
1147
 *     the original.
1148
 * @template VALUE
1149
 */
1150
goog.iter.slice = function(iterable, start, opt_end) {
1151
  goog.asserts.assert(goog.math.isInt(start) && start >= 0);
1152

1153
  var iterator = goog.iter.consume(iterable, start);
1154

1155
  if (goog.isNumber(opt_end)) {
1156
    goog.asserts.assert(goog.math.isInt(opt_end) && opt_end >= start);
1157
    iterator = goog.iter.limit(iterator, opt_end - start /* limitSize */);
1158
  }
1159

1160
  return iterator;
1161
};
1162

1163

1164
/**
1165
 * Checks an array for duplicate elements.
1166
 * @param {?IArrayLike<VALUE>} arr The array to check for
1167
 *     duplicates.
1168
 * @return {boolean} True, if the array contains duplicates, false otherwise.
1169
 * @private
1170
 * @template VALUE
1171
 */
1172
// TODO(user): Consider moving this into goog.array as a public function.
1173
goog.iter.hasDuplicates_ = function(arr) {
1174
  var deduped = [];
1175
  goog.array.removeDuplicates(arr, deduped);
1176
  return arr.length != deduped.length;
1177
};
1178

1179

1180
/**
1181
 * Creates an iterator that returns permutations of elements in
1182
 * {@code iterable}.
1183
 *
1184
 * Permutations are obtained by taking the Cartesian product of
1185
 * {@code opt_length} iterables and filtering out those with repeated
1186
 * elements. For example, the permutations of {@code [1,2,3]} are
1187
 * {@code [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]}.
1188
 * @see http://docs.python.org/2/library/itertools.html#itertools.permutations
1189
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1190
 *     iterable from which to generate permutations.
1191
 * @param {number=} opt_length Length of each permutation. If omitted, defaults
1192
 *     to the length of {@code iterable}.
1193
 * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator containing the
1194
 *     permutations of {@code iterable}.
1195
 * @template VALUE
1196
 */
1197
goog.iter.permutations = function(iterable, opt_length) {
1198
  var elements = goog.iter.toArray(iterable);
1199
  var length = goog.isNumber(opt_length) ? opt_length : elements.length;
1200

1201
  var sets = goog.array.repeat(elements, length);
1202
  var product = goog.iter.product.apply(undefined, sets);
1203

1204
  return goog.iter.filter(
1205
      product, function(arr) { return !goog.iter.hasDuplicates_(arr); });
1206
};
1207

1208

1209
/**
1210
 * Creates an iterator that returns combinations of elements from
1211
 * {@code iterable}.
1212
 *
1213
 * Combinations are obtained by taking the {@see goog.iter#permutations} of
1214
 * {@code iterable} and filtering those whose elements appear in the order they
1215
 * are encountered in {@code iterable}. For example, the 3-length combinations
1216
 * of {@code [0,1,2,3]} are {@code [[0,1,2], [0,1,3], [0,2,3], [1,2,3]]}.
1217
 * @see http://docs.python.org/2/library/itertools.html#itertools.combinations
1218
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1219
 *     iterable from which to generate combinations.
1220
 * @param {number} length The length of each combination.
1221
 * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator containing
1222
 *     combinations from the {@code iterable}.
1223
 * @template VALUE
1224
 */
1225
goog.iter.combinations = function(iterable, length) {
1226
  var elements = goog.iter.toArray(iterable);
1227
  var indexes = goog.iter.range(elements.length);
1228
  var indexIterator = goog.iter.permutations(indexes, length);
1229
  // sortedIndexIterator will now give arrays of with the given length that
1230
  // indicate what indexes into "elements" should be returned on each iteration.
1231
  var sortedIndexIterator = goog.iter.filter(
1232
      indexIterator, function(arr) { return goog.array.isSorted(arr); });
1233

1234
  var iter = new goog.iter.Iterator();
1235

1236
  function getIndexFromElements(index) { return elements[index]; }
1237

1238
  iter.next = function() {
1239
    return goog.array.map(sortedIndexIterator.next(), getIndexFromElements);
1240
  };
1241

1242
  return iter;
1243
};
1244

1245

1246
/**
1247
 * Creates an iterator that returns combinations of elements from
1248
 * {@code iterable}, with repeated elements possible.
1249
 *
1250
 * Combinations are obtained by taking the Cartesian product of {@code length}
1251
 * iterables and filtering those whose elements appear in the order they are
1252
 * encountered in {@code iterable}. For example, the 2-length combinations of
1253
 * {@code [1,2,3]} are {@code [[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]]}.
1254
 * @see https://goo.gl/C0yXe4
1255
 * @see https://goo.gl/djOCsk
1256
 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1257
 *     iterable to combine.
1258
 * @param {number} length The length of each combination.
1259
 * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator containing
1260
 *     combinations from the {@code iterable}.
1261
 * @template VALUE
1262
 */
1263
goog.iter.combinationsWithReplacement = function(iterable, length) {
1264
  var elements = goog.iter.toArray(iterable);
1265
  var indexes = goog.array.range(elements.length);
1266
  var sets = goog.array.repeat(indexes, length);
1267
  var indexIterator = goog.iter.product.apply(undefined, sets);
1268
  // sortedIndexIterator will now give arrays of with the given length that
1269
  // indicate what indexes into "elements" should be returned on each iteration.
1270
  var sortedIndexIterator = goog.iter.filter(
1271
      indexIterator, function(arr) { return goog.array.isSorted(arr); });
1272

1273
  var iter = new goog.iter.Iterator();
1274

1275
  function getIndexFromElements(index) { return elements[index]; }
1276

1277
  iter.next = function() {
1278
    return goog.array.map(
1279
        /** @type {!Array<number>} */
1280
        (sortedIndexIterator.next()), getIndexFromElements);
1281
  };
1282

1283
  return iter;
1284
};
1285

1286