lib/goog/iter/iter.js

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