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.Iterator');
23goog.provide('goog.iter.StopIteration');
24
25goog.require('goog.array');
26goog.require('goog.asserts');
27
28
29// TODO(nnaze): Add more functions from Python's itertools.
30// http://docs.python.org/library/itertools.html
31
32
33/**
34 * @typedef {goog.iter.Iterator|{length:number}|{__iterator__}}
35 */
36goog.iter.Iterable;
37
38
39// For script engines that already support iterators.
40if ('StopIteration' in goog.global) {
41 /**
42 * Singleton Error object that is used to terminate iterations.
43 * @type {Error}
44 */
45 goog.iter.StopIteration = goog.global['StopIteration'];
46} else {
47 /**
48 * Singleton Error object that is used to terminate iterations.
49 * @type {Error}
50 * @suppress {duplicate}
51 */
52 goog.iter.StopIteration = Error('StopIteration');
53}
54
55
56
57/**
58 * Class/interface for iterators. An iterator needs to implement a {@code next}
59 * method and it needs to throw a {@code goog.iter.StopIteration} when the
60 * iteration passes beyond the end. Iterators have no {@code hasNext} method.
61 * It is recommended to always use the helper functions to iterate over the
62 * iterator or in case you are only targeting JavaScript 1.7 for in loops.
63 * @constructor
64 */
65goog.iter.Iterator = function() {};
66
67
68/**
69 * Returns the next value of the iteration. This will throw the object
70 * {@see goog.iter#StopIteration} when the iteration passes the end.
71 * @return {*} Any object or value.
72 */
73goog.iter.Iterator.prototype.next = function() {
74 throw goog.iter.StopIteration;
75};
76
77
78/**
79 * Returns the {@code Iterator} object itself. This is used to implement
80 * the iterator protocol in JavaScript 1.7
81 * @param {boolean=} opt_keys Whether to return the keys or values. Default is
82 * to only return the values. This is being used by the for-in loop (true)
83 * and the for-each-in loop (false). Even though the param gives a hint
84 * about what the iterator will return there is no guarantee that it will
85 * return the keys when true is passed.
86 * @return {!goog.iter.Iterator} The object itself.
87 */
88goog.iter.Iterator.prototype.__iterator__ = function(opt_keys) {
89 return this;
90};
91
92
93/**
94 * Returns an iterator that knows how to iterate over the values in the object.
95 * @param {goog.iter.Iterable} iterable If the object is an iterator it
96 * will be returned as is. If the object has a {@code __iterator__} method
97 * that will be called to get the value iterator. If the object is an
98 * array-like object we create an iterator for that.
99 * @return {!goog.iter.Iterator} An iterator that knows how to iterate over the
100 * values in {@code iterable}.
101 */
102goog.iter.toIterator = function(iterable) {
103 if (iterable instanceof goog.iter.Iterator) {
104 return iterable;
105 }
106 if (typeof iterable.__iterator__ == 'function') {
107 return iterable.__iterator__(false);
108 }
109 if (goog.isArrayLike(iterable)) {
110 var i = 0;
111 var newIter = new goog.iter.Iterator;
112 newIter.next = function() {
113 while (true) {
114 if (i >= iterable.length) {
115 throw goog.iter.StopIteration;
116 }
117 // Don't include deleted elements.
118 if (!(i in iterable)) {
119 i++;
120 continue;
121 }
122 return iterable[i++];
123 }
124 };
125 return newIter;
126 }
127
128
129 // TODO(arv): Should we fall back on goog.structs.getValues()?
130 throw Error('Not implemented');
131};
132
133
134/**
135 * Calls a function for each element in the iterator with the element of the
136 * iterator passed as argument.
137 *
138 * @param {goog.iter.Iterable} iterable The iterator to iterate
139 * over. If the iterable is an object {@code toIterator} will be called on
140 * it.
141* @param {function(this:T,?,?,?):?} f The function to call for every
142 * element. This function
143 * takes 3 arguments (the element, undefined, and the iterator) and the
144 * return value is irrelevant. The reason for passing undefined as the
145 * second argument is so that the same function can be used in
146 * {@see goog.array#forEach} as well as others.
147 * @param {T=} opt_obj The object to be used as the value of 'this' within
148 * {@code f}.
149 * @template T
150 */
151goog.iter.forEach = function(iterable, f, opt_obj) {
152 if (goog.isArrayLike(iterable)) {
153 /** @preserveTry */
154 try {
155 // NOTES: this passes the index number to the second parameter
156 // of the callback contrary to the documentation above.
157 goog.array.forEach(/** @type {goog.array.ArrayLike} */(iterable), f,
158 opt_obj);
159 } catch (ex) {
160 if (ex !== goog.iter.StopIteration) {
161 throw ex;
162 }
163 }
164 } else {
165 iterable = goog.iter.toIterator(iterable);
166 /** @preserveTry */
167 try {
168 while (true) {
169 f.call(opt_obj, iterable.next(), undefined, iterable);
170 }
171 } catch (ex) {
172 if (ex !== goog.iter.StopIteration) {
173 throw ex;
174 }
175 }
176 }
177};
178
179
180/**
181 * Calls a function for every element in the iterator, and if the function
182 * returns true adds the element to a new iterator.
183 *
184 * @param {goog.iter.Iterable} iterable The iterator to iterate over.
185 * @param {function(this:T,?,undefined,?):boolean} f The function to call for
186 * every element. This function
187 * takes 3 arguments (the element, undefined, and the iterator) and should
188 * return a boolean. If the return value is true the element will be
189 * included in the returned iteror. If it is false the element is not
190 * included.
191 * @param {T=} opt_obj The object to be used as the value of 'this' within
192 * {@code f}.
193 * @return {!goog.iter.Iterator} A new iterator in which only elements that
194 * passed the test are present.
195 * @template T
196 */
197goog.iter.filter = function(iterable, f, opt_obj) {
198 var iterator = goog.iter.toIterator(iterable);
199 var newIter = new goog.iter.Iterator;
200 newIter.next = function() {
201 while (true) {
202 var val = iterator.next();
203 if (f.call(opt_obj, val, undefined, iterator)) {
204 return val;
205 }
206 }
207 };
208 return newIter;
209};
210
211
212/**
213 * Creates a new iterator that returns the values in a range. This function
214 * can take 1, 2 or 3 arguments:
215 * <pre>
216 * range(5) same as range(0, 5, 1)
217 * range(2, 5) same as range(2, 5, 1)
218 * </pre>
219 *
220 * @param {number} startOrStop The stop value if only one argument is provided.
221 * The start value if 2 or more arguments are provided. If only one
222 * argument is used the start value is 0.
223 * @param {number=} opt_stop The stop value. If left out then the first
224 * argument is used as the stop value.
225 * @param {number=} opt_step The number to increment with between each call to
226 * next. This can be negative.
227 * @return {!goog.iter.Iterator} A new iterator that returns the values in the
228 * range.
229 */
230goog.iter.range = function(startOrStop, opt_stop, opt_step) {
231 var start = 0;
232 var stop = startOrStop;
233 var step = opt_step || 1;
234 if (arguments.length > 1) {
235 start = startOrStop;
236 stop = opt_stop;
237 }
238 if (step == 0) {
239 throw Error('Range step argument must not be zero');
240 }
241
242 var newIter = new goog.iter.Iterator;
243 newIter.next = function() {
244 if (step > 0 && start >= stop || step < 0 && start <= stop) {
245 throw goog.iter.StopIteration;
246 }
247 var rv = start;
248 start += step;
249 return rv;
250 };
251 return newIter;
252};
253
254
255/**
256 * Joins the values in a iterator with a delimiter.
257 * @param {goog.iter.Iterable} iterable The iterator to get the values from.
258 * @param {string} deliminator The text to put between the values.
259 * @return {string} The joined value string.
260 */
261goog.iter.join = function(iterable, deliminator) {
262 return goog.iter.toArray(iterable).join(deliminator);
263};
264
265
266/**
267 * For every element in the iterator call a function and return a new iterator
268 * with that value.
269 *
270 * @param {goog.iter.Iterable} iterable The iterator to iterate over.
271 * @param {function(this:T,?,undefined,?):?} f The function to call for every
272 * element. This function
273 * takes 3 arguments (the element, undefined, and the iterator) and should
274 * return a new value.
275 * @param {T=} opt_obj The object to be used as the value of 'this' within
276 * {@code f}.
277 * @return {!goog.iter.Iterator} A new iterator that returns the results of
278 * applying the function to each element in the original iterator.
279 * @template T
280 */
281goog.iter.map = function(iterable, f, opt_obj) {
282 var iterator = goog.iter.toIterator(iterable);
283 var newIter = new goog.iter.Iterator;
284 newIter.next = function() {
285 while (true) {
286 var val = iterator.next();
287 return f.call(opt_obj, val, undefined, iterator);
288 }
289 };
290 return newIter;
291};
292
293
294/**
295 * Passes every element of an iterator into a function and accumulates the
296 * result.
297 *
298 * @param {goog.iter.Iterable} iterable The iterator to iterate over.
299 * @param {function(this:T,V,?):V} f The function to call for every
300 * element. This function takes 2 arguments (the function's previous result
301 * or the initial value, and the value of the current element).
302 * function(previousValue, currentElement) : newValue.
303 * @param {V} val The initial value to pass into the function on the first call.
304 * @param {T=} opt_obj The object to be used as the value of 'this'
305 * within f.
306 * @return {V} Result of evaluating f repeatedly across the values of
307 * the iterator.
308 * @template T,V
309 */
310goog.iter.reduce = function(iterable, f, val, opt_obj) {
311 var rval = val;
312 goog.iter.forEach(iterable, function(val) {
313 rval = f.call(opt_obj, rval, val);
314 });
315 return rval;
316};
317
318
319/**
320 * Goes through the values in the iterator. Calls f for each these and if any of
321 * them returns true, this returns true (without checking the rest). If all
322 * return false this will return false.
323 *
324 * @param {goog.iter.Iterable} iterable The iterator object.
325 * @param {function(this:T,?,undefined,?):boolean} f The function to call for
326 * every value. This function
327 * takes 3 arguments (the value, undefined, and the iterator) and should
328 * return a boolean.
329 * @param {T=} opt_obj The object to be used as the value of 'this' within
330 * {@code f}.
331 * @return {boolean} true if any value passes the test.
332 * @template T
333 */
334goog.iter.some = function(iterable, f, opt_obj) {
335 iterable = goog.iter.toIterator(iterable);
336 /** @preserveTry */
337 try {
338 while (true) {
339 if (f.call(opt_obj, iterable.next(), undefined, iterable)) {
340 return true;
341 }
342 }
343 } catch (ex) {
344 if (ex !== goog.iter.StopIteration) {
345 throw ex;
346 }
347 }
348 return false;
349};
350
351
352/**
353 * Goes through the values in the iterator. Calls f for each these and if any of
354 * them returns false this returns false (without checking the rest). If all
355 * return true this will return true.
356 *
357 * @param {goog.iter.Iterable} iterable The iterator object.
358 * @param {function(this:T,?,undefined,?):boolean} f The function to call for
359 * every value. This function
360 * takes 3 arguments (the value, undefined, and the iterator) and should
361 * return a boolean.
362 * @param {T=} opt_obj The object to be used as the value of 'this' within
363 * {@code f}.
364 * @return {boolean} true if every value passes the test.
365 * @template T
366 */
367goog.iter.every = function(iterable, f, opt_obj) {
368 iterable = goog.iter.toIterator(iterable);
369 /** @preserveTry */
370 try {
371 while (true) {
372 if (!f.call(opt_obj, iterable.next(), undefined, iterable)) {
373 return false;
374 }
375 }
376 } catch (ex) {
377 if (ex !== goog.iter.StopIteration) {
378 throw ex;
379 }
380 }
381 return true;
382};
383
384
385/**
386 * Takes zero or more iterators and returns one iterator that will iterate over
387 * them in the order chained.
388 * @param {...goog.iter.Iterator} var_args Any number of iterator objects.
389 * @return {!goog.iter.Iterator} Returns a new iterator that will iterate over
390 * all the given iterators' contents.
391 */
392goog.iter.chain = function(var_args) {
393 var args = arguments;
394 var length = args.length;
395 var i = 0;
396 var newIter = new goog.iter.Iterator;
397
398 /**
399 * @return {*} The next item in the iteration.
400 * @this {goog.iter.Iterator}
401 */
402 newIter.next = function() {
403 /** @preserveTry */
404 try {
405 if (i >= length) {
406 throw goog.iter.StopIteration;
407 }
408 var current = goog.iter.toIterator(args[i]);
409 return current.next();
410 } catch (ex) {
411 if (ex !== goog.iter.StopIteration || i >= length) {
412 throw ex;
413 } else {
414 // In case we got a StopIteration increment counter and try again.
415 i++;
416 return this.next();
417 }
418 }
419 };
420
421 return newIter;
422};
423
424
425/**
426 * Builds a new iterator that iterates over the original, but skips elements as
427 * long as a supplied function returns true.
428 * @param {goog.iter.Iterable} iterable The iterator object.
429 * @param {function(this:T,?,undefined,?):boolean} f The function to call for
430 * every value. This function
431 * takes 3 arguments (the value, undefined, and the iterator) and should
432 * return a boolean.
433 * @param {T=} opt_obj The object to be used as the value of 'this' within
434 * {@code f}.
435 * @return {!goog.iter.Iterator} A new iterator that drops elements from the
436 * original iterator as long as {@code f} is true.
437 * @template T
438 */
439goog.iter.dropWhile = function(iterable, f, opt_obj) {
440 var iterator = goog.iter.toIterator(iterable);
441 var newIter = new goog.iter.Iterator;
442 var dropping = true;
443 newIter.next = function() {
444 while (true) {
445 var val = iterator.next();
446 if (dropping && f.call(opt_obj, val, undefined, iterator)) {
447 continue;
448 } else {
449 dropping = false;
450 }
451 return val;
452 }
453 };
454 return newIter;
455};
456
457
458/**
459 * Builds a new iterator that iterates over the original, but only as long as a
460 * supplied function returns true.
461 * @param {goog.iter.Iterable} iterable The iterator object.
462 * @param {function(this:T,?,undefined,?):boolean} f The function to call for
463 * every value. This function
464 * takes 3 arguments (the value, undefined, and the iterator) and should
465 * return a boolean.
466 * @param {T=} opt_obj This is used as the 'this' object in f when called.
467 * @return {!goog.iter.Iterator} A new iterator that keeps elements in the
468 * original iterator as long as the function is true.
469 * @template T
470 */
471goog.iter.takeWhile = function(iterable, f, opt_obj) {
472 var iterator = goog.iter.toIterator(iterable);
473 var newIter = new goog.iter.Iterator;
474 var taking = true;
475 newIter.next = function() {
476 while (true) {
477 if (taking) {
478 var val = iterator.next();
479 if (f.call(opt_obj, val, undefined, iterator)) {
480 return val;
481 } else {
482 taking = false;
483 }
484 } else {
485 throw goog.iter.StopIteration;
486 }
487 }
488 };
489 return newIter;
490};
491
492
493/**
494 * Converts the iterator to an array
495 * @param {goog.iter.Iterable} iterable The iterator to convert to an array.
496 * @return {!Array} An array of the elements the iterator iterates over.
497 */
498goog.iter.toArray = function(iterable) {
499 // Fast path for array-like.
500 if (goog.isArrayLike(iterable)) {
501 return goog.array.toArray(/** @type {!goog.array.ArrayLike} */(iterable));
502 }
503 iterable = goog.iter.toIterator(iterable);
504 var array = [];
505 goog.iter.forEach(iterable, function(val) {
506 array.push(val);
507 });
508 return array;
509};
510
511
512/**
513 * Iterates over 2 iterators and returns true if they contain the same sequence
514 * of elements and have the same length.
515 * @param {goog.iter.Iterable} iterable1 The first iterable object.
516 * @param {goog.iter.Iterable} iterable2 The second iterable object.
517 * @return {boolean} true if the iterators contain the same sequence of
518 * elements and have the same length.
519 */
520goog.iter.equals = function(iterable1, iterable2) {
521 iterable1 = goog.iter.toIterator(iterable1);
522 iterable2 = goog.iter.toIterator(iterable2);
523 var b1, b2;
524 /** @preserveTry */
525 try {
526 while (true) {
527 b1 = b2 = false;
528 var val1 = iterable1.next();
529 b1 = true;
530 var val2 = iterable2.next();
531 b2 = true;
532 if (val1 != val2) {
533 return false;
534 }
535 }
536 } catch (ex) {
537 if (ex !== goog.iter.StopIteration) {
538 throw ex;
539 } else {
540 if (b1 && !b2) {
541 // iterable1 done but iterable2 is not done.
542 return false;
543 }
544 if (!b2) {
545 /** @preserveTry */
546 try {
547 // iterable2 not done?
548 val2 = iterable2.next();
549 // iterable2 not done but iterable1 is done
550 return false;
551 } catch (ex1) {
552 if (ex1 !== goog.iter.StopIteration) {
553 throw ex1;
554 }
555 // iterable2 done as well... They are equal
556 return true;
557 }
558 }
559 }
560 }
561 return false;
562};
563
564
565/**
566 * Advances the iterator to the next position, returning the given default value
567 * instead of throwing an exception if the iterator has no more entries.
568 * @param {goog.iter.Iterable} iterable The iterable object.
569 * @param {*} defaultValue The value to return if the iterator is empty.
570 * @return {*} The next item in the iteration, or defaultValue if the iterator
571 * was empty.
572 */
573goog.iter.nextOrValue = function(iterable, defaultValue) {
574 try {
575 return goog.iter.toIterator(iterable).next();
576 } catch (e) {
577 if (e != goog.iter.StopIteration) {
578 throw e;
579 }
580 return defaultValue;
581 }
582};
583
584
585/**
586 * Cartesian product of zero or more sets. Gives an iterator that gives every
587 * combination of one element chosen from each set. For example,
588 * ([1, 2], [3, 4]) gives ([1, 3], [1, 4], [2, 3], [2, 4]).
589 * @see http://docs.python.org/library/itertools.html#itertools.product
590 * @param {...!goog.array.ArrayLike.<*>} var_args Zero or more sets, as arrays.
591 * @return {!goog.iter.Iterator} An iterator that gives each n-tuple (as an
592 * array).
593 */
594goog.iter.product = function(var_args) {
595 var someArrayEmpty = goog.array.some(arguments, function(arr) {
596 return !arr.length;
597 });
598
599 // An empty set in a cartesian product gives an empty set.
600 if (someArrayEmpty || !arguments.length) {
601 return new goog.iter.Iterator();
602 }
603
604 var iter = new goog.iter.Iterator();
605 var arrays = arguments;
606
607 // The first indicies are [0, 0, ...]
608 var indicies = goog.array.repeat(0, arrays.length);
609
610 iter.next = function() {
611
612 if (indicies) {
613 var retVal = goog.array.map(indicies, function(valueIndex, arrayIndex) {
614 return arrays[arrayIndex][valueIndex];
615 });
616
617 // Generate the next-largest indicies for the next call.
618 // Increase the rightmost index. If it goes over, increase the next
619 // rightmost (like carry-over addition).
620 for (var i = indicies.length - 1; i >= 0; i--) {
621 // Assertion prevents compiler warning below.
622 goog.asserts.assert(indicies);
623 if (indicies[i] < arrays[i].length - 1) {
624 indicies[i]++;
625 break;
626 }
627
628 // We're at the last indicies (the last element of every array), so
629 // the iteration is over on the next call.
630 if (i == 0) {
631 indicies = null;
632 break;
633 }
634 // Reset the index in this column and loop back to increment the
635 // next one.
636 indicies[i] = 0;
637 }
638 return retVal;
639 }
640
641 throw goog.iter.StopIteration;
642 };
643
644 return iter;
645};
646
647
648/**
649 * Create an iterator to cycle over the iterable's elements indefinitely.
650 * For example, ([1, 2, 3]) would return : 1, 2, 3, 1, 2, 3, ...
651 * @see: http://docs.python.org/library/itertools.html#itertools.cycle.
652 * @param {!goog.iter.Iterable} iterable The iterable object.
653 * @return {!goog.iter.Iterator} An iterator that iterates indefinitely over
654 * the values in {@code iterable}.
655 */
656goog.iter.cycle = function(iterable) {
657
658 var baseIterator = goog.iter.toIterator(iterable);
659
660 // We maintain a cache to store the iterable elements as we iterate
661 // over them. The cache is used to return elements once we have
662 // iterated over the iterable once.
663 var cache = [];
664 var cacheIndex = 0;
665
666 var iter = new goog.iter.Iterator();
667
668 // This flag is set after the iterable is iterated over once
669 var useCache = false;
670
671 iter.next = function() {
672 var returnElement = null;
673
674 // Pull elements off the original iterator if not using cache
675 if (!useCache) {
676 try {
677 // Return the element from the iterable
678 returnElement = baseIterator.next();
679 cache.push(returnElement);
680 return returnElement;
681 } catch (e) {
682 // If an exception other than StopIteration is thrown
683 // or if there are no elements to iterate over (the iterable was empty)
684 // throw an exception
685 if (e != goog.iter.StopIteration || goog.array.isEmpty(cache)) {
686 throw e;
687 }
688 // set useCache to true after we know that a 'StopIteration' exception
689 // was thrown and the cache is not empty (to handle the 'empty iterable'
690 // use case)
691 useCache = true;
692 }
693 }
694
695 returnElement = cache[cacheIndex];
696 cacheIndex = (cacheIndex + 1) % cache.length;
697
698 return returnElement;
699 };
700
701 return iter;
702};