| // Copyright 2006 The Closure Library Authors. All Rights Reserved. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS-IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| /** |
| * @fileoverview Utilities for manipulating arrays. |
| * |
| * @author arv@google.com (Erik Arvidsson) |
| */ |
| |
| |
| goog.provide('goog.array'); |
| goog.provide('goog.array.ArrayLike'); |
| |
| goog.require('goog.asserts'); |
| |
| |
| /** |
| * @define {boolean} NATIVE_ARRAY_PROTOTYPES indicates whether the code should |
| * rely on Array.prototype functions, if available. |
| * |
| * The Array.prototype functions can be defined by external libraries like |
| * Prototype and setting this flag to false forces closure to use its own |
| * goog.array implementation. |
| * |
| * If your javascript can be loaded by a third party site and you are wary about |
| * relying on the prototype functions, specify |
| * "--define goog.NATIVE_ARRAY_PROTOTYPES=false" to the JSCompiler. |
| * |
| * Setting goog.TRUSTED_SITE to false will automatically set |
| * NATIVE_ARRAY_PROTOTYPES to false. |
| */ |
| goog.define('goog.NATIVE_ARRAY_PROTOTYPES', goog.TRUSTED_SITE); |
| |
| |
| /** |
| * @define {boolean} If true, JSCompiler will use the native implementation of |
| * array functions where appropriate (e.g., {@code Array#filter}) and remove the |
| * unused pure JS implementation. |
| */ |
| goog.define('goog.array.ASSUME_NATIVE_FUNCTIONS', false); |
| |
| |
| /** |
| * @typedef {Array|NodeList|Arguments|{length: number}} |
| */ |
| goog.array.ArrayLike; |
| |
| |
| /** |
| * Returns the last element in an array without removing it. |
| * Same as goog.array.last. |
| * @param {Array<T>|goog.array.ArrayLike} array The array. |
| * @return {T} Last item in array. |
| * @template T |
| */ |
| goog.array.peek = function(array) { |
| return array[array.length - 1]; |
| }; |
| |
| |
| /** |
| * Returns the last element in an array without removing it. |
| * Same as goog.array.peek. |
| * @param {Array<T>|goog.array.ArrayLike} array The array. |
| * @return {T} Last item in array. |
| * @template T |
| */ |
| goog.array.last = goog.array.peek; |
| |
| |
| /** |
| * Reference to the original {@code Array.prototype}. |
| * @private |
| */ |
| goog.array.ARRAY_PROTOTYPE_ = Array.prototype; |
| |
| |
| // NOTE(arv): Since most of the array functions are generic it allows you to |
| // pass an array-like object. Strings have a length and are considered array- |
| // like. However, the 'in' operator does not work on strings so we cannot just |
| // use the array path even if the browser supports indexing into strings. We |
| // therefore end up splitting the string. |
| |
| |
| /** |
| * Returns the index of the first element of an array with a specified value, or |
| * -1 if the element is not present in the array. |
| * |
| * See {@link http://tinyurl.com/developer-mozilla-org-array-indexof} |
| * |
| * @param {Array<T>|goog.array.ArrayLike} arr The array to be searched. |
| * @param {T} obj The object for which we are searching. |
| * @param {number=} opt_fromIndex The index at which to start the search. If |
| * omitted the search starts at index 0. |
| * @return {number} The index of the first matching array element. |
| * @template T |
| */ |
| goog.array.indexOf = goog.NATIVE_ARRAY_PROTOTYPES && |
| (goog.array.ASSUME_NATIVE_FUNCTIONS || |
| goog.array.ARRAY_PROTOTYPE_.indexOf) ? |
| function(arr, obj, opt_fromIndex) { |
| goog.asserts.assert(arr.length != null); |
| |
| return goog.array.ARRAY_PROTOTYPE_.indexOf.call(arr, obj, opt_fromIndex); |
| } : |
| function(arr, obj, opt_fromIndex) { |
| var fromIndex = opt_fromIndex == null ? |
| 0 : (opt_fromIndex < 0 ? |
| Math.max(0, arr.length + opt_fromIndex) : opt_fromIndex); |
| |
| if (goog.isString(arr)) { |
| // Array.prototype.indexOf uses === so only strings should be found. |
| if (!goog.isString(obj) || obj.length != 1) { |
| return -1; |
| } |
| return arr.indexOf(obj, fromIndex); |
| } |
| |
| for (var i = fromIndex; i < arr.length; i++) { |
| if (i in arr && arr[i] === obj) |
| return i; |
| } |
| return -1; |
| }; |
| |
| |
| /** |
| * Returns the index of the last element of an array with a specified value, or |
| * -1 if the element is not present in the array. |
| * |
| * See {@link http://tinyurl.com/developer-mozilla-org-array-lastindexof} |
| * |
| * @param {!Array<T>|!goog.array.ArrayLike} arr The array to be searched. |
| * @param {T} obj The object for which we are searching. |
| * @param {?number=} opt_fromIndex The index at which to start the search. If |
| * omitted the search starts at the end of the array. |
| * @return {number} The index of the last matching array element. |
| * @template T |
| */ |
| goog.array.lastIndexOf = goog.NATIVE_ARRAY_PROTOTYPES && |
| (goog.array.ASSUME_NATIVE_FUNCTIONS || |
| goog.array.ARRAY_PROTOTYPE_.lastIndexOf) ? |
| function(arr, obj, opt_fromIndex) { |
| goog.asserts.assert(arr.length != null); |
| |
| // Firefox treats undefined and null as 0 in the fromIndex argument which |
| // leads it to always return -1 |
| var fromIndex = opt_fromIndex == null ? arr.length - 1 : opt_fromIndex; |
| return goog.array.ARRAY_PROTOTYPE_.lastIndexOf.call(arr, obj, fromIndex); |
| } : |
| function(arr, obj, opt_fromIndex) { |
| var fromIndex = opt_fromIndex == null ? arr.length - 1 : opt_fromIndex; |
| |
| if (fromIndex < 0) { |
| fromIndex = Math.max(0, arr.length + fromIndex); |
| } |
| |
| if (goog.isString(arr)) { |
| // Array.prototype.lastIndexOf uses === so only strings should be found. |
| if (!goog.isString(obj) || obj.length != 1) { |
| return -1; |
| } |
| return arr.lastIndexOf(obj, fromIndex); |
| } |
| |
| for (var i = fromIndex; i >= 0; i--) { |
| if (i in arr && arr[i] === obj) |
| return i; |
| } |
| return -1; |
| }; |
| |
| |
| /** |
| * Calls a function for each element in an array. Skips holes in the array. |
| * See {@link http://tinyurl.com/developer-mozilla-org-array-foreach} |
| * |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array like object over |
| * which to iterate. |
| * @param {?function(this: S, T, number, ?): ?} f The function to call for every |
| * element. This function takes 3 arguments (the element, the index and the |
| * array). The return value is ignored. |
| * @param {S=} opt_obj The object to be used as the value of 'this' within f. |
| * @template T,S |
| */ |
| goog.array.forEach = goog.NATIVE_ARRAY_PROTOTYPES && |
| (goog.array.ASSUME_NATIVE_FUNCTIONS || |
| goog.array.ARRAY_PROTOTYPE_.forEach) ? |
| function(arr, f, opt_obj) { |
| goog.asserts.assert(arr.length != null); |
| |
| goog.array.ARRAY_PROTOTYPE_.forEach.call(arr, f, opt_obj); |
| } : |
| function(arr, f, opt_obj) { |
| var l = arr.length; // must be fixed during loop... see docs |
| var arr2 = goog.isString(arr) ? arr.split('') : arr; |
| for (var i = 0; i < l; i++) { |
| if (i in arr2) { |
| f.call(opt_obj, arr2[i], i, arr); |
| } |
| } |
| }; |
| |
| |
| /** |
| * Calls a function for each element in an array, starting from the last |
| * element rather than the first. |
| * |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array |
| * like object over which to iterate. |
| * @param {?function(this: S, T, number, ?): ?} f The function to call for every |
| * element. This function |
| * takes 3 arguments (the element, the index and the array). The return |
| * value is ignored. |
| * @param {S=} opt_obj The object to be used as the value of 'this' |
| * within f. |
| * @template T,S |
| */ |
| goog.array.forEachRight = function(arr, f, opt_obj) { |
| var l = arr.length; // must be fixed during loop... see docs |
| var arr2 = goog.isString(arr) ? arr.split('') : arr; |
| for (var i = l - 1; i >= 0; --i) { |
| if (i in arr2) { |
| f.call(opt_obj, arr2[i], i, arr); |
| } |
| } |
| }; |
| |
| |
| /** |
| * Calls a function for each element in an array, and if the function returns |
| * true adds the element to a new array. |
| * |
| * See {@link http://tinyurl.com/developer-mozilla-org-array-filter} |
| * |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array |
| * like object over which to iterate. |
| * @param {?function(this:S, T, number, ?):boolean} f The function to call for |
| * every element. This function |
| * takes 3 arguments (the element, the index and the array) and must |
| * return a Boolean. If the return value is true the element is added to the |
| * result array. If it is false the element is not included. |
| * @param {S=} opt_obj The object to be used as the value of 'this' |
| * within f. |
| * @return {!Array<T>} a new array in which only elements that passed the test |
| * are present. |
| * @template T,S |
| */ |
| goog.array.filter = goog.NATIVE_ARRAY_PROTOTYPES && |
| (goog.array.ASSUME_NATIVE_FUNCTIONS || |
| goog.array.ARRAY_PROTOTYPE_.filter) ? |
| function(arr, f, opt_obj) { |
| goog.asserts.assert(arr.length != null); |
| |
| return goog.array.ARRAY_PROTOTYPE_.filter.call(arr, f, opt_obj); |
| } : |
| function(arr, f, opt_obj) { |
| var l = arr.length; // must be fixed during loop... see docs |
| var res = []; |
| var resLength = 0; |
| var arr2 = goog.isString(arr) ? arr.split('') : arr; |
| for (var i = 0; i < l; i++) { |
| if (i in arr2) { |
| var val = arr2[i]; // in case f mutates arr2 |
| if (f.call(opt_obj, val, i, arr)) { |
| res[resLength++] = val; |
| } |
| } |
| } |
| return res; |
| }; |
| |
| |
| /** |
| * Calls a function for each element in an array and inserts the result into a |
| * new array. |
| * |
| * See {@link http://tinyurl.com/developer-mozilla-org-array-map} |
| * |
| * @param {Array<VALUE>|goog.array.ArrayLike} arr Array or array like object |
| * over which to iterate. |
| * @param {function(this:THIS, VALUE, number, ?): RESULT} f The function to call |
| * for every element. This function takes 3 arguments (the element, |
| * the index and the array) and should return something. The result will be |
| * inserted into a new array. |
| * @param {THIS=} opt_obj The object to be used as the value of 'this' within f. |
| * @return {!Array<RESULT>} a new array with the results from f. |
| * @template THIS, VALUE, RESULT |
| */ |
| goog.array.map = goog.NATIVE_ARRAY_PROTOTYPES && |
| (goog.array.ASSUME_NATIVE_FUNCTIONS || |
| goog.array.ARRAY_PROTOTYPE_.map) ? |
| function(arr, f, opt_obj) { |
| goog.asserts.assert(arr.length != null); |
| |
| return goog.array.ARRAY_PROTOTYPE_.map.call(arr, f, opt_obj); |
| } : |
| function(arr, f, opt_obj) { |
| var l = arr.length; // must be fixed during loop... see docs |
| var res = new Array(l); |
| var arr2 = goog.isString(arr) ? arr.split('') : arr; |
| for (var i = 0; i < l; i++) { |
| if (i in arr2) { |
| res[i] = f.call(opt_obj, arr2[i], i, arr); |
| } |
| } |
| return res; |
| }; |
| |
| |
| /** |
| * Passes every element of an array into a function and accumulates the result. |
| * |
| * See {@link http://tinyurl.com/developer-mozilla-org-array-reduce} |
| * |
| * For example: |
| * var a = [1, 2, 3, 4]; |
| * goog.array.reduce(a, function(r, v, i, arr) {return r + v;}, 0); |
| * returns 10 |
| * |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array |
| * like object over which to iterate. |
| * @param {function(this:S, R, T, number, ?) : R} f The function to call for |
| * every element. This function |
| * takes 4 arguments (the function's previous result or the initial value, |
| * the value of the current array element, the current array index, and the |
| * array itself) |
| * function(previousValue, currentValue, index, array). |
| * @param {?} val The initial value to pass into the function on the first call. |
| * @param {S=} opt_obj The object to be used as the value of 'this' |
| * within f. |
| * @return {R} Result of evaluating f repeatedly across the values of the array. |
| * @template T,S,R |
| */ |
| goog.array.reduce = goog.NATIVE_ARRAY_PROTOTYPES && |
| (goog.array.ASSUME_NATIVE_FUNCTIONS || |
| goog.array.ARRAY_PROTOTYPE_.reduce) ? |
| function(arr, f, val, opt_obj) { |
| goog.asserts.assert(arr.length != null); |
| var params = []; |
| for(var i = 1, l = arguments.length; i < l; i++){ |
| params.push(arguments[i]); |
| } |
| if (opt_obj) { |
| params[0] = goog.bind(f, opt_obj); |
| } |
| return goog.array.ARRAY_PROTOTYPE_.reduce.apply(arr, params); |
| } : |
| function(arr, f, val, opt_obj) { |
| var rval = val; |
| goog.array.forEach(arr, function(val, index) { |
| rval = f.call(opt_obj, rval, val, index, arr); |
| }); |
| return rval; |
| }; |
| |
| |
| /** |
| * Passes every element of an array into a function and accumulates the result, |
| * starting from the last element and working towards the first. |
| * |
| * See {@link http://tinyurl.com/developer-mozilla-org-array-reduceright} |
| * |
| * For example: |
| * var a = ['a', 'b', 'c']; |
| * goog.array.reduceRight(a, function(r, v, i, arr) {return r + v;}, ''); |
| * returns 'cba' |
| * |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array |
| * like object over which to iterate. |
| * @param {?function(this:S, R, T, number, ?) : R} f The function to call for |
| * every element. This function |
| * takes 4 arguments (the function's previous result or the initial value, |
| * the value of the current array element, the current array index, and the |
| * array itself) |
| * function(previousValue, currentValue, index, array). |
| * @param {?} val The initial value to pass into the function on the first call. |
| * @param {S=} opt_obj The object to be used as the value of 'this' |
| * within f. |
| * @return {R} Object returned as a result of evaluating f repeatedly across the |
| * values of the array. |
| * @template T,S,R |
| */ |
| goog.array.reduceRight = goog.NATIVE_ARRAY_PROTOTYPES && |
| (goog.array.ASSUME_NATIVE_FUNCTIONS || |
| goog.array.ARRAY_PROTOTYPE_.reduceRight) ? |
| function(arr, f, val, opt_obj) { |
| goog.asserts.assert(arr.length != null); |
| if (opt_obj) { |
| f = goog.bind(f, opt_obj); |
| } |
| return goog.array.ARRAY_PROTOTYPE_.reduceRight.call(arr, f, val); |
| } : |
| function(arr, f, val, opt_obj) { |
| var rval = val; |
| goog.array.forEachRight(arr, function(val, index) { |
| rval = f.call(opt_obj, rval, val, index, arr); |
| }); |
| return rval; |
| }; |
| |
| |
| /** |
| * Calls f for each element of an array. If any call returns true, some() |
| * returns true (without checking the remaining elements). If all calls |
| * return false, some() returns false. |
| * |
| * See {@link http://tinyurl.com/developer-mozilla-org-array-some} |
| * |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array |
| * like object over which to iterate. |
| * @param {?function(this:S, T, number, ?) : boolean} f The function to call for |
| * for every element. This function takes 3 arguments (the element, the |
| * index and the array) and should return a boolean. |
| * @param {S=} opt_obj The object to be used as the value of 'this' |
| * within f. |
| * @return {boolean} true if any element passes the test. |
| * @template T,S |
| */ |
| goog.array.some = goog.NATIVE_ARRAY_PROTOTYPES && |
| (goog.array.ASSUME_NATIVE_FUNCTIONS || |
| goog.array.ARRAY_PROTOTYPE_.some) ? |
| function(arr, f, opt_obj) { |
| goog.asserts.assert(arr.length != null); |
| |
| return goog.array.ARRAY_PROTOTYPE_.some.call(arr, f, opt_obj); |
| } : |
| function(arr, f, opt_obj) { |
| var l = arr.length; // must be fixed during loop... see docs |
| var arr2 = goog.isString(arr) ? arr.split('') : arr; |
| for (var i = 0; i < l; i++) { |
| if (i in arr2 && f.call(opt_obj, arr2[i], i, arr)) { |
| return true; |
| } |
| } |
| return false; |
| }; |
| |
| |
| /** |
| * Call f for each element of an array. If all calls return true, every() |
| * returns true. If any call returns false, every() returns false and |
| * does not continue to check the remaining elements. |
| * |
| * See {@link http://tinyurl.com/developer-mozilla-org-array-every} |
| * |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array |
| * like object over which to iterate. |
| * @param {?function(this:S, T, number, ?) : boolean} f The function to call for |
| * for every element. This function takes 3 arguments (the element, the |
| * index and the array) and should return a boolean. |
| * @param {S=} opt_obj The object to be used as the value of 'this' |
| * within f. |
| * @return {boolean} false if any element fails the test. |
| * @template T,S |
| */ |
| goog.array.every = goog.NATIVE_ARRAY_PROTOTYPES && |
| (goog.array.ASSUME_NATIVE_FUNCTIONS || |
| goog.array.ARRAY_PROTOTYPE_.every) ? |
| function(arr, f, opt_obj) { |
| goog.asserts.assert(arr.length != null); |
| |
| return goog.array.ARRAY_PROTOTYPE_.every.call(arr, f, opt_obj); |
| } : |
| function(arr, f, opt_obj) { |
| var l = arr.length; // must be fixed during loop... see docs |
| var arr2 = goog.isString(arr) ? arr.split('') : arr; |
| for (var i = 0; i < l; i++) { |
| if (i in arr2 && !f.call(opt_obj, arr2[i], i, arr)) { |
| return false; |
| } |
| } |
| return true; |
| }; |
| |
| |
| /** |
| * Counts the array elements that fulfill the predicate, i.e. for which the |
| * callback function returns true. Skips holes in the array. |
| * |
| * @param {!(Array<T>|goog.array.ArrayLike)} arr Array or array like object |
| * over which to iterate. |
| * @param {function(this: S, T, number, ?): boolean} f The function to call for |
| * every element. Takes 3 arguments (the element, the index and the array). |
| * @param {S=} opt_obj The object to be used as the value of 'this' within f. |
| * @return {number} The number of the matching elements. |
| * @template T,S |
| */ |
| goog.array.count = function(arr, f, opt_obj) { |
| var count = 0; |
| goog.array.forEach(arr, function(element, index, arr) { |
| if (f.call(opt_obj, element, index, arr)) { |
| ++count; |
| } |
| }, opt_obj); |
| return count; |
| }; |
| |
| |
| /** |
| * Search an array for the first element that satisfies a given condition and |
| * return that element. |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array |
| * like object over which to iterate. |
| * @param {?function(this:S, T, number, ?) : boolean} f The function to call |
| * for every element. This function takes 3 arguments (the element, the |
| * index and the array) and should return a boolean. |
| * @param {S=} opt_obj An optional "this" context for the function. |
| * @return {T|null} The first array element that passes the test, or null if no |
| * element is found. |
| * @template T,S |
| */ |
| goog.array.find = function(arr, f, opt_obj) { |
| var i = goog.array.findIndex(arr, f, opt_obj); |
| return i < 0 ? null : goog.isString(arr) ? arr.charAt(i) : arr[i]; |
| }; |
| |
| |
| /** |
| * Search an array for the first element that satisfies a given condition and |
| * return its index. |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array |
| * like object over which to iterate. |
| * @param {?function(this:S, T, number, ?) : boolean} f The function to call for |
| * every element. This function |
| * takes 3 arguments (the element, the index and the array) and should |
| * return a boolean. |
| * @param {S=} opt_obj An optional "this" context for the function. |
| * @return {number} The index of the first array element that passes the test, |
| * or -1 if no element is found. |
| * @template T,S |
| */ |
| goog.array.findIndex = function(arr, f, opt_obj) { |
| var l = arr.length; // must be fixed during loop... see docs |
| var arr2 = goog.isString(arr) ? arr.split('') : arr; |
| for (var i = 0; i < l; i++) { |
| if (i in arr2 && f.call(opt_obj, arr2[i], i, arr)) { |
| return i; |
| } |
| } |
| return -1; |
| }; |
| |
| |
| /** |
| * Search an array (in reverse order) for the last element that satisfies a |
| * given condition and return that element. |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array |
| * like object over which to iterate. |
| * @param {?function(this:S, T, number, ?) : boolean} f The function to call |
| * for every element. This function |
| * takes 3 arguments (the element, the index and the array) and should |
| * return a boolean. |
| * @param {S=} opt_obj An optional "this" context for the function. |
| * @return {T|null} The last array element that passes the test, or null if no |
| * element is found. |
| * @template T,S |
| */ |
| goog.array.findRight = function(arr, f, opt_obj) { |
| var i = goog.array.findIndexRight(arr, f, opt_obj); |
| return i < 0 ? null : goog.isString(arr) ? arr.charAt(i) : arr[i]; |
| }; |
| |
| |
| /** |
| * Search an array (in reverse order) for the last element that satisfies a |
| * given condition and return its index. |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array |
| * like object over which to iterate. |
| * @param {?function(this:S, T, number, ?) : boolean} f The function to call |
| * for every element. This function |
| * takes 3 arguments (the element, the index and the array) and should |
| * return a boolean. |
| * @param {S=} opt_obj An optional "this" context for the function. |
| * @return {number} The index of the last array element that passes the test, |
| * or -1 if no element is found. |
| * @template T,S |
| */ |
| goog.array.findIndexRight = function(arr, f, opt_obj) { |
| var l = arr.length; // must be fixed during loop... see docs |
| var arr2 = goog.isString(arr) ? arr.split('') : arr; |
| for (var i = l - 1; i >= 0; i--) { |
| if (i in arr2 && f.call(opt_obj, arr2[i], i, arr)) { |
| return i; |
| } |
| } |
| return -1; |
| }; |
| |
| |
| /** |
| * Whether the array contains the given object. |
| * @param {goog.array.ArrayLike} arr The array to test for the presence of the |
| * element. |
| * @param {*} obj The object for which to test. |
| * @return {boolean} true if obj is present. |
| */ |
| goog.array.contains = function(arr, obj) { |
| return goog.array.indexOf(arr, obj) >= 0; |
| }; |
| |
| |
| /** |
| * Whether the array is empty. |
| * @param {goog.array.ArrayLike} arr The array to test. |
| * @return {boolean} true if empty. |
| */ |
| goog.array.isEmpty = function(arr) { |
| return arr.length == 0; |
| }; |
| |
| |
| /** |
| * Clears the array. |
| * @param {goog.array.ArrayLike} arr Array or array like object to clear. |
| */ |
| goog.array.clear = function(arr) { |
| // For non real arrays we don't have the magic length so we delete the |
| // indices. |
| if (!goog.isArray(arr)) { |
| for (var i = arr.length - 1; i >= 0; i--) { |
| delete arr[i]; |
| } |
| } |
| arr.length = 0; |
| }; |
| |
| |
| /** |
| * Pushes an item into an array, if it's not already in the array. |
| * @param {Array<T>} arr Array into which to insert the item. |
| * @param {T} obj Value to add. |
| * @template T |
| */ |
| goog.array.insert = function(arr, obj) { |
| if (!goog.array.contains(arr, obj)) { |
| arr.push(obj); |
| } |
| }; |
| |
| |
| /** |
| * Inserts an object at the given index of the array. |
| * @param {goog.array.ArrayLike} arr The array to modify. |
| * @param {*} obj The object to insert. |
| * @param {number=} opt_i The index at which to insert the object. If omitted, |
| * treated as 0. A negative index is counted from the end of the array. |
| */ |
| goog.array.insertAt = function(arr, obj, opt_i) { |
| goog.array.splice(arr, opt_i, 0, obj); |
| }; |
| |
| |
| /** |
| * Inserts at the given index of the array, all elements of another array. |
| * @param {goog.array.ArrayLike} arr The array to modify. |
| * @param {goog.array.ArrayLike} elementsToAdd The array of elements to add. |
| * @param {number=} opt_i The index at which to insert the object. If omitted, |
| * treated as 0. A negative index is counted from the end of the array. |
| */ |
| goog.array.insertArrayAt = function(arr, elementsToAdd, opt_i) { |
| goog.partial(goog.array.splice, arr, opt_i, 0).apply(null, elementsToAdd); |
| }; |
| |
| |
| /** |
| * Inserts an object into an array before a specified object. |
| * @param {Array<T>} arr The array to modify. |
| * @param {T} obj The object to insert. |
| * @param {T=} opt_obj2 The object before which obj should be inserted. If obj2 |
| * is omitted or not found, obj is inserted at the end of the array. |
| * @template T |
| */ |
| goog.array.insertBefore = function(arr, obj, opt_obj2) { |
| var i; |
| if (arguments.length == 2 || (i = goog.array.indexOf(arr, opt_obj2)) < 0) { |
| arr.push(obj); |
| } else { |
| goog.array.insertAt(arr, obj, i); |
| } |
| }; |
| |
| |
| /** |
| * Removes the first occurrence of a particular value from an array. |
| * @param {Array<T>|goog.array.ArrayLike} arr Array from which to remove |
| * value. |
| * @param {T} obj Object to remove. |
| * @return {boolean} True if an element was removed. |
| * @template T |
| */ |
| goog.array.remove = function(arr, obj) { |
| var i = goog.array.indexOf(arr, obj); |
| var rv; |
| if ((rv = i >= 0)) { |
| goog.array.removeAt(arr, i); |
| } |
| return rv; |
| }; |
| |
| |
| /** |
| * Removes from an array the element at index i |
| * @param {goog.array.ArrayLike} arr Array or array like object from which to |
| * remove value. |
| * @param {number} i The index to remove. |
| * @return {boolean} True if an element was removed. |
| */ |
| goog.array.removeAt = function(arr, i) { |
| goog.asserts.assert(arr.length != null); |
| |
| // use generic form of splice |
| // splice returns the removed items and if successful the length of that |
| // will be 1 |
| return goog.array.ARRAY_PROTOTYPE_.splice.call(arr, i, 1).length == 1; |
| }; |
| |
| |
| /** |
| * Removes the first value that satisfies the given condition. |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array |
| * like object over which to iterate. |
| * @param {?function(this:S, T, number, ?) : boolean} f The function to call |
| * for every element. This function |
| * takes 3 arguments (the element, the index and the array) and should |
| * return a boolean. |
| * @param {S=} opt_obj An optional "this" context for the function. |
| * @return {boolean} True if an element was removed. |
| * @template T,S |
| */ |
| goog.array.removeIf = function(arr, f, opt_obj) { |
| var i = goog.array.findIndex(arr, f, opt_obj); |
| if (i >= 0) { |
| goog.array.removeAt(arr, i); |
| return true; |
| } |
| return false; |
| }; |
| |
| |
| /** |
| * Removes all values that satisfy the given condition. |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array |
| * like object over which to iterate. |
| * @param {?function(this:S, T, number, ?) : boolean} f The function to call |
| * for every element. This function |
| * takes 3 arguments (the element, the index and the array) and should |
| * return a boolean. |
| * @param {S=} opt_obj An optional "this" context for the function. |
| * @return {number} The number of items removed |
| * @template T,S |
| */ |
| goog.array.removeAllIf = function(arr, f, opt_obj) { |
| var removedCount = 0; |
| goog.array.forEachRight(arr, function(val, index) { |
| if (f.call(opt_obj, val, index, arr)) { |
| if (goog.array.removeAt(arr, index)) { |
| removedCount++; |
| } |
| } |
| }); |
| return removedCount; |
| }; |
| |
| |
| /** |
| * Returns a new array that is the result of joining the arguments. If arrays |
| * are passed then their items are added, however, if non-arrays are passed they |
| * will be added to the return array as is. |
| * |
| * Note that ArrayLike objects will be added as is, rather than having their |
| * items added. |
| * |
| * goog.array.concat([1, 2], [3, 4]) -> [1, 2, 3, 4] |
| * goog.array.concat(0, [1, 2]) -> [0, 1, 2] |
| * goog.array.concat([1, 2], null) -> [1, 2, null] |
| * |
| * There is bug in all current versions of IE (6, 7 and 8) where arrays created |
| * in an iframe become corrupted soon (not immediately) after the iframe is |
| * destroyed. This is common if loading data via goog.net.IframeIo, for example. |
| * This corruption only affects the concat method which will start throwing |
| * Catastrophic Errors (#-2147418113). |
| * |
| * See http://endoflow.com/scratch/corrupted-arrays.html for a test case. |
| * |
| * Internally goog.array should use this, so that all methods will continue to |
| * work on these broken array objects. |
| * |
| * @param {...*} var_args Items to concatenate. Arrays will have each item |
| * added, while primitives and objects will be added as is. |
| * @return {!Array<?>} The new resultant array. |
| */ |
| goog.array.concat = function(var_args) { |
| return goog.array.ARRAY_PROTOTYPE_.concat.apply( |
| goog.array.ARRAY_PROTOTYPE_, arguments); |
| }; |
| |
| |
| /** |
| * Returns a new array that contains the contents of all the arrays passed. |
| * @param {...!Array<T>} var_args |
| * @return {!Array<T>} |
| * @template T |
| */ |
| goog.array.join = function(var_args) { |
| return goog.array.ARRAY_PROTOTYPE_.concat.apply( |
| goog.array.ARRAY_PROTOTYPE_, arguments); |
| }; |
| |
| |
| /** |
| * Converts an object to an array. |
| * @param {Array<T>|goog.array.ArrayLike} object The object to convert to an |
| * array. |
| * @return {!Array<T>} The object converted into an array. If object has a |
| * length property, every property indexed with a non-negative number |
| * less than length will be included in the result. If object does not |
| * have a length property, an empty array will be returned. |
| * @template T |
| */ |
| goog.array.toArray = function(object) { |
| var length = object.length; |
| |
| // If length is not a number the following it false. This case is kept for |
| // backwards compatibility since there are callers that pass objects that are |
| // not array like. |
| if (length > 0) { |
| var rv = new Array(length); |
| for (var i = 0; i < length; i++) { |
| rv[i] = object[i]; |
| } |
| return rv; |
| } |
| return []; |
| }; |
| |
| |
| /** |
| * Does a shallow copy of an array. |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array-like object to |
| * clone. |
| * @return {!Array<T>} Clone of the input array. |
| * @template T |
| */ |
| goog.array.clone = goog.array.toArray; |
| |
| |
| /** |
| * Extends an array with another array, element, or "array like" object. |
| * This function operates 'in-place', it does not create a new Array. |
| * |
| * Example: |
| * var a = []; |
| * goog.array.extend(a, [0, 1]); |
| * a; // [0, 1] |
| * goog.array.extend(a, 2); |
| * a; // [0, 1, 2] |
| * |
| * @param {Array<VALUE>} arr1 The array to modify. |
| * @param {...(Array<VALUE>|VALUE)} var_args The elements or arrays of elements |
| * to add to arr1. |
| * @template VALUE |
| */ |
| goog.array.extend = function(arr1, var_args) { |
| for (var i = 1; i < arguments.length; i++) { |
| var arr2 = arguments[i]; |
| if (goog.isArrayLike(arr2)) { |
| var len1 = arr1.length || 0; |
| var len2 = arr2.length || 0; |
| arr1.length = len1 + len2; |
| for (var j = 0; j < len2; j++) { |
| arr1[len1 + j] = arr2[j]; |
| } |
| } else { |
| arr1.push(arr2); |
| } |
| } |
| }; |
| |
| |
| /** |
| * Adds or removes elements from an array. This is a generic version of Array |
| * splice. This means that it might work on other objects similar to arrays, |
| * such as the arguments object. |
| * |
| * @param {Array<T>|goog.array.ArrayLike} arr The array to modify. |
| * @param {number|undefined} index The index at which to start changing the |
| * array. If not defined, treated as 0. |
| * @param {number} howMany How many elements to remove (0 means no removal. A |
| * value below 0 is treated as zero and so is any other non number. Numbers |
| * are floored). |
| * @param {...T} var_args Optional, additional elements to insert into the |
| * array. |
| * @return {!Array<T>} the removed elements. |
| * @template T |
| */ |
| goog.array.splice = function(arr, index, howMany, var_args) { |
| goog.asserts.assert(arr.length != null); |
| |
| return goog.array.ARRAY_PROTOTYPE_.splice.apply( |
| arr, goog.array.slice(arguments, 1)); |
| }; |
| |
| |
| /** |
| * Returns a new array from a segment of an array. This is a generic version of |
| * Array slice. This means that it might work on other objects similar to |
| * arrays, such as the arguments object. |
| * |
| * @param {Array<T>|goog.array.ArrayLike} arr The array from |
| * which to copy a segment. |
| * @param {number} start The index of the first element to copy. |
| * @param {number=} opt_end The index after the last element to copy. |
| * @return {!Array<T>} A new array containing the specified segment of the |
| * original array. |
| * @template T |
| */ |
| goog.array.slice = function(arr, start, opt_end) { |
| goog.asserts.assert(arr.length != null); |
| |
| // passing 1 arg to slice is not the same as passing 2 where the second is |
| // null or undefined (in that case the second argument is treated as 0). |
| // we could use slice on the arguments object and then use apply instead of |
| // testing the length |
| if (arguments.length <= 2) { |
| return goog.array.ARRAY_PROTOTYPE_.slice.call(arr, start); |
| } else { |
| return goog.array.ARRAY_PROTOTYPE_.slice.call(arr, start, opt_end); |
| } |
| }; |
| |
| |
| /** |
| * Removes all duplicates from an array (retaining only the first |
| * occurrence of each array element). This function modifies the |
| * array in place and doesn't change the order of the non-duplicate items. |
| * |
| * For objects, duplicates are identified as having the same unique ID as |
| * defined by {@link goog.getUid}. |
| * |
| * Alternatively you can specify a custom hash function that returns a unique |
| * value for each item in the array it should consider unique. |
| * |
| * Runtime: N, |
| * Worstcase space: 2N (no dupes) |
| * |
| * @param {Array<T>|goog.array.ArrayLike} arr The array from which to remove |
| * duplicates. |
| * @param {Array=} opt_rv An optional array in which to return the results, |
| * instead of performing the removal inplace. If specified, the original |
| * array will remain unchanged. |
| * @param {function(T):string=} opt_hashFn An optional function to use to |
| * apply to every item in the array. This function should return a unique |
| * value for each item in the array it should consider unique. |
| * @template T |
| */ |
| goog.array.removeDuplicates = function(arr, opt_rv, opt_hashFn) { |
| var returnArray = opt_rv || arr; |
| var defaultHashFn = function(item) { |
| // Prefix each type with a single character representing the type to |
| // prevent conflicting keys (e.g. true and 'true'). |
| return goog.isObject(current) ? 'o' + goog.getUid(current) : |
| (typeof current).charAt(0) + current; |
| }; |
| var hashFn = opt_hashFn || defaultHashFn; |
| |
| var seen = {}, cursorInsert = 0, cursorRead = 0; |
| while (cursorRead < arr.length) { |
| var current = arr[cursorRead++]; |
| var key = hashFn(current); |
| if (!Object.prototype.hasOwnProperty.call(seen, key)) { |
| seen[key] = true; |
| returnArray[cursorInsert++] = current; |
| } |
| } |
| returnArray.length = cursorInsert; |
| }; |
| |
| |
| /** |
| * Searches the specified array for the specified target using the binary |
| * search algorithm. If no opt_compareFn is specified, elements are compared |
| * using <code>goog.array.defaultCompare</code>, which compares the elements |
| * using the built in < and > operators. This will produce the expected |
| * behavior for homogeneous arrays of String(s) and Number(s). The array |
| * specified <b>must</b> be sorted in ascending order (as defined by the |
| * comparison function). If the array is not sorted, results are undefined. |
| * If the array contains multiple instances of the specified target value, any |
| * of these instances may be found. |
| * |
| * Runtime: O(log n) |
| * |
| * @param {Array<VALUE>|goog.array.ArrayLike} arr The array to be searched. |
| * @param {TARGET} target The sought value. |
| * @param {function(TARGET, VALUE): number=} opt_compareFn Optional comparison |
| * function by which the array is ordered. Should take 2 arguments to |
| * compare, and return a negative number, zero, or a positive number |
| * depending on whether the first argument is less than, equal to, or |
| * greater than the second. |
| * @return {number} Lowest index of the target value if found, otherwise |
| * (-(insertion point) - 1). The insertion point is where the value should |
| * be inserted into arr to preserve the sorted property. Return value >= 0 |
| * iff target is found. |
| * @template TARGET, VALUE |
| */ |
| goog.array.binarySearch = function(arr, target, opt_compareFn) { |
| return goog.array.binarySearch_(arr, |
| opt_compareFn || goog.array.defaultCompare, false /* isEvaluator */, |
| target); |
| }; |
| |
| |
| /** |
| * Selects an index in the specified array using the binary search algorithm. |
| * The evaluator receives an element and determines whether the desired index |
| * is before, at, or after it. The evaluator must be consistent (formally, |
| * goog.array.map(goog.array.map(arr, evaluator, opt_obj), goog.math.sign) |
| * must be monotonically non-increasing). |
| * |
| * Runtime: O(log n) |
| * |
| * @param {Array<VALUE>|goog.array.ArrayLike} arr The array to be searched. |
| * @param {function(this:THIS, VALUE, number, ?): number} evaluator |
| * Evaluator function that receives 3 arguments (the element, the index and |
| * the array). Should return a negative number, zero, or a positive number |
| * depending on whether the desired index is before, at, or after the |
| * element passed to it. |
| * @param {THIS=} opt_obj The object to be used as the value of 'this' |
| * within evaluator. |
| * @return {number} Index of the leftmost element matched by the evaluator, if |
| * such exists; otherwise (-(insertion point) - 1). The insertion point is |
| * the index of the first element for which the evaluator returns negative, |
| * or arr.length if no such element exists. The return value is non-negative |
| * iff a match is found. |
| * @template THIS, VALUE |
| */ |
| goog.array.binarySelect = function(arr, evaluator, opt_obj) { |
| return goog.array.binarySearch_(arr, evaluator, true /* isEvaluator */, |
| undefined /* opt_target */, opt_obj); |
| }; |
| |
| |
| /** |
| * Implementation of a binary search algorithm which knows how to use both |
| * comparison functions and evaluators. If an evaluator is provided, will call |
| * the evaluator with the given optional data object, conforming to the |
| * interface defined in binarySelect. Otherwise, if a comparison function is |
| * provided, will call the comparison function against the given data object. |
| * |
| * This implementation purposefully does not use goog.bind or goog.partial for |
| * performance reasons. |
| * |
| * Runtime: O(log n) |
| * |
| * @param {Array<VALUE>|goog.array.ArrayLike} arr The array to be searched. |
| * @param {function(TARGET, VALUE): number| |
| * function(this:THIS, VALUE, number, ?): number} compareFn Either an |
| * evaluator or a comparison function, as defined by binarySearch |
| * and binarySelect above. |
| * @param {boolean} isEvaluator Whether the function is an evaluator or a |
| * comparison function. |
| * @param {TARGET=} opt_target If the function is a comparison function, then |
| * this is the target to binary search for. |
| * @param {THIS=} opt_selfObj If the function is an evaluator, this is an |
| * optional this object for the evaluator. |
| * @return {number} Lowest index of the target value if found, otherwise |
| * (-(insertion point) - 1). The insertion point is where the value should |
| * be inserted into arr to preserve the sorted property. Return value >= 0 |
| * iff target is found. |
| * @template THIS, VALUE, TARGET |
| * @private |
| */ |
| goog.array.binarySearch_ = function(arr, compareFn, isEvaluator, opt_target, |
| opt_selfObj) { |
| var left = 0; // inclusive |
| var right = arr.length; // exclusive |
| var found; |
| while (left < right) { |
| var middle = (left + right) >> 1; |
| var compareResult; |
| if (isEvaluator) { |
| compareResult = compareFn.call(opt_selfObj, arr[middle], middle, arr); |
| } else { |
| compareResult = compareFn(opt_target, arr[middle]); |
| } |
| if (compareResult > 0) { |
| left = middle + 1; |
| } else { |
| right = middle; |
| // We are looking for the lowest index so we can't return immediately. |
| found = !compareResult; |
| } |
| } |
| // left is the index if found, or the insertion point otherwise. |
| // ~left is a shorthand for -left - 1. |
| return found ? left : ~left; |
| }; |
| |
| |
| /** |
| * Sorts the specified array into ascending order. If no opt_compareFn is |
| * specified, elements are compared using |
| * <code>goog.array.defaultCompare</code>, which compares the elements using |
| * the built in < and > operators. This will produce the expected behavior |
| * for homogeneous arrays of String(s) and Number(s), unlike the native sort, |
| * but will give unpredictable results for heterogenous lists of strings and |
| * numbers with different numbers of digits. |
| * |
| * This sort is not guaranteed to be stable. |
| * |
| * Runtime: Same as <code>Array.prototype.sort</code> |
| * |
| * @param {Array<T>} arr The array to be sorted. |
| * @param {?function(T,T):number=} opt_compareFn Optional comparison |
| * function by which the |
| * array is to be ordered. Should take 2 arguments to compare, and return a |
| * negative number, zero, or a positive number depending on whether the |
| * first argument is less than, equal to, or greater than the second. |
| * @template T |
| */ |
| goog.array.sort = function(arr, opt_compareFn) { |
| // TODO(arv): Update type annotation since null is not accepted. |
| arr.sort(opt_compareFn || goog.array.defaultCompare); |
| }; |
| |
| |
| /** |
| * Sorts the specified array into ascending order in a stable way. If no |
| * opt_compareFn is specified, elements are compared using |
| * <code>goog.array.defaultCompare</code>, which compares the elements using |
| * the built in < and > operators. This will produce the expected behavior |
| * for homogeneous arrays of String(s) and Number(s). |
| * |
| * Runtime: Same as <code>Array.prototype.sort</code>, plus an additional |
| * O(n) overhead of copying the array twice. |
| * |
| * @param {Array<T>} arr The array to be sorted. |
| * @param {?function(T, T): number=} opt_compareFn Optional comparison function |
| * by which the array is to be ordered. Should take 2 arguments to compare, |
| * and return a negative number, zero, or a positive number depending on |
| * whether the first argument is less than, equal to, or greater than the |
| * second. |
| * @template T |
| */ |
| goog.array.stableSort = function(arr, opt_compareFn) { |
| for (var i = 0; i < arr.length; i++) { |
| arr[i] = {index: i, value: arr[i]}; |
| } |
| var valueCompareFn = opt_compareFn || goog.array.defaultCompare; |
| function stableCompareFn(obj1, obj2) { |
| return valueCompareFn(obj1.value, obj2.value) || obj1.index - obj2.index; |
| }; |
| goog.array.sort(arr, stableCompareFn); |
| for (var i = 0; i < arr.length; i++) { |
| arr[i] = arr[i].value; |
| } |
| }; |
| |
| |
| /** |
| * Sort the specified array into ascending order based on item keys |
| * returned by the specified key function. |
| * If no opt_compareFn is specified, the keys are compared in ascending order |
| * using <code>goog.array.defaultCompare</code>. |
| * |
| * Runtime: O(S(f(n)), where S is runtime of <code>goog.array.sort</code> |
| * and f(n) is runtime of the key function. |
| * |
| * @param {Array<T>} arr The array to be sorted. |
| * @param {function(T): K} keyFn Function taking array element and returning |
| * a key used for sorting this element. |
| * @param {?function(K, K): number=} opt_compareFn Optional comparison function |
| * by which the keys are to be ordered. Should take 2 arguments to compare, |
| * and return a negative number, zero, or a positive number depending on |
| * whether the first argument is less than, equal to, or greater than the |
| * second. |
| * @template T |
| * @template K |
| */ |
| goog.array.sortByKey = function(arr, keyFn, opt_compareFn) { |
| var keyCompareFn = opt_compareFn || goog.array.defaultCompare; |
| goog.array.sort(arr, function(a, b) { |
| return keyCompareFn(keyFn(a), keyFn(b)); |
| }); |
| }; |
| |
| |
| /** |
| * Sorts an array of objects by the specified object key and compare |
| * function. If no compare function is provided, the key values are |
| * compared in ascending order using <code>goog.array.defaultCompare</code>. |
| * This won't work for keys that get renamed by the compiler. So use |
| * {'foo': 1, 'bar': 2} rather than {foo: 1, bar: 2}. |
| * @param {Array<Object>} arr An array of objects to sort. |
| * @param {string} key The object key to sort by. |
| * @param {Function=} opt_compareFn The function to use to compare key |
| * values. |
| */ |
| goog.array.sortObjectsByKey = function(arr, key, opt_compareFn) { |
| goog.array.sortByKey(arr, |
| function(obj) { return obj[key]; }, |
| opt_compareFn); |
| }; |
| |
| |
| /** |
| * Tells if the array is sorted. |
| * @param {!Array<T>} arr The array. |
| * @param {?function(T,T):number=} opt_compareFn Function to compare the |
| * array elements. |
| * Should take 2 arguments to compare, and return a negative number, zero, |
| * or a positive number depending on whether the first argument is less |
| * than, equal to, or greater than the second. |
| * @param {boolean=} opt_strict If true no equal elements are allowed. |
| * @return {boolean} Whether the array is sorted. |
| * @template T |
| */ |
| goog.array.isSorted = function(arr, opt_compareFn, opt_strict) { |
| var compare = opt_compareFn || goog.array.defaultCompare; |
| for (var i = 1; i < arr.length; i++) { |
| var compareResult = compare(arr[i - 1], arr[i]); |
| if (compareResult > 0 || compareResult == 0 && opt_strict) { |
| return false; |
| } |
| } |
| return true; |
| }; |
| |
| |
| /** |
| * Compares two arrays for equality. Two arrays are considered equal if they |
| * have the same length and their corresponding elements are equal according to |
| * the comparison function. |
| * |
| * @param {goog.array.ArrayLike} arr1 The first array to compare. |
| * @param {goog.array.ArrayLike} arr2 The second array to compare. |
| * @param {Function=} opt_equalsFn Optional comparison function. |
| * Should take 2 arguments to compare, and return true if the arguments |
| * are equal. Defaults to {@link goog.array.defaultCompareEquality} which |
| * compares the elements using the built-in '===' operator. |
| * @return {boolean} Whether the two arrays are equal. |
| */ |
| goog.array.equals = function(arr1, arr2, opt_equalsFn) { |
| if (!goog.isArrayLike(arr1) || !goog.isArrayLike(arr2) || |
| arr1.length != arr2.length) { |
| return false; |
| } |
| var l = arr1.length; |
| var equalsFn = opt_equalsFn || goog.array.defaultCompareEquality; |
| for (var i = 0; i < l; i++) { |
| if (!equalsFn(arr1[i], arr2[i])) { |
| return false; |
| } |
| } |
| return true; |
| }; |
| |
| |
| /** |
| * 3-way array compare function. |
| * @param {!Array<VALUE>|!goog.array.ArrayLike} arr1 The first array to |
| * compare. |
| * @param {!Array<VALUE>|!goog.array.ArrayLike} arr2 The second array to |
| * compare. |
| * @param {function(VALUE, VALUE): number=} opt_compareFn Optional comparison |
| * function by which the array is to be ordered. Should take 2 arguments to |
| * compare, and return a negative number, zero, or a positive number |
| * depending on whether the first argument is less than, equal to, or |
| * greater than the second. |
| * @return {number} Negative number, zero, or a positive number depending on |
| * whether the first argument is less than, equal to, or greater than the |
| * second. |
| * @template VALUE |
| */ |
| goog.array.compare3 = function(arr1, arr2, opt_compareFn) { |
| var compare = opt_compareFn || goog.array.defaultCompare; |
| var l = Math.min(arr1.length, arr2.length); |
| for (var i = 0; i < l; i++) { |
| var result = compare(arr1[i], arr2[i]); |
| if (result != 0) { |
| return result; |
| } |
| } |
| return goog.array.defaultCompare(arr1.length, arr2.length); |
| }; |
| |
| |
| /** |
| * Compares its two arguments for order, using the built in < and > |
| * operators. |
| * @param {VALUE} a The first object to be compared. |
| * @param {VALUE} b The second object to be compared. |
| * @return {number} A negative number, zero, or a positive number as the first |
| * argument is less than, equal to, or greater than the second, |
| * respectively. |
| * @template VALUE |
| */ |
| goog.array.defaultCompare = function(a, b) { |
| return a > b ? 1 : a < b ? -1 : 0; |
| }; |
| |
| |
| /** |
| * Compares its two arguments for inverse order, using the built in < and > |
| * operators. |
| * @param {VALUE} a The first object to be compared. |
| * @param {VALUE} b The second object to be compared. |
| * @return {number} A negative number, zero, or a positive number as the first |
| * argument is greater than, equal to, or less than the second, |
| * respectively. |
| * @template VALUE |
| */ |
| goog.array.inverseDefaultCompare = function(a, b) { |
| return -goog.array.defaultCompare(a, b); |
| }; |
| |
| |
| /** |
| * Compares its two arguments for equality, using the built in === operator. |
| * @param {*} a The first object to compare. |
| * @param {*} b The second object to compare. |
| * @return {boolean} True if the two arguments are equal, false otherwise. |
| */ |
| goog.array.defaultCompareEquality = function(a, b) { |
| return a === b; |
| }; |
| |
| |
| /** |
| * Inserts a value into a sorted array. The array is not modified if the |
| * value is already present. |
| * @param {Array<VALUE>|goog.array.ArrayLike} array The array to modify. |
| * @param {VALUE} value The object to insert. |
| * @param {function(VALUE, VALUE): number=} opt_compareFn Optional comparison |
| * function by which the array is ordered. Should take 2 arguments to |
| * compare, and return a negative number, zero, or a positive number |
| * depending on whether the first argument is less than, equal to, or |
| * greater than the second. |
| * @return {boolean} True if an element was inserted. |
| * @template VALUE |
| */ |
| goog.array.binaryInsert = function(array, value, opt_compareFn) { |
| var index = goog.array.binarySearch(array, value, opt_compareFn); |
| if (index < 0) { |
| goog.array.insertAt(array, value, -(index + 1)); |
| return true; |
| } |
| return false; |
| }; |
| |
| |
| /** |
| * Removes a value from a sorted array. |
| * @param {!Array<VALUE>|!goog.array.ArrayLike} array The array to modify. |
| * @param {VALUE} value The object to remove. |
| * @param {function(VALUE, VALUE): number=} opt_compareFn Optional comparison |
| * function by which the array is ordered. Should take 2 arguments to |
| * compare, and return a negative number, zero, or a positive number |
| * depending on whether the first argument is less than, equal to, or |
| * greater than the second. |
| * @return {boolean} True if an element was removed. |
| * @template VALUE |
| */ |
| goog.array.binaryRemove = function(array, value, opt_compareFn) { |
| var index = goog.array.binarySearch(array, value, opt_compareFn); |
| return (index >= 0) ? goog.array.removeAt(array, index) : false; |
| }; |
| |
| |
| /** |
| * Splits an array into disjoint buckets according to a splitting function. |
| * @param {Array<T>} array The array. |
| * @param {function(this:S, T,number,Array<T>):?} sorter Function to call for |
| * every element. This takes 3 arguments (the element, the index and the |
| * array) and must return a valid object key (a string, number, etc), or |
| * undefined, if that object should not be placed in a bucket. |
| * @param {S=} opt_obj The object to be used as the value of 'this' within |
| * sorter. |
| * @return {!Object} An object, with keys being all of the unique return values |
| * of sorter, and values being arrays containing the items for |
| * which the splitter returned that key. |
| * @template T,S |
| */ |
| goog.array.bucket = function(array, sorter, opt_obj) { |
| var buckets = {}; |
| |
| for (var i = 0; i < array.length; i++) { |
| var value = array[i]; |
| var key = sorter.call(opt_obj, value, i, array); |
| if (goog.isDef(key)) { |
| // Push the value to the right bucket, creating it if necessary. |
| var bucket = buckets[key] || (buckets[key] = []); |
| bucket.push(value); |
| } |
| } |
| |
| return buckets; |
| }; |
| |
| |
| /** |
| * Creates a new object built from the provided array and the key-generation |
| * function. |
| * @param {Array<T>|goog.array.ArrayLike} arr Array or array like object over |
| * which to iterate whose elements will be the values in the new object. |
| * @param {?function(this:S, T, number, ?) : string} keyFunc The function to |
| * call for every element. This function takes 3 arguments (the element, the |
| * index and the array) and should return a string that will be used as the |
| * key for the element in the new object. If the function returns the same |
| * key for more than one element, the value for that key is |
| * implementation-defined. |
| * @param {S=} opt_obj The object to be used as the value of 'this' |
| * within keyFunc. |
| * @return {!Object<T>} The new object. |
| * @template T,S |
| */ |
| goog.array.toObject = function(arr, keyFunc, opt_obj) { |
| var ret = {}; |
| goog.array.forEach(arr, function(element, index) { |
| ret[keyFunc.call(opt_obj, element, index, arr)] = element; |
| }); |
| return ret; |
| }; |
| |
| |
| /** |
| * Creates a range of numbers in an arithmetic progression. |
| * |
| * Range takes 1, 2, or 3 arguments: |
| * <pre> |
| * range(5) is the same as range(0, 5, 1) and produces [0, 1, 2, 3, 4] |
| * range(2, 5) is the same as range(2, 5, 1) and produces [2, 3, 4] |
| * range(-2, -5, -1) produces [-2, -3, -4] |
| * range(-2, -5, 1) produces [], since stepping by 1 wouldn't ever reach -5. |
| * </pre> |
| * |
| * @param {number} startOrEnd The starting value of the range if an end argument |
| * is provided. Otherwise, the start value is 0, and this is the end value. |
| * @param {number=} opt_end The optional end value of the range. |
| * @param {number=} opt_step The step size between range values. Defaults to 1 |
| * if opt_step is undefined or 0. |
| * @return {!Array<number>} An array of numbers for the requested range. May be |
| * an empty array if adding the step would not converge toward the end |
| * value. |
| */ |
| goog.array.range = function(startOrEnd, opt_end, opt_step) { |
| var array = []; |
| var start = 0; |
| var end = startOrEnd; |
| var step = opt_step || 1; |
| if (opt_end !== undefined) { |
| start = startOrEnd; |
| end = opt_end; |
| } |
| |
| if (step * (end - start) < 0) { |
| // Sign mismatch: start + step will never reach the end value. |
| return []; |
| } |
| |
| if (step > 0) { |
| for (var i = start; i < end; i += step) { |
| array.push(i); |
| } |
| } else { |
| for (var i = start; i > end; i += step) { |
| array.push(i); |
| } |
| } |
| return array; |
| }; |
| |
| |
| /** |
| * Returns an array consisting of the given value repeated N times. |
| * |
| * @param {VALUE} value The value to repeat. |
| * @param {number} n The repeat count. |
| * @return {!Array<VALUE>} An array with the repeated value. |
| * @template VALUE |
| */ |
| goog.array.repeat = function(value, n) { |
| var array = []; |
| for (var i = 0; i < n; i++) { |
| array[i] = value; |
| } |
| return array; |
| }; |
| |
| |
| /** |
| * Returns an array consisting of every argument with all arrays |
| * expanded in-place recursively. |
| * |
| * @param {...*} var_args The values to flatten. |
| * @return {!Array<?>} An array containing the flattened values. |
| */ |
| goog.array.flatten = function(var_args) { |
| var CHUNK_SIZE = 8192; |
| |
| var result = []; |
| for (var i = 0; i < arguments.length; i++) { |
| var element = arguments[i]; |
| if (goog.isArray(element)) { |
| for (var c = 0; c < element.length; c += CHUNK_SIZE) { |
| var chunk = goog.array.slice(element, c, c + CHUNK_SIZE); |
| var recurseResult = goog.array.flatten.apply(null, chunk); |
| for (var r = 0; r < recurseResult.length; r++) { |
| result.push(recurseResult[r]); |
| } |
| } |
| } else { |
| result.push(element); |
| } |
| } |
| return result; |
| }; |
| |
| |
| /** |
| * Rotates an array in-place. After calling this method, the element at |
| * index i will be the element previously at index (i - n) % |
| * array.length, for all values of i between 0 and array.length - 1, |
| * inclusive. |
| * |
| * For example, suppose list comprises [t, a, n, k, s]. After invoking |
| * rotate(array, 1) (or rotate(array, -4)), array will comprise [s, t, a, n, k]. |
| * |
| * @param {!Array<T>} array The array to rotate. |
| * @param {number} n The amount to rotate. |
| * @return {!Array<T>} The array. |
| * @template T |
| */ |
| goog.array.rotate = function(array, n) { |
| goog.asserts.assert(array.length != null); |
| |
| if (array.length) { |
| n %= array.length; |
| if (n > 0) { |
| goog.array.ARRAY_PROTOTYPE_.unshift.apply(array, array.splice(-n, n)); |
| } else if (n < 0) { |
| goog.array.ARRAY_PROTOTYPE_.push.apply(array, array.splice(0, -n)); |
| } |
| } |
| return array; |
| }; |
| |
| |
| /** |
| * Moves one item of an array to a new position keeping the order of the rest |
| * of the items. Example use case: keeping a list of JavaScript objects |
| * synchronized with the corresponding list of DOM elements after one of the |
| * elements has been dragged to a new position. |
| * @param {!(Array|Arguments|{length:number})} arr The array to modify. |
| * @param {number} fromIndex Index of the item to move between 0 and |
| * {@code arr.length - 1}. |
| * @param {number} toIndex Target index between 0 and {@code arr.length - 1}. |
| */ |
| goog.array.moveItem = function(arr, fromIndex, toIndex) { |
| goog.asserts.assert(fromIndex >= 0 && fromIndex < arr.length); |
| goog.asserts.assert(toIndex >= 0 && toIndex < arr.length); |
| // Remove 1 item at fromIndex. |
| var removedItems = goog.array.ARRAY_PROTOTYPE_.splice.call(arr, fromIndex, 1); |
| // Insert the removed item at toIndex. |
| goog.array.ARRAY_PROTOTYPE_.splice.call(arr, toIndex, 0, removedItems[0]); |
| // We don't use goog.array.insertAt and goog.array.removeAt, because they're |
| // significantly slower than splice. |
| }; |
| |
| |
| /** |
| * Creates a new array for which the element at position i is an array of the |
| * ith element of the provided arrays. The returned array will only be as long |
| * as the shortest array provided; additional values are ignored. For example, |
| * the result of zipping [1, 2] and [3, 4, 5] is [[1,3], [2, 4]]. |
| * |
| * This is similar to the zip() function in Python. See {@link |
| * http://docs.python.org/library/functions.html#zip} |
| * |
| * @param {...!goog.array.ArrayLike} var_args Arrays to be combined. |
| * @return {!Array<!Array<?>>} A new array of arrays created from |
| * provided arrays. |
| */ |
| goog.array.zip = function(var_args) { |
| if (!arguments.length) { |
| return []; |
| } |
| var result = []; |
| for (var i = 0; true; i++) { |
| var value = []; |
| for (var j = 0; j < arguments.length; j++) { |
| var arr = arguments[j]; |
| // If i is larger than the array length, this is the shortest array. |
| if (i >= arr.length) { |
| return result; |
| } |
| value.push(arr[i]); |
| } |
| result.push(value); |
| } |
| }; |
| |
| |
| /** |
| * Shuffles the values in the specified array using the Fisher-Yates in-place |
| * shuffle (also known as the Knuth Shuffle). By default, calls Math.random() |
| * and so resets the state of that random number generator. Similarly, may reset |
| * the state of the any other specified random number generator. |
| * |
| * Runtime: O(n) |
| * |
| * @param {!Array<?>} arr The array to be shuffled. |
| * @param {function():number=} opt_randFn Optional random function to use for |
| * shuffling. |
| * Takes no arguments, and returns a random number on the interval [0, 1). |
| * Defaults to Math.random() using JavaScript's built-in Math library. |
| */ |
| goog.array.shuffle = function(arr, opt_randFn) { |
| var randFn = opt_randFn || Math.random; |
| |
| for (var i = arr.length - 1; i > 0; i--) { |
| // Choose a random array index in [0, i] (inclusive with i). |
| var j = Math.floor(randFn() * (i + 1)); |
| |
| var tmp = arr[i]; |
| arr[i] = arr[j]; |
| arr[j] = tmp; |
| } |
| }; |
| |
| |
| /** |
| * Returns a new array of elements from arr, based on the indexes of elements |
| * provided by index_arr. For example, the result of index copying |
| * ['a', 'b', 'c'] with index_arr [1,0,0,2] is ['b', 'a', 'a', 'c']. |
| * |
| * @param {!Array<T>} arr The array to get a indexed copy from. |
| * @param {!Array<number>} index_arr An array of indexes to get from arr. |
| * @return {!Array<T>} A new array of elements from arr in index_arr order. |
| * @template T |
| */ |
| goog.array.copyByIndex = function(arr, index_arr) { |
| var result = []; |
| goog.array.forEach(index_arr, function(index) { |
| result.push(arr[index]); |
| }); |
| return result; |
| }; |