| 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 |
}; |