Debian Codegraph @

closure-library/closure/goog/iter/iter.js

raw
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 new 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 new 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 /** @type {?Array<number>} */
613 var indicies = goog.array.repeat(0, arrays.length);
614
615 iter.next = function() {
616
617 if (indicies) {
618 var retVal = goog.array.map(indicies, function(valueIndex, arrayIndex) {
619 return arrays[arrayIndex][valueIndex];
620 });
621
622 // Generate the next-largest indices for the next call.
623 // Increase the rightmost index. If it goes over, increase the next
624 // rightmost (like carry-over addition).
625 for (var i = indicies.length - 1; i >= 0; i--) {
626 // Assertion prevents compiler warning below.
627 goog.asserts.assert(indicies);
628 if (indicies[i] < arrays[i].length - 1) {
629 indicies[i]++;
630 break;
631 }
632
633 // We're at the last indices (the last element of every array), so
634 // the iteration is over on the next call.
635 if (i == 0) {
636 indicies = null;
637 break;
638 }
639 // Reset the index in this column and loop back to increment the
640 // next one.
641 indicies[i] = 0;
642 }
643 return retVal;
644 }
645
646 throw goog.iter.StopIteration;
647 };
648
649 return iter;
650 };
651
652
653 /**
654 * Create an iterator to cycle over the iterable's elements indefinitely.
655 * For example, ([1, 2, 3]) would return : 1, 2, 3, 1, 2, 3, ...
656 * @see: http://docs.python.org/library/itertools.html#itertools.cycle.
657 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
658 * iterable object.
659 * @return {!goog.iter.Iterator<VALUE>} An iterator that iterates indefinitely
660 * over the values in {@code iterable}.
661 * @template VALUE
662 */
663 goog.iter.cycle = function(iterable) {
664 var baseIterator = goog.iter.toIterator(iterable);
665
666 // We maintain a cache to store the iterable elements as we iterate
667 // over them. The cache is used to return elements once we have
668 // iterated over the iterable once.
669 var cache = [];
670 var cacheIndex = 0;
671
672 var iter = new goog.iter.Iterator();
673
674 // This flag is set after the iterable is iterated over once
675 var useCache = false;
676
677 iter.next = function() {
678 var returnElement = null;
679
680 // Pull elements off the original iterator if not using cache
681 if (!useCache) {
682 try {
683 // Return the element from the iterable
684 returnElement = baseIterator.next();
685 cache.push(returnElement);
686 return returnElement;
687 } catch (e) {
688 // If an exception other than StopIteration is thrown
689 // or if there are no elements to iterate over (the iterable was empty)
690 // throw an exception
691 if (e != goog.iter.StopIteration || goog.array.isEmpty(cache)) {
692 throw e;
693 }
694 // set useCache to true after we know that a 'StopIteration' exception
695 // was thrown and the cache is not empty (to handle the 'empty iterable'
696 // use case)
697 useCache = true;
698 }
699 }
700
701 returnElement = cache[cacheIndex];
702 cacheIndex = (cacheIndex + 1) % cache.length;
703
704 return returnElement;
705 };
706
707 return iter;
708 };
709
710
711 /**
712 * Creates an iterator that counts indefinitely from a starting value.
713 * @see http://docs.python.org/2/library/itertools.html#itertools.count
714 * @param {number=} opt_start The starting value. Default is 0.
715 * @param {number=} opt_step The number to increment with between each call to
716 * next. Negative and floating point numbers are allowed. Default is 1.
717 * @return {!goog.iter.Iterator<number>} A new iterator that returns the values
718 * in the series.
719 */
720 goog.iter.count = function(opt_start, opt_step) {
721 var counter = opt_start || 0;
722 var step = goog.isDef(opt_step) ? opt_step : 1;
723 var iter = new goog.iter.Iterator();
724
725 iter.next = function() {
726 var returnValue = counter;
727 counter += step;
728 return returnValue;
729 };
730
731 return iter;
732 };
733
734
735 /**
736 * Creates an iterator that returns the same object or value repeatedly.
737 * @param {VALUE} value Any object or value to repeat.
738 * @return {!goog.iter.Iterator<VALUE>} A new iterator that returns the
739 * repeated value.
740 * @template VALUE
741 */
742 goog.iter.repeat = function(value) {
743 var iter = new goog.iter.Iterator();
744
745 iter.next = goog.functions.constant(value);
746
747 return iter;
748 };
749
750
751 /**
752 * Creates an iterator that returns running totals from the numbers in
753 * {@code iterable}. For example, the array {@code [1, 2, 3, 4, 5]} yields
754 * {@code 1 -> 3 -> 6 -> 10 -> 15}.
755 * @see http://docs.python.org/3.2/library/itertools.html#itertools.accumulate
756 * @param {!goog.iter.Iterable} iterable The iterable of numbers to
757 * accumulate.
758 * @return {!goog.iter.Iterator<number>} A new iterator that returns the
759 * numbers in the series.
760 */
761 goog.iter.accumulate = function(iterable) {
762 var iterator = goog.iter.toIterator(iterable);
763 var total = 0;
764 var iter = new goog.iter.Iterator();
765
766 iter.next = function() {
767 total += iterator.next();
768 return total;
769 };
770
771 return iter;
772 };
773
774
775 /**
776 * Creates an iterator that returns arrays containing the ith elements from the
777 * provided iterables. The returned arrays will be the same size as the number
778 * of iterables given in {@code var_args}. Once the shortest iterable is
779 * exhausted, subsequent calls to {@code next()} will throw
780 * {@code goog.iter.StopIteration}.
781 * @see http://docs.python.org/2/library/itertools.html#itertools.izip
782 * @param {...!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} var_args Any
783 * number of iterable objects.
784 * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator that returns
785 * arrays of elements from the provided iterables.
786 * @template VALUE
787 */
788 goog.iter.zip = function(var_args) {
789 var args = arguments;
790 var iter = new goog.iter.Iterator();
791
792 if (args.length > 0) {
793 var iterators = goog.array.map(args, goog.iter.toIterator);
794 iter.next = function() {
795 var arr = goog.array.map(iterators, function(it) { return it.next(); });
796 return arr;
797 };
798 }
799
800 return iter;
801 };
802
803
804 /**
805 * Creates an iterator that returns arrays containing the ith elements from the
806 * provided iterables. The returned arrays will be the same size as the number
807 * of iterables given in {@code var_args}. Shorter iterables will be extended
808 * with {@code fillValue}. Once the longest iterable is exhausted, subsequent
809 * calls to {@code next()} will throw {@code goog.iter.StopIteration}.
810 * @see http://docs.python.org/2/library/itertools.html#itertools.izip_longest
811 * @param {VALUE} fillValue The object or value used to fill shorter iterables.
812 * @param {...!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} var_args Any
813 * number of iterable objects.
814 * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator that returns
815 * arrays of elements from the provided iterables.
816 * @template VALUE
817 */
818 goog.iter.zipLongest = function(fillValue, var_args) {
819 var args = goog.array.slice(arguments, 1);
820 var iter = new goog.iter.Iterator();
821
822 if (args.length > 0) {
823 var iterators = goog.array.map(args, goog.iter.toIterator);
824
825 iter.next = function() {
826 var iteratorsHaveValues = false; // false when all iterators are empty.
827 var arr = goog.array.map(iterators, function(it) {
828 var returnValue;
829 try {
830 returnValue = it.next();
831 // Iterator had a value, so we've not exhausted the iterators.
832 // Set flag accordingly.
833 iteratorsHaveValues = true;
834 } catch (ex) {
835 if (ex !== goog.iter.StopIteration) {
836 throw ex;
837 }
838 returnValue = fillValue;
839 }
840 return returnValue;
841 });
842
843 if (!iteratorsHaveValues) {
844 throw goog.iter.StopIteration;
845 }
846 return arr;
847 };
848 }
849
850 return iter;
851 };
852
853
854 /**
855 * Creates an iterator that filters {@code iterable} based on a series of
856 * {@code selectors}. On each call to {@code next()}, one item is taken from
857 * both the {@code iterable} and {@code selectors} iterators. If the item from
858 * {@code selectors} evaluates to true, the item from {@code iterable} is given.
859 * Otherwise, it is skipped. Once either {@code iterable} or {@code selectors}
860 * is exhausted, subsequent calls to {@code next()} will throw
861 * {@code goog.iter.StopIteration}.
862 * @see http://docs.python.org/2/library/itertools.html#itertools.compress
863 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
864 * iterable to filter.
865 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} selectors An
866 * iterable of items to be evaluated in a boolean context to determine if
867 * the corresponding element in {@code iterable} should be included in the
868 * result.
869 * @return {!goog.iter.Iterator<VALUE>} A new iterator that returns the
870 * filtered values.
871 * @template VALUE
872 */
873 goog.iter.compress = function(iterable, selectors) {
874 var selectorIterator = goog.iter.toIterator(selectors);
875
876 return goog.iter.filter(
877 iterable, function() { return !!selectorIterator.next(); });
878 };
879
880
881
882 /**
883 * Implements the {@code goog.iter.groupBy} iterator.
884 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
885 * iterable to group.
886 * @param {function(VALUE): KEY=} opt_keyFunc Optional function for
887 * determining the key value for each group in the {@code iterable}. Default
888 * is the identity function.
889 * @constructor
890 * @extends {goog.iter.Iterator<!Array<?>>}
891 * @template KEY, VALUE
892 * @private
893 */
894 goog.iter.GroupByIterator_ = function(iterable, opt_keyFunc) {
895
896 /**
897 * The iterable to group, coerced to an iterator.
898 * @type {!goog.iter.Iterator}
899 */
900 this.iterator = goog.iter.toIterator(iterable);
901
902 /**
903 * A function for determining the key value for each element in the iterable.
904 * If no function is provided, the identity function is used and returns the
905 * element unchanged.
906 * @type {function(VALUE): KEY}
907 */
908 this.keyFunc = opt_keyFunc || goog.functions.identity;
909
910 /**
911 * The target key for determining the start of a group.
912 * @type {KEY}
913 */
914 this.targetKey;
915
916 /**
917 * The current key visited during iteration.
918 * @type {KEY}
919 */
920 this.currentKey;
921
922 /**
923 * The current value being added to the group.
924 * @type {VALUE}
925 */
926 this.currentValue;
927 };
928 goog.inherits(goog.iter.GroupByIterator_, goog.iter.Iterator);
929
930
931 /** @override */
932 goog.iter.GroupByIterator_.prototype.next = function() {
933 while (this.currentKey == this.targetKey) {
934 this.currentValue = this.iterator.next(); // Exits on StopIteration
935 this.currentKey = this.keyFunc(this.currentValue);
936 }
937 this.targetKey = this.currentKey;
938 return [this.currentKey, this.groupItems_(this.targetKey)];
939 };
940
941
942 /**
943 * Performs the grouping of objects using the given key.
944 * @param {KEY} targetKey The target key object for the group.
945 * @return {!Array<VALUE>} An array of grouped objects.
946 * @private
947 */
948 goog.iter.GroupByIterator_.prototype.groupItems_ = function(targetKey) {
949 var arr = [];
950 while (this.currentKey == targetKey) {
951 arr.push(this.currentValue);
952 try {
953 this.currentValue = this.iterator.next();
954 } catch (ex) {
955 if (ex !== goog.iter.StopIteration) {
956 throw ex;
957 }
958 break;
959 }
960 this.currentKey = this.keyFunc(this.currentValue);
961 }
962 return arr;
963 };
964
965
966 /**
967 * Creates an iterator that returns arrays containing elements from the
968 * {@code iterable} grouped by a key value. For iterables with repeated
969 * elements (i.e. sorted according to a particular key function), this function
970 * has a {@code uniq}-like effect. For example, grouping the array:
971 * {@code [A, B, B, C, C, A]} produces
972 * {@code [A, [A]], [B, [B, B]], [C, [C, C]], [A, [A]]}.
973 * @see http://docs.python.org/2/library/itertools.html#itertools.groupby
974 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
975 * iterable to group.
976 * @param {function(VALUE): KEY=} opt_keyFunc Optional function for
977 * determining the key value for each group in the {@code iterable}. Default
978 * is the identity function.
979 * @return {!goog.iter.Iterator<!Array<?>>} A new iterator that returns
980 * arrays of consecutive key and groups.
981 * @template KEY, VALUE
982 */
983 goog.iter.groupBy = function(iterable, opt_keyFunc) {
984 return new goog.iter.GroupByIterator_(iterable, opt_keyFunc);
985 };
986
987
988 /**
989 * Gives an iterator that gives the result of calling the given function
990 * <code>f</code> with the arguments taken from the next element from
991 * <code>iterable</code> (the elements are expected to also be iterables).
992 *
993 * Similar to {@see goog.iter#map} but allows the function to accept multiple
994 * arguments from the iterable.
995 *
996 * @param {!goog.iter.Iterable} iterable The iterable of
997 * iterables to iterate over.
998 * @param {function(this:THIS,...*):RESULT} f The function to call for every
999 * element. This function takes N+2 arguments, where N represents the
1000 * number of items from the next element of the iterable. The two
1001 * additional arguments passed to the function are undefined and the
1002 * iterator itself. The function should return a new value.
1003 * @param {THIS=} opt_obj The object to be used as the value of 'this' within
1004 * {@code f}.
1005 * @return {!goog.iter.Iterator<RESULT>} A new iterator that returns the
1006 * results of applying the function to each element in the original
1007 * iterator.
1008 * @template THIS, RESULT
1009 */
1010 goog.iter.starMap = function(iterable, f, opt_obj) {
1011 var iterator = goog.iter.toIterator(iterable);
1012 var iter = new goog.iter.Iterator();
1013
1014 iter.next = function() {
1015 var args = goog.iter.toArray(iterator.next());
1016 return f.apply(opt_obj, goog.array.concat(args, undefined, iterator));
1017 };
1018
1019 return iter;
1020 };
1021
1022
1023 /**
1024 * Returns an array of iterators each of which can iterate over the values in
1025 * {@code iterable} without advancing the others.
1026 * @see http://docs.python.org/2/library/itertools.html#itertools.tee
1027 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1028 * iterable to tee.
1029 * @param {number=} opt_num The number of iterators to create. Default is 2.
1030 * @return {!Array<goog.iter.Iterator<VALUE>>} An array of iterators.
1031 * @template VALUE
1032 */
1033 goog.iter.tee = function(iterable, opt_num) {
1034 var iterator = goog.iter.toIterator(iterable);
1035 var num = goog.isNumber(opt_num) ? opt_num : 2;
1036 var buffers =
1037 goog.array.map(goog.array.range(num), function() { return []; });
1038
1039 var addNextIteratorValueToBuffers = function() {
1040 var val = iterator.next();
1041 goog.array.forEach(buffers, function(buffer) { buffer.push(val); });
1042 };
1043
1044 var createIterator = function(buffer) {
1045 // Each tee'd iterator has an associated buffer (initially empty). When a
1046 // tee'd iterator's buffer is empty, it calls
1047 // addNextIteratorValueToBuffers(), adding the next value to all tee'd
1048 // iterators' buffers, and then returns that value. This allows each
1049 // iterator to be advanced independently.
1050 var iter = new goog.iter.Iterator();
1051
1052 iter.next = function() {
1053 if (goog.array.isEmpty(buffer)) {
1054 addNextIteratorValueToBuffers();
1055 }
1056 goog.asserts.assert(!goog.array.isEmpty(buffer));
1057 return buffer.shift();
1058 };
1059
1060 return iter;
1061 };
1062
1063 return goog.array.map(buffers, createIterator);
1064 };
1065
1066
1067 /**
1068 * Creates an iterator that returns arrays containing a count and an element
1069 * obtained from the given {@code iterable}.
1070 * @see http://docs.python.org/2/library/functions.html#enumerate
1071 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1072 * iterable to enumerate.
1073 * @param {number=} opt_start Optional starting value. Default is 0.
1074 * @return {!goog.iter.Iterator<!Array<?>>} A new iterator containing
1075 * count/item pairs.
1076 * @template VALUE
1077 */
1078 goog.iter.enumerate = function(iterable, opt_start) {
1079 return goog.iter.zip(goog.iter.count(opt_start), iterable);
1080 };
1081
1082
1083 /**
1084 * Creates an iterator that returns the first {@code limitSize} elements from an
1085 * iterable. If this number is greater than the number of elements in the
1086 * iterable, all the elements are returned.
1087 * @see http://goo.gl/V0sihp Inspired by the limit iterator in Guava.
1088 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1089 * iterable to limit.
1090 * @param {number} limitSize The maximum number of elements to return.
1091 * @return {!goog.iter.Iterator<VALUE>} A new iterator containing
1092 * {@code limitSize} elements.
1093 * @template VALUE
1094 */
1095 goog.iter.limit = function(iterable, limitSize) {
1096 goog.asserts.assert(goog.math.isInt(limitSize) && limitSize >= 0);
1097
1098 var iterator = goog.iter.toIterator(iterable);
1099
1100 var iter = new goog.iter.Iterator();
1101 var remaining = limitSize;
1102
1103 iter.next = function() {
1104 if (remaining-- > 0) {
1105 return iterator.next();
1106 }
1107 throw goog.iter.StopIteration;
1108 };
1109
1110 return iter;
1111 };
1112
1113
1114 /**
1115 * Creates an iterator that is advanced {@code count} steps ahead. Consumed
1116 * values are silently discarded. If {@code count} is greater than the number
1117 * of elements in {@code iterable}, an empty iterator is returned. Subsequent
1118 * calls to {@code next()} will throw {@code goog.iter.StopIteration}.
1119 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1120 * iterable to consume.
1121 * @param {number} count The number of elements to consume from the iterator.
1122 * @return {!goog.iter.Iterator<VALUE>} An iterator advanced zero or more steps
1123 * ahead.
1124 * @template VALUE
1125 */
1126 goog.iter.consume = function(iterable, count) {
1127 goog.asserts.assert(goog.math.isInt(count) && count >= 0);
1128
1129 var iterator = goog.iter.toIterator(iterable);
1130
1131 while (count-- > 0) {
1132 goog.iter.nextOrValue(iterator, null);
1133 }
1134
1135 return iterator;
1136 };
1137
1138
1139 /**
1140 * Creates an iterator that returns a range of elements from an iterable.
1141 * Similar to {@see goog.array#slice} but does not support negative indexes.
1142 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1143 * iterable to slice.
1144 * @param {number} start The index of the first element to return.
1145 * @param {number=} opt_end The index after the last element to return. If
1146 * defined, must be greater than or equal to {@code start}.
1147 * @return {!goog.iter.Iterator<VALUE>} A new iterator containing a slice of
1148 * the original.
1149 * @template VALUE
1150 */
1151 goog.iter.slice = function(iterable, start, opt_end) {
1152 goog.asserts.assert(goog.math.isInt(start) && start >= 0);
1153
1154 var iterator = goog.iter.consume(iterable, start);
1155
1156 if (goog.isNumber(opt_end)) {
1157 goog.asserts.assert(goog.math.isInt(opt_end) && opt_end >= start);
1158 iterator = goog.iter.limit(iterator, opt_end - start /* limitSize */);
1159 }
1160
1161 return iterator;
1162 };
1163
1164
1165 /**
1166 * Checks an array for duplicate elements.
1167 * @param {?IArrayLike<VALUE>} arr The array to check for
1168 * duplicates.
1169 * @return {boolean} True, if the array contains duplicates, false otherwise.
1170 * @private
1171 * @template VALUE
1172 */
1173 // TODO(user): Consider moving this into goog.array as a public function.
1174 goog.iter.hasDuplicates_ = function(arr) {
1175 var deduped = [];
1176 goog.array.removeDuplicates(arr, deduped);
1177 return arr.length != deduped.length;
1178 };
1179
1180
1181 /**
1182 * Creates an iterator that returns permutations of elements in
1183 * {@code iterable}.
1184 *
1185 * Permutations are obtained by taking the Cartesian product of
1186 * {@code opt_length} iterables and filtering out those with repeated
1187 * elements. For example, the permutations of {@code [1,2,3]} are
1188 * {@code [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]}.
1189 * @see http://docs.python.org/2/library/itertools.html#itertools.permutations
1190 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1191 * iterable from which to generate permutations.
1192 * @param {number=} opt_length Length of each permutation. If omitted, defaults
1193 * to the length of {@code iterable}.
1194 * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator containing the
1195 * permutations of {@code iterable}.
1196 * @template VALUE
1197 */
1198 goog.iter.permutations = function(iterable, opt_length) {
1199 var elements = goog.iter.toArray(iterable);
1200 var length = goog.isNumber(opt_length) ? opt_length : elements.length;
1201
1202 var sets = goog.array.repeat(elements, length);
1203 var product = goog.iter.product.apply(undefined, sets);
1204
1205 return goog.iter.filter(
1206 product, function(arr) { return !goog.iter.hasDuplicates_(arr); });
1207 };
1208
1209
1210 /**
1211 * Creates an iterator that returns combinations of elements from
1212 * {@code iterable}.
1213 *
1214 * Combinations are obtained by taking the {@see goog.iter#permutations} of
1215 * {@code iterable} and filtering those whose elements appear in the order they
1216 * are encountered in {@code iterable}. For example, the 3-length combinations
1217 * of {@code [0,1,2,3]} are {@code [[0,1,2], [0,1,3], [0,2,3], [1,2,3]]}.
1218 * @see http://docs.python.org/2/library/itertools.html#itertools.combinations
1219 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1220 * iterable from which to generate combinations.
1221 * @param {number} length The length of each combination.
1222 * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator containing
1223 * combinations from the {@code iterable}.
1224 * @template VALUE
1225 */
1226 goog.iter.combinations = function(iterable, length) {
1227 var elements = goog.iter.toArray(iterable);
1228 var indexes = goog.iter.range(elements.length);
1229 var indexIterator = goog.iter.permutations(indexes, length);
1230 // sortedIndexIterator will now give arrays of with the given length that
1231 // indicate what indexes into "elements" should be returned on each iteration.
1232 var sortedIndexIterator = goog.iter.filter(
1233 indexIterator, function(arr) { return goog.array.isSorted(arr); });
1234
1235 var iter = new goog.iter.Iterator();
1236
1237 function getIndexFromElements(index) { return elements[index]; }
1238
1239 iter.next = function() {
1240 return goog.array.map(sortedIndexIterator.next(), getIndexFromElements);
1241 };
1242
1243 return iter;
1244 };
1245
1246
1247 /**
1248 * Creates an iterator that returns combinations of elements from
1249 * {@code iterable}, with repeated elements possible.
1250 *
1251 * Combinations are obtained by taking the Cartesian product of {@code length}
1252 * iterables and filtering those whose elements appear in the order they are
1253 * encountered in {@code iterable}. For example, the 2-length combinations of
1254 * {@code [1,2,3]} are {@code [[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]]}.
1255 * @see https://goo.gl/C0yXe4
1256 * @see https://goo.gl/djOCsk
1257 * @param {!goog.iter.Iterator<VALUE>|!goog.iter.Iterable} iterable The
1258 * iterable to combine.
1259 * @param {number} length The length of each combination.
1260 * @return {!goog.iter.Iterator<!Array<VALUE>>} A new iterator containing
1261 * combinations from the {@code iterable}.
1262 * @template VALUE
1263 */
1264 goog.iter.combinationsWithReplacement = function(iterable, length) {
1265 var elements = goog.iter.toArray(iterable);
1266 var indexes = goog.array.range(elements.length);
1267 var sets = goog.array.repeat(indexes, length);
1268 var indexIterator = goog.iter.product.apply(undefined, sets);
1269 // sortedIndexIterator will now give arrays of with the given length that
1270 // indicate what indexes into "elements" should be returned on each iteration.
1271 var sortedIndexIterator = goog.iter.filter(
1272 indexIterator, function(arr) { return goog.array.isSorted(arr); });
1273
1274 var iter = new goog.iter.Iterator();
1275
1276 function getIndexFromElements(index) { return elements[index]; }
1277
1278 iter.next = function() {
1279 return goog.array.map(
1280 /** @type {!Array<number>} */
1281 (sortedIndexIterator.next()), getIndexFromElements);
1282 };
1283
1284 return iter;
1285 };