Debian Codegraph @

closure-library/closure/goog/array/array.js

raw
1 // Copyright 2006 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 Utilities for manipulating arrays.
17 *
18 * @author [email protected] (Erik Arvidsson)
19 */
20
21
22 goog.provide('goog.array');
23
24 goog.require('goog.asserts');
25
26
27 /**
28 * @define {boolean} NATIVE_ARRAY_PROTOTYPES indicates whether the code should
29 * rely on Array.prototype functions, if available.
30 *
31 * The Array.prototype functions can be defined by external libraries like
32 * Prototype and setting this flag to false forces closure to use its own
33 * goog.array implementation.
34 *
35 * If your javascript can be loaded by a third party site and you are wary about
36 * relying on the prototype functions, specify
37 * "--define goog.NATIVE_ARRAY_PROTOTYPES=false" to the JSCompiler.
38 *
39 * Setting goog.TRUSTED_SITE to false will automatically set
40 * NATIVE_ARRAY_PROTOTYPES to false.
41 */
42 goog.define('goog.NATIVE_ARRAY_PROTOTYPES', goog.TRUSTED_SITE);
43
44
45 /**
46 * @define {boolean} If true, JSCompiler will use the native implementation of
47 * array functions where appropriate (e.g., {@code Array#filter}) and remove the
48 * unused pure JS implementation.
49 */
50 goog.define('goog.array.ASSUME_NATIVE_FUNCTIONS', false);
51
52
53 /**
54 * Returns the last element in an array without removing it.
55 * Same as goog.array.last.
56 * @param {IArrayLike<T>|string} array The array.
57 * @return {T} Last item in array.
58 * @template T
59 */
60 goog.array.peek = function(array) {
61 return array[array.length - 1];
62 };
63
64
65 /**
66 * Returns the last element in an array without removing it.
67 * Same as goog.array.peek.
68 * @param {IArrayLike<T>|string} array The array.
69 * @return {T} Last item in array.
70 * @template T
71 */
72 goog.array.last = goog.array.peek;
73
74 // NOTE(arv): Since most of the array functions are generic it allows you to
75 // pass an array-like object. Strings have a length and are considered array-
76 // like. However, the 'in' operator does not work on strings so we cannot just
77 // use the array path even if the browser supports indexing into strings. We
78 // therefore end up splitting the string.
79
80
81 /**
82 * Returns the index of the first element of an array with a specified value, or
83 * -1 if the element is not present in the array.
84 *
85 * See {@link http://tinyurl.com/developer-mozilla-org-array-indexof}
86 *
87 * @param {IArrayLike<T>|string} arr The array to be searched.
88 * @param {T} obj The object for which we are searching.
89 * @param {number=} opt_fromIndex The index at which to start the search. If
90 * omitted the search starts at index 0.
91 * @return {number} The index of the first matching array element.
92 * @template T
93 */
94 goog.array.indexOf = goog.NATIVE_ARRAY_PROTOTYPES &&
95 (goog.array.ASSUME_NATIVE_FUNCTIONS || Array.prototype.indexOf) ?
96 function(arr, obj, opt_fromIndex) {
97 goog.asserts.assert(arr.length != null);
98
99 return Array.prototype.indexOf.call(arr, obj, opt_fromIndex);
100 } :
101 function(arr, obj, opt_fromIndex) {
102 var fromIndex = opt_fromIndex == null ?
103 0 :
104 (opt_fromIndex < 0 ? Math.max(0, arr.length + opt_fromIndex) :
105 opt_fromIndex);
106
107 if (goog.isString(arr)) {
108 // Array.prototype.indexOf uses === so only strings should be found.
109 if (!goog.isString(obj) || obj.length != 1) {
110 return -1;
111 }
112 return arr.indexOf(obj, fromIndex);
113 }
114
115 for (var i = fromIndex; i < arr.length; i++) {
116 if (i in arr && arr[i] === obj) return i;
117 }
118 return -1;
119 };
120
121
122 /**
123 * Returns the index of the last element of an array with a specified value, or
124 * -1 if the element is not present in the array.
125 *
126 * See {@link http://tinyurl.com/developer-mozilla-org-array-lastindexof}
127 *
128 * @param {!IArrayLike<T>|string} arr The array to be searched.
129 * @param {T} obj The object for which we are searching.
130 * @param {?number=} opt_fromIndex The index at which to start the search. If
131 * omitted the search starts at the end of the array.
132 * @return {number} The index of the last matching array element.
133 * @template T
134 */
135 goog.array.lastIndexOf = goog.NATIVE_ARRAY_PROTOTYPES &&
136 (goog.array.ASSUME_NATIVE_FUNCTIONS || Array.prototype.lastIndexOf) ?
137 function(arr, obj, opt_fromIndex) {
138 goog.asserts.assert(arr.length != null);
139
140 // Firefox treats undefined and null as 0 in the fromIndex argument which
141 // leads it to always return -1
142 var fromIndex = opt_fromIndex == null ? arr.length - 1 : opt_fromIndex;
143 return Array.prototype.lastIndexOf.call(arr, obj, fromIndex);
144 } :
145 function(arr, obj, opt_fromIndex) {
146 var fromIndex = opt_fromIndex == null ? arr.length - 1 : opt_fromIndex;
147
148 if (fromIndex < 0) {
149 fromIndex = Math.max(0, arr.length + fromIndex);
150 }
151
152 if (goog.isString(arr)) {
153 // Array.prototype.lastIndexOf uses === so only strings should be found.
154 if (!goog.isString(obj) || obj.length != 1) {
155 return -1;
156 }
157 return arr.lastIndexOf(obj, fromIndex);
158 }
159
160 for (var i = fromIndex; i >= 0; i--) {
161 if (i in arr && arr[i] === obj) return i;
162 }
163 return -1;
164 };
165
166
167 /**
168 * Calls a function for each element in an array. Skips holes in the array.
169 * See {@link http://tinyurl.com/developer-mozilla-org-array-foreach}
170 *
171 * @param {IArrayLike<T>|string} arr Array or array like object over
172 * which to iterate.
173 * @param {?function(this: S, T, number, ?): ?} f The function to call for every
174 * element. This function takes 3 arguments (the element, the index and the
175 * array). The return value is ignored.
176 * @param {S=} opt_obj The object to be used as the value of 'this' within f.
177 * @template T,S
178 */
179 goog.array.forEach = goog.NATIVE_ARRAY_PROTOTYPES &&
180 (goog.array.ASSUME_NATIVE_FUNCTIONS || Array.prototype.forEach) ?
181 function(arr, f, opt_obj) {
182 goog.asserts.assert(arr.length != null);
183
184 Array.prototype.forEach.call(arr, f, opt_obj);
185 } :
186 function(arr, f, opt_obj) {
187 var l = arr.length; // must be fixed during loop... see docs
188 var arr2 = goog.isString(arr) ? arr.split('') : arr;
189 for (var i = 0; i < l; i++) {
190 if (i in arr2) {
191 f.call(/** @type {?} */ (opt_obj), arr2[i], i, arr);
192 }
193 }
194 };
195
196
197 /**
198 * Calls a function for each element in an array, starting from the last
199 * element rather than the first.
200 *
201 * @param {IArrayLike<T>|string} arr Array or array
202 * like object over which to iterate.
203 * @param {?function(this: S, T, number, ?): ?} f The function to call for every
204 * element. This function
205 * takes 3 arguments (the element, the index and the array). The return
206 * value is ignored.
207 * @param {S=} opt_obj The object to be used as the value of 'this'
208 * within f.
209 * @template T,S
210 */
211 goog.array.forEachRight = function(arr, f, opt_obj) {
212 var l = arr.length; // must be fixed during loop... see docs
213 var arr2 = goog.isString(arr) ? arr.split('') : arr;
214 for (var i = l - 1; i >= 0; --i) {
215 if (i in arr2) {
216 f.call(/** @type {?} */ (opt_obj), arr2[i], i, arr);
217 }
218 }
219 };
220
221
222 /**
223 * Calls a function for each element in an array, and if the function returns
224 * true adds the element to a new array.
225 *
226 * See {@link http://tinyurl.com/developer-mozilla-org-array-filter}
227 *
228 * @param {IArrayLike<T>|string} arr Array or array
229 * like object over which to iterate.
230 * @param {?function(this:S, T, number, ?):boolean} f The function to call for
231 * every element. This function
232 * takes 3 arguments (the element, the index and the array) and must
233 * return a Boolean. If the return value is true the element is added to the
234 * result array. If it is false the element is not included.
235 * @param {S=} opt_obj The object to be used as the value of 'this'
236 * within f.
237 * @return {!Array<T>} a new array in which only elements that passed the test
238 * are present.
239 * @template T,S
240 */
241 goog.array.filter = goog.NATIVE_ARRAY_PROTOTYPES &&
242 (goog.array.ASSUME_NATIVE_FUNCTIONS || Array.prototype.filter) ?
243 function(arr, f, opt_obj) {
244 goog.asserts.assert(arr.length != null);
245
246 return Array.prototype.filter.call(arr, f, opt_obj);
247 } :
248 function(arr, f, opt_obj) {
249 var l = arr.length; // must be fixed during loop... see docs
250 var res = [];
251 var resLength = 0;
252 var arr2 = goog.isString(arr) ? arr.split('') : arr;
253 for (var i = 0; i < l; i++) {
254 if (i in arr2) {
255 var val = arr2[i]; // in case f mutates arr2
256 if (f.call(/** @type {?} */ (opt_obj), val, i, arr)) {
257 res[resLength++] = val;
258 }
259 }
260 }
261 return res;
262 };
263
264
265 /**
266 * Calls a function for each element in an array and inserts the result into a
267 * new array.
268 *
269 * See {@link http://tinyurl.com/developer-mozilla-org-array-map}
270 *
271 * @param {IArrayLike<VALUE>|string} arr Array or array like object
272 * over which to iterate.
273 * @param {function(this:THIS, VALUE, number, ?): RESULT} f The function to call
274 * for every element. This function takes 3 arguments (the element,
275 * the index and the array) and should return something. The result will be
276 * inserted into a new array.
277 * @param {THIS=} opt_obj The object to be used as the value of 'this' within f.
278 * @return {!Array<RESULT>} a new array with the results from f.
279 * @template THIS, VALUE, RESULT
280 */
281 goog.array.map = goog.NATIVE_ARRAY_PROTOTYPES &&
282 (goog.array.ASSUME_NATIVE_FUNCTIONS || Array.prototype.map) ?
283 function(arr, f, opt_obj) {
284 goog.asserts.assert(arr.length != null);
285
286 return Array.prototype.map.call(arr, f, opt_obj);
287 } :
288 function(arr, f, opt_obj) {
289 var l = arr.length; // must be fixed during loop... see docs
290 var res = new Array(l);
291 var arr2 = goog.isString(arr) ? arr.split('') : arr;
292 for (var i = 0; i < l; i++) {
293 if (i in arr2) {
294 res[i] = f.call(/** @type {?} */ (opt_obj), arr2[i], i, arr);
295 }
296 }
297 return res;
298 };
299
300
301 /**
302 * Passes every element of an array into a function and accumulates the result.
303 *
304 * See {@link http://tinyurl.com/developer-mozilla-org-array-reduce}
305 *
306 * For example:
307 * var a = [1, 2, 3, 4];
308 * goog.array.reduce(a, function(r, v, i, arr) {return r + v;}, 0);
309 * returns 10
310 *
311 * @param {IArrayLike<T>|string} arr Array or array
312 * like object over which to iterate.
313 * @param {function(this:S, R, T, number, ?) : R} f The function to call for
314 * every element. This function
315 * takes 4 arguments (the function's previous result or the initial value,
316 * the value of the current array element, the current array index, and the
317 * array itself)
318 * function(previousValue, currentValue, index, array).
319 * @param {?} val The initial value to pass into the function on the first call.
320 * @param {S=} opt_obj The object to be used as the value of 'this'
321 * within f.
322 * @return {R} Result of evaluating f repeatedly across the values of the array.
323 * @template T,S,R
324 */
325 goog.array.reduce = goog.NATIVE_ARRAY_PROTOTYPES &&
326 (goog.array.ASSUME_NATIVE_FUNCTIONS || Array.prototype.reduce) ?
327 function(arr, f, val, opt_obj) {
328 goog.asserts.assert(arr.length != null);
329 if (opt_obj) {
330 f = goog.bind(f, opt_obj);
331 }
332 return Array.prototype.reduce.call(arr, f, val);
333 } :
334 function(arr, f, val, opt_obj) {
335 var rval = val;
336 goog.array.forEach(arr, function(val, index) {
337 rval = f.call(/** @type {?} */ (opt_obj), rval, val, index, arr);
338 });
339 return rval;
340 };
341
342
343 /**
344 * Passes every element of an array into a function and accumulates the result,
345 * starting from the last element and working towards the first.
346 *
347 * See {@link http://tinyurl.com/developer-mozilla-org-array-reduceright}
348 *
349 * For example:
350 * var a = ['a', 'b', 'c'];
351 * goog.array.reduceRight(a, function(r, v, i, arr) {return r + v;}, '');
352 * returns 'cba'
353 *
354 * @param {IArrayLike<T>|string} arr Array or array
355 * like object over which to iterate.
356 * @param {?function(this:S, R, T, number, ?) : R} f The function to call for
357 * every element. This function
358 * takes 4 arguments (the function's previous result or the initial value,
359 * the value of the current array element, the current array index, and the
360 * array itself)
361 * function(previousValue, currentValue, index, array).
362 * @param {?} val The initial value to pass into the function on the first call.
363 * @param {S=} opt_obj The object to be used as the value of 'this'
364 * within f.
365 * @return {R} Object returned as a result of evaluating f repeatedly across the
366 * values of the array.
367 * @template T,S,R
368 */
369 goog.array.reduceRight = goog.NATIVE_ARRAY_PROTOTYPES &&
370 (goog.array.ASSUME_NATIVE_FUNCTIONS || Array.prototype.reduceRight) ?
371 function(arr, f, val, opt_obj) {
372 goog.asserts.assert(arr.length != null);
373 goog.asserts.assert(f != null);
374 if (opt_obj) {
375 f = goog.bind(f, opt_obj);
376 }
377 return Array.prototype.reduceRight.call(arr, f, val);
378 } :
379 function(arr, f, val, opt_obj) {
380 var rval = val;
381 goog.array.forEachRight(arr, function(val, index) {
382 rval = f.call(/** @type {?} */ (opt_obj), rval, val, index, arr);
383 });
384 return rval;
385 };
386
387
388 /**
389 * Calls f for each element of an array. If any call returns true, some()
390 * returns true (without checking the remaining elements). If all calls
391 * return false, some() returns false.
392 *
393 * See {@link http://tinyurl.com/developer-mozilla-org-array-some}
394 *
395 * @param {IArrayLike<T>|string} arr Array or array
396 * like object over which to iterate.
397 * @param {?function(this:S, T, number, ?) : boolean} f The function to call for
398 * for every element. This function takes 3 arguments (the element, the
399 * index and the array) and should return a boolean.
400 * @param {S=} opt_obj The object to be used as the value of 'this'
401 * within f.
402 * @return {boolean} true if any element passes the test.
403 * @template T,S
404 */
405 goog.array.some = goog.NATIVE_ARRAY_PROTOTYPES &&
406 (goog.array.ASSUME_NATIVE_FUNCTIONS || Array.prototype.some) ?
407 function(arr, f, opt_obj) {
408 goog.asserts.assert(arr.length != null);
409
410 return Array.prototype.some.call(arr, f, opt_obj);
411 } :
412 function(arr, f, opt_obj) {
413 var l = arr.length; // must be fixed during loop... see docs
414 var arr2 = goog.isString(arr) ? arr.split('') : arr;
415 for (var i = 0; i < l; i++) {
416 if (i in arr2 && f.call(/** @type {?} */ (opt_obj), arr2[i], i, arr)) {
417 return true;
418 }
419 }
420 return false;
421 };
422
423
424 /**
425 * Call f for each element of an array. If all calls return true, every()
426 * returns true. If any call returns false, every() returns false and
427 * does not continue to check the remaining elements.
428 *
429 * See {@link http://tinyurl.com/developer-mozilla-org-array-every}
430 *
431 * @param {IArrayLike<T>|string} arr Array or array
432 * like object over which to iterate.
433 * @param {?function(this:S, T, number, ?) : boolean} f The function to call for
434 * for every element. This function takes 3 arguments (the element, the
435 * index and the array) and should return a boolean.
436 * @param {S=} opt_obj The object to be used as the value of 'this'
437 * within f.
438 * @return {boolean} false if any element fails the test.
439 * @template T,S
440 */
441 goog.array.every = goog.NATIVE_ARRAY_PROTOTYPES &&
442 (goog.array.ASSUME_NATIVE_FUNCTIONS || Array.prototype.every) ?
443 function(arr, f, opt_obj) {
444 goog.asserts.assert(arr.length != null);
445
446 return Array.prototype.every.call(arr, f, opt_obj);
447 } :
448 function(arr, f, opt_obj) {
449 var l = arr.length; // must be fixed during loop... see docs
450 var arr2 = goog.isString(arr) ? arr.split('') : arr;
451 for (var i = 0; i < l; i++) {
452 if (i in arr2 && !f.call(/** @type {?} */ (opt_obj), arr2[i], i, arr)) {
453 return false;
454 }
455 }
456 return true;
457 };
458
459
460 /**
461 * Counts the array elements that fulfill the predicate, i.e. for which the
462 * callback function returns true. Skips holes in the array.
463 *
464 * @param {!IArrayLike<T>|string} arr Array or array like object
465 * over which to iterate.
466 * @param {function(this: S, T, number, ?): boolean} f The function to call for
467 * every element. Takes 3 arguments (the element, the index and the array).
468 * @param {S=} opt_obj The object to be used as the value of 'this' within f.
469 * @return {number} The number of the matching elements.
470 * @template T,S
471 */
472 goog.array.count = function(arr, f, opt_obj) {
473 var count = 0;
474 goog.array.forEach(arr, function(element, index, arr) {
475 if (f.call(/** @type {?} */ (opt_obj), element, index, arr)) {
476 ++count;
477 }
478 }, opt_obj);
479 return count;
480 };
481
482
483 /**
484 * Search an array for the first element that satisfies a given condition and
485 * return that element.
486 * @param {IArrayLike<T>|string} arr Array or array
487 * like object over which to iterate.
488 * @param {?function(this:S, T, number, ?) : boolean} f The function to call
489 * for every element. This function takes 3 arguments (the element, the
490 * index and the array) and should return a boolean.
491 * @param {S=} opt_obj An optional "this" context for the function.
492 * @return {T|null} The first array element that passes the test, or null if no
493 * element is found.
494 * @template T,S
495 */
496 goog.array.find = function(arr, f, opt_obj) {
497 var i = goog.array.findIndex(arr, f, opt_obj);
498 return i < 0 ? null : goog.isString(arr) ? arr.charAt(i) : arr[i];
499 };
500
501
502 /**
503 * Search an array for the first element that satisfies a given condition and
504 * return its index.
505 * @param {IArrayLike<T>|string} arr Array or array
506 * like object over which to iterate.
507 * @param {?function(this:S, T, number, ?) : boolean} f The function to call for
508 * every element. This function
509 * takes 3 arguments (the element, the index and the array) and should
510 * return a boolean.
511 * @param {S=} opt_obj An optional "this" context for the function.
512 * @return {number} The index of the first array element that passes the test,
513 * or -1 if no element is found.
514 * @template T,S
515 */
516 goog.array.findIndex = function(arr, f, opt_obj) {
517 var l = arr.length; // must be fixed during loop... see docs
518 var arr2 = goog.isString(arr) ? arr.split('') : arr;
519 for (var i = 0; i < l; i++) {
520 if (i in arr2 && f.call(/** @type {?} */ (opt_obj), arr2[i], i, arr)) {
521 return i;
522 }
523 }
524 return -1;
525 };
526
527
528 /**
529 * Search an array (in reverse order) for the last element that satisfies a
530 * given condition and return that element.
531 * @param {IArrayLike<T>|string} arr Array or array
532 * like object over which to iterate.
533 * @param {?function(this:S, T, number, ?) : boolean} f The function to call
534 * for every element. This function
535 * takes 3 arguments (the element, the index and the array) and should
536 * return a boolean.
537 * @param {S=} opt_obj An optional "this" context for the function.
538 * @return {T|null} The last array element that passes the test, or null if no
539 * element is found.
540 * @template T,S
541 */
542 goog.array.findRight = function(arr, f, opt_obj) {
543 var i = goog.array.findIndexRight(arr, f, opt_obj);
544 return i < 0 ? null : goog.isString(arr) ? arr.charAt(i) : arr[i];
545 };
546
547
548 /**
549 * Search an array (in reverse order) for the last element that satisfies a
550 * given condition and return its index.
551 * @param {IArrayLike<T>|string} arr Array or array
552 * like object over which to iterate.
553 * @param {?function(this:S, T, number, ?) : boolean} f The function to call
554 * for every element. This function
555 * takes 3 arguments (the element, the index and the array) and should
556 * return a boolean.
557 * @param {S=} opt_obj An optional "this" context for the function.
558 * @return {number} The index of the last array element that passes the test,
559 * or -1 if no element is found.
560 * @template T,S
561 */
562 goog.array.findIndexRight = function(arr, f, opt_obj) {
563 var l = arr.length; // must be fixed during loop... see docs
564 var arr2 = goog.isString(arr) ? arr.split('') : arr;
565 for (var i = l - 1; i >= 0; i--) {
566 if (i in arr2 && f.call(/** @type {?} */ (opt_obj), arr2[i], i, arr)) {
567 return i;
568 }
569 }
570 return -1;
571 };
572
573
574 /**
575 * Whether the array contains the given object.
576 * @param {IArrayLike<?>|string} arr The array to test for the presence of the
577 * element.
578 * @param {*} obj The object for which to test.
579 * @return {boolean} true if obj is present.
580 */
581 goog.array.contains = function(arr, obj) {
582 return goog.array.indexOf(arr, obj) >= 0;
583 };
584
585
586 /**
587 * Whether the array is empty.
588 * @param {IArrayLike<?>|string} arr The array to test.
589 * @return {boolean} true if empty.
590 */
591 goog.array.isEmpty = function(arr) {
592 return arr.length == 0;
593 };
594
595
596 /**
597 * Clears the array.
598 * @param {IArrayLike<?>} arr Array or array like object to clear.
599 */
600 goog.array.clear = function(arr) {
601 // For non real arrays we don't have the magic length so we delete the
602 // indices.
603 if (!goog.isArray(arr)) {
604 for (var i = arr.length - 1; i >= 0; i--) {
605 delete arr[i];
606 }
607 }
608 arr.length = 0;
609 };
610
611
612 /**
613 * Pushes an item into an array, if it's not already in the array.
614 * @param {Array<T>} arr Array into which to insert the item.
615 * @param {T} obj Value to add.
616 * @template T
617 */
618 goog.array.insert = function(arr, obj) {
619 if (!goog.array.contains(arr, obj)) {
620 arr.push(obj);
621 }
622 };
623
624
625 /**
626 * Inserts an object at the given index of the array.
627 * @param {IArrayLike<?>} arr The array to modify.
628 * @param {*} obj The object to insert.
629 * @param {number=} opt_i The index at which to insert the object. If omitted,
630 * treated as 0. A negative index is counted from the end of the array.
631 */
632 goog.array.insertAt = function(arr, obj, opt_i) {
633 goog.array.splice(arr, opt_i, 0, obj);
634 };
635
636
637 /**
638 * Inserts at the given index of the array, all elements of another array.
639 * @param {IArrayLike<?>} arr The array to modify.
640 * @param {IArrayLike<?>} elementsToAdd The array of elements to add.
641 * @param {number=} opt_i The index at which to insert the object. If omitted,
642 * treated as 0. A negative index is counted from the end of the array.
643 */
644 goog.array.insertArrayAt = function(arr, elementsToAdd, opt_i) {
645 goog.partial(goog.array.splice, arr, opt_i, 0).apply(null, elementsToAdd);
646 };
647
648
649 /**
650 * Inserts an object into an array before a specified object.
651 * @param {Array<T>} arr The array to modify.
652 * @param {T} obj The object to insert.
653 * @param {T=} opt_obj2 The object before which obj should be inserted. If obj2
654 * is omitted or not found, obj is inserted at the end of the array.
655 * @template T
656 */
657 goog.array.insertBefore = function(arr, obj, opt_obj2) {
658 var i;
659 if (arguments.length == 2 || (i = goog.array.indexOf(arr, opt_obj2)) < 0) {
660 arr.push(obj);
661 } else {
662 goog.array.insertAt(arr, obj, i);
663 }
664 };
665
666
667 /**
668 * Removes the first occurrence of a particular value from an array.
669 * @param {IArrayLike<T>} arr Array from which to remove
670 * value.
671 * @param {T} obj Object to remove.
672 * @return {boolean} True if an element was removed.
673 * @template T
674 */
675 goog.array.remove = function(arr, obj) {
676 var i = goog.array.indexOf(arr, obj);
677 var rv;
678 if ((rv = i >= 0)) {
679 goog.array.removeAt(arr, i);
680 }
681 return rv;
682 };
683
684
685 /**
686 * Removes the last occurrence of a particular value from an array.
687 * @param {!IArrayLike<T>} arr Array from which to remove value.
688 * @param {T} obj Object to remove.
689 * @return {boolean} True if an element was removed.
690 * @template T
691 */
692 goog.array.removeLast = function(arr, obj) {
693 var i = goog.array.lastIndexOf(arr, obj);
694 if (i >= 0) {
695 goog.array.removeAt(arr, i);
696 return true;
697 }
698 return false;
699 };
700
701
702 /**
703 * Removes from an array the element at index i
704 * @param {IArrayLike<?>} arr Array or array like object from which to
705 * remove value.
706 * @param {number} i The index to remove.
707 * @return {boolean} True if an element was removed.
708 */
709 goog.array.removeAt = function(arr, i) {
710 goog.asserts.assert(arr.length != null);
711
712 // use generic form of splice
713 // splice returns the removed items and if successful the length of that
714 // will be 1
715 return Array.prototype.splice.call(arr, i, 1).length == 1;
716 };
717
718
719 /**
720 * Removes the first value that satisfies the given condition.
721 * @param {IArrayLike<T>} arr Array or array
722 * like object over which to iterate.
723 * @param {?function(this:S, T, number, ?) : boolean} f The function to call
724 * for every element. This function
725 * takes 3 arguments (the element, the index and the array) and should
726 * return a boolean.
727 * @param {S=} opt_obj An optional "this" context for the function.
728 * @return {boolean} True if an element was removed.
729 * @template T,S
730 */
731 goog.array.removeIf = function(arr, f, opt_obj) {
732 var i = goog.array.findIndex(arr, f, opt_obj);
733 if (i >= 0) {
734 goog.array.removeAt(arr, i);
735 return true;
736 }
737 return false;
738 };
739
740
741 /**
742 * Removes all values that satisfy the given condition.
743 * @param {IArrayLike<T>} arr Array or array
744 * like object over which to iterate.
745 * @param {?function(this:S, T, number, ?) : boolean} f The function to call
746 * for every element. This function
747 * takes 3 arguments (the element, the index and the array) and should
748 * return a boolean.
749 * @param {S=} opt_obj An optional "this" context for the function.
750 * @return {number} The number of items removed
751 * @template T,S
752 */
753 goog.array.removeAllIf = function(arr, f, opt_obj) {
754 var removedCount = 0;
755 goog.array.forEachRight(arr, function(val, index) {
756 if (f.call(/** @type {?} */ (opt_obj), val, index, arr)) {
757 if (goog.array.removeAt(arr, index)) {
758 removedCount++;
759 }
760 }
761 });
762 return removedCount;
763 };
764
765
766 /**
767 * Returns a new array that is the result of joining the arguments. If arrays
768 * are passed then their items are added, however, if non-arrays are passed they
769 * will be added to the return array as is.
770 *
771 * Note that ArrayLike objects will be added as is, rather than having their
772 * items added.
773 *
774 * goog.array.concat([1, 2], [3, 4]) -> [1, 2, 3, 4]
775 * goog.array.concat(0, [1, 2]) -> [0, 1, 2]
776 * goog.array.concat([1, 2], null) -> [1, 2, null]
777 *
778 * There is bug in all current versions of IE (6, 7 and 8) where arrays created
779 * in an iframe become corrupted soon (not immediately) after the iframe is
780 * destroyed. This is common if loading data via goog.net.IframeIo, for example.
781 * This corruption only affects the concat method which will start throwing
782 * Catastrophic Errors (#-2147418113).
783 *
784 * See http://endoflow.com/scratch/corrupted-arrays.html for a test case.
785 *
786 * Internally goog.array should use this, so that all methods will continue to
787 * work on these broken array objects.
788 *
789 * @param {...*} var_args Items to concatenate. Arrays will have each item
790 * added, while primitives and objects will be added as is.
791 * @return {!Array<?>} The new resultant array.
792 */
793 goog.array.concat = function(var_args) {
794 return Array.prototype.concat.apply([], arguments);
795 };
796
797
798 /**
799 * Returns a new array that contains the contents of all the arrays passed.
800 * @param {...!Array<T>} var_args
801 * @return {!Array<T>}
802 * @template T
803 */
804 goog.array.join = function(var_args) {
805 return Array.prototype.concat.apply([], arguments);
806 };
807
808
809 /**
810 * Converts an object to an array.
811 * @param {IArrayLike<T>|string} object The object to convert to an
812 * array.
813 * @return {!Array<T>} The object converted into an array. If object has a
814 * length property, every property indexed with a non-negative number
815 * less than length will be included in the result. If object does not
816 * have a length property, an empty array will be returned.
817 * @template T
818 */
819 goog.array.toArray = function(object) {
820 var length = object.length;
821
822 // If length is not a number the following it false. This case is kept for
823 // backwards compatibility since there are callers that pass objects that are
824 // not array like.
825 if (length > 0) {
826 var rv = new Array(length);
827 for (var i = 0; i < length; i++) {
828 rv[i] = object[i];
829 }
830 return rv;
831 }
832 return [];
833 };
834
835
836 /**
837 * Does a shallow copy of an array.
838 * @param {IArrayLike<T>|string} arr Array or array-like object to
839 * clone.
840 * @return {!Array<T>} Clone of the input array.
841 * @template T
842 */
843 goog.array.clone = goog.array.toArray;
844
845
846 /**
847 * Extends an array with another array, element, or "array like" object.
848 * This function operates 'in-place', it does not create a new Array.
849 *
850 * Example:
851 * var a = [];
852 * goog.array.extend(a, [0, 1]);
853 * a; // [0, 1]
854 * goog.array.extend(a, 2);
855 * a; // [0, 1, 2]
856 *
857 * @param {Array<VALUE>} arr1 The array to modify.
858 * @param {...(IArrayLike<VALUE>|VALUE)} var_args The elements or arrays of
859 * elements to add to arr1.
860 * @template VALUE
861 */
862 goog.array.extend = function(arr1, var_args) {
863 for (var i = 1; i < arguments.length; i++) {
864 var arr2 = arguments[i];
865 if (goog.isArrayLike(arr2)) {
866 var len1 = arr1.length || 0;
867 var len2 = arr2.length || 0;
868 arr1.length = len1 + len2;
869 for (var j = 0; j < len2; j++) {
870 arr1[len1 + j] = arr2[j];
871 }
872 } else {
873 arr1.push(arr2);
874 }
875 }
876 };
877
878
879 /**
880 * Adds or removes elements from an array. This is a generic version of Array
881 * splice. This means that it might work on other objects similar to arrays,
882 * such as the arguments object.
883 *
884 * @param {IArrayLike<T>} arr The array to modify.
885 * @param {number|undefined} index The index at which to start changing the
886 * array. If not defined, treated as 0.
887 * @param {number} howMany How many elements to remove (0 means no removal. A
888 * value below 0 is treated as zero and so is any other non number. Numbers
889 * are floored).
890 * @param {...T} var_args Optional, additional elements to insert into the
891 * array.
892 * @return {!Array<T>} the removed elements.
893 * @template T
894 */
895 goog.array.splice = function(arr, index, howMany, var_args) {
896 goog.asserts.assert(arr.length != null);
897
898 return Array.prototype.splice.apply(arr, goog.array.slice(arguments, 1));
899 };
900
901
902 /**
903 * Returns a new array from a segment of an array. This is a generic version of
904 * Array slice. This means that it might work on other objects similar to
905 * arrays, such as the arguments object.
906 *
907 * @param {IArrayLike<T>|string} arr The array from
908 * which to copy a segment.
909 * @param {number} start The index of the first element to copy.
910 * @param {number=} opt_end The index after the last element to copy.
911 * @return {!Array<T>} A new array containing the specified segment of the
912 * original array.
913 * @template T
914 */
915 goog.array.slice = function(arr, start, opt_end) {
916 goog.asserts.assert(arr.length != null);
917
918 // passing 1 arg to slice is not the same as passing 2 where the second is
919 // null or undefined (in that case the second argument is treated as 0).
920 // we could use slice on the arguments object and then use apply instead of
921 // testing the length
922 if (arguments.length <= 2) {
923 return Array.prototype.slice.call(arr, start);
924 } else {
925 return Array.prototype.slice.call(arr, start, opt_end);
926 }
927 };
928
929
930 /**
931 * Removes all duplicates from an array (retaining only the first
932 * occurrence of each array element). This function modifies the
933 * array in place and doesn't change the order of the non-duplicate items.
934 *
935 * For objects, duplicates are identified as having the same unique ID as
936 * defined by {@link goog.getUid}.
937 *
938 * Alternatively you can specify a custom hash function that returns a unique
939 * value for each item in the array it should consider unique.
940 *
941 * Runtime: N,
942 * Worstcase space: 2N (no dupes)
943 *
944 * @param {IArrayLike<T>} arr The array from which to remove
945 * duplicates.
946 * @param {Array=} opt_rv An optional array in which to return the results,
947 * instead of performing the removal inplace. If specified, the original
948 * array will remain unchanged.
949 * @param {function(T):string=} opt_hashFn An optional function to use to
950 * apply to every item in the array. This function should return a unique
951 * value for each item in the array it should consider unique.
952 * @template T
953 */
954 goog.array.removeDuplicates = function(arr, opt_rv, opt_hashFn) {
955 var returnArray = opt_rv || arr;
956 var defaultHashFn = function(item) {
957 // Prefix each type with a single character representing the type to
958 // prevent conflicting keys (e.g. true and 'true').
959 return goog.isObject(item) ? 'o' + goog.getUid(item) :
960 (typeof item).charAt(0) + item;
961 };
962 var hashFn = opt_hashFn || defaultHashFn;
963
964 var seen = {}, cursorInsert = 0, cursorRead = 0;
965 while (cursorRead < arr.length) {
966 var current = arr[cursorRead++];
967 var key = hashFn(current);
968 if (!Object.prototype.hasOwnProperty.call(seen, key)) {
969 seen[key] = true;
970 returnArray[cursorInsert++] = current;
971 }
972 }
973 returnArray.length = cursorInsert;
974 };
975
976
977 /**
978 * Searches the specified array for the specified target using the binary
979 * search algorithm. If no opt_compareFn is specified, elements are compared
980 * using <code>goog.array.defaultCompare</code>, which compares the elements
981 * using the built in < and > operators. This will produce the expected
982 * behavior for homogeneous arrays of String(s) and Number(s). The array
983 * specified <b>must</b> be sorted in ascending order (as defined by the
984 * comparison function). If the array is not sorted, results are undefined.
985 * If the array contains multiple instances of the specified target value, any
986 * of these instances may be found.
987 *
988 * Runtime: O(log n)
989 *
990 * @param {IArrayLike<VALUE>} arr The array to be searched.
991 * @param {TARGET} target The sought value.
992 * @param {function(TARGET, VALUE): number=} opt_compareFn Optional comparison
993 * function by which the array is ordered. Should take 2 arguments to
994 * compare, and return a negative number, zero, or a positive number
995 * depending on whether the first argument is less than, equal to, or
996 * greater than the second.
997 * @return {number} Lowest index of the target value if found, otherwise
998 * (-(insertion point) - 1). The insertion point is where the value should
999 * be inserted into arr to preserve the sorted property. Return value >= 0
1000 * iff target is found.
1001 * @template TARGET, VALUE
1002 */
1003 goog.array.binarySearch = function(arr, target, opt_compareFn) {
1004 return goog.array.binarySearch_(
1005 arr, opt_compareFn || goog.array.defaultCompare, false /* isEvaluator */,
1006 target);
1007 };
1008
1009
1010 /**
1011 * Selects an index in the specified array using the binary search algorithm.
1012 * The evaluator receives an element and determines whether the desired index
1013 * is before, at, or after it. The evaluator must be consistent (formally,
1014 * goog.array.map(goog.array.map(arr, evaluator, opt_obj), goog.math.sign)
1015 * must be monotonically non-increasing).
1016 *
1017 * Runtime: O(log n)
1018 *
1019 * @param {IArrayLike<VALUE>} arr The array to be searched.
1020 * @param {function(this:THIS, VALUE, number, ?): number} evaluator
1021 * Evaluator function that receives 3 arguments (the element, the index and
1022 * the array). Should return a negative number, zero, or a positive number
1023 * depending on whether the desired index is before, at, or after the
1024 * element passed to it.
1025 * @param {THIS=} opt_obj The object to be used as the value of 'this'
1026 * within evaluator.
1027 * @return {number} Index of the leftmost element matched by the evaluator, if
1028 * such exists; otherwise (-(insertion point) - 1). The insertion point is
1029 * the index of the first element for which the evaluator returns negative,
1030 * or arr.length if no such element exists. The return value is non-negative
1031 * iff a match is found.
1032 * @template THIS, VALUE
1033 */
1034 goog.array.binarySelect = function(arr, evaluator, opt_obj) {
1035 return goog.array.binarySearch_(
1036 arr, evaluator, true /* isEvaluator */, undefined /* opt_target */,
1037 opt_obj);
1038 };
1039
1040
1041 /**
1042 * Implementation of a binary search algorithm which knows how to use both
1043 * comparison functions and evaluators. If an evaluator is provided, will call
1044 * the evaluator with the given optional data object, conforming to the
1045 * interface defined in binarySelect. Otherwise, if a comparison function is
1046 * provided, will call the comparison function against the given data object.
1047 *
1048 * This implementation purposefully does not use goog.bind or goog.partial for
1049 * performance reasons.
1050 *
1051 * Runtime: O(log n)
1052 *
1053 * @param {IArrayLike<?>} arr The array to be searched.
1054 * @param {function(?, ?, ?): number | function(?, ?): number} compareFn
1055 * Either an evaluator or a comparison function, as defined by binarySearch
1056 * and binarySelect above.
1057 * @param {boolean} isEvaluator Whether the function is an evaluator or a
1058 * comparison function.
1059 * @param {?=} opt_target If the function is a comparison function, then
1060 * this is the target to binary search for.
1061 * @param {Object=} opt_selfObj If the function is an evaluator, this is an
1062 * optional this object for the evaluator.
1063 * @return {number} Lowest index of the target value if found, otherwise
1064 * (-(insertion point) - 1). The insertion point is where the value should
1065 * be inserted into arr to preserve the sorted property. Return value >= 0
1066 * iff target is found.
1067 * @private
1068 */
1069 goog.array.binarySearch_ = function(
1070 arr, compareFn, isEvaluator, opt_target, opt_selfObj) {
1071 var left = 0; // inclusive
1072 var right = arr.length; // exclusive
1073 var found;
1074 while (left < right) {
1075 var middle = (left + right) >> 1;
1076 var compareResult;
1077 if (isEvaluator) {
1078 compareResult = compareFn.call(opt_selfObj, arr[middle], middle, arr);
1079 } else {
1080 // NOTE(dimvar): To avoid this cast, we'd have to use function overloading
1081 // for the type of binarySearch_, which the type system can't express yet.
1082 compareResult = /** @type {function(?, ?): number} */ (compareFn)(
1083 opt_target, arr[middle]);
1084 }
1085 if (compareResult > 0) {
1086 left = middle + 1;
1087 } else {
1088 right = middle;
1089 // We are looking for the lowest index so we can't return immediately.
1090 found = !compareResult;
1091 }
1092 }
1093 // left is the index if found, or the insertion point otherwise.
1094 // ~left is a shorthand for -left - 1.
1095 return found ? left : ~left;
1096 };
1097
1098
1099 /**
1100 * Sorts the specified array into ascending order. If no opt_compareFn is
1101 * specified, elements are compared using
1102 * <code>goog.array.defaultCompare</code>, which compares the elements using
1103 * the built in < and > operators. This will produce the expected behavior
1104 * for homogeneous arrays of String(s) and Number(s), unlike the native sort,
1105 * but will give unpredictable results for heterogeneous lists of strings and
1106 * numbers with different numbers of digits.
1107 *
1108 * This sort is not guaranteed to be stable.
1109 *
1110 * Runtime: Same as <code>Array.prototype.sort</code>
1111 *
1112 * @param {Array<T>} arr The array to be sorted.
1113 * @param {?function(T,T):number=} opt_compareFn Optional comparison
1114 * function by which the
1115 * array is to be ordered. Should take 2 arguments to compare, and return a
1116 * negative number, zero, or a positive number depending on whether the
1117 * first argument is less than, equal to, or greater than the second.
1118 * @template T
1119 */
1120 goog.array.sort = function(arr, opt_compareFn) {
1121 // TODO(arv): Update type annotation since null is not accepted.
1122 arr.sort(opt_compareFn || goog.array.defaultCompare);
1123 };
1124
1125
1126 /**
1127 * Sorts the specified array into ascending order in a stable way. If no
1128 * opt_compareFn is specified, elements are compared using
1129 * <code>goog.array.defaultCompare</code>, which compares the elements using
1130 * the built in < and > operators. This will produce the expected behavior
1131 * for homogeneous arrays of String(s) and Number(s).
1132 *
1133 * Runtime: Same as <code>Array.prototype.sort</code>, plus an additional
1134 * O(n) overhead of copying the array twice.
1135 *
1136 * @param {Array<T>} arr The array to be sorted.
1137 * @param {?function(T, T): number=} opt_compareFn Optional comparison function
1138 * by which the array is to be ordered. Should take 2 arguments to compare,
1139 * and return a negative number, zero, or a positive number depending on
1140 * whether the first argument is less than, equal to, or greater than the
1141 * second.
1142 * @template T
1143 */
1144 goog.array.stableSort = function(arr, opt_compareFn) {
1145 var compArr = new Array(arr.length);
1146 for (var i = 0; i < arr.length; i++) {
1147 compArr[i] = {index: i, value: arr[i]};
1148 }
1149 var valueCompareFn = opt_compareFn || goog.array.defaultCompare;
1150 function stableCompareFn(obj1, obj2) {
1151 return valueCompareFn(obj1.value, obj2.value) || obj1.index - obj2.index;
1152 }
1153 goog.array.sort(compArr, stableCompareFn);
1154 for (var i = 0; i < arr.length; i++) {
1155 arr[i] = compArr[i].value;
1156 }
1157 };
1158
1159
1160 /**
1161 * Sort the specified array into ascending order based on item keys
1162 * returned by the specified key function.
1163 * If no opt_compareFn is specified, the keys are compared in ascending order
1164 * using <code>goog.array.defaultCompare</code>.
1165 *
1166 * Runtime: O(S(f(n)), where S is runtime of <code>goog.array.sort</code>
1167 * and f(n) is runtime of the key function.
1168 *
1169 * @param {Array<T>} arr The array to be sorted.
1170 * @param {function(T): K} keyFn Function taking array element and returning
1171 * a key used for sorting this element.
1172 * @param {?function(K, K): number=} opt_compareFn Optional comparison function
1173 * by which the keys are to be ordered. Should take 2 arguments to compare,
1174 * and return a negative number, zero, or a positive number depending on
1175 * whether the first argument is less than, equal to, or greater than the
1176 * second.
1177 * @template T,K
1178 */
1179 goog.array.sortByKey = function(arr, keyFn, opt_compareFn) {
1180 var keyCompareFn = opt_compareFn || goog.array.defaultCompare;
1181 goog.array.sort(
1182 arr, function(a, b) { return keyCompareFn(keyFn(a), keyFn(b)); });
1183 };
1184
1185
1186 /**
1187 * Sorts an array of objects by the specified object key and compare
1188 * function. If no compare function is provided, the key values are
1189 * compared in ascending order using <code>goog.array.defaultCompare</code>.
1190 * This won't work for keys that get renamed by the compiler. So use
1191 * {'foo': 1, 'bar': 2} rather than {foo: 1, bar: 2}.
1192 * @param {Array<Object>} arr An array of objects to sort.
1193 * @param {string} key The object key to sort by.
1194 * @param {Function=} opt_compareFn The function to use to compare key
1195 * values.
1196 */
1197 goog.array.sortObjectsByKey = function(arr, key, opt_compareFn) {
1198 goog.array.sortByKey(arr, function(obj) { return obj[key]; }, opt_compareFn);
1199 };
1200
1201
1202 /**
1203 * Tells if the array is sorted.
1204 * @param {!IArrayLike<T>} arr The array.
1205 * @param {?function(T,T):number=} opt_compareFn Function to compare the
1206 * array elements.
1207 * Should take 2 arguments to compare, and return a negative number, zero,
1208 * or a positive number depending on whether the first argument is less
1209 * than, equal to, or greater than the second.
1210 * @param {boolean=} opt_strict If true no equal elements are allowed.
1211 * @return {boolean} Whether the array is sorted.
1212 * @template T
1213 */
1214 goog.array.isSorted = function(arr, opt_compareFn, opt_strict) {
1215 var compare = opt_compareFn || goog.array.defaultCompare;
1216 for (var i = 1; i < arr.length; i++) {
1217 var compareResult = compare(arr[i - 1], arr[i]);
1218 if (compareResult > 0 || compareResult == 0 && opt_strict) {
1219 return false;
1220 }
1221 }
1222 return true;
1223 };
1224
1225
1226 /**
1227 * Compares two arrays for equality. Two arrays are considered equal if they
1228 * have the same length and their corresponding elements are equal according to
1229 * the comparison function.
1230 *
1231 * @param {IArrayLike<?>} arr1 The first array to compare.
1232 * @param {IArrayLike<?>} arr2 The second array to compare.
1233 * @param {Function=} opt_equalsFn Optional comparison function.
1234 * Should take 2 arguments to compare, and return true if the arguments
1235 * are equal. Defaults to {@link goog.array.defaultCompareEquality} which
1236 * compares the elements using the built-in '===' operator.
1237 * @return {boolean} Whether the two arrays are equal.
1238 */
1239 goog.array.equals = function(arr1, arr2, opt_equalsFn) {
1240 if (!goog.isArrayLike(arr1) || !goog.isArrayLike(arr2) ||
1241 arr1.length != arr2.length) {
1242 return false;
1243 }
1244 var l = arr1.length;
1245 var equalsFn = opt_equalsFn || goog.array.defaultCompareEquality;
1246 for (var i = 0; i < l; i++) {
1247 if (!equalsFn(arr1[i], arr2[i])) {
1248 return false;
1249 }
1250 }
1251 return true;
1252 };
1253
1254
1255 /**
1256 * 3-way array compare function.
1257 * @param {!IArrayLike<VALUE>} arr1 The first array to
1258 * compare.
1259 * @param {!IArrayLike<VALUE>} arr2 The second array to
1260 * compare.
1261 * @param {function(VALUE, VALUE): number=} opt_compareFn Optional comparison
1262 * function by which the array is to be ordered. Should take 2 arguments to
1263 * compare, and return a negative number, zero, or a positive number
1264 * depending on whether the first argument is less than, equal to, or
1265 * greater than the second.
1266 * @return {number} Negative number, zero, or a positive number depending on
1267 * whether the first argument is less than, equal to, or greater than the
1268 * second.
1269 * @template VALUE
1270 */
1271 goog.array.compare3 = function(arr1, arr2, opt_compareFn) {
1272 var compare = opt_compareFn || goog.array.defaultCompare;
1273 var l = Math.min(arr1.length, arr2.length);
1274 for (var i = 0; i < l; i++) {
1275 var result = compare(arr1[i], arr2[i]);
1276 if (result != 0) {
1277 return result;
1278 }
1279 }
1280 return goog.array.defaultCompare(arr1.length, arr2.length);
1281 };
1282
1283
1284 /**
1285 * Compares its two arguments for order, using the built in < and >
1286 * operators.
1287 * @param {VALUE} a The first object to be compared.
1288 * @param {VALUE} b The second object to be compared.
1289 * @return {number} A negative number, zero, or a positive number as the first
1290 * argument is less than, equal to, or greater than the second,
1291 * respectively.
1292 * @template VALUE
1293 */
1294 goog.array.defaultCompare = function(a, b) {
1295 return a > b ? 1 : a < b ? -1 : 0;
1296 };
1297
1298
1299 /**
1300 * Compares its two arguments for inverse order, using the built in < and >
1301 * operators.
1302 * @param {VALUE} a The first object to be compared.
1303 * @param {VALUE} b The second object to be compared.
1304 * @return {number} A negative number, zero, or a positive number as the first
1305 * argument is greater than, equal to, or less than the second,
1306 * respectively.
1307 * @template VALUE
1308 */
1309 goog.array.inverseDefaultCompare = function(a, b) {
1310 return -goog.array.defaultCompare(a, b);
1311 };
1312
1313
1314 /**
1315 * Compares its two arguments for equality, using the built in === operator.
1316 * @param {*} a The first object to compare.
1317 * @param {*} b The second object to compare.
1318 * @return {boolean} True if the two arguments are equal, false otherwise.
1319 */
1320 goog.array.defaultCompareEquality = function(a, b) {
1321 return a === b;
1322 };
1323
1324
1325 /**
1326 * Inserts a value into a sorted array. The array is not modified if the
1327 * value is already present.
1328 * @param {IArrayLike<VALUE>} array The array to modify.
1329 * @param {VALUE} value The object to insert.
1330 * @param {function(VALUE, VALUE): number=} opt_compareFn Optional comparison
1331 * function by which the array is ordered. Should take 2 arguments to
1332 * compare, and return a negative number, zero, or a positive number
1333 * depending on whether the first argument is less than, equal to, or
1334 * greater than the second.
1335 * @return {boolean} True if an element was inserted.
1336 * @template VALUE
1337 */
1338 goog.array.binaryInsert = function(array, value, opt_compareFn) {
1339 var index = goog.array.binarySearch(array, value, opt_compareFn);
1340 if (index < 0) {
1341 goog.array.insertAt(array, value, -(index + 1));
1342 return true;
1343 }
1344 return false;
1345 };
1346
1347
1348 /**
1349 * Removes a value from a sorted array.
1350 * @param {!IArrayLike<VALUE>} array The array to modify.
1351 * @param {VALUE} value The object to remove.
1352 * @param {function(VALUE, VALUE): number=} opt_compareFn Optional comparison
1353 * function by which the array is ordered. Should take 2 arguments to
1354 * compare, and return a negative number, zero, or a positive number
1355 * depending on whether the first argument is less than, equal to, or
1356 * greater than the second.
1357 * @return {boolean} True if an element was removed.
1358 * @template VALUE
1359 */
1360 goog.array.binaryRemove = function(array, value, opt_compareFn) {
1361 var index = goog.array.binarySearch(array, value, opt_compareFn);
1362 return (index >= 0) ? goog.array.removeAt(array, index) : false;
1363 };
1364
1365
1366 /**
1367 * Splits an array into disjoint buckets according to a splitting function.
1368 * @param {IArrayLike<T>} array The array.
1369 * @param {function(this:S, T, number, !IArrayLike<T>):?} sorter Function to
1370 * call for every element. This takes 3 arguments (the element, the index
1371 * and the array) and must return a valid object key (a string, number,
1372 * etc), or undefined, if that object should not be placed in a bucket.
1373 * @param {S=} opt_obj The object to be used as the value of 'this' within
1374 * sorter.
1375 * @return {!Object<!Array<T>>} An object, with keys being all of the unique
1376 * return values of sorter, and values being arrays containing the items for
1377 * which the splitter returned that key.
1378 * @template T,S
1379 */
1380 goog.array.bucket = function(array, sorter, opt_obj) {
1381 var buckets = {};
1382
1383 for (var i = 0; i < array.length; i++) {
1384 var value = array[i];
1385 var key = sorter.call(/** @type {?} */ (opt_obj), value, i, array);
1386 if (goog.isDef(key)) {
1387 // Push the value to the right bucket, creating it if necessary.
1388 var bucket = buckets[key] || (buckets[key] = []);
1389 bucket.push(value);
1390 }
1391 }
1392
1393 return buckets;
1394 };
1395
1396
1397 /**
1398 * Creates a new object built from the provided array and the key-generation
1399 * function.
1400 * @param {IArrayLike<T>} arr Array or array like object over
1401 * which to iterate whose elements will be the values in the new object.
1402 * @param {?function(this:S, T, number, ?) : string} keyFunc The function to
1403 * call for every element. This function takes 3 arguments (the element, the
1404 * index and the array) and should return a string that will be used as the
1405 * key for the element in the new object. If the function returns the same
1406 * key for more than one element, the value for that key is
1407 * implementation-defined.
1408 * @param {S=} opt_obj The object to be used as the value of 'this'
1409 * within keyFunc.
1410 * @return {!Object<T>} The new object.
1411 * @template T,S
1412 */
1413 goog.array.toObject = function(arr, keyFunc, opt_obj) {
1414 var ret = {};
1415 goog.array.forEach(arr, function(element, index) {
1416 ret[keyFunc.call(/** @type {?} */ (opt_obj), element, index, arr)] =
1417 element;
1418 });
1419 return ret;
1420 };
1421
1422
1423 /**
1424 * Creates a range of numbers in an arithmetic progression.
1425 *
1426 * Range takes 1, 2, or 3 arguments:
1427 * <pre>
1428 * range(5) is the same as range(0, 5, 1) and produces [0, 1, 2, 3, 4]
1429 * range(2, 5) is the same as range(2, 5, 1) and produces [2, 3, 4]
1430 * range(-2, -5, -1) produces [-2, -3, -4]
1431 * range(-2, -5, 1) produces [], since stepping by 1 wouldn't ever reach -5.
1432 * </pre>
1433 *
1434 * @param {number} startOrEnd The starting value of the range if an end argument
1435 * is provided. Otherwise, the start value is 0, and this is the end value.
1436 * @param {number=} opt_end The optional end value of the range.
1437 * @param {number=} opt_step The step size between range values. Defaults to 1
1438 * if opt_step is undefined or 0.
1439 * @return {!Array<number>} An array of numbers for the requested range. May be
1440 * an empty array if adding the step would not converge toward the end
1441 * value.
1442 */
1443 goog.array.range = function(startOrEnd, opt_end, opt_step) {
1444 var array = [];
1445 var start = 0;
1446 var end = startOrEnd;
1447 var step = opt_step || 1;
1448 if (opt_end !== undefined) {
1449 start = startOrEnd;
1450 end = opt_end;
1451 }
1452
1453 if (step * (end - start) < 0) {
1454 // Sign mismatch: start + step will never reach the end value.
1455 return [];
1456 }
1457
1458 if (step > 0) {
1459 for (var i = start; i < end; i += step) {
1460 array.push(i);
1461 }
1462 } else {
1463 for (var i = start; i > end; i += step) {
1464 array.push(i);
1465 }
1466 }
1467 return array;
1468 };
1469
1470
1471 /**
1472 * Returns an array consisting of the given value repeated N times.
1473 *
1474 * @param {VALUE} value The value to repeat.
1475 * @param {number} n The repeat count.
1476 * @return {!Array<VALUE>} An array with the repeated value.
1477 * @template VALUE
1478 */
1479 goog.array.repeat = function(value, n) {
1480 var array = [];
1481 for (var i = 0; i < n; i++) {
1482 array[i] = value;
1483 }
1484 return array;
1485 };
1486
1487
1488 /**
1489 * Returns an array consisting of every argument with all arrays
1490 * expanded in-place recursively.
1491 *
1492 * @param {...*} var_args The values to flatten.
1493 * @return {!Array<?>} An array containing the flattened values.
1494 */
1495 goog.array.flatten = function(var_args) {
1496 var CHUNK_SIZE = 8192;
1497
1498 var result = [];
1499 for (var i = 0; i < arguments.length; i++) {
1500 var element = arguments[i];
1501 if (goog.isArray(element)) {
1502 for (var c = 0; c < element.length; c += CHUNK_SIZE) {
1503 var chunk = goog.array.slice(element, c, c + CHUNK_SIZE);
1504 var recurseResult = goog.array.flatten.apply(null, chunk);
1505 for (var r = 0; r < recurseResult.length; r++) {
1506 result.push(recurseResult[r]);
1507 }
1508 }
1509 } else {
1510 result.push(element);
1511 }
1512 }
1513 return result;
1514 };
1515
1516
1517 /**
1518 * Rotates an array in-place. After calling this method, the element at
1519 * index i will be the element previously at index (i - n) %
1520 * array.length, for all values of i between 0 and array.length - 1,
1521 * inclusive.
1522 *
1523 * For example, suppose list comprises [t, a, n, k, s]. After invoking
1524 * rotate(array, 1) (or rotate(array, -4)), array will comprise [s, t, a, n, k].
1525 *
1526 * @param {!Array<T>} array The array to rotate.
1527 * @param {number} n The amount to rotate.
1528 * @return {!Array<T>} The array.
1529 * @template T
1530 */
1531 goog.array.rotate = function(array, n) {
1532 goog.asserts.assert(array.length != null);
1533
1534 if (array.length) {
1535 n %= array.length;
1536 if (n > 0) {
1537 Array.prototype.unshift.apply(array, array.splice(-n, n));
1538 } else if (n < 0) {
1539 Array.prototype.push.apply(array, array.splice(0, -n));
1540 }
1541 }
1542 return array;
1543 };
1544
1545
1546 /**
1547 * Moves one item of an array to a new position keeping the order of the rest
1548 * of the items. Example use case: keeping a list of JavaScript objects
1549 * synchronized with the corresponding list of DOM elements after one of the
1550 * elements has been dragged to a new position.
1551 * @param {!IArrayLike<?>} arr The array to modify.
1552 * @param {number} fromIndex Index of the item to move between 0 and
1553 * {@code arr.length - 1}.
1554 * @param {number} toIndex Target index between 0 and {@code arr.length - 1}.
1555 */
1556 goog.array.moveItem = function(arr, fromIndex, toIndex) {
1557 goog.asserts.assert(fromIndex >= 0 && fromIndex < arr.length);
1558 goog.asserts.assert(toIndex >= 0 && toIndex < arr.length);
1559 // Remove 1 item at fromIndex.
1560 var removedItems = Array.prototype.splice.call(arr, fromIndex, 1);
1561 // Insert the removed item at toIndex.
1562 Array.prototype.splice.call(arr, toIndex, 0, removedItems[0]);
1563 // We don't use goog.array.insertAt and goog.array.removeAt, because they're
1564 // significantly slower than splice.
1565 };
1566
1567
1568 /**
1569 * Creates a new array for which the element at position i is an array of the
1570 * ith element of the provided arrays. The returned array will only be as long
1571 * as the shortest array provided; additional values are ignored. For example,
1572 * the result of zipping [1, 2] and [3, 4, 5] is [[1,3], [2, 4]].
1573 *
1574 * This is similar to the zip() function in Python. See {@link
1575 * http://docs.python.org/library/functions.html#zip}
1576 *
1577 * @param {...!IArrayLike<?>} var_args Arrays to be combined.
1578 * @return {!Array<!Array<?>>} A new array of arrays created from
1579 * provided arrays.
1580 */
1581 goog.array.zip = function(var_args) {
1582 if (!arguments.length) {
1583 return [];
1584 }
1585 var result = [];
1586 var minLen = arguments[0].length;
1587 for (var i = 1; i < arguments.length; i++) {
1588 if (arguments[i].length < minLen) {
1589 minLen = arguments[i].length;
1590 }
1591 }
1592 for (var i = 0; i < minLen; i++) {
1593 var value = [];
1594 for (var j = 0; j < arguments.length; j++) {
1595 value.push(arguments[j][i]);
1596 }
1597 result.push(value);
1598 }
1599 return result;
1600 };
1601
1602
1603 /**
1604 * Shuffles the values in the specified array using the Fisher-Yates in-place
1605 * shuffle (also known as the Knuth Shuffle). By default, calls Math.random()
1606 * and so resets the state of that random number generator. Similarly, may reset
1607 * the state of the any other specified random number generator.
1608 *
1609 * Runtime: O(n)
1610 *
1611 * @param {!Array<?>} arr The array to be shuffled.
1612 * @param {function():number=} opt_randFn Optional random function to use for
1613 * shuffling.
1614 * Takes no arguments, and returns a random number on the interval [0, 1).
1615 * Defaults to Math.random() using JavaScript's built-in Math library.
1616 */
1617 goog.array.shuffle = function(arr, opt_randFn) {
1618 var randFn = opt_randFn || Math.random;
1619
1620 for (var i = arr.length - 1; i > 0; i--) {
1621 // Choose a random array index in [0, i] (inclusive with i).
1622 var j = Math.floor(randFn() * (i + 1));
1623
1624 var tmp = arr[i];
1625 arr[i] = arr[j];
1626 arr[j] = tmp;
1627 }
1628 };
1629
1630
1631 /**
1632 * Returns a new array of elements from arr, based on the indexes of elements
1633 * provided by index_arr. For example, the result of index copying
1634 * ['a', 'b', 'c'] with index_arr [1,0,0,2] is ['b', 'a', 'a', 'c'].
1635 *
1636 * @param {!IArrayLike<T>} arr The array to get a indexed copy from.
1637 * @param {!IArrayLike<number>} index_arr An array of indexes to get from arr.
1638 * @return {!Array<T>} A new array of elements from arr in index_arr order.
1639 * @template T
1640 */
1641 goog.array.copyByIndex = function(arr, index_arr) {
1642 var result = [];
1643 goog.array.forEach(index_arr, function(index) { result.push(arr[index]); });
1644 return result;
1645 };
1646
1647
1648 /**
1649 * Maps each element of the input array into zero or more elements of the output
1650 * array.
1651 *
1652 * @param {!IArrayLike<VALUE>|string} arr Array or array like object
1653 * over which to iterate.
1654 * @param {function(this:THIS, VALUE, number, ?): !Array<RESULT>} f The function
1655 * to call for every element. This function takes 3 arguments (the element,
1656 * the index and the array) and should return an array. The result will be
1657 * used to extend a new array.
1658 * @param {THIS=} opt_obj The object to be used as the value of 'this' within f.
1659 * @return {!Array<RESULT>} a new array with the concatenation of all arrays
1660 * returned from f.
1661 * @template THIS, VALUE, RESULT
1662 */
1663 goog.array.concatMap = function(arr, f, opt_obj) {
1664 return goog.array.concat.apply([], goog.array.map(arr, f, opt_obj));
1665 };