diff options
Diffstat (limited to 'contexts/data/lib/closure-library/closure/goog/array/array.js')
| -rw-r--r-- | contexts/data/lib/closure-library/closure/goog/array/array.js | 1416 |
1 files changed, 0 insertions, 1416 deletions
diff --git a/contexts/data/lib/closure-library/closure/goog/array/array.js b/contexts/data/lib/closure-library/closure/goog/array/array.js deleted file mode 100644 index 9faac38..0000000 --- a/contexts/data/lib/closure-library/closure/goog/array/array.js +++ /dev/null @@ -1,1416 +0,0 @@ -// 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. - * - */ - - -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. - */ -goog.NATIVE_ARRAY_PROTOTYPES = true; - - -/** - * @typedef {Array|NodeList|Arguments|{length: number}} - */ -goog.array.ArrayLike; - - -/** - * Returns the last element in an array without removing it. - * @param {goog.array.ArrayLike} array The array. - * @return {*} Last item in array. - */ -goog.array.peek = function(array) { - return array[array.length - 1]; -}; - - -/** - * 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 {goog.array.ArrayLike} arr The array to be searched. - * @param {*} 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. - */ -goog.array.indexOf = goog.NATIVE_ARRAY_PROTOTYPES && - 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 {goog.array.ArrayLike} arr The array to be searched. - * @param {*} 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. - */ -goog.array.lastIndexOf = goog.NATIVE_ARRAY_PROTOTYPES && - 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. - * - * 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. The function is called only for indexes of - * the array which have assigned values; it is not called for indexes which - * have been deleted or which have never been assigned values. - * @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.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} 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.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.<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) and should - * return something. The result will be inserted into a new array. - * @param {S=} opt_obj The object to be used as the value of 'this' - * within f. - * @return {!Array} a new array with the results from f. - * @template T,S - */ -goog.array.map = goog.NATIVE_ARRAY_PROTOTYPES && - 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 = function(arr, f, val, opt_obj) { - if (arr.reduce) { - if (opt_obj) { - return arr.reduce(goog.bind(f, opt_obj), val); - } else { - return arr.reduce(f, val); - } - } - 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 = function(arr, f, val, opt_obj) { - if (arr.reduceRight) { - if (opt_obj) { - return arr.reduceRight(goog.bind(f, opt_obj), val); - } else { - return arr.reduceRight(f, val); - } - } - 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.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.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; - }; - - -/** - * 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} 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} 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 {Object=} 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 {goog.array.ArrayLike} arr Array from which to remove value. - * @param {*} obj Object to remove. - * @return {boolean} True if an element was removed. - */ -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; -}; - - -/** - * 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); -}; - - -/** - * Converts an object to an array. - * @param {goog.array.ArrayLike} object The object to convert to an array. - * @return {!Array} 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. - */ -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 {goog.array.ArrayLike} arr Array or array-like object to clone. - * @return {!Array} Clone of the input array. - */ -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} arr1 The array to modify. - * @param {...*} var_args The elements or arrays of elements to add to arr1. - */ -goog.array.extend = function(arr1, var_args) { - for (var i = 1; i < arguments.length; i++) { - var arr2 = arguments[i]; - // If we have an Array or an Arguments object we can just call push - // directly. - var isArrayLike; - if (goog.isArray(arr2) || - // Detect Arguments. ES5 says that the [[Class]] of an Arguments object - // is "Arguments" but only V8 and JSC/Safari gets this right. We instead - // detect Arguments by checking for array like and presence of "callee". - (isArrayLike = goog.isArrayLike(arr2)) && - // The getter for callee throws an exception in strict mode - // according to section 10.6 in ES5 so check for presence instead. - arr2.hasOwnProperty('callee')) { - arr1.push.apply(arr1, arr2); - - } else if (isArrayLike) { - // Otherwise loop over arr2 to prevent copying the object. - var len1 = arr1.length; - var len2 = arr2.length; - 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 {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 {...*} var_args Optional, additional elements to insert into the - * array. - * @return {!Array} the removed elements. - */ -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}. - * - * Runtime: N, - * Worstcase space: 2N (no dupes) - * - * @param {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. - */ -goog.array.removeDuplicates = function(arr, opt_rv) { - var returnArray = opt_rv || arr; - - var seen = {}, cursorInsert = 0, cursorRead = 0; - while (cursorRead < arr.length) { - var current = arr[cursorRead++]; - - // Prefix each type with a single character representing the type to - // prevent conflicting keys (e.g. true and 'true'). - var key = goog.isObject(current) ? - 'o' + goog.getUid(current) : - (typeof current).charAt(0) + 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 {goog.array.ArrayLike} arr The array to be searched. - * @param {*} target The sought value. - * @param {Function=} 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. - */ -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 {goog.array.ArrayLike} arr The array to be searched. - * @param {Function} 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 {Object=} 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. - */ -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 {goog.array.ArrayLike} arr The array to be searched. - * @param {Function} 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 {*=} opt_target If the function is a comparison function, then this is - * the target to binary search for. - * @param {Object=} 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. - * @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. - goog.asserts.assert(arr.length != null); - - goog.array.ARRAY_PROTOTYPE_.sort.call( - arr, 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; - } -}; - - -/** - * 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) { - var compare = opt_compareFn || goog.array.defaultCompare; - goog.array.sort(arr, function(a, b) { - return compare(a[key], b[key]); - }); -}; - - -/** - * 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; -}; - - -/** - * @deprecated Use {@link goog.array.equals}. - * @param {goog.array.ArrayLike} arr1 See {@link goog.array.equals}. - * @param {goog.array.ArrayLike} arr2 See {@link goog.array.equals}. - * @param {Function=} opt_equalsFn See {@link goog.array.equals}. - * @return {boolean} See {@link goog.array.equals}. - */ -goog.array.compare = function(arr1, arr2, opt_equalsFn) { - return goog.array.equals(arr1, arr2, opt_equalsFn); -}; - - -/** - * 3-way array compare function. - * @param {!goog.array.ArrayLike} arr1 The first array to compare. - * @param {!goog.array.ArrayLike} arr2 The second array to compare. - * @param {?function(?, ?): 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. - */ -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 {*} a The first object to be compared. - * @param {*} 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. - */ -goog.array.defaultCompare = function(a, b) { - return a > b ? 1 : a < b ? -1 : 0; -}; - - -/** - * 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.<T>} array The array to modify. - * @param {T} value The object to insert. - * @param {?function(T,T):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 T - */ -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} array The array to modify. - * @param {*} value The object to remove. - * @param {Function=} 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. - */ -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(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. - * @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 - */ -goog.array.bucket = function(array, sorter) { - var buckets = {}; - - for (var i = 0; i < array.length; i++) { - var value = array[i]; - var key = sorter(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; -}; - - -/** - * Returns an array consisting of the given value repeated N times. - * - * @param {*} value The value to repeat. - * @param {number} n The repeat count. - * @return {!Array} An array with the repeated 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 result = []; - for (var i = 0; i < arguments.length; i++) { - var element = arguments[i]; - if (goog.isArray(element)) { - result.push.apply(result, goog.array.flatten.apply(null, element)); - } 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; -}; - - -/** - * 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; - } -}; |