// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// Copyright 2007 Google Inc. All Rights Reserved.
/**
* @fileoverview Python style iteration utilities.
*/
goog.provide('goog.iter');
goog.provide('goog.iter.Iterator');
goog.provide('goog.iter.StopIteration');
goog.require('goog.array');
/**
* @type {goog.iter.Iterator|{length:number}|{__iterator__}}
*/
goog.iter.Iterable = goog.typedef;
// For script engines that already support iterators.
if ('StopIteration' in goog.global) {
/**
* Singleton Error object that is used to terminate iterations.
* @type {Error}
*/
goog.iter.StopIteration = goog.global['StopIteration'];
} else {
/**
* Singleton Error object that is used to terminate iterations.
* @type {Error}
* @suppress {duplicate}
*/
goog.iter.StopIteration = Error('StopIteration');
}
/**
* Class/interface for iterators. An iterator needs to implement a {@code next}
* method and it needs to throw a {@code goog.iter.StopIteration} when the
* iteration passes beyond the end. Iterators have no {@code hasNext} method.
* It is recommended to always use the helper functions to iterate over the
* iterator or in case you are only targeting JavaScript 1.7 for in loops.
* @constructor
*/
goog.iter.Iterator = function() {};
/**
* Returns the next value of the iteration. This will throw the object
* {@see goog.iter#StopIteration} when the iteration passes the end.
* @return {*} Any object or value.
*/
goog.iter.Iterator.prototype.next = function() {
throw goog.iter.StopIteration;
};
/**
* Returns the {@code Iterator} object itself. This is used to implement
* the iterator protocol in JavaScript 1.7
* @param {boolean} opt_keys Whether to return the keys or values. Default is
* to only return the values. This is being used by the for-in loop (true)
* and the for-each-in loop (false). Even though the param gives a hint
* about what the iterator will return there is no guarantee that it will
* return the keys when true is passed.
* @return {!goog.iter.Iterator} The object itself.
*/
goog.iter.Iterator.prototype.__iterator__ = function(opt_keys) {
return this;
};
/**
* Returns an iterator that knows how to iterate over the values in the object.
* @param {goog.iter.Iterable} iterable If the object is an iterator it
* will be returned as is. If the object has a {@code __iterator__} method
* that will be called to get the value iterator. If the object is an
* array-like object we create an iterator for that.
* @return {!goog.iter.Iterator} An iterator that knows how to iterate over the
* values in {@code iterable}.
*/
goog.iter.toIterator = function(iterable) {
if (iterable instanceof goog.iter.Iterator) {
return iterable;
}
if (typeof iterable.__iterator__ == 'function') {
return iterable.__iterator__(false);
}
if (goog.isArrayLike(iterable)) {
var i = 0;
var newIter = new goog.iter.Iterator;
newIter.next = function() {
while (true) {
if (i >= iterable.length) {
throw goog.iter.StopIteration;
}
// Don't include deleted elements.
if (!(i in iterable)) {
i++;
continue;
}
return iterable[i++];
}
};
return newIter;
}
// TODO: Should we fall back on goog.structs.getValues()?
throw Error('Not implemented');
};
/**
* Calls a function for each element in the iterator with the element of the
* iterator passed as argument.
*
* @param {goog.iter.Iterable} iterable The iterator to iterate
* over. If the iterable is an object {@code toIterator} will be called on
* it.
* @param {Function} f The function to call for every element. This function
* takes 3 arguments (the element, undefined, and the iterator) and the
* return value is irrelevant. The reason for passing undefined as the
* second argument is so that the same function can be used in
* {@see goog.array#forEach} as well as others.
* @param {Object} opt_obj The object to be used as the value of 'this' within
* {@code f}.
*/
goog.iter.forEach = function(iterable, f, opt_obj) {
if (goog.isArrayLike(iterable)) {
/** @preserveTry */
try {
goog.array.forEach((/** @type {goog.array.ArrayLike} */ iterable), f,
opt_obj);
} catch (ex) {
if (ex !== goog.iter.StopIteration) {
throw ex;
}
}
} else {
iterable = goog.iter.toIterator(iterable);
/** @preserveTry */
try {
while (true) {
f.call(opt_obj, iterable.next(), undefined, iterable);
}
} catch (ex) {
if (ex !== goog.iter.StopIteration) {
throw ex;
}
}
}
};
/**
* Calls a function for every element in the iterator, and if the function
* returns true adds the element to a new iterator.
*
* @param {goog.iter.Iterable} iterable The iterator to iterate over.
* @param {Function} f The function to call for every element. This function
* takes 3 arguments (the element, undefined, and the iterator) and should
* return a boolean. If the return value is true the element will be
* included in the returned iteror. If it is false the element is not
* included.
* @param {Object} opt_obj The object to be used as the value of 'this' within
* {@code f}.
* @return {!goog.iter.Iterator} A new iterator in which only elements that
* passed the test are present.
*/
goog.iter.filter = function(iterable, f, opt_obj) {
iterable = goog.iter.toIterator(iterable);
var newIter = new goog.iter.Iterator;
newIter.next = function() {
while (true) {
var val = iterable.next();
if (f.call(opt_obj, val, undefined, iterable)) {
return val;
}
}
};
return newIter;
};
/**
* Creates a new iterator that returns the values in a range. This function
* can take 1, 2 or 3 arguments:
* <pre>
* range(5) same as range(0, 5, 1)
* range(2, 5) same as range(2, 5, 1)
* </pre>
*
* @param {number} startOrStop The stop value if only one argument is provided.
* The start value if 2 or more arguments are provided. If only one
* argument is used the start value is 0.
* @param {number} opt_stop The stop value. If left out then the first
* argument is used as the stop value.
* @param {number} opt_step The number to increment with between each call to
* next. This can be negative.
* @return {!goog.iter.Iterator} A new iterator that returns the values in the
* range.
*/
goog.iter.range = function(startOrStop, opt_stop, opt_step) {
var start = 0;
var stop = startOrStop;
var step = opt_step || 1;
if (arguments.length > 1) {
start = startOrStop;
stop = opt_stop;
}
if (step == 0) {
throw Error('Range step argument must not be zero');
}
var newIter = new goog.iter.Iterator;
newIter.next = function() {
if (step > 0 && start >= stop || step < 0 && start <= stop) {
throw goog.iter.StopIteration;
}
var rv = start;
start += step;
return rv;
};
return newIter;
};
/**
* Joins the values in a iterator with a delimiter.
* @param {goog.iter.Iterable} iterable The iterator to get the values from.
* @param {string} deliminator The text to put between the values.
* @return {string} The joined value string.
*/
goog.iter.join = function(iterable, deliminator) {
return goog.iter.toArray(iterable).join(deliminator);
};
/**
* For every element in the iterator call a function and return a new iterator
* with that value.
*
* @param {goog.iter.Iterable} iterable The iterator to iterate over.
* @param {Function} f The function to call for every element. This function
* takes 3 arguments (the element, undefined, and the iterator) and should
* return a new value.
* @param {Object} opt_obj The object to be used as the value of 'this' within
* {@code f}.
* @return {!goog.iter.Iterator} A new iterator that returns the results of
* applying the function to each element in the original iterator.
*/
goog.iter.map = function(iterable, f, opt_obj) {
iterable = goog.iter.toIterator(iterable);
var newIter = new goog.iter.Iterator;
newIter.next = function() {
while (true) {
var val = iterable.next();
return f.call(opt_obj, val, undefined, iterable);
}
};
return newIter;
};
/**
* Passes every element of an iterator into a function and accumulates the
* result.
*
* @param {goog.iter.Iterable} iterable The iterator to iterate over.
* @param {Function} f The function to call for every element. This function
* takes 2 arguments (the function's previous result or the initial value,
* and the value of the current element).
* function(previousValue, currentElement) : newValue.
* @param {*} val The initial value to pass into the function on the first call.
* @param {Object} opt_obj The object to be used as the value of 'this'
* within f.
* @return {*} Result of evaluating f repeatedly across the values of
* the iterator.
*/
goog.iter.reduce = function(iterable, f, val, opt_obj) {
var rval = val;
goog.iter.forEach(iterable, function(val) {
rval = f.call(opt_obj, rval, val);
});
return rval;
};
/**
* Goes through the values in the iterator. Calls f for each these and if any of
* them returns true, this returns true (without checking the rest). If all
* return false this will return false.
*
* @param {goog.iter.Iterable} iterable The iterator object.
* @param {Function} f The function to call for every value. This function
* takes 3 arguments (the value, undefined, and the iterator) and should
* return a boolean.
* @param {Object} opt_obj The object to be used as the value of 'this' within
* {@code f}.
* @return {boolean} true if any value passes the test.
*/
goog.iter.some = function(iterable, f, opt_obj) {
iterable = goog.iter.toIterator(iterable);
/** @preserveTry */
try {
while (true) {
if (f.call(opt_obj, iterable.next(), undefined, iterable)) {
return true;
}
}
} catch (ex) {
if (ex !== goog.iter.StopIteration) {
throw ex;
}
}
return false;
};
/**
* Goes through the values in the iterator. Calls f for each these and if any of
* them returns false this returns false (without checking the rest). If all
* return true this will return true.
*
* @param {goog.iter.Iterable} iterable The iterator object.
* @param {Function} f The function to call for every value. This function
* takes 3 arguments (the value, undefined, and the iterator) and should
* return a boolean.
* @param {Object} opt_obj The object to be used as the value of 'this' within
* {@code f}.
* @return {boolean} true if every value passes the test.
*/
goog.iter.every = function(iterable, f, opt_obj) {
iterable = goog.iter.toIterator(iterable);
/** @preserveTry */
try {
while (true) {
if (!f.call(opt_obj, iterable.next(), undefined, iterable)) {
return false;
}
}
} catch (ex) {
if (ex !== goog.iter.StopIteration) {
throw ex;
}
}
return true;
};
/**
* Takes zero or more iterators and returns one iterator that will iterate over
* them in the order chained.
* @param {goog.iter.Iterator} var_args Any number of iterator objects.
* @return {!goog.iter.Iterator} Returns a new iterator that will iterate over
* all the given iterators' contents.
*/
goog.iter.chain = function(var_args) {
var args = arguments;
var length = args.length;
var i = 0;
var newIter = new goog.iter.Iterator;
newIter.next = function() {
/** @preserveTry */
try {
if (i >= length) {
throw goog.iter.StopIteration;
}
var current = goog.iter.toIterator(args[i]);
return current.next();
} catch (ex) {
if (ex !== goog.iter.StopIteration || i >= length) {
throw ex;
} else {
// In case we got a StopIteration increment counter and try again.
i++;
return this.next();
}
}
};
return newIter;
};
/**
* Builds a new iterator that iterates over the original, but skips elements as
* long as a supplied function returns true.
* @param {goog.iter.Iterable} iterable The iterator object.
* @param {Function} f The function to call for every value. This function
* takes 3 arguments (the value, undefined, and the iterator) and should
* return a boolean.
* @param {Object} opt_obj The object to be used as the value of 'this' within
* {@code f}.
* @return {!goog.iter.Iterator} A new iterator that drops elements from the
* original iterator as long as {@code f} is true.
*/
goog.iter.dropWhile = function(iterable, f, opt_obj) {
iterable = goog.iter.toIterator(iterable);
var newIter = new goog.iter.Iterator;
var dropping = true;
newIter.next = function() {
while (true) {
var val = iterable.next();
if (dropping && f.call(opt_obj, val, undefined, iterable)) {
continue;
} else {
dropping = false;
}
return val;
}
};
return newIter;
};
/**
* Builds a new iterator that iterates over the original, but only as long as a
* supplied function returns true.
* @param {goog.iter.Iterable} iterable The iterator object.
* @param {Function} f The function to call for every value. This function
* takes 3 arguments (the value, undefined, and the iterator) and should
* return a boolean.
* @param {Object} opt_obj This is used as the 'this' object in f when called.
* @return {!goog.iter.Iterator} A new iterator that keeps elements in the
* original iterator as long as the function is true.
*/
goog.iter.takeWhile = function(iterable, f, opt_obj) {
iterable = goog.iter.toIterator(iterable);
var newIter = new goog.iter.Iterator;
var taking = true;
newIter.next = function() {
while (true) {
if (taking) {
var val = iterable.next();
if (f.call(opt_obj, val, undefined, iterable)) {
return val;
} else {
taking = false;
}
} else {
throw goog.iter.StopIteration;
}
}
};
return newIter;
};
/**
* Converts the iterator to an array
* @param {goog.iter.Iterable} iterable The iterator to convert to an array.
* @return {!Array} An array of the elements the iterator iterates over.
*/
goog.iter.toArray = function(iterable) {
// Fast path for array-like.
if (goog.isArrayLike(iterable)) {
return goog.array.toArray((/** @type {!goog.array.ArrayLike} */ iterable));
}
iterable = goog.iter.toIterator(iterable);
var array = [];
goog.iter.forEach(iterable, function(val) {
array.push(val);
});
return array;
};
/**
* Iterates over 2 iterators and returns true if they contain the same sequence
* of elements and have the same length.
* @param {goog.iter.Iterable} iterable1 The first iterable object.
* @param {goog.iter.Iterable} iterable2 The second iterable object.
* @return {boolean} true if the iterators contain the same sequence of
* elements and have the same length.
*/
goog.iter.equals = function(iterable1, iterable2) {
iterable1 = goog.iter.toIterator(iterable1);
iterable2 = goog.iter.toIterator(iterable2);
var b1, b2;
/** @preserveTry */
try {
while (true) {
b1 = b2 = false;
var val1 = iterable1.next();
b1 = true;
var val2 = iterable2.next();
b2 = true;
if (val1 != val2) {
return false;
}
}
} catch (ex) {
if (ex !== goog.iter.StopIteration) {
throw ex;
} else {
if (b1 && !b2) {
// iterable1 done but iterable2 is not done.
return false;
}
if (!b2) {
/** @preserveTry */
try {
// iterable2 not done?
val2 = iterable2.next();
// iterable2 not done but iterable1 is done
return false;
} catch (ex1) {
if (ex1 !== goog.iter.StopIteration) {
throw ex1;
}
// iterable2 done as well... They are equal
return true;
}
}
}
}
return false;
};
/**
* Advances the iterator to the next position, returning the given default value
* instead of throwing an exception if the iterator has no more entries.
* @param {goog.iter.Iterable} iterable The iterable object.
* @param {*} defaultValue The value to return if the iterator is empty.
* @return {*} The next item in the iteration, or defaultValue if the iterator
* was empty.
*/
goog.iter.nextOrValue = function(iterable, defaultValue) {
try {
return goog.iter.toIterator(iterable).next();
} catch (e) {
if (e != goog.iter.StopIteration) {
throw e;
}
return defaultValue;
}
};