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 {...(Array<VALUE>|VALUE)} var_args The elements or arrays of elements
859
 *     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 {!Array<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 {Array<T>} array The array.
1369
 * @param {function(this:S, T,number,Array<T>):?} sorter Function to call for
1370
 *     every element.  This takes 3 arguments (the element, the index and the
1371
 *     array) and must return a valid object key (a string, number, etc), or
1372
 *     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} An object, with keys being all of the unique return values
1376
 *     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 {!Array<T>} arr The array to get a indexed copy from.
1637
 * @param {!Array<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
};
1666

1667