text: // 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.
  
  // Modifications
  // Copyright 2011 Eric Bréchemier, Some Rights Reserved
  // Copyright 2010-2011 Legal-Box SAS, All Rights Reserved
  // Licensed under the BSD License
  // http://creativecommons.org/licenses/BSD/
  //
  // * renamed file from goog/array/array.js to goog.array.js
  // * commented all calls to goog.asserts and associated require
  // * wrapped code in a function in a call to define for dependency management
  //   using requireJS
  
  /**
   * @fileoverview Utilities for manipulating arrays.
   *
   */
  define(["./goog"], function(goog){
  
    goog.provide('goog.array');
    goog.provide('goog.array.ArrayLike');
  
    // LB: disable asserts
    // goog.require('goog.asserts');
  
  
    /**
     * @const {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(user): 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) {
          // LB: disabled asserts
          //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) {
          // LB: disable asserts
          //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 {goog.array.ArrayLike} arr Array or array like object over
     *     which to iterate.
     * @param {Function} 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 {Object=} opt_obj The object to be used as the value of 'this'
     *     within f.
     */
    goog.array.forEach = goog.NATIVE_ARRAY_PROTOTYPES &&
                         goog.array.ARRAY_PROTOTYPE_.forEach ?
        function(arr, f, opt_obj) {
          // LB: disable asserts
          //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 {goog.array.ArrayLike} arr The array over which to iterate.
     * @param {Function} 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 {Object=} opt_obj The object to be used as the value of 'this'
     *     within f.
     */
    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 {goog.array.ArrayLike} arr The array over which to iterate.
     * @param {Function} 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 {Object=} 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.
     */
    goog.array.filter = goog.NATIVE_ARRAY_PROTOTYPES &&
                        goog.array.ARRAY_PROTOTYPE_.filter ?
        function(arr, f, opt_obj) {
          // LB: disable asserts
          //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 {goog.array.ArrayLike} arr The array over which to iterate.
     * @param {Function} 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 {Object=} opt_obj The object to be used as the value of 'this'
     *     within f.
     * @return {!Array} a new array with the results from f.
     */
    goog.array.map = goog.NATIVE_ARRAY_PROTOTYPES &&
                     goog.array.ARRAY_PROTOTYPE_.map ?
        function(arr, f, opt_obj) {
          // LB: disable asserts
          //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 {goog.array.ArrayLike} arr The array over which to iterate.
     * @param {Function} 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 {Object=} opt_obj  The object to be used as the value of 'this'
     *     within f.
     * @return {*} Result of evaluating f repeatedly across the values of the array.
     */
    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 {goog.array.ArrayLike} arr The array over which to iterate.
     * @param {Function} 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 {Object=} opt_obj The object to be used as the value of 'this'
     *     within f.
     * @return {*} Object returned as a result of evaluating f repeatedly across the
     *     values of the array.
     */
    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 {goog.array.ArrayLike} arr The array to check.
     * @param {Function} 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.
     * @param {Object=} opt_obj  The object to be used as the value of 'this'
     *     within f.
     * @return {boolean} true if any element passes the test.
     */
    goog.array.some = goog.NATIVE_ARRAY_PROTOTYPES &&
                      goog.array.ARRAY_PROTOTYPE_.some ?
        function(arr, f, opt_obj) {
          // LB: disable asserts
          //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 {goog.array.ArrayLike} arr The array to check.
     * @param {Function} 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.
     * @param {Object=} opt_obj The object to be used as the value of 'this'
     *     within f.
     * @return {boolean} false if any element fails the test.
     */
    goog.array.every = goog.NATIVE_ARRAY_PROTOTYPES &&
                       goog.array.ARRAY_PROTOTYPE_.every ?
        function(arr, f, opt_obj) {
          // LB: disable asserts
          //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 {goog.array.ArrayLike} arr The array to search.
     * @param {Function} 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 {*} The first array element that passes the test, or null if no
     *     element is found.
     */
    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 {goog.array.ArrayLike} arr The array to search.
     * @param {Function} 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 first array element that passes the test,
     *     or -1 if no element is found.
     */
    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 {goog.array.ArrayLike} arr The array to search.
     * @param {Function} 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 {*} The last array element that passes the test, or null if no
     *     element is found.
     */
    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 {goog.array.ArrayLike} arr The array to search.
     * @param {Function} 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.
     */
    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} arr Array into which to insert the item.
     * @param {*} obj Value to add.
     */
    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} arr The array to modify.
     * @param {*} obj The object to insert.
     * @param {*=} 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.
     */
    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) {
      // LB: disable asserts
      //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 {goog.array.ArrayLike} arr Array from which to remove value.
     * @param {Function} 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 {boolean} True if an element was removed.
     */
    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);
    };
  
  
    /**
     * 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 = function(arr) {
      if (goog.isArray(arr)) {
        return goog.array.concat(/** @type {!Array} */ (arr));
      } else { // array like
        // Concat does not work with non arrays.
        var rv = [];
        for (var i = 0, len = arr.length; i < len; i++) {
          rv[i] = arr[i];
        }
        return rv;
      }
    };
  
  
    /**
     * 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) {
      if (goog.isArray(object)) {
        // This fixes the JS compiler warning and forces the Object to an Array type
        return goog.array.concat(/** @type {!Array} */ (object));
      }
      // Clone what we hope to be an array-like object to an array.
      // We could check isArrayLike() first, but no check we perform would be as
      // reliable as simply making the call.
      return goog.array.clone(/** @type {Array} */ (object));
    };
  
  
    /**
     * 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) {
      // LB: disable asserts
      //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 {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} A new array containing the specified segment of the original
     *     array.
     */
    goog.array.slice = function(arr, start, opt_end) {
      // LB: disable asserts
      //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} arr The array to be sorted.
     * @param {Function=} 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.
     */
    goog.array.sort = function(arr, opt_compareFn) {
      // TODO(user): Update type annotation since null is not accepted.
      // LB: disable asserts
      //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} arr The array to be sorted.
     * @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.
     */
    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} arr The array.
     * @param {Function=} 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.
     */
    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);
    };
  
  
    /**
     * 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} array The array to modify.
     * @param {*} value The object to insert.
     * @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 inserted.
     */
    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} array The array.
     * @param {Function} 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.
     */
    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;
    };
  
  
    /**
     * 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.<*>} array The array to rotate.
     * @param {number} n The amount to rotate.
     * @return {!Array.<*>} The array.
     */
    goog.array.rotate = function(array, n) {
      // LB: disable asserts
      //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=} 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;
      }
    };
  
    return goog.array;
  });
  