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.
  
  /**
   * @fileoverview Bootstrap for the Google JS Library (Closure).
   *
   * In uncompiled mode base.js will write out Closure's deps file, unless the
   * global <code>CLOSURE_NO_DEPS</code> is set to true.  This allows projects to
   * include their own deps file(s) from different locations.
   *
   */
  
  
  /**
   * @define {boolean} Overridden to true by the compiler when --closure_pass
   *     or --mark_as_compiled is specified.
   */
  var COMPILED = false;
  
  
  /**
   * Base namespace for the Closure library.  Checks to see goog is
   * already defined in the current scope before assigning to prevent
   * clobbering if base.js is loaded more than once.
   *
   * @const
   */
  var goog = goog || {};
  
  
  /**
   * Reference to the global context.  In most cases this will be 'window'.
   */
  goog.global = this;
  
  
  /**
   * @define {boolean} DEBUG is provided as a convenience so that debugging code
   * that should not be included in a production js_binary can be easily stripped
   * by specifying --define goog.DEBUG=false to the JSCompiler. For example, most
   * toString() methods should be declared inside an "if (goog.DEBUG)" conditional
   * because they are generally used for debugging purposes and it is difficult
   * for the JSCompiler to statically determine whether they are used.
   */
  goog.DEBUG = true;
  
  
  /**
   * @define {string} LOCALE defines the locale being used for compilation. It is
   * used to select locale specific data to be compiled in js binary. BUILD rule
   * can specify this value by "--define goog.LOCALE=<locale_name>" as JSCompiler
   * option.
   *
   * Take into account that the locale code format is important. You should use
   * the canonical Unicode format with hyphen as a delimiter. Language must be
   * lowercase, Language Script - Capitalized, Region - UPPERCASE.
   * There are few examples: pt-BR, en, en-US, sr-Latin-BO, zh-Hans-CN.
   *
   * See more info about locale codes here:
   * http://www.unicode.org/reports/tr35/#Unicode_Language_and_Locale_Identifiers
   *
   * For language codes you should use values defined by ISO 693-1. See it here
   * http://www.w3.org/WAI/ER/IG/ert/iso639.htm. There is only one exception from
   * this rule: the Hebrew language. For legacy reasons the old code (iw) should
   * be used instead of the new code (he), see http://wiki/Main/IIISynonyms.
   */
  goog.LOCALE = 'en';  // default to en
  
  
  /**
   * Indicates whether or not we can call 'eval' directly to eval code in the
   * global scope. Set to a Boolean by the first call to goog.globalEval (which
   * empirically tests whether eval works for globals). @see goog.globalEval
   * @type {?boolean}
   * @private
   */
  goog.evalWorksForGlobals_ = null;
  
  
  /**
   * Creates object stubs for a namespace. When present in a file, goog.provide
   * also indicates that the file defines the indicated object. Calls to
   * goog.provide are resolved by the compiler if --closure_pass is set.
   * @param {string} name name of the object that this file defines.
   */
  goog.provide = function(name) {
    if (!COMPILED) {
      // Ensure that the same namespace isn't provided twice. This is intended
      // to teach new developers that 'goog.provide' is effectively a variable
      // declaration. And when JSCompiler transforms goog.provide into a real
      // variable declaration, the compiled JS should work the same as the raw
      // JS--even when the raw JS uses goog.provide incorrectly.
      if (goog.getObjectByName(name) && !goog.implicitNamespaces_[name]) {
        throw Error('Namespace "' + name + '" already declared.');
      }
  
      var namespace = name;
      while ((namespace = namespace.substring(0, namespace.lastIndexOf('.')))) {
        goog.implicitNamespaces_[namespace] = true;
      }
    }
  
    goog.exportPath_(name);
  };
  
  
  /**
   * Marks that the current file should only be used for testing, and never for
   * live code in production.
   * @param {string=} opt_message Optional message to add to the error that's
   *     raised when used in production code.
   */
  goog.setTestOnly = function(opt_message) {
    if (COMPILED && !goog.DEBUG) {
      opt_message = opt_message || '';
      throw Error('Importing test-only code into non-debug environment' +
                  opt_message ? ': ' + opt_message : '.');
    }
  };
  
  
  if (!COMPILED) {
    /**
     * Namespaces implicitly defined by goog.provide. For example,
     * goog.provide('goog.events.Event') implicitly declares
     * that 'goog' and 'goog.events' must be namespaces.
     *
     * @type {Object}
     * @private
     */
    goog.implicitNamespaces_ = {};
  }
  
  
  /**
   * Builds an object structure for the provided namespace path,
   * ensuring that names that already exist are not overwritten. For
   * example:
   * "a.b.c" -> a = {};a.b={};a.b.c={};
   * Used by goog.provide and goog.exportSymbol.
   * @param {string} name name of the object that this file defines.
   * @param {*=} opt_object the object to expose at the end of the path.
   * @param {Object=} opt_objectToExportTo The object to add the path to; default
   *     is |goog.global|.
   * @private
   */
  goog.exportPath_ = function(name, opt_object, opt_objectToExportTo) {
    var parts = name.split('.');
    var cur = opt_objectToExportTo || goog.global;
  
    // Internet Explorer exhibits strange behavior when throwing errors from
    // methods externed in this manner.  See the testExportSymbolExceptions in
    // base_test.html for an example.
    if (!(parts[0] in cur) && cur.execScript) {
      cur.execScript('var ' + parts[0]);
    }
  
    // Certain browsers cannot parse code in the form for((a in b); c;);
    // This pattern is produced by the JSCompiler when it collapses the
    // statement above into the conditional loop below. To prevent this from
    // happening, use a for-loop and reserve the init logic as below.
  
    // Parentheses added to eliminate strict JS warning in Firefox.
    for (var part; parts.length && (part = parts.shift());) {
      if (!parts.length && goog.isDef(opt_object)) {
        // last part and we have an object; use it
        cur[part] = opt_object;
      } else if (cur[part]) {
        cur = cur[part];
      } else {
        cur = cur[part] = {};
      }
    }
  };
  
  
  /**
   * Returns an object based on its fully qualified external name.  If you are
   * using a compilation pass that renames property names beware that using this
   * function will not find renamed properties.
   *
   * @param {string} name The fully qualified name.
   * @param {Object=} opt_obj The object within which to look; default is
   *     |goog.global|.
   * @return {Object} The object or, if not found, null.
   */
  goog.getObjectByName = function(name, opt_obj) {
    var parts = name.split('.');
    var cur = opt_obj || goog.global;
    for (var part; part = parts.shift(); ) {
      if (goog.isDefAndNotNull(cur[part])) {
        cur = cur[part];
      } else {
        return null;
      }
    }
    return cur;
  };
  
  
  /**
   * Globalizes a whole namespace, such as goog or goog.lang.
   *
   * @param {Object} obj The namespace to globalize.
   * @param {Object=} opt_global The object to add the properties to.
   * @deprecated Properties may be explicitly exported to the global scope, but
   *     this should no longer be done in bulk.
   */
  goog.globalize = function(obj, opt_global) {
    var global = opt_global || goog.global;
    for (var x in obj) {
      global[x] = obj[x];
    }
  };
  
  
  /**
   * Adds a dependency from a file to the files it requires.
   * @param {string} relPath The path to the js file.
   * @param {Array} provides An array of strings with the names of the objects
   *                         this file provides.
   * @param {Array} requires An array of strings with the names of the objects
   *                         this file requires.
   */
  goog.addDependency = function(relPath, provides, requires) {
    if (!COMPILED) {
      var provide, require;
      var path = relPath.replace(/\\/g, '/');
      var deps = goog.dependencies_;
      for (var i = 0; provide = provides[i]; i++) {
        deps.nameToPath[provide] = path;
        if (!(path in deps.pathToNames)) {
          deps.pathToNames[path] = {};
        }
        deps.pathToNames[path][provide] = true;
      }
      for (var j = 0; require = requires[j]; j++) {
        if (!(path in deps.requires)) {
          deps.requires[path] = {};
        }
        deps.requires[path][require] = true;
      }
    }
  };
  
  
  /**
   * Implements a system for the dynamic resolution of dependencies
   * that works in parallel with the BUILD system. Note that all calls
   * to goog.require will be stripped by the JSCompiler when the
   * --closure_pass option is used.
   * @param {string} rule Rule to include, in the form goog.package.part.
   */
  goog.require = function(rule) {
  
    // if the object already exists we do not need do do anything
    // TODO(user): If we start to support require based on file name this has
    //            to change
    // TODO(user): If we allow goog.foo.* this has to change
    // TODO(user): If we implement dynamic load after page load we should probably
    //            not remove this code for the compiled output
    if (!COMPILED) {
      if (goog.getObjectByName(rule)) {
        return;
      }
      var path = goog.getPathFromDeps_(rule);
      if (path) {
        goog.included_[path] = true;
        goog.writeScripts_();
      } else {
        var errorMessage = 'goog.require could not find: ' + rule;
        if (goog.global.console) {
          goog.global.console['error'](errorMessage);
        }
  
          throw Error(errorMessage);
      }
    }
  };
  
  
  /**
   * Path for included scripts
   * @type {string}
   */
  goog.basePath = '';
  
  
  /**
   * A hook for overriding the base path.
   * @type {string|undefined}
   */
  goog.global.CLOSURE_BASE_PATH;
  
  
  /**
   * Whether to write out Closure's deps file. By default,
   * the deps are written.
   * @type {boolean|undefined}
   */
  goog.global.CLOSURE_NO_DEPS;
  
  
  /**
   * A function to import a single script. This is meant to be overridden when
   * Closure is being run in non-HTML contexts, such as web workers. It's defined
   * in the global scope so that it can be set before base.js is loaded, which
   * allows deps.js to be imported properly.
   *
   * The function is passed the script source, which is a relative URI. It should
   * return true if the script was imported, false otherwise.
   */
  goog.global.CLOSURE_IMPORT_SCRIPT;
  
  
  /**
   * Null function used for default values of callbacks, etc.
   * @return {void} Nothing.
   */
  goog.nullFunction = function() {};
  
  
  /**
   * The identity function. Returns its first argument.
   *
   * @param {...*} var_args The arguments of the function.
   * @return {*} The first argument.
   * @deprecated Use goog.functions.identity instead.
   */
  goog.identityFunction = function(var_args) {
    return arguments[0];
  };
  
  
  /**
   * When defining a class Foo with an abstract method bar(), you can do:
   *
   * Foo.prototype.bar = goog.abstractMethod
   *
   * Now if a subclass of Foo fails to override bar(), an error
   * will be thrown when bar() is invoked.
   *
   * Note: This does not take the name of the function to override as
   * an argument because that would make it more difficult to obfuscate
   * our JavaScript code.
   *
   * @type {!Function}
   * @throws {Error} when invoked to indicate the method should be
   *   overridden.
   */
  goog.abstractMethod = function() {
    throw Error('unimplemented abstract method');
  };
  
  
  /**
   * Adds a {@code getInstance} static method that always return the same instance
   * object.
   * @param {!Function} ctor The constructor for the class to add the static
   *     method to.
   */
  goog.addSingletonGetter = function(ctor) {
    ctor.getInstance = function() {
      return ctor.instance_ || (ctor.instance_ = new ctor());
    };
  };
  
  
  if (!COMPILED) {
    /**
     * Object used to keep track of urls that have already been added. This
     * record allows the prevention of circular dependencies.
     * @type {Object}
     * @private
     */
    goog.included_ = {};
  
  
    /**
     * This object is used to keep track of dependencies and other data that is
     * used for loading scripts
     * @private
     * @type {Object}
     */
    goog.dependencies_ = {
      pathToNames: {}, // 1 to many
      nameToPath: {}, // 1 to 1
      requires: {}, // 1 to many
      // used when resolving dependencies to prevent us from
      // visiting the file twice
      visited: {},
      written: {} // used to keep track of script files we have written
    };
  
  
    /**
     * Tries to detect whether is in the context of an HTML document.
     * @return {boolean} True if it looks like HTML document.
     * @private
     */
    goog.inHtmlDocument_ = function() {
      var doc = goog.global.document;
      return typeof doc != 'undefined' &&
             'write' in doc;  // XULDocument misses write.
    };
  
  
    /**
     * Tries to detect the base path of the base.js script that bootstraps Closure
     * @private
     */
    goog.findBasePath_ = function() {
      if (goog.global.CLOSURE_BASE_PATH) {
        goog.basePath = goog.global.CLOSURE_BASE_PATH;
        return;
      } else if (!goog.inHtmlDocument_()) {
        return;
      }
      var doc = goog.global.document;
      var scripts = doc.getElementsByTagName('script');
      // Search backwards since the current script is in almost all cases the one
      // that has base.js.
      for (var i = scripts.length - 1; i >= 0; --i) {
        var src = scripts[i].src;
        var qmark = src.lastIndexOf('?');
        var l = qmark == -1 ? src.length : qmark;
        if (src.substr(l - 7, 7) == 'base.js') {
          goog.basePath = src.substr(0, l - 7);
          return;
        }
      }
    };
  
  
    /**
     * Imports a script if, and only if, that script hasn't already been imported.
     * (Must be called at execution time)
     * @param {string} src Script source.
     * @private
     */
    goog.importScript_ = function(src) {
      var importScript = goog.global.CLOSURE_IMPORT_SCRIPT ||
          goog.writeScriptTag_;
      if (!goog.dependencies_.written[src] && importScript(src)) {
        goog.dependencies_.written[src] = true;
      }
    };
  
  
    /**
     * The default implementation of the import function. Writes a script tag to
     * import the script.
     *
     * @param {string} src The script source.
     * @return {boolean} True if the script was imported, false otherwise.
     * @private
     */
    goog.writeScriptTag_ = function(src) {
      if (goog.inHtmlDocument_()) {
        var doc = goog.global.document;
        doc.write(
            '<script type="text/javascript" src="' + src + '"></' + 'script>');
        return true;
      } else {
        return false;
      }
    };
  
  
    /**
     * Resolves dependencies based on the dependencies added using addDependency
     * and calls importScript_ in the correct order.
     * @private
     */
    goog.writeScripts_ = function() {
      // the scripts we need to write this time
      var scripts = [];
      var seenScript = {};
      var deps = goog.dependencies_;
  
      function visitNode(path) {
        if (path in deps.written) {
          return;
        }
  
        // we have already visited this one. We can get here if we have cyclic
        // dependencies
        if (path in deps.visited) {
          if (!(path in seenScript)) {
            seenScript[path] = true;
            scripts.push(path);
          }
          return;
        }
  
        deps.visited[path] = true;
  
        if (path in deps.requires) {
          for (var requireName in deps.requires[path]) {
            if (requireName in deps.nameToPath) {
              visitNode(deps.nameToPath[requireName]);
            } else if (!goog.getObjectByName(requireName)) {
              // If the required name is defined, we assume that this
              // dependency was bootstapped by other means. Otherwise,
              // throw an exception.
              throw Error('Undefined nameToPath for ' + requireName);
            }
          }
        }
  
        if (!(path in seenScript)) {
          seenScript[path] = true;
          scripts.push(path);
        }
      }
  
      for (var path in goog.included_) {
        if (!deps.written[path]) {
          visitNode(path);
        }
      }
  
      for (var i = 0; i < scripts.length; i++) {
        if (scripts[i]) {
          goog.importScript_(goog.basePath + scripts[i]);
        } else {
          throw Error('Undefined script input');
        }
      }
    };
  
  
    /**
     * Looks at the dependency rules and tries to determine the script file that
     * fulfills a particular rule.
     * @param {string} rule In the form goog.namespace.Class or project.script.
     * @return {?string} Url corresponding to the rule, or null.
     * @private
     */
    goog.getPathFromDeps_ = function(rule) {
      if (rule in goog.dependencies_.nameToPath) {
        return goog.dependencies_.nameToPath[rule];
      } else {
        return null;
      }
    };
  
    goog.findBasePath_();
  
    // Allow projects to manage the deps files themselves.
    if (!goog.global.CLOSURE_NO_DEPS) {
      goog.importScript_(goog.basePath + 'deps.js');
    }
  }
  
  
  
  //==============================================================================
  // Language Enhancements
  //==============================================================================
  
  
  /**
   * This is a "fixed" version of the typeof operator.  It differs from the typeof
   * operator in such a way that null returns 'null' and arrays return 'array'.
   * @param {*} value The value to get the type of.
   * @return {string} The name of the type.
   */
  goog.typeOf = function(value) {
    var s = typeof value;
    if (s == 'object') {
      if (value) {
        // Check these first, so we can avoid calling Object.prototype.toString if
        // possible.
        //
        // IE improperly marshals tyepof across execution contexts, but a
        // cross-context object will still return false for "instanceof Object".
        if (value instanceof Array) {
          return 'array';
        } else if (value instanceof Object) {
          return s;
        }
  
        // HACK: In order to use an Object prototype method on the arbitrary
        //   value, the compiler requires the value be cast to type Object,
        //   even though the ECMA spec explicitly allows it.
        var className = Object.prototype.toString.call(
            /** @type {Object} */ (value));
        // In Firefox 3.6, attempting to access iframe window objects' length
        // property throws an NS_ERROR_FAILURE, so we need to special-case it
        // here.
        if (className == '[object Window]') {
          return 'object';
        }
  
        // We cannot always use constructor == Array or instanceof Array because
        // different frames have different Array objects. In IE6, if the iframe
        // where the array was created is destroyed, the array loses its
        // prototype. Then dereferencing val.splice here throws an exception, so
        // we can't use goog.isFunction. Calling typeof directly returns 'unknown'
        // so that will work. In this case, this function will return false and
        // most array functions will still work because the array is still
        // array-like (supports length and []) even though it has lost its
        // prototype.
        // Mark Miller noticed that Object.prototype.toString
        // allows access to the unforgeable [[Class]] property.
        //  15.2.4.2 Object.prototype.toString ( )
        //  When the toString method is called, the following steps are taken:
        //      1. Get the [[Class]] property of this object.
        //      2. Compute a string value by concatenating the three strings
        //         "[object ", Result(1), and "]".
        //      3. Return Result(2).
        // and this behavior survives the destruction of the execution context.
        if ((className == '[object Array]' ||
             // In IE all non value types are wrapped as objects across window
             // boundaries (not iframe though) so we have to do object detection
             // for this edge case
             typeof value.length == 'number' &&
             typeof value.splice != 'undefined' &&
             typeof value.propertyIsEnumerable != 'undefined' &&
             !value.propertyIsEnumerable('splice')
  
            )) {
          return 'array';
        }
        // HACK: There is still an array case that fails.
        //     function ArrayImpostor() {}
        //     ArrayImpostor.prototype = [];
        //     var impostor = new ArrayImpostor;
        // this can be fixed by getting rid of the fast path
        // (value instanceof Array) and solely relying on
        // (value && Object.prototype.toString.vall(value) === '[object Array]')
        // but that would require many more function calls and is not warranted
        // unless closure code is receiving objects from untrusted sources.
  
        // IE in cross-window calls does not correctly marshal the function type
        // (it appears just as an object) so we cannot use just typeof val ==
        // 'function'. However, if the object has a call property, it is a
        // function.
        if ((className == '[object Function]' ||
            typeof value.call != 'undefined' &&
            typeof value.propertyIsEnumerable != 'undefined' &&
            !value.propertyIsEnumerable('call'))) {
          return 'function';
        }
  
  
      } else {
        return 'null';
      }
  
    } else if (s == 'function' && typeof value.call == 'undefined') {
      // In Safari typeof nodeList returns 'function', and on Firefox
      // typeof behaves similarly for HTML{Applet,Embed,Object}Elements
      // and RegExps.  We would like to return object for those and we can
      // detect an invalid function by making sure that the function
      // object has a call method.
      return 'object';
    }
    return s;
  };
  
  
  /**
   * Safe way to test whether a property is enumarable.  It allows testing
   * for enumerable on objects where 'propertyIsEnumerable' is overridden or
   * does not exist (like DOM nodes in IE). Does not use browser native
   * Object.propertyIsEnumerable.
   * @param {Object} object The object to test if the property is enumerable.
   * @param {string} propName The property name to check for.
   * @return {boolean} True if the property is enumarable.
   * @private
   */
  goog.propertyIsEnumerableCustom_ = function(object, propName) {
    // KJS in Safari 2 is not ECMAScript compatible and lacks crucial methods
    // such as propertyIsEnumerable.  We therefore use a workaround.
    // Does anyone know a more efficient work around?
    if (propName in object) {
      for (var key in object) {
        if (key == propName &&
            Object.prototype.hasOwnProperty.call(object, propName)) {
          return true;
        }
      }
    }
    return false;
  };
  
  
  /**
   * Safe way to test whether a property is enumarable.  It allows testing
   * for enumerable on objects where 'propertyIsEnumerable' is overridden or
   * does not exist (like DOM nodes in IE).
   * @param {Object} object The object to test if the property is enumerable.
   * @param {string} propName The property name to check for.
   * @return {boolean} True if the property is enumarable.
   * @private
   */
  goog.propertyIsEnumerable_ = function(object, propName) {
    // In IE if object is from another window, cannot use propertyIsEnumerable
    // from this window's Object. Will raise a 'JScript object expected' error.
    if (object instanceof Object) {
      return Object.prototype.propertyIsEnumerable.call(object, propName);
    } else {
      return goog.propertyIsEnumerableCustom_(object, propName);
    }
  };
  
  
  /**
   * Returns true if the specified value is not |undefined|.
   * WARNING: Do not use this to test if an object has a property. Use the in
   * operator instead.  Additionally, this function assumes that the global
   * undefined variable has not been redefined.
   * @param {*} val Variable to test.
   * @return {boolean} Whether variable is defined.
   */
  goog.isDef = function(val) {
    return val !== undefined;
  };
  
  
  /**
   * Returns true if the specified value is |null|
   * @param {*} val Variable to test.
   * @return {boolean} Whether variable is null.
   */
  goog.isNull = function(val) {
    return val === null;
  };
  
  
  /**
   * Returns true if the specified value is defined and not null
   * @param {*} val Variable to test.
   * @return {boolean} Whether variable is defined and not null.
   */
  goog.isDefAndNotNull = function(val) {
    // Note that undefined == null.
    return val != null;
  };
  
  
  /**
   * Returns true if the specified value is an array
   * @param {*} val Variable to test.
   * @return {boolean} Whether variable is an array.
   */
  goog.isArray = function(val) {
    return goog.typeOf(val) == 'array';
  };
  
  
  /**
   * Returns true if the object looks like an array. To qualify as array like
   * the value needs to be either a NodeList or an object with a Number length
   * property.
   * @param {*} val Variable to test.
   * @return {boolean} Whether variable is an array.
   */
  goog.isArrayLike = function(val) {
    var type = goog.typeOf(val);
    return type == 'array' || type == 'object' && typeof val.length == 'number';
  };
  
  
  /**
   * Returns true if the object looks like a Date. To qualify as Date-like
   * the value needs to be an object and have a getFullYear() function.
   * @param {*} val Variable to test.
   * @return {boolean} Whether variable is a like a Date.
   */
  goog.isDateLike = function(val) {
    return goog.isObject(val) && typeof val.getFullYear == 'function';
  };
  
  
  /**
   * Returns true if the specified value is a string
   * @param {*} val Variable to test.
   * @return {boolean} Whether variable is a string.
   */
  goog.isString = function(val) {
    return typeof val == 'string';
  };
  
  
  /**
   * Returns true if the specified value is a boolean
   * @param {*} val Variable to test.
   * @return {boolean} Whether variable is boolean.
   */
  goog.isBoolean = function(val) {
    return typeof val == 'boolean';
  };
  
  
  /**
   * Returns true if the specified value is a number
   * @param {*} val Variable to test.
   * @return {boolean} Whether variable is a number.
   */
  goog.isNumber = function(val) {
    return typeof val == 'number';
  };
  
  
  /**
   * Returns true if the specified value is a function
   * @param {*} val Variable to test.
   * @return {boolean} Whether variable is a function.
   */
  goog.isFunction = function(val) {
    return goog.typeOf(val) == 'function';
  };
  
  
  /**
   * Returns true if the specified value is an object.  This includes arrays
   * and functions.
   * @param {*} val Variable to test.
   * @return {boolean} Whether variable is an object.
   */
  goog.isObject = function(val) {
    var type = goog.typeOf(val);
    return type == 'object' || type == 'array' || type == 'function';
  };
  
  
  /**
   * Gets a unique ID for an object. This mutates the object so that further
   * calls with the same object as a parameter returns the same value. The unique
   * ID is guaranteed to be unique across the current session amongst objects that
   * are passed into {@code getUid}. There is no guarantee that the ID is unique
   * or consistent across sessions. It is unsafe to generate unique ID for
   * function prototypes.
   *
   * @param {Object} obj The object to get the unique ID for.
   * @return {number} The unique ID for the object.
   */
  goog.getUid = function(obj) {
    // TODO(user): Make the type stricter, do not accept null.
  
    // In Opera window.hasOwnProperty exists but always returns false so we avoid
    // using it. As a consequence the unique ID generated for BaseClass.prototype
    // and SubClass.prototype will be the same.
    return obj[goog.UID_PROPERTY_] ||
        (obj[goog.UID_PROPERTY_] = ++goog.uidCounter_);
  };
  
  
  /**
   * Removes the unique ID from an object. This is useful if the object was
   * previously mutated using {@code goog.getUid} in which case the mutation is
   * undone.
   * @param {Object} obj The object to remove the unique ID field from.
   */
  goog.removeUid = function(obj) {
    // TODO(user): Make the type stricter, do not accept null.
  
    // DOM nodes in IE are not instance of Object and throws exception
    // for delete. Instead we try to use removeAttribute
    if ('removeAttribute' in obj) {
      obj.removeAttribute(goog.UID_PROPERTY_);
    }
    /** @preserveTry */
    try {
      delete obj[goog.UID_PROPERTY_];
    } catch (ex) {
    }
  };
  
  
  /**
   * Name for unique ID property. Initialized in a way to help avoid collisions
   * with other closure javascript on the same page.
   * @type {string}
   * @private
   */
  goog.UID_PROPERTY_ = 'closure_uid_' +
      Math.floor(Math.random() * 2147483648).toString(36);
  
  
  /**
   * Counter for UID.
   * @type {number}
   * @private
   */
  goog.uidCounter_ = 0;
  
  
  /**
   * Adds a hash code field to an object. The hash code is unique for the
   * given object.
   * @param {Object} obj The object to get the hash code for.
   * @return {number} The hash code for the object.
   * @deprecated Use goog.getUid instead.
   */
  goog.getHashCode = goog.getUid;
  
  
  /**
   * Removes the hash code field from an object.
   * @param {Object} obj The object to remove the field from.
   * @deprecated Use goog.removeUid instead.
   */
  goog.removeHashCode = goog.removeUid;
  
  
  /**
   * Clones a value. The input may be an Object, Array, or basic type. Objects and
   * arrays will be cloned recursively.
   *
   * WARNINGS:
   * <code>goog.cloneObject</code> does not detect reference loops. Objects that
   * refer to themselves will cause infinite recursion.
   *
   * <code>goog.cloneObject</code> is unaware of unique identifiers, and copies
   * UIDs created by <code>getUid</code> into cloned results.
   *
   * @param {*} obj The value to clone.
   * @return {*} A clone of the input value.
   * @deprecated goog.cloneObject is unsafe. Prefer the goog.object methods.
   */
  goog.cloneObject = function(obj) {
    var type = goog.typeOf(obj);
    if (type == 'object' || type == 'array') {
      if (obj.clone) {
        return obj.clone();
      }
      var clone = type == 'array' ? [] : {};
      for (var key in obj) {
        clone[key] = goog.cloneObject(obj[key]);
      }
      return clone;
    }
  
    return obj;
  };
  
  
  /**
   * Forward declaration for the clone method. This is necessary until the
   * compiler can better support duck-typing constructs as used in
   * goog.cloneObject.
   *
   * TODO(user): Remove once the JSCompiler can infer that the check for
   * proto.clone is safe in goog.cloneObject.
   *
   * @type {Function}
   */
  Object.prototype.clone;
  
  
  /**
   * A native implementation of goog.bind.
   * @param {Function} fn A function to partially apply.
   * @param {Object|undefined} selfObj Specifies the object which |this| should
   *     point to when the function is run. If the value is null or undefined, it
   *     will default to the global object.
   * @param {...*} var_args Additional arguments that are partially
   *     applied to the function.
   * @return {!Function} A partially-applied form of the function bind() was
   *     invoked as a method of.
   * @private
   * @suppress {deprecated} The compiler thinks that Function.prototype.bind
   *     is deprecated because some people have declared a pure-JS version.
   *     Only the pure-JS version is truly deprecated.
   */
  goog.bindNative_ = function(fn, selfObj, var_args) {
    return /** @type {!Function} */ (fn.call.apply(fn.bind, arguments));
  };
  
  
  /**
   * A pure-JS implementation of goog.bind.
   * @param {Function} fn A function to partially apply.
   * @param {Object|undefined} selfObj Specifies the object which |this| should
   *     point to when the function is run. If the value is null or undefined, it
   *     will default to the global object.
   * @param {...*} var_args Additional arguments that are partially
   *     applied to the function.
   * @return {!Function} A partially-applied form of the function bind() was
   *     invoked as a method of.
   * @private
   */
  goog.bindJs_ = function(fn, selfObj, var_args) {
    var context = selfObj || goog.global;
  
    if (arguments.length > 2) {
      var boundArgs = Array.prototype.slice.call(arguments, 2);
      return function() {
        // Prepend the bound arguments to the current arguments.
        var newArgs = Array.prototype.slice.call(arguments);
        Array.prototype.unshift.apply(newArgs, boundArgs);
        return fn.apply(context, newArgs);
      };
  
    } else {
      return function() {
        return fn.apply(context, arguments);
      };
    }
  };
  
  
  /**
   * Partially applies this function to a particular 'this object' and zero or
   * more arguments. The result is a new function with some arguments of the first
   * function pre-filled and the value of |this| 'pre-specified'.<br><br>
   *
   * Remaining arguments specified at call-time are appended to the pre-
   * specified ones.<br><br>
   *
   * Also see: {@link #partial}.<br><br>
   *
   * Usage:
   * <pre>var barMethBound = bind(myFunction, myObj, 'arg1', 'arg2');
   * barMethBound('arg3', 'arg4');</pre>
   *
   * @param {Function} fn A function to partially apply.
   * @param {Object|undefined} selfObj Specifies the object which |this| should
   *     point to when the function is run. If the value is null or undefined, it
   *     will default to the global object.
   * @param {...*} var_args Additional arguments that are partially
   *     applied to the function.
   * @return {!Function} A partially-applied form of the function bind() was
   *     invoked as a method of.
   * @suppress {deprecated} See above.
   */
  goog.bind = function(fn, selfObj, var_args) {
    // TODO(nicksantos): narrow the type signature.
    if (Function.prototype.bind &&
        // NOTE(nicksantos): Somebody pulled base.js into the default
        // Chrome extension environment. This means that for Chrome extensions,
        // they get the implementation of Function.prototype.bind that
        // calls goog.bind instead of the native one. Even worse, we don't want
        // to introduce a circular dependency between goog.bind and
        // Function.prototype.bind, so we have to hack this to make sure it
        // works correctly.
        Function.prototype.bind.toString().indexOf('native code') != -1) {
      goog.bind = goog.bindNative_;
    } else {
      goog.bind = goog.bindJs_;
    }
    return goog.bind.apply(null, arguments);
  };
  
  
  /**
   * Like bind(), except that a 'this object' is not required. Useful when the
   * target function is already bound.
   *
   * Usage:
   * var g = partial(f, arg1, arg2);
   * g(arg3, arg4);
   *
   * @param {Function} fn A function to partially apply.
   * @param {...*} var_args Additional arguments that are partially
   *     applied to fn.
   * @return {!Function} A partially-applied form of the function bind() was
   *     invoked as a method of.
   */
  goog.partial = function(fn, var_args) {
    var args = Array.prototype.slice.call(arguments, 1);
    return function() {
      // Prepend the bound arguments to the current arguments.
      var newArgs = Array.prototype.slice.call(arguments);
      newArgs.unshift.apply(newArgs, args);
      return fn.apply(this, newArgs);
    };
  };
  
  
  /**
   * Copies all the members of a source object to a target object. This method
   * does not work on all browsers for all objects that contain keys such as
   * toString or hasOwnProperty. Use goog.object.extend for this purpose.
   * @param {Object} target Target.
   * @param {Object} source Source.
   */
  goog.mixin = function(target, source) {
    for (var x in source) {
      target[x] = source[x];
    }
  
    // For IE7 or lower, the for-in-loop does not contain any properties that are
    // not enumerable on the prototype object (for example, isPrototypeOf from
    // Object.prototype) but also it will not include 'replace' on objects that
    // extend String and change 'replace' (not that it is common for anyone to
    // extend anything except Object).
  };
  
  
  /**
   * @return {number} An integer value representing the number of milliseconds
   *     between midnight, January 1, 1970 and the current time.
   */
  goog.now = Date.now || (function() {
    // Unary plus operator converts its operand to a number which in the case of
    // a date is done by calling getTime().
    return +new Date();
  });
  
  
  /**
   * Evals javascript in the global scope.  In IE this uses execScript, other
   * browsers use goog.global.eval. If goog.global.eval does not evaluate in the
   * global scope (for example, in Safari), appends a script tag instead.
   * Throws an exception if neither execScript or eval is defined.
   * @param {string} script JavaScript string.
   */
  goog.globalEval = function(script) {
    if (goog.global.execScript) {
      goog.global.execScript(script, 'JavaScript');
    } else if (goog.global.eval) {
      // Test to see if eval works
      if (goog.evalWorksForGlobals_ == null) {
        goog.global.eval('var _et_ = 1;');
        if (typeof goog.global['_et_'] != 'undefined') {
          delete goog.global['_et_'];
          goog.evalWorksForGlobals_ = true;
        } else {
          goog.evalWorksForGlobals_ = false;
        }
      }
  
      if (goog.evalWorksForGlobals_) {
        goog.global.eval(script);
      } else {
        var doc = goog.global.document;
        var scriptElt = doc.createElement('script');
        scriptElt.type = 'text/javascript';
        scriptElt.defer = false;
        // Note(user): can't use .innerHTML since "t('<test>')" will fail and
        // .text doesn't work in Safari 2.  Therefore we append a text node.
        scriptElt.appendChild(doc.createTextNode(script));
        doc.body.appendChild(scriptElt);
        doc.body.removeChild(scriptElt);
      }
    } else {
      throw Error('goog.globalEval not available');
    }
  };
  
  
  /**
   * A macro for defining composite types.
   *
   * By assigning goog.typedef to a name, this tells JSCompiler that this is not
   * the name of a class, but rather it's the name of a composite type.
   *
   * For example,
   * /** @type {Array|NodeList} / goog.ArrayLike = goog.typedef;
   * will tell JSCompiler to replace all appearances of goog.ArrayLike in type
   * definitions with the union of Array and NodeList.
   *
   * Does nothing in uncompiled code.
   *
   * @deprecated Please use the {@code @typedef} annotation.
   */
  goog.typedef = true;
  
  
  /**
   * Optional map of CSS class names to obfuscated names used with
   * goog.getCssName().
   * @type {Object|undefined}
   * @private
   * @see goog.setCssNameMapping
   */
  goog.cssNameMapping_;
  
  
  /**
   * Optional obfuscation style for CSS class names. Should be set to either
   * 'BY_WHOLE' or 'BY_PART' if defined.
   * @type {string|undefined}
   * @private
   * @see goog.setCssNameMapping
   */
  goog.cssNameMappingStyle_;
  
  
  /**
   * Handles strings that are intended to be used as CSS class names.
   *
   * This function works in tandem with @see goog.setCssNameMapping.
   *
   * Without any mapping set, the arguments are simple joined with a
   * hyphen and passed through unaltered.
   *
   * When there is a mapping, there are two possible styles in which
   * these mappings are used. In the BY_PART style, each part (i.e. in
   * between hyphens) of the passed in css name is rewritten according
   * to the map. In the BY_WHOLE style, the full css name is looked up in
   * the map directly. If a rewrite is not specified by the map, the
   * compiler will output a warning.
   *
   * When the mapping is passed to the compiler, it will replace calls
   * to goog.getCssName with the strings from the mapping, e.g.
   *     var x = goog.getCssName('foo');
   *     var y = goog.getCssName(this.baseClass, 'active');
   *  becomes:
   *     var x= 'foo';
   *     var y = this.baseClass + '-active';
   *
   * If one argument is passed it will be processed, if two are passed
   * only the modifier will be processed, as it is assumed the first
   * argument was generated as a result of calling goog.getCssName.
   *
   * @param {string} className The class name.
   * @param {string=} opt_modifier A modifier to be appended to the class name.
   * @return {string} The class name or the concatenation of the class name and
   *     the modifier.
   */
  goog.getCssName = function(className, opt_modifier) {
    var getMapping = function(cssName) {
      return goog.cssNameMapping_[cssName];
    };
  
    var renameByParts = function(cssName) {
      // Remap all the parts individually.
      var parts = cssName.split('-');
      var mapped = [];
      for (var i = 0; i < parts.length; i++) {
        var mapping = getMapping(parts[i]);
        if (!mapping) {
          // If any of the parts fail to match,
          // just return the whole string unmodified.
          // The compiler will emit a warning about this.
          return cssName;
        }
        mapped.push(mapping);
      }
      return mapped.join('-');
    };
  
    var renameByWhole = function(cssName) {
      return getMapping(cssName) || cssName;
    };
  
    var rename;
    if (goog.cssNameMapping_) {
      rename = goog.cssNameMappingStyle_ == 'BY_WHOLE' ?
          renameByWhole : renameByParts;
    } else {
      rename = function(a) {
        return a;
      };
    }
  
    if (opt_modifier) {
      return className + '-' + rename(opt_modifier);
    } else {
      return rename(className);
    }
  };
  
  
  /**
   * Sets the map to check when returning a value from goog.getCssName(). Example:
   * <pre>
   * goog.setCssNameMapping({
   *   "goog": "a",
   *   "disabled": "b",
   * });
   *
   * var x = goog.getCssName('goog');
   * // The following evaluates to: "a a-b".
   * goog.getCssName('goog') + ' ' + goog.getCssName(x, 'disabled')
   * </pre>
   * When declared as a map of string literals to string literals, the JSCompiler
   * will replace all calls to goog.getCssName() using the supplied map if the
   * --closure_pass flag is set.
   *
   * @param {!Object} mapping A map of strings to strings where keys are possible
   *     arguments to goog.getCssName() and values are the corresponding values
   *     that should be returned.
   * @param {string=} style The style of css name mapping. There are two valid
   *     options: 'BY_PART', and 'BY_WHOLE'.
   * @see goog.getCssName for a description.
   */
  goog.setCssNameMapping = function(mapping, style) {
    goog.cssNameMapping_ = mapping;
    goog.cssNameMappingStyle_ = style;
  };
  
  
  /**
   * Abstract implementation of goog.getMsg for use with localized messages.
   * @param {string} str Translatable string, places holders in the form {$foo}.
   * @param {Object=} opt_values Map of place holder name to value.
   * @return {string} message with placeholders filled.
   */
  goog.getMsg = function(str, opt_values) {
    var values = opt_values || {};
    for (var key in values) {
      var value = ('' + values[key]).replace(/\$/g, '$$$$');
      str = str.replace(new RegExp('\\{\\$' + key + '\\}', 'gi'), value);
    }
    return str;
  };
  
  
  /**
   * Exposes an unobfuscated global namespace path for the given object.
   * Note that fields of the exported object *will* be obfuscated,
   * unless they are exported in turn via this function or
   * goog.exportProperty
   *
   * <p>Also handy for making public items that are defined in anonymous
   * closures.
   *
   * ex. goog.exportSymbol('Foo', Foo);
   *
   * ex. goog.exportSymbol('public.path.Foo.staticFunction',
   *                       Foo.staticFunction);
   *     public.path.Foo.staticFunction();
   *
   * ex. goog.exportSymbol('public.path.Foo.prototype.myMethod',
   *                       Foo.prototype.myMethod);
   *     new public.path.Foo().myMethod();
   *
   * @param {string} publicPath Unobfuscated name to export.
   * @param {*} object Object the name should point to.
   * @param {Object=} opt_objectToExportTo The object to add the path to; default
   *     is |goog.global|.
   */
  goog.exportSymbol = function(publicPath, object, opt_objectToExportTo) {
    goog.exportPath_(publicPath, object, opt_objectToExportTo);
  };
  
  
  /**
   * Exports a property unobfuscated into the object's namespace.
   * ex. goog.exportProperty(Foo, 'staticFunction', Foo.staticFunction);
   * ex. goog.exportProperty(Foo.prototype, 'myMethod', Foo.prototype.myMethod);
   * @param {Object} object Object whose static property is being exported.
   * @param {string} publicName Unobfuscated name to export.
   * @param {*} symbol Object the name should point to.
   */
  goog.exportProperty = function(object, publicName, symbol) {
    object[publicName] = symbol;
  };
  
  
  /**
   * Inherit the prototype methods from one constructor into another.
   *
   * Usage:
   * <pre>
   * function ParentClass(a, b) { }
   * ParentClass.prototype.foo = function(a) { }
   *
   * function ChildClass(a, b, c) {
   *   ParentClass.call(this, a, b);
   * }
   *
   * goog.inherits(ChildClass, ParentClass);
   *
   * var child = new ChildClass('a', 'b', 'see');
   * child.foo(); // works
   * </pre>
   *
   * In addition, a superclass' implementation of a method can be invoked
   * as follows:
   *
   * <pre>
   * ChildClass.prototype.foo = function(a) {
   *   ChildClass.superClass_.foo.call(this, a);
   *   // other code
   * };
   * </pre>
   *
   * @param {Function} childCtor Child class.
   * @param {Function} parentCtor Parent class.
   */
  goog.inherits = function(childCtor, parentCtor) {
    /** @constructor */
    function tempCtor() {};
    tempCtor.prototype = parentCtor.prototype;
    childCtor.superClass_ = parentCtor.prototype;
    childCtor.prototype = new tempCtor();
    childCtor.prototype.constructor = childCtor;
  };
  
  
  /**
   * Call up to the superclass.
   *
   * If this is called from a constructor, then this calls the superclass
   * contructor with arguments 1-N.
   *
   * If this is called from a prototype method, then you must pass
   * the name of the method as the second argument to this function. If
   * you do not, you will get a runtime error. This calls the superclass'
   * method with arguments 2-N.
   *
   * This function only works if you use goog.inherits to express
   * inheritance relationships between your classes.
   *
   * This function is a compiler primitive. At compile-time, the
   * compiler will do macro expansion to remove a lot of
   * the extra overhead that this function introduces. The compiler
   * will also enforce a lot of the assumptions that this function
   * makes, and treat it as a compiler error if you break them.
   *
   * @param {!Object} me Should always be "this".
   * @param {*=} opt_methodName The method name if calling a super method.
   * @param {...*} var_args The rest of the arguments.
   * @return {*} The return value of the superclass method.
   */
  goog.base = function(me, opt_methodName, var_args) {
    var caller = arguments.callee.caller;
    if (caller.superClass_) {
      // This is a constructor. Call the superclass constructor.
      return caller.superClass_.constructor.apply(
          me, Array.prototype.slice.call(arguments, 1));
    }
  
    var args = Array.prototype.slice.call(arguments, 2);
    var foundCaller = false;
    for (var ctor = me.constructor;
         ctor; ctor = ctor.superClass_ && ctor.superClass_.constructor) {
      if (ctor.prototype[opt_methodName] === caller) {
        foundCaller = true;
      } else if (foundCaller) {
        return ctor.prototype[opt_methodName].apply(me, args);
      }
    }
  
    // If we did not find the caller in the prototype chain,
    // then one of two things happened:
    // 1) The caller is an instance method.
    // 2) This method was not called by the right caller.
    if (me[opt_methodName] === caller) {
      return me.constructor.prototype[opt_methodName].apply(me, args);
    } else {
      throw Error(
          'goog.base called from a method of one name ' +
          'to a method of a different name');
    }
  };
  
  
  /**
   * Allow for aliasing within scope functions.  This function exists for
   * uncompiled code - in compiled code the calls will be inlined and the
   * aliases applied.  In uncompiled code the function is simply run since the
   * aliases as written are valid JavaScript.
   * @param {function()} fn Function to call.  This function can contain aliases
   *     to namespaces (e.g. "var dom = goog.dom") or classes
   *    (e.g. "var Timer = goog.Timer").
   */
  goog.scope = function(fn) {
    fn.call(goog.global);
  };
  
  
  // 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 objects/maps/hashes.
   */
  
  goog.provide('goog.object');
  
  
  /**
   * Calls a function for each element in an object/map/hash.
   *
   * @param {Object} obj The 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 object)
   *     and the return value is irrelevant.
   * @param {Object=} opt_obj This is used as the 'this' object within f.
   */
  goog.object.forEach = function(obj, f, opt_obj) {
    for (var key in obj) {
      f.call(opt_obj, obj[key], key, obj);
    }
  };
  
  
  /**
   * Calls a function for each element in an object/map/hash. If that call returns
   * true, adds the element to a new object.
   *
   * @param {Object} obj The 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 object)
   *     and should return a boolean. If the return value is true the
   *     element is added to the result object. If it is false the
   *     element is not included.
   * @param {Object=} opt_obj This is used as the 'this' object within f.
   * @return {!Object} a new object in which only elements that passed the test
   *     are present.
   */
  goog.object.filter = function(obj, f, opt_obj) {
    var res = {};
    for (var key in obj) {
      if (f.call(opt_obj, obj[key], key, obj)) {
        res[key] = obj[key];
      }
    }
    return res;
  };
  
  
  /**
   * For every element in an object/map/hash calls a function and inserts the
   * result into a new object.
   *
   * @param {Object} obj The 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 object)
   *     and should return something. The result will be inserted
   *     into a new object.
   * @param {Object=} opt_obj This is used as the 'this' object within f.
   * @return {!Object} a new object with the results from f.
   */
  goog.object.map = function(obj, f, opt_obj) {
    var res = {};
    for (var key in obj) {
      res[key] = f.call(opt_obj, obj[key], key, obj);
    }
    return res;
  };
  
  
  /**
   * Calls a function for each element in an object/map/hash. If any
   * call returns true, returns true (without checking the rest). If
   * all calls return false, returns false.
   *
   * @param {Object} obj The object to check.
   * @param {Function} f The function to call for every element. This function
   *     takes 3 arguments (the element, the index and the object) and should
   *     return a boolean.
   * @param {Object=} opt_obj This is used as the 'this' object within f.
   * @return {boolean} true if any element passes the test.
   */
  goog.object.some = function(obj, f, opt_obj) {
    for (var key in obj) {
      if (f.call(opt_obj, obj[key], key, obj)) {
        return true;
      }
    }
    return false;
  };
  
  
  /**
   * Calls a function for each element in an object/map/hash. If
   * all calls return true, returns true. If any call returns false, returns
   * false at this point and does not continue to check the remaining elements.
   *
   * @param {Object} obj The object to check.
   * @param {Function} f The function to call for every element. This function
   *     takes 3 arguments (the element, the index and the object) and should
   *     return a boolean.
   * @param {Object=} opt_obj This is used as the 'this' object within f.
   * @return {boolean} false if any element fails the test.
   */
  goog.object.every = function(obj, f, opt_obj) {
    for (var key in obj) {
      if (!f.call(opt_obj, obj[key], key, obj)) {
        return false;
      }
    }
    return true;
  };
  
  
  /**
   * Returns the number of key-value pairs in the object map.
   *
   * @param {Object} obj The object for which to get the number of key-value
   *     pairs.
   * @return {number} The number of key-value pairs in the object map.
   */
  goog.object.getCount = function(obj) {
    // JS1.5 has __count__ but it has been deprecated so it raises a warning...
    // in other words do not use. Also __count__ only includes the fields on the
    // actual object and not in the prototype chain.
    var rv = 0;
    for (var key in obj) {
      rv++;
    }
    return rv;
  };
  
  
  /**
   * Returns one key from the object map, if any exists.
   * For map literals the returned key will be the first one in most of the
   * browsers (a know exception is Konqueror).
   *
   * @param {Object} obj The object to pick a key from.
   * @return {string|undefined} The key or undefined if the object is empty.
   */
  goog.object.getAnyKey = function(obj) {
    for (var key in obj) {
      return key;
    }
  };
  
  
  /**
   * Returns one value from the object map, if any exists.
   * For map literals the returned value will be the first one in most of the
   * browsers (a know exception is Konqueror).
   *
   * @param {Object} obj The object to pick a value from.
   * @return {*} The value or undefined if the object is empty.
   */
  goog.object.getAnyValue = function(obj) {
    for (var key in obj) {
      return obj[key];
    }
  };
  
  
  /**
   * Whether the object/hash/map contains the given object as a value.
   * An alias for goog.object.containsValue(obj, val).
   *
   * @param {Object} obj The object in which to look for val.
   * @param {*} val The object for which to check.
   * @return {boolean} true if val is present.
   */
  goog.object.contains = function(obj, val) {
    return goog.object.containsValue(obj, val);
  };
  
  
  /**
   * Returns the values of the object/map/hash.
   *
   * @param {Object} obj The object from which to get the values.
   * @return {!Array} The values in the object/map/hash.
   */
  goog.object.getValues = function(obj) {
    var res = [];
    var i = 0;
    for (var key in obj) {
      res[i++] = obj[key];
    }
    return res;
  };
  
  
  /**
   * Returns the keys of the object/map/hash.
   *
   * @param {Object} obj The object from which to get the keys.
   * @return {!Array.<string>} Array of property keys.
   */
  goog.object.getKeys = function(obj) {
    var res = [];
    var i = 0;
    for (var key in obj) {
      res[i++] = key;
    }
    return res;
  };
  
  
  /**
   * Get a value from an object multiple levels deep.  This is useful for
   * pulling values from deeply nested objects, such as JSON responses.
   * Example usage: getValueByKeys(jsonObj, 'foo', 'entries', 3)
   *
   * @param {!Object} obj An object to get the value from.  Can be array-like.
   * @param {...(string|number|!Array.<number|string>)} var_args A number of keys
   *     (as strings, or nubmers, for array-like objects).  Can also be
   *     specified as a single array of keys.
   * @return {*} The resulting value.  If, at any point, the value for a key
   *     is undefined, returns undefined.
   */
  goog.object.getValueByKeys = function(obj, var_args) {
    var isArrayLike = goog.isArrayLike(var_args);
    var keys = isArrayLike ? var_args : arguments;
  
    // Start with the 2nd parameter for the variable parameters syntax.
    for (var i = isArrayLike ? 0 : 1; i < keys.length; i++) {
      obj = obj[keys[i]];
      if (!goog.isDef(obj)) {
        break;
      }
    }
  
    return obj;
  };
  
  
  /**
   * Whether the object/map/hash contains the given key.
   *
   * @param {Object} obj The object in which to look for key.
   * @param {*} key The key for which to check.
   * @return {boolean} true If the map contains the key.
   */
  goog.object.containsKey = function(obj, key) {
    return key in obj;
  };
  
  
  /**
   * Whether the object/map/hash contains the given value. This is O(n).
   *
   * @param {Object} obj The object in which to look for val.
   * @param {*} val The value for which to check.
   * @return {boolean} true If the map contains the value.
   */
  goog.object.containsValue = function(obj, val) {
    for (var key in obj) {
      if (obj[key] == val) {
        return true;
      }
    }
    return false;
  };
  
  
  /**
   * Searches an object for an element that satisfies the given condition and
   * returns its key.
   * @param {Object} obj The object to search in.
   * @param {function(*, string, Object): boolean} f The function to call for
   *     every element. Takes 3 arguments (the value, the key and the object) and
   *     should return a boolean.
   * @param {Object=} opt_this An optional "this" context for the function.
   * @return {string|undefined} The key of an element for which the function
   *     returns true or undefined if no such element is found.
   */
  goog.object.findKey = function(obj, f, opt_this) {
    for (var key in obj) {
      if (f.call(opt_this, obj[key], key, obj)) {
        return key;
      }
    }
    return undefined;
  };
  
  
  /**
   * Searches an object for an element that satisfies the given condition and
   * returns its value.
   * @param {Object} obj The object to search in.
   * @param {function(*, string, Object): boolean} f The function to call for
   *     every element. Takes 3 arguments (the value, the key and the object) and
   *     should return a boolean.
   * @param {Object=} opt_this An optional "this" context for the function.
   * @return {*} The value of an element for which the function returns true or
   *     undefined if no such element is found.
   */
  goog.object.findValue = function(obj, f, opt_this) {
    var key = goog.object.findKey(obj, f, opt_this);
    return key && obj[key];
  };
  
  
  /**
   * Whether the object/map/hash is empty.
   *
   * @param {Object} obj The object to test.
   * @return {boolean} true if obj is empty.
   */
  goog.object.isEmpty = function(obj) {
    for (var key in obj) {
      return false;
    }
    return true;
  };
  
  
  /**
   * Removes all key value pairs from the object/map/hash.
   *
   * @param {Object} obj The object to clear.
   */
  goog.object.clear = function(obj) {
    for (var i in obj) {
      delete obj[i];
    }
  };
  
  
  /**
   * Removes a key-value pair based on the key.
   *
   * @param {Object} obj The object from which to remove the key.
   * @param {*} key The key to remove.
   * @return {boolean} Whether an element was removed.
   */
  goog.object.remove = function(obj, key) {
    var rv;
    if ((rv = key in obj)) {
      delete obj[key];
    }
    return rv;
  };
  
  
  /**
   * Adds a key-value pair to the object. Throws an exception if the key is
   * already in use. Use set if you want to change an existing pair.
   *
   * @param {Object} obj The object to which to add the key-value pair.
   * @param {string} key The key to add.
   * @param {*} val The value to add.
   */
  goog.object.add = function(obj, key, val) {
    if (key in obj) {
      throw Error('The object already contains the key "' + key + '"');
    }
    goog.object.set(obj, key, val);
  };
  
  
  /**
   * Returns the value for the given key.
   *
   * @param {Object} obj The object from which to get the value.
   * @param {string} key The key for which to get the value.
   * @param {*=} opt_val The value to return if no item is found for the given
   *     key (default is undefined).
   * @return {*} The value for the given key.
   */
  goog.object.get = function(obj, key, opt_val) {
    if (key in obj) {
      return obj[key];
    }
    return opt_val;
  };
  
  
  /**
   * Adds a key-value pair to the object/map/hash.
   *
   * @param {Object} obj The object to which to add the key-value pair.
   * @param {string} key The key to add.
   * @param {*} value The value to add.
   */
  goog.object.set = function(obj, key, value) {
    obj[key] = value;
  };
  
  
  /**
   * Adds a key-value pair to the object/map/hash if it doesn't exist yet.
   *
   * @param {Object} obj The object to which to add the key-value pair.
   * @param {string} key The key to add.
   * @param {*} value The value to add if the key wasn't present.
   * @return {*} The value of the entry at the end of the function.
   */
  goog.object.setIfUndefined = function(obj, key, value) {
    return key in obj ? obj[key] : (obj[key] = value);
  };
  
  
  /**
   * Does a flat clone of the object.
   *
   * @param {Object} obj Object to clone.
   * @return {!Object} Clone of the input object.
   */
  goog.object.clone = function(obj) {
    // We cannot use the prototype trick because a lot of methods depend on where
    // the actual key is set.
  
    var res = {};
    for (var key in obj) {
      res[key] = obj[key];
    }
    return res;
    // We could also use goog.mixin but I wanted this to be independent from that.
  };
  
  
  /**
   * Returns a new object in which all the keys and values are interchanged
   * (keys become values and values become keys). If multiple keys map to the
   * same value, the chosen transposed value is implementation-dependent.
   *
   * @param {Object} obj The object to transpose.
   * @return {!Object} The transposed object.
   */
  goog.object.transpose = function(obj) {
    var transposed = {};
    for (var key in obj) {
      transposed[obj[key]] = key;
    }
    return transposed;
  };
  
  
  /**
   * The names of the fields that are defined on Object.prototype.
   * @type {Array.<string>}
   * @private
   */
  goog.object.PROTOTYPE_FIELDS_ = [
    'constructor',
    'hasOwnProperty',
    'isPrototypeOf',
    'propertyIsEnumerable',
    'toLocaleString',
    'toString',
    'valueOf'
  ];
  
  
  /**
   * Extends an object with another object.
   * This operates 'in-place'; it does not create a new Object.
   *
   * Example:
   * var o = {};
   * goog.object.extend(o, {a: 0, b: 1});
   * o; // {a: 0, b: 1}
   * goog.object.extend(o, {c: 2});
   * o; // {a: 0, b: 1, c: 2}
   *
   * @param {Object} target  The object to modify.
   * @param {...Object} var_args The objects from which values will be copied.
   */
  goog.object.extend = function(target, var_args) {
    var key, source;
    for (var i = 1; i < arguments.length; i++) {
      source = arguments[i];
      for (key in source) {
        target[key] = source[key];
      }
  
      // For IE the for-in-loop does not contain any properties that are not
      // enumerable on the prototype object (for example isPrototypeOf from
      // Object.prototype) and it will also not include 'replace' on objects that
      // extend String and change 'replace' (not that it is common for anyone to
      // extend anything except Object).
  
      for (var j = 0; j < goog.object.PROTOTYPE_FIELDS_.length; j++) {
        key = goog.object.PROTOTYPE_FIELDS_[j];
        if (Object.prototype.hasOwnProperty.call(source, key)) {
          target[key] = source[key];
        }
      }
    }
  };
  
  
  /**
   * Creates a new object built from the key-value pairs provided as arguments.
   * @param {...*} var_args If only one argument is provided and it is an array
   *     then this is used as the arguments,  otherwise even arguments are used as
   *     the property names and odd arguments are used as the property values.
   * @return {!Object} The new object.
   * @throws {Error} If there are uneven number of arguments or there is only one
   *     non array argument.
   */
  goog.object.create = function(var_args) {
    var argLength = arguments.length;
    if (argLength == 1 && goog.isArray(arguments[0])) {
      return goog.object.create.apply(null, arguments[0]);
    }
  
    if (argLength % 2) {
      throw Error('Uneven number of arguments');
    }
  
    var rv = {};
    for (var i = 0; i < argLength; i += 2) {
      rv[arguments[i]] = arguments[i + 1];
    }
    return rv;
  };
  
  
  /**
   * Creates a new object where the property names come from the arguments but
   * the value is always set to true
   * @param {...*} var_args If only one argument is provided and it is an array
   *     then this is used as the arguments,  otherwise the arguments are used
   *     as the property names.
   * @return {!Object} The new object.
   */
  goog.object.createSet = function(var_args) {
    var argLength = arguments.length;
    if (argLength == 1 && goog.isArray(arguments[0])) {
      return goog.object.createSet.apply(null, arguments[0]);
    }
  
    var rv = {};
    for (var i = 0; i < argLength; i++) {
      rv[arguments[i]] = true;
    }
    return rv;
  };
  // Copyright 2009 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 Provides a base class for custom Error objects such that the
   * stack is correctly maintained.
   *
   * You should never need to throw goog.debug.Error(msg) directly, Error(msg) is
   * sufficient.
   *
   */
  
  goog.provide('goog.debug.Error');
  
  
  
  /**
   * Base class for custom error objects.
   * @param {*=} opt_msg The message associated with the error.
   * @constructor
   * @extends {Error}
   */
  goog.debug.Error = function(opt_msg) {
  
    // Ensure there is a stack trace.
    this.stack = new Error().stack || '';
  
    if (opt_msg) {
      this.message = String(opt_msg);
    }
  };
  goog.inherits(goog.debug.Error, Error);
  
  
  /** @inheritDoc */
  goog.debug.Error.prototype.name = 'CustomError';
  // 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 string manipulation.
   */
  
  
  /**
   * Namespace for string utilities
   */
  goog.provide('goog.string');
  goog.provide('goog.string.Unicode');
  
  
  /**
   * Common Unicode string characters.
   * @enum {string}
   */
  goog.string.Unicode = {
    NBSP: '\xa0'
  };
  
  
  /**
   * Fast prefix-checker.
   * @param {string} str The string to check.
   * @param {string} prefix A string to look for at the start of {@code str}.
   * @return {boolean} True if {@code str} begins with {@code prefix}.
   */
  goog.string.startsWith = function(str, prefix) {
    return str.lastIndexOf(prefix, 0) == 0;
  };
  
  
  /**
   * Fast suffix-checker.
   * @param {string} str The string to check.
   * @param {string} suffix A string to look for at the end of {@code str}.
   * @return {boolean} True if {@code str} ends with {@code suffix}.
   */
  goog.string.endsWith = function(str, suffix) {
    var l = str.length - suffix.length;
    return l >= 0 && str.indexOf(suffix, l) == l;
  };
  
  
  /**
   * Case-insensitive prefix-checker.
   * @param {string} str The string to check.
   * @param {string} prefix  A string to look for at the end of {@code str}.
   * @return {boolean} True if {@code str} begins with {@code prefix} (ignoring
   *     case).
   */
  goog.string.caseInsensitiveStartsWith = function(str, prefix) {
    return goog.string.caseInsensitiveCompare(
        prefix, str.substr(0, prefix.length)) == 0;
  };
  
  
  /**
   * Case-insensitive suffix-checker.
   * @param {string} str The string to check.
   * @param {string} suffix A string to look for at the end of {@code str}.
   * @return {boolean} True if {@code str} ends with {@code suffix} (ignoring
   *     case).
   */
  goog.string.caseInsensitiveEndsWith = function(str, suffix) {
    return goog.string.caseInsensitiveCompare(
        suffix, str.substr(str.length - suffix.length, suffix.length)) == 0;
  };
  
  
  /**
   * Does simple python-style string substitution.
   * subs("foo%s hot%s", "bar", "dog") becomes "foobar hotdog".
   * @param {string} str The string containing the pattern.
   * @param {...*} var_args The items to substitute into the pattern.
   * @return {string} A copy of {@code str} in which each occurrence of
   *     {@code %s} has been replaced an argument from {@code var_args}.
   */
  goog.string.subs = function(str, var_args) {
    // This appears to be slow, but testing shows it compares more or less
    // equivalent to the regex.exec method.
    for (var i = 1; i < arguments.length; i++) {
      // We cast to String in case an argument is a Function.  Replacing $&, for
      // example, with $$$& stops the replace from subsituting the whole match
      // into the resultant string.  $$$& in the first replace becomes $$& in the
      //  second, which leaves $& in the resultant string.  Also:
      // $$, $`, $', $n $nn
      var replacement = String(arguments[i]).replace(/\$/g, '$$$$');
      str = str.replace(/\%s/, replacement);
    }
    return str;
  };
  
  
  /**
   * Converts multiple whitespace chars (spaces, non-breaking-spaces, new lines
   * and tabs) to a single space, and strips leading and trailing whitespace.
   * @param {string} str Input string.
   * @return {string} A copy of {@code str} with collapsed whitespace.
   */
  goog.string.collapseWhitespace = function(str) {
    // Since IE doesn't include non-breaking-space (0xa0) in their \s character
    // class (as required by section 7.2 of the ECMAScript spec), we explicitly
    // include it in the regexp to enforce consistent cross-browser behavior.
    return str.replace(/[\s\xa0]+/g, ' ').replace(/^\s+|\s+$/g, '');
  };
  
  
  /**
   * Checks if a string is empty or contains only whitespaces.
   * @param {string} str The string to check.
   * @return {boolean} True if {@code str} is empty or whitespace only.
   */
  goog.string.isEmpty = function(str) {
    // testing length == 0 first is actually slower in all browsers (about the
    // same in Opera).
    // Since IE doesn't include non-breaking-space (0xa0) in their \s character
    // class (as required by section 7.2 of the ECMAScript spec), we explicitly
    // include it in the regexp to enforce consistent cross-browser behavior.
    return /^[\s\xa0]*$/.test(str);
  };
  
  
  /**
   * Checks if a string is null, empty or contains only whitespaces.
   * @param {*} str The string to check.
   * @return {boolean} True if{@code str} is null, empty, or whitespace only.
   */
  goog.string.isEmptySafe = function(str) {
    return goog.string.isEmpty(goog.string.makeSafe(str));
  };
  
  
  /**
   * Checks if a string is all breaking whitespace.
   * @param {string} str The string to check.
   * @return {boolean} Whether the string is all breaking whitespace.
   */
  goog.string.isBreakingWhitespace = function(str) {
    return !/[^\t\n\r ]/.test(str);
  };
  
  
  /**
   * Checks if a string contains all letters.
   * @param {string} str string to check.
   * @return {boolean} True if {@code str} consists entirely of letters.
   */
  goog.string.isAlpha = function(str) {
    return !/[^a-zA-Z]/.test(str);
  };
  
  
  /**
   * Checks if a string contains only numbers.
   * @param {*} str string to check. If not a string, it will be
   *     casted to one.
   * @return {boolean} True if {@code str} is numeric.
   */
  goog.string.isNumeric = function(str) {
    return !/[^0-9]/.test(str);
  };
  
  
  /**
   * Checks if a string contains only numbers or letters.
   * @param {string} str string to check.
   * @return {boolean} True if {@code str} is alphanumeric.
   */
  goog.string.isAlphaNumeric = function(str) {
    return !/[^a-zA-Z0-9]/.test(str);
  };
  
  
  /**
   * Checks if a character is a space character.
   * @param {string} ch Character to check.
   * @return {boolean} True if {code ch} is a space.
   */
  goog.string.isSpace = function(ch) {
    return ch == ' ';
  };
  
  
  /**
   * Checks if a character is a valid unicode character.
   * @param {string} ch Character to check.
   * @return {boolean} True if {code ch} is a valid unicode character.
   */
  goog.string.isUnicodeChar = function(ch) {
    return ch.length == 1 && ch >= ' ' && ch <= '~' ||
           ch >= '\u0080' && ch <= '\uFFFD';
  };
  
  
  /**
   * Takes a string and replaces newlines with a space. Multiple lines are
   * replaced with a single space.
   * @param {string} str The string from which to strip newlines.
   * @return {string} A copy of {@code str} stripped of newlines.
   */
  goog.string.stripNewlines = function(str) {
    return str.replace(/(\r\n|\r|\n)+/g, ' ');
  };
  
  
  /**
   * Replaces Windows and Mac new lines with unix style: \r or \r\n with \n.
   * @param {string} str The string to in which to canonicalize newlines.
   * @return {string} {@code str} A copy of {@code} with canonicalized newlines.
   */
  goog.string.canonicalizeNewlines = function(str) {
    return str.replace(/(\r\n|\r|\n)/g, '\n');
  };
  
  
  /**
   * Normalizes whitespace in a string, replacing all whitespace chars with
   * a space.
   * @param {string} str The string in which to normalize whitespace.
   * @return {string} A copy of {@code str} with all whitespace normalized.
   */
  goog.string.normalizeWhitespace = function(str) {
    return str.replace(/\xa0|\s/g, ' ');
  };
  
  
  /**
   * Normalizes spaces in a string, replacing all consecutive spaces and tabs
   * with a single space. Replaces non-breaking space with a space.
   * @param {string} str The string in which to normalize spaces.
   * @return {string} A copy of {@code str} with all consecutive spaces and tabs
   *    replaced with a single space.
   */
  goog.string.normalizeSpaces = function(str) {
    return str.replace(/\xa0|[ \t]+/g, ' ');
  };
  
  
  /**
   * Trims white spaces to the left and right of a string.
   * @param {string} str The string to trim.
   * @return {string} A trimmed copy of {@code str}.
   */
  goog.string.trim = function(str) {
    // Since IE doesn't include non-breaking-space (0xa0) in their \s character
    // class (as required by section 7.2 of the ECMAScript spec), we explicitly
    // include it in the regexp to enforce consistent cross-browser behavior.
    return str.replace(/^[\s\xa0]+|[\s\xa0]+$/g, '');
  };
  
  
  /**
   * Trims whitespaces at the left end of a string.
   * @param {string} str The string to left trim.
   * @return {string} A trimmed copy of {@code str}.
   */
  goog.string.trimLeft = function(str) {
    // Since IE doesn't include non-breaking-space (0xa0) in their \s character
    // class (as required by section 7.2 of the ECMAScript spec), we explicitly
    // include it in the regexp to enforce consistent cross-browser behavior.
    return str.replace(/^[\s\xa0]+/, '');
  };
  
  
  /**
   * Trims whitespaces at the right end of a string.
   * @param {string} str The string to right trim.
   * @return {string} A trimmed copy of {@code str}.
   */
  goog.string.trimRight = function(str) {
    // Since IE doesn't include non-breaking-space (0xa0) in their \s character
    // class (as required by section 7.2 of the ECMAScript spec), we explicitly
    // include it in the regexp to enforce consistent cross-browser behavior.
    return str.replace(/[\s\xa0]+$/, '');
  };
  
  
  /**
   * A string comparator that ignores case.
   * -1 = str1 less than str2
   *  0 = str1 equals str2
   *  1 = str1 greater than str2
   *
   * @param {string} str1 The string to compare.
   * @param {string} str2 The string to compare {@code str1} to.
   * @return {number} The comparator result, as described above.
   */
  goog.string.caseInsensitiveCompare = function(str1, str2) {
    var test1 = String(str1).toLowerCase();
    var test2 = String(str2).toLowerCase();
  
    if (test1 < test2) {
      return -1;
    } else if (test1 == test2) {
      return 0;
    } else {
      return 1;
    }
  };
  
  
  /**
   * Regular expression used for splitting a string into substrings of fractional
   * numbers, integers, and non-numeric characters.
   * @type {RegExp}
   * @private
   */
  goog.string.numerateCompareRegExp_ = /(\.\d+)|(\d+)|(\D+)/g;
  
  
  /**
   * String comparison function that handles numbers in a way humans might expect.
   * Using this function, the string "File 2.jpg" sorts before "File 10.jpg". The
   * comparison is mostly case-insensitive, though strings that are identical
   * except for case are sorted with the upper-case strings before lower-case.
   *
   * This comparison function is significantly slower (about 500x) than either
   * the default or the case-insensitive compare. It should not be used in
   * time-critical code, but should be fast enough to sort several hundred short
   * strings (like filenames) with a reasonable delay.
   *
   * @param {string} str1 The string to compare in a numerically sensitive way.
   * @param {string} str2 The string to compare {@code str1} to.
   * @return {number} less than 0 if str1 < str2, 0 if str1 == str2, greater than
   *     0 if str1 > str2.
   */
  goog.string.numerateCompare = function(str1, str2) {
    if (str1 == str2) {
      return 0;
    }
    if (!str1) {
      return -1;
    }
    if (!str2) {
      return 1;
    }
  
    // Using match to split the entire string ahead of time turns out to be faster
    // for most inputs than using RegExp.exec or iterating over each character.
    var tokens1 = str1.toLowerCase().match(goog.string.numerateCompareRegExp_);
    var tokens2 = str2.toLowerCase().match(goog.string.numerateCompareRegExp_);
  
    var count = Math.min(tokens1.length, tokens2.length);
  
    for (var i = 0; i < count; i++) {
      var a = tokens1[i];
      var b = tokens2[i];
  
      // Compare pairs of tokens, returning if one token sorts before the other.
      if (a != b) {
  
        // Only if both tokens are integers is a special comparison required.
        // Decimal numbers are sorted as strings (e.g., '.09' < '.1').
        var num1 = parseInt(a, 10);
        if (!isNaN(num1)) {
          var num2 = parseInt(b, 10);
          if (!isNaN(num2) && num1 - num2) {
            return num1 - num2;
          }
        }
        return a < b ? -1 : 1;
      }
    }
  
    // If one string is a substring of the other, the shorter string sorts first.
    if (tokens1.length != tokens2.length) {
      return tokens1.length - tokens2.length;
    }
  
    // The two strings must be equivalent except for case (perfect equality is
    // tested at the head of the function.) Revert to default ASCII-betical string
    // comparison to stablize the sort.
    return str1 < str2 ? -1 : 1;
  };
  
  
  /**
   * Regular expression used for determining if a string needs to be encoded.
   * @type {RegExp}
   * @private
   */
  goog.string.encodeUriRegExp_ = /^[a-zA-Z0-9\-_.!~*'()]*$/;
  
  
  /**
   * URL-encodes a string
   * @param {*} str The string to url-encode.
   * @return {string} An encoded copy of {@code str} that is safe for urls.
   *     Note that '#', ':', and other characters used to delimit portions
   *     of URLs *will* be encoded.
   */
  goog.string.urlEncode = function(str) {
    str = String(str);
    // Checking if the search matches before calling encodeURIComponent avoids an
    // extra allocation in IE6. This adds about 10us time in FF and a similiar
    // over head in IE6 for lower working set apps, but for large working set
    // apps like Gmail, it saves about 70us per call.
    if (!goog.string.encodeUriRegExp_.test(str)) {
      return encodeURIComponent(str);
    }
    return str;
  };
  
  
  /**
   * URL-decodes the string. We need to specially handle '+'s because
   * the javascript library doesn't convert them to spaces.
   * @param {string} str The string to url decode.
   * @return {string} The decoded {@code str}.
   */
  goog.string.urlDecode = function(str) {
    return decodeURIComponent(str.replace(/\+/g, ' '));
  };
  
  
  /**
   * Converts \n to <br>s or <br />s.
   * @param {string} str The string in which to convert newlines.
   * @param {boolean=} opt_xml Whether to use XML compatible tags.
   * @return {string} A copy of {@code str} with converted newlines.
   */
  goog.string.newLineToBr = function(str, opt_xml) {
    return str.replace(/(\r\n|\r|\n)/g, opt_xml ? '<br />' : '<br>');
  };
  
  
  /**
   * Escape double quote '"' characters in addition to '&', '<', and '>' so that a
   * string can be included in an HTML tag attribute value within double quotes.
   *
   * It should be noted that > doesn't need to be escaped for the HTML or XML to
   * be valid, but it has been decided to escape it for consistency with other
   * implementations.
   *
   * NOTE(user):
   * HtmlEscape is often called during the generation of large blocks of HTML.
   * Using statics for the regular expressions and strings is an optimization
   * that can more than half the amount of time IE spends in this function for
   * large apps, since strings and regexes both contribute to GC allocations.
   *
   * Testing for the presence of a character before escaping increases the number
   * of function calls, but actually provides a speed increase for the average
   * case -- since the average case often doesn't require the escaping of all 4
   * characters and indexOf() is much cheaper than replace().
   * The worst case does suffer slightly from the additional calls, therefore the
   * opt_isLikelyToContainHtmlChars option has been included for situations
   * where all 4 HTML entities are very likely to be present and need escaping.
   *
   * Some benchmarks (times tended to fluctuate +-0.05ms):
   *                                     FireFox                     IE6
   * (no chars / average (mix of cases) / all 4 chars)
   * no checks                     0.13 / 0.22 / 0.22         0.23 / 0.53 / 0.80
   * indexOf                       0.08 / 0.17 / 0.26         0.22 / 0.54 / 0.84
   * indexOf + re test             0.07 / 0.17 / 0.28         0.19 / 0.50 / 0.85
   *
   * An additional advantage of checking if replace actually needs to be called
   * is a reduction in the number of object allocations, so as the size of the
   * application grows the difference between the various methods would increase.
   *
   * @param {string} str string to be escaped.
   * @param {boolean=} opt_isLikelyToContainHtmlChars Don't perform a check to see
   *     if the character needs replacing - use this option if you expect each of
   *     the characters to appear often. Leave false if you expect few html
   *     characters to occur in your strings, such as if you are escaping HTML.
   * @return {string} An escaped copy of {@code str}.
   */
  goog.string.htmlEscape = function(str, opt_isLikelyToContainHtmlChars) {
  
    if (opt_isLikelyToContainHtmlChars) {
      return str.replace(goog.string.amperRe_, '&amp;')
            .replace(goog.string.ltRe_, '&lt;')
            .replace(goog.string.gtRe_, '&gt;')
            .replace(goog.string.quotRe_, '&quot;');
  
    } else {
      // quick test helps in the case when there are no chars to replace, in
      // worst case this makes barely a difference to the time taken
      if (!goog.string.allRe_.test(str)) return str;
  
      // str.indexOf is faster than regex.test in this case
      if (str.indexOf('&') != -1) {
        str = str.replace(goog.string.amperRe_, '&amp;');
      }
      if (str.indexOf('<') != -1) {
        str = str.replace(goog.string.ltRe_, '&lt;');
      }
      if (str.indexOf('>') != -1) {
        str = str.replace(goog.string.gtRe_, '&gt;');
      }
      if (str.indexOf('"') != -1) {
        str = str.replace(goog.string.quotRe_, '&quot;');
      }
      return str;
    }
  };
  
  
  /**
   * Regular expression that matches an ampersand, for use in escaping.
   * @type {RegExp}
   * @private
   */
  goog.string.amperRe_ = /&/g;
  
  
  /**
   * Regular expression that matches a less than sign, for use in escaping.
   * @type {RegExp}
   * @private
   */
  goog.string.ltRe_ = /</g;
  
  
  /**
   * Regular expression that matches a greater than sign, for use in escaping.
   * @type {RegExp}
   * @private
   */
  goog.string.gtRe_ = />/g;
  
  
  /**
   * Regular expression that matches a double quote, for use in escaping.
   * @type {RegExp}
   * @private
   */
  goog.string.quotRe_ = /\"/g;
  
  
  /**
   * Regular expression that matches any character that needs to be escaped.
   * @type {RegExp}
   * @private
   */
  goog.string.allRe_ = /[&<>\"]/;
  
  
  /**
   * Unescapes an HTML string.
   *
   * @param {string} str The string to unescape.
   * @return {string} An unescaped copy of {@code str}.
   */
  goog.string.unescapeEntities = function(str) {
    if (goog.string.contains(str, '&')) {
      // We are careful not to use a DOM if we do not have one. We use the []
      // notation so that the JSCompiler will not complain about these objects and
      // fields in the case where we have no DOM.
      // If the string contains < then there could be a script tag in there and in
      // that case we fall back to a non DOM solution as well.
      if ('document' in goog.global && !goog.string.contains(str, '<')) {
        return goog.string.unescapeEntitiesUsingDom_(str);
      } else {
        // Fall back on pure XML entities
        return goog.string.unescapePureXmlEntities_(str);
      }
    }
    return str;
  };
  
  
  /**
   * Unescapes an HTML string using a DOM. Don't use this function directly, it
   * should only be used by unescapeEntities. If used directly you will be
   * vulnerable to XSS attacks.
   * @private
   * @param {string} str The string to unescape.
   * @return {string} The unescaped {@code str} string.
   */
  goog.string.unescapeEntitiesUsingDom_ = function(str) {
    // Use a DIV as FF3 generates bogus markup for A > PRE.
    var el = goog.global['document']['createElement']('div');
    // Wrap in PRE to preserve whitespace in IE.
    // The PRE must be part of the innerHTML markup,
    // just setting innerHTML on a PRE element does not work.
    // Also include a leading character since conforming HTML5
    // UAs will strip leading newlines inside a PRE element.
    el['innerHTML'] = '<pre>x' + str + '</pre>';
    // Accesing the function directly triggers some virus scanners.
    if (el['firstChild'][goog.string.NORMALIZE_FN_]) {
      el['firstChild'][goog.string.NORMALIZE_FN_]();
    }
    // Remove the leading character we added.
    str = el['firstChild']['firstChild']['nodeValue'].slice(1);
    el['innerHTML'] = '';
    // IE will also return non-standard newlines for TextNode.nodeValue,
    // switching \r and \n, so canonicalize them before returning.
    return goog.string.canonicalizeNewlines(str);
  };
  
  
  /**
   * Unescapes XML entities.
   * @private
   * @param {string} str The string to unescape.
   * @return {string} An unescaped copy of {@code str}.
   */
  goog.string.unescapePureXmlEntities_ = function(str) {
    return str.replace(/&([^;]+);/g, function(s, entity) {
      switch (entity) {
        case 'amp':
          return '&';
        case 'lt':
          return '<';
        case 'gt':
          return '>';
        case 'quot':
          return '"';
        default:
          if (entity.charAt(0) == '#') {
            var n = Number('0' + entity.substr(1));
            if (!isNaN(n)) {
              return String.fromCharCode(n);
            }
          }
          // For invalid entities we just return the entity
          return s;
      }
    });
  };
  
  
  /**
   * String name for the node.normalize function. Anti-virus programs use this as
   * a signature for some viruses so we need a work around (temporary).
   * @private
   * @type {string}
   */
  goog.string.NORMALIZE_FN_ = 'normalize';
  
  
  /**
   * Do escaping of whitespace to preserve spatial formatting. We use character
   * entity #160 to make it safer for xml.
   * @param {string} str The string in which to escape whitespace.
   * @param {boolean=} opt_xml Whether to use XML compatible tags.
   * @return {string} An escaped copy of {@code str}.
   */
  goog.string.whitespaceEscape = function(str, opt_xml) {
    return goog.string.newLineToBr(str.replace(/  /g, ' &#160;'), opt_xml);
  };
  
  
  /**
   * Strip quote characters around a string.  The second argument is a string of
   * characters to treat as quotes.  This can be a single character or a string of
   * multiple character and in that case each of those are treated as possible
   * quote characters. For example:
   *
   * <pre>
   * goog.string.stripQuotes('"abc"', '"`') --> 'abc'
   * goog.string.stripQuotes('`abc`', '"`') --> 'abc'
   * </pre>
   *
   * @param {string} str The string to strip.
   * @param {string} quoteChars The quote characters to strip.
   * @return {string} A copy of {@code str} without the quotes.
   */
  goog.string.stripQuotes = function(str, quoteChars) {
    var length = quoteChars.length;
    for (var i = 0; i < length; i++) {
      var quoteChar = length == 1 ? quoteChars : quoteChars.charAt(i);
      if (str.charAt(0) == quoteChar && str.charAt(str.length - 1) == quoteChar) {
        return str.substring(1, str.length - 1);
      }
    }
    return str;
  };
  
  
  /**
   * Truncates a string to a certain length and adds '...' if necessary.  The
   * length also accounts for the ellipsis, so a maximum length of 10 and a string
   * 'Hello World!' produces 'Hello W...'.
   * @param {string} str The string to truncate.
   * @param {number} chars Max number of characters.
   * @param {boolean=} opt_protectEscapedCharacters Whether to protect escaped
   *     characters from being cut off in the middle.
   * @return {string} The truncated {@code str} string.
   */
  goog.string.truncate = function(str, chars, opt_protectEscapedCharacters) {
    if (opt_protectEscapedCharacters) {
      str = goog.string.unescapeEntities(str);
    }
  
    if (str.length > chars) {
      str = str.substring(0, chars - 3) + '...';
    }
  
    if (opt_protectEscapedCharacters) {
      str = goog.string.htmlEscape(str);
    }
  
    return str;
  };
  
  
  /**
   * Truncate a string in the middle, adding "..." if necessary,
   * and favoring the beginning of the string.
   * @param {string} str The string to truncate the middle of.
   * @param {number} chars Max number of characters.
   * @param {boolean=} opt_protectEscapedCharacters Whether to protect escaped
   *     characters from being cutoff in the middle.
   * @return {string} A truncated copy of {@code str}.
   */
  goog.string.truncateMiddle = function(str, chars,
      opt_protectEscapedCharacters) {
    if (opt_protectEscapedCharacters) {
      str = goog.string.unescapeEntities(str);
    }
  
    if (str.length > chars) {
      // Favor the beginning of the string:
      var half = Math.floor(chars / 2);
      var endPos = str.length - half;
      half += chars % 2;
      str = str.substring(0, half) + '...' + str.substring(endPos);
    }
  
    if (opt_protectEscapedCharacters) {
      str = goog.string.htmlEscape(str);
    }
  
    return str;
  };
  
  
  /**
   * Special chars that need to be escaped for goog.string.quote.
   * @private
   * @type {Object}
   */
  goog.string.specialEscapeChars_ = {
    '\0': '\\0',
    '\b': '\\b',
    '\f': '\\f',
    '\n': '\\n',
    '\r': '\\r',
    '\t': '\\t',
    '\x0B': '\\x0B', // '\v' is not supported in JScript
    '"': '\\"',
    '\\': '\\\\'
  };
  
  
  /**
   * Character mappings used internally for goog.string.escapeChar.
   * @private
   * @type {Object}
   */
  goog.string.jsEscapeCache_ = {
    '\'': '\\\''
  };
  
  
  /**
   * Encloses a string in double quotes and escapes characters so that the
   * string is a valid JS string.
   * @param {string} s The string to quote.
   * @return {string} A copy of {@code s} surrounded by double quotes.
   */
  goog.string.quote = function(s) {
    s = String(s);
    if (s.quote) {
      return s.quote();
    } else {
      var sb = ['"'];
      for (var i = 0; i < s.length; i++) {
        var ch = s.charAt(i);
        var cc = ch.charCodeAt(0);
        sb[i + 1] = goog.string.specialEscapeChars_[ch] ||
            ((cc > 31 && cc < 127) ? ch : goog.string.escapeChar(ch));
      }
      sb.push('"');
      return sb.join('');
    }
  };
  
  
  /**
   * Takes a string and returns the escaped string for that character.
   * @param {string} str The string to escape.
   * @return {string} An escaped string representing {@code str}.
   */
  goog.string.escapeString = function(str) {
    var sb = [];
    for (var i = 0; i < str.length; i++) {
      sb[i] = goog.string.escapeChar(str.charAt(i));
    }
    return sb.join('');
  };
  
  
  /**
   * Takes a character and returns the escaped string for that character. For
   * example escapeChar(String.fromCharCode(15)) -> "\\x0E".
   * @param {string} c The character to escape.
   * @return {string} An escaped string representing {@code c}.
   */
  goog.string.escapeChar = function(c) {
    if (c in goog.string.jsEscapeCache_) {
      return goog.string.jsEscapeCache_[c];
    }
  
    if (c in goog.string.specialEscapeChars_) {
      return goog.string.jsEscapeCache_[c] = goog.string.specialEscapeChars_[c];
    }
  
    var rv = c;
    var cc = c.charCodeAt(0);
    if (cc > 31 && cc < 127) {
      rv = c;
    } else {
      // tab is 9 but handled above
      if (cc < 256) {
        rv = '\\x';
        if (cc < 16 || cc > 256) {
          rv += '0';
        }
      } else {
        rv = '\\u';
        if (cc < 4096) { // \u1000
          rv += '0';
        }
      }
      rv += cc.toString(16).toUpperCase();
    }
  
    return goog.string.jsEscapeCache_[c] = rv;
  };
  
  
  /**
   * Takes a string and creates a map (Object) in which the keys are the
   * characters in the string. The value for the key is set to true. You can
   * then use goog.object.map or goog.array.map to change the values.
   * @param {string} s The string to build the map from.
   * @return {Object} The map of characters used.
   */
  // TODO(user): It seems like we should have a generic goog.array.toMap. But do
  //            we want a dependency on goog.array in goog.string?
  goog.string.toMap = function(s) {
    var rv = {};
    for (var i = 0; i < s.length; i++) {
      rv[s.charAt(i)] = true;
    }
    return rv;
  };
  
  
  /**
   * Checks whether a string contains a given character.
   * @param {string} s The string to test.
   * @param {string} ss The substring to test for.
   * @return {boolean} True if {@code s} contains {@code ss}.
   */
  goog.string.contains = function(s, ss) {
    return s.indexOf(ss) != -1;
  };
  
  
  /**
   * Removes a substring of a specified length at a specific
   * index in a string.
   * @param {string} s The base string from which to remove.
   * @param {number} index The index at which to remove the substring.
   * @param {number} stringLength The length of the substring to remove.
   * @return {string} A copy of {@code s} with the substring removed or the full
   *     string if nothing is removed or the input is invalid.
   */
  goog.string.removeAt = function(s, index, stringLength) {
    var resultStr = s;
    // If the index is greater or equal to 0 then remove substring
    if (index >= 0 && index < s.length && stringLength > 0) {
      resultStr = s.substr(0, index) +
          s.substr(index + stringLength, s.length - index - stringLength);
    }
    return resultStr;
  };
  
  
  /**
   *  Removes the first occurrence of a substring from a string.
   *  @param {string} s The base string from which to remove.
   *  @param {string} ss The string to remove.
   *  @return {string} A copy of {@code s} with {@code ss} removed or the full
   *      string if nothing is removed.
   */
  goog.string.remove = function(s, ss) {
    var re = new RegExp(goog.string.regExpEscape(ss), '');
    return s.replace(re, '');
  };
  
  
  /**
   *  Removes all occurrences of a substring from a string.
   *  @param {string} s The base string from which to remove.
   *  @param {string} ss The string to remove.
   *  @return {string} A copy of {@code s} with {@code ss} removed or the full
   *      string if nothing is removed.
   */
  goog.string.removeAll = function(s, ss) {
    var re = new RegExp(goog.string.regExpEscape(ss), 'g');
    return s.replace(re, '');
  };
  
  
  /**
   * Escapes characters in the string that are not safe to use in a RegExp.
   * @param {*} s The string to escape. If not a string, it will be casted
   *     to one.
   * @return {string} A RegExp safe, escaped copy of {@code s}.
   */
  goog.string.regExpEscape = function(s) {
    return String(s).replace(/([-()\[\]{}+?*.$\^|,:#<!\\])/g, '\\$1').
        replace(/\x08/g, '\\x08');
  };
  
  
  /**
   * Repeats a string n times.
   * @param {string} string The string to repeat.
   * @param {number} length The number of times to repeat.
   * @return {string} A string containing {@code length} repetitions of
   *     {@code string}.
   */
  goog.string.repeat = function(string, length) {
    return new Array(length + 1).join(string);
  };
  
  
  /**
   * Pads number to given length and optionally rounds it to a given precision.
   * For example:
   * <pre>padNumber(1.25, 2, 3) -> '01.250'
   * padNumber(1.25, 2) -> '01.25'
   * padNumber(1.25, 2, 1) -> '01.3'
   * padNumber(1.25, 0) -> '1.25'</pre>
   *
   * @param {number} num The number to pad.
   * @param {number} length The desired length.
   * @param {number=} opt_precision The desired precision.
   * @return {string} {@code num} as a string with the given options.
   */
  goog.string.padNumber = function(num, length, opt_precision) {
    var s = goog.isDef(opt_precision) ? num.toFixed(opt_precision) : String(num);
    var index = s.indexOf('.');
    if (index == -1) {
      index = s.length;
    }
    return goog.string.repeat('0', Math.max(0, length - index)) + s;
  };
  
  
  /**
   * Returns a string representation of the given object, with
   * null and undefined being returned as the empty string.
   *
   * @param {*} obj The object to convert.
   * @return {string} A string representation of the {@code obj}.
   */
  goog.string.makeSafe = function(obj) {
    return obj == null ? '' : String(obj);
  };
  
  
  /**
   * Concatenates string expressions. This is useful
   * since some browsers are very inefficient when it comes to using plus to
   * concat strings. Be careful when using null and undefined here since
   * these will not be included in the result. If you need to represent these
   * be sure to cast the argument to a String first.
   * For example:
   * <pre>buildString('a', 'b', 'c', 'd') -> 'abcd'
   * buildString(null, undefined) -> ''
   * </pre>
   * @param {...*} var_args A list of strings to concatenate. If not a string,
   *     it will be casted to one.
   * @return {string} The concatenation of {@code var_args}.
   */
  goog.string.buildString = function(var_args) {
    return Array.prototype.join.call(arguments, '');
  };
  
  
  /**
   * Returns a string with at least 64-bits of randomness.
   *
   * Doesn't trust Javascript's random function entirely. Uses a combination of
   * random and current timestamp, and then encodes the string in base-36 to
   * make it shorter.
   *
   * @return {string} A random string, e.g. sn1s7vb4gcic.
   */
  goog.string.getRandomString = function() {
    var x = 2147483648;
    return Math.floor(Math.random() * x).toString(36) +
           Math.abs(Math.floor(Math.random() * x) ^ goog.now()).toString(36);
  };
  
  
  /**
   * Compares two version numbers.
   *
   * @param {string|number} version1 Version of first item.
   * @param {string|number} version2 Version of second item.
   *
   * @return {number}  1 if {@code version1} is higher.
   *                   0 if arguments are equal.
   *                  -1 if {@code version2} is higher.
   */
  goog.string.compareVersions = function(version1, version2) {
    var order = 0;
    // Trim leading and trailing whitespace and split the versions into
    // subversions.
    var v1Subs = goog.string.trim(String(version1)).split('.');
    var v2Subs = goog.string.trim(String(version2)).split('.');
    var subCount = Math.max(v1Subs.length, v2Subs.length);
  
    // Iterate over the subversions, as long as they appear to be equivalent.
    for (var subIdx = 0; order == 0 && subIdx < subCount; subIdx++) {
      var v1Sub = v1Subs[subIdx] || '';
      var v2Sub = v2Subs[subIdx] || '';
  
      // Split the subversions into pairs of numbers and qualifiers (like 'b').
      // Two different RegExp objects are needed because they are both using
      // the 'g' flag.
      var v1CompParser = new RegExp('(\\d*)(\\D*)', 'g');
      var v2CompParser = new RegExp('(\\d*)(\\D*)', 'g');
      do {
        var v1Comp = v1CompParser.exec(v1Sub) || ['', '', ''];
        var v2Comp = v2CompParser.exec(v2Sub) || ['', '', ''];
        // Break if there are no more matches.
        if (v1Comp[0].length == 0 && v2Comp[0].length == 0) {
          break;
        }
  
        // Parse the numeric part of the subversion. A missing number is
        // equivalent to 0.
        var v1CompNum = v1Comp[1].length == 0 ? 0 : parseInt(v1Comp[1], 10);
        var v2CompNum = v2Comp[1].length == 0 ? 0 : parseInt(v2Comp[1], 10);
  
        // Compare the subversion components. The number has the highest
        // precedence. Next, if the numbers are equal, a subversion without any
        // qualifier is always higher than a subversion with any qualifier. Next,
        // the qualifiers are compared as strings.
        order = goog.string.compareElements_(v1CompNum, v2CompNum) ||
            goog.string.compareElements_(v1Comp[2].length == 0,
                v2Comp[2].length == 0) ||
            goog.string.compareElements_(v1Comp[2], v2Comp[2]);
        // Stop as soon as an inequality is discovered.
      } while (order == 0);
    }
  
    return order;
  };
  
  
  /**
   * Compares elements of a version number.
   *
   * @param {string|number|boolean} left An element from a version number.
   * @param {string|number|boolean} right An element from a version number.
   *
   * @return {number}  1 if {@code left} is higher.
   *                   0 if arguments are equal.
   *                  -1 if {@code right} is higher.
   * @private
   */
  goog.string.compareElements_ = function(left, right) {
    if (left < right) {
      return -1;
    } else if (left > right) {
      return 1;
    }
    return 0;
  };
  
  
  /**
   * Maximum value of #goog.string.hashCode, exclusive. 2^32.
   * @type {number}
   * @private
   */
  goog.string.HASHCODE_MAX_ = 0x100000000;
  
  
  /**
   * String hash function similar to java.lang.String.hashCode().
   * The hash code for a string is computed as
   * s[0] * 31 ^ (n - 1) + s[1] * 31 ^ (n - 2) + ... + s[n - 1],
   * where s[i] is the ith character of the string and n is the length of
   * the string. We mod the result to make it between 0 (inclusive) and 2^32
   * (exclusive).
   * @param {string} str A string.
   * @return {number} Hash value for {@code str}, between 0 (inclusive) and 2^32
   *  (exclusive). The empty string returns 0.
   */
  goog.string.hashCode = function(str) {
    var result = 0;
    for (var i = 0; i < str.length; ++i) {
      result = 31 * result + str.charCodeAt(i);
      // Normalize to 4 byte range, 0 ... 2^32.
      result %= goog.string.HASHCODE_MAX_;
    }
    return result;
  };
  
  
  /**
   * The most recent unique ID. |0 is equivalent to Math.floor in this case.
   * @type {number}
   * @private
   */
  goog.string.uniqueStringCounter_ = Math.random() * 0x80000000 | 0;
  
  
  /**
   * Generates and returns a string which is unique in the current document.
   * This is useful, for example, to create unique IDs for DOM elements.
   * @return {string} A unique id.
   */
  goog.string.createUniqueString = function() {
    return 'goog_' + goog.string.uniqueStringCounter_++;
  };
  
  
  /**
   * Converts the supplied string to a number, which may be Ininity or NaN.
   * This function strips whitespace: (toNumber(' 123') === 123)
   * This function accepts scientific notation: (toNumber('1e1') === 10)
   *
   * This is better than Javascript's built-in conversions because, sadly:
   *     (Number(' ') === 0) and (parseFloat('123a') === 123)
   *
   * @param {string} str The string to convert.
   * @return {number} The number the supplied string represents, or NaN.
   */
  goog.string.toNumber = function(str) {
    var num = Number(str);
    if (num == 0 && goog.string.isEmpty(str)) {
      return NaN;
    }
    return num;
  };
  
  
  /**
   * A memoized cache for goog.string.toCamelCase.
   * @type {Object.<string>}
   * @private
   */
  goog.string.toCamelCaseCache_ = {};
  
  
  /**
   * Converts a string from selector-case to camelCase (e.g. from
   * "multi-part-string" to "multiPartString"), useful for converting
   * CSS selectors and HTML dataset keys to their equivalent JS properties.
   * @param {string} str The string in selector-case form.
   * @return {string} The string in camelCase form.
   */
  goog.string.toCamelCase = function(str) {
    return goog.string.toCamelCaseCache_[str] ||
        (goog.string.toCamelCaseCache_[str] =
            String(str).replace(/\-([a-z])/g, function(all, match) {
              return match.toUpperCase();
            }));
  };
  
  
  /**
   * A memoized cache for goog.string.toSelectorCase.
   * @type {Object.<string>}
   * @private
   */
  goog.string.toSelectorCaseCache_ = {};
  
  
  /**
   * Converts a string from camelCase to selector-case (e.g. from
   * "multiPartString" to "multi-part-string"), useful for converting JS
   * style and dataset properties to equivalent CSS selectors and HTML keys.
   * @param {string} str The string in camelCase form.
   * @return {string} The string in selector-case form.
   */
  goog.string.toSelectorCase = function(str) {
    return goog.string.toSelectorCaseCache_[str] ||
        (goog.string.toSelectorCaseCache_[str] =
            String(str).replace(/([A-Z])/g, '-$1').toLowerCase());
  };
  // Copyright 2008 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 to check the preconditions, postconditions and
   * invariants runtime.
   *
   * Methods in this package should be given special treatment by the compiler
   * for type-inference. For example, <code>goog.asserts.assert(foo)</code>
   * will restrict <code>foo</code> to a truthy value.
   *
   * The compiler has an option to disable asserts. So code like:
   * <code>
   * var x = goog.asserts.assert(foo()); goog.asserts.assert(bar());
   * </code>
   * will be transformed into:
   * <code>
   * var x = foo();
   * </code>
   * The compiler will leave in foo() (because its return value is used),
   * but it will remove bar() because it assumes it does not have side-effects.
   *
   */
  
  goog.provide('goog.asserts');
  goog.provide('goog.asserts.AssertionError');
  
  goog.require('goog.debug.Error');
  goog.require('goog.string');
  
  
  /**
   * @define {boolean} Whether to strip out asserts or to leave them in.
   */
  goog.asserts.ENABLE_ASSERTS = goog.DEBUG;
  
  
  
  /**
   * Error object for failed assertions.
   * @param {string} messagePattern The pattern that was used to form message.
   * @param {!Array.<*>} messageArgs The items to substitute into the pattern.
   * @constructor
   * @extends {goog.debug.Error}
   */
  goog.asserts.AssertionError = function(messagePattern, messageArgs) {
    messageArgs.unshift(messagePattern);
    goog.debug.Error.call(this, goog.string.subs.apply(null, messageArgs));
    // Remove the messagePattern afterwards to avoid permenantly modifying the
    // passed in array.
    messageArgs.shift();
  
    /**
     * The message pattern used to format the error message. Error handlers can
     * use this to uniquely identify the assertion.
     * @type {string}
     */
    this.messagePattern = messagePattern;
  };
  goog.inherits(goog.asserts.AssertionError, goog.debug.Error);
  
  
  /** @inheritDoc */
  goog.asserts.AssertionError.prototype.name = 'AssertionError';
  
  
  /**
   * Throws an exception with the given message and "Assertion failed" prefixed
   * onto it.
   * @param {string} defaultMessage The message to use if givenMessage is empty.
   * @param {Array.<*>} defaultArgs The substitution arguments for defaultMessage.
   * @param {string|undefined} givenMessage Message supplied by the caller.
   * @param {Array.<*>} givenArgs The substitution arguments for givenMessage.
   * @throws {goog.asserts.AssertionError} When the value is not a number.
   * @private
   */
  goog.asserts.doAssertFailure_ =
      function(defaultMessage, defaultArgs, givenMessage, givenArgs) {
    var message = 'Assertion failed';
    if (givenMessage) {
      message += ': ' + givenMessage;
      var args = givenArgs;
    } else if (defaultMessage) {
      message += ': ' + defaultMessage;
      args = defaultArgs;
    }
    // The '' + works around an Opera 10 bug in the unit tests. Without it,
    // a stack trace is added to var message above. With this, a stack trace is
    // not added until this line (it causes the extra garbage to be added after
    // the assertion message instead of in the middle of it).
    throw new goog.asserts.AssertionError('' + message, args || []);
  };
  
  
  /**
   * Checks if the condition evaluates to true if goog.asserts.ENABLE_ASSERTS is
   * true.
   * @param {*} condition The condition to check.
   * @param {string=} opt_message Error message in case of failure.
   * @param {...*} var_args The items to substitute into the failure message.
   * @return {*} The value of the condition.
   * @throws {goog.asserts.AssertionError} When the condition evaluates to false.
   */
  goog.asserts.assert = function(condition, opt_message, var_args) {
    if (goog.asserts.ENABLE_ASSERTS && !condition) {
      goog.asserts.doAssertFailure_('', null, opt_message,
          Array.prototype.slice.call(arguments, 2));
    }
    return condition;
  };
  
  
  /**
   * Fails if goog.asserts.ENABLE_ASSERTS is true. This function is useful in case
   * when we want to add a check in the unreachable area like switch-case
   * statement:
   *
   * <pre>
   *  switch(type) {
   *    case FOO: doSomething(); break;
   *    case BAR: doSomethingElse(); break;
   *    default: goog.assert.fail('Unrecognized type: ' + type);
   *      // We have only 2 types - "default:" section is unreachable code.
   *  }
   * </pre>
   *
   * @param {string=} opt_message Error message in case of failure.
   * @param {...*} var_args The items to substitute into the failure message.
   * @throws {goog.asserts.AssertionError} Failure.
   */
  goog.asserts.fail = function(opt_message, var_args) {
    if (goog.asserts.ENABLE_ASSERTS) {
      throw new goog.asserts.AssertionError(
          'Failure' + (opt_message ? ': ' + opt_message : ''),
          Array.prototype.slice.call(arguments, 1));
    }
  };
  
  
  /**
   * Checks if the value is a number if goog.asserts.ENABLE_ASSERTS is true.
   * @param {*} value The value to check.
   * @param {string=} opt_message Error message in case of failure.
   * @param {...*} var_args The items to substitute into the failure message.
   * @return {number} The value, guaranteed to be a number when asserts enabled.
   * @throws {goog.asserts.AssertionError} When the value is not a number.
   */
  goog.asserts.assertNumber = function(value, opt_message, var_args) {
    if (goog.asserts.ENABLE_ASSERTS && !goog.isNumber(value)) {
      goog.asserts.doAssertFailure_('Expected number but got %s: %s.',
          [goog.typeOf(value), value], opt_message,
          Array.prototype.slice.call(arguments, 2));
    }
    return /** @type {number} */ (value);
  };
  
  
  /**
   * Checks if the value is a string if goog.asserts.ENABLE_ASSERTS is true.
   * @param {*} value The value to check.
   * @param {string=} opt_message Error message in case of failure.
   * @param {...*} var_args The items to substitute into the failure message.
   * @return {string} The value, guaranteed to be a string when asserts enabled.
   * @throws {goog.asserts.AssertionError} When the value is not a string.
   */
  goog.asserts.assertString = function(value, opt_message, var_args) {
    if (goog.asserts.ENABLE_ASSERTS && !goog.isString(value)) {
      goog.asserts.doAssertFailure_('Expected string but got %s: %s.',
          [goog.typeOf(value), value], opt_message,
          Array.prototype.slice.call(arguments, 2));
    }
    return /** @type {string} */ (value);
  };
  
  
  /**
   * Checks if the value is a function if goog.asserts.ENABLE_ASSERTS is true.
   * @param {*} value The value to check.
   * @param {string=} opt_message Error message in case of failure.
   * @param {...*} var_args The items to substitute into the failure message.
   * @return {!Function} The value, guaranteed to be a function when asserts
   *     enabled.
   * @throws {goog.asserts.AssertionError} When the value is not a function.
   */
  goog.asserts.assertFunction = function(value, opt_message, var_args) {
    if (goog.asserts.ENABLE_ASSERTS && !goog.isFunction(value)) {
      goog.asserts.doAssertFailure_('Expected function but got %s: %s.',
          [goog.typeOf(value), value], opt_message,
          Array.prototype.slice.call(arguments, 2));
    }
    return /** @type {!Function} */ (value);
  };
  
  
  /**
   * Checks if the value is an Object if goog.asserts.ENABLE_ASSERTS is true.
   * @param {*} value The value to check.
   * @param {string=} opt_message Error message in case of failure.
   * @param {...*} var_args The items to substitute into the failure message.
   * @return {!Object} The value, guaranteed to be a non-null object.
   * @throws {goog.asserts.AssertionError} When the value is not an object.
   */
  goog.asserts.assertObject = function(value, opt_message, var_args) {
    if (goog.asserts.ENABLE_ASSERTS && !goog.isObject(value)) {
      goog.asserts.doAssertFailure_('Expected object but got %s: %s.',
          [goog.typeOf(value), value],
          opt_message, Array.prototype.slice.call(arguments, 2));
    }
    return /** @type {!Object} */ (value);
  };
  
  
  /**
   * Checks if the value is an Array if goog.asserts.ENABLE_ASSERTS is true.
   * @param {*} value The value to check.
   * @param {string=} opt_message Error message in case of failure.
   * @param {...*} var_args The items to substitute into the failure message.
   * @return {!Array} The value, guaranteed to be a non-null array.
   * @throws {goog.asserts.AssertionError} When the value is not an array.
   */
  goog.asserts.assertArray = function(value, opt_message, var_args) {
    if (goog.asserts.ENABLE_ASSERTS && !goog.isArray(value)) {
      goog.asserts.doAssertFailure_('Expected array but got %s: %s.',
          [goog.typeOf(value), value], opt_message,
          Array.prototype.slice.call(arguments, 2));
    }
    return /** @type {!Array} */ (value);
  };
  
  
  /**
   * Checks if the value is a boolean if goog.asserts.ENABLE_ASSERTS is true.
   * @param {*} value The value to check.
   * @param {string=} opt_message Error message in case of failure.
   * @param {...*} var_args The items to substitute into the failure message.
   * @return {boolean} The value, guaranteed to be a boolean when asserts are
   *     enabled.
   * @throws {goog.asserts.AssertionError} When the value is not a boolean.
   */
  goog.asserts.assertBoolean = function(value, opt_message, var_args) {
    if (goog.asserts.ENABLE_ASSERTS && !goog.isBoolean(value)) {
      goog.asserts.doAssertFailure_('Expected boolean but got %s: %s.',
          [goog.typeOf(value), value], opt_message,
          Array.prototype.slice.call(arguments, 2));
    }
    return /** @type {boolean} */ (value);
  };
  
  
  /**
   * Checks if the value is an instance of the user-defined type if
   * goog.asserts.ENABLE_ASSERTS is true.
   * @param {*} value The value to check.
   * @param {!Function} type A user-defined constructor.
   * @param {string=} opt_message Error message in case of failure.
   * @param {...*} var_args The items to substitute into the failure message.
   * @throws {goog.asserts.AssertionError} When the value is not an instance of
   *     type.
   */
  goog.asserts.assertInstanceof = function(value, type, opt_message, var_args) {
    if (goog.asserts.ENABLE_ASSERTS && !(value instanceof type)) {
      goog.asserts.doAssertFailure_('instanceof check failed.', null,
          opt_message, Array.prototype.slice.call(arguments, 3));
    }
  };
  
  // 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');
  
  
  /**
   * @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.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.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 {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.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 {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.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 {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.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 {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.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 {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.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 {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) {
    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) {
    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) {
    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.
    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) {
    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;
    }
  };
  // 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 Generics method for collection-like classes and objects.
   *
   *
   * This file contains functions to work with collections. It supports using
   * Map, Set, Array and Object and other classes that implement collection-like
   * methods.
   */
  
  
  goog.provide('goog.structs');
  
  goog.require('goog.array');
  goog.require('goog.object');
  
  
  // We treat an object as a dictionary if it has getKeys or it is an object that
  // isn't arrayLike.
  
  
  /**
   * Returns the number of values in the collection-like object.
   * @param {Object} col The collection-like object.
   * @return {number} The number of values in the collection-like object.
   */
  goog.structs.getCount = function(col) {
    if (typeof col.getCount == 'function') {
      return col.getCount();
    }
    if (goog.isArrayLike(col) || goog.isString(col)) {
      return col.length;
    }
    return goog.object.getCount(col);
  };
  
  
  /**
   * Returns the values of the collection-like object.
   * @param {Object} col The collection-like object.
   * @return {!Array} The values in the collection-like object.
   */
  goog.structs.getValues = function(col) {
    if (typeof col.getValues == 'function') {
      return col.getValues();
    }
    if (goog.isString(col)) {
      return col.split('');
    }
    if (goog.isArrayLike(col)) {
      var rv = [];
      var l = col.length;
      for (var i = 0; i < l; i++) {
        rv.push(col[i]);
      }
      return rv;
    }
    return goog.object.getValues(col);
  };
  
  
  /**
   * Returns the keys of the collection. Some collections have no notion of
   * keys/indexes and this function will return undefined in those cases.
   * @param {Object} col The collection-like object.
   * @return {!Array|undefined} The keys in the collection.
   */
  goog.structs.getKeys = function(col) {
    if (typeof col.getKeys == 'function') {
      return col.getKeys();
    }
    // if we have getValues but no getKeys we know this is a key-less collection
    if (typeof col.getValues == 'function') {
      return undefined;
    }
    if (goog.isArrayLike(col) || goog.isString(col)) {
      var rv = [];
      var l = col.length;
      for (var i = 0; i < l; i++) {
        rv.push(i);
      }
      return rv;
    }
  
    return goog.object.getKeys(col);
  };
  
  
  /**
   * Whether the collection contains the given value. This is O(n) and uses
   * equals (==) to test the existence.
   * @param {Object} col The collection-like object.
   * @param {*} val The value to check for.
   * @return {boolean} True if the map contains the value.
   */
  goog.structs.contains = function(col, val) {
    if (typeof col.contains == 'function') {
      return col.contains(val);
    }
    if (typeof col.containsValue == 'function') {
      return col.containsValue(val);
    }
    if (goog.isArrayLike(col) || goog.isString(col)) {
      return goog.array.contains(/** @type {Array} */ (col), val);
    }
    return goog.object.containsValue(col, val);
  };
  
  
  /**
   * Whether the collection is empty.
   * @param {Object} col The collection-like object.
   * @return {boolean} True if empty.
   */
  goog.structs.isEmpty = function(col) {
    if (typeof col.isEmpty == 'function') {
      return col.isEmpty();
    }
  
    // We do not use goog.string.isEmpty because here we treat the string as
    // collection and as such even whitespace matters
  
    if (goog.isArrayLike(col) || goog.isString(col)) {
      return goog.array.isEmpty(/** @type {Array} */ (col));
    }
    return goog.object.isEmpty(col);
  };
  
  
  /**
   * Removes all the elements from the collection.
   * @param {Object} col The collection-like object.
   */
  goog.structs.clear = function(col) {
    // NOTE(user): This should not contain strings because strings are immutable
    if (typeof col.clear == 'function') {
      col.clear();
    } else if (goog.isArrayLike(col)) {
      goog.array.clear((/** @type {goog.array.ArrayLike} */ col));
    } else {
      goog.object.clear(col);
    }
  };
  
  
  /**
   * Calls a function for each value in a collection. The function takes
   * three arguments; the value, the key and the collection.
   *
   * @param {Object} col The collection-like object.
   * @param {Function} f The function to call for every value. This function takes
   *     3 arguments (the value, the key or undefined if the collection has no
   *     notion of keys, and the collection) and the return value is irrelevant.
   * @param {Object=} opt_obj The object to be used as the value of 'this'
   *     within {@code f}.
   */
  goog.structs.forEach = function(col, f, opt_obj) {
    if (typeof col.forEach == 'function') {
      col.forEach(f, opt_obj);
    } else if (goog.isArrayLike(col) || goog.isString(col)) {
      goog.array.forEach(/** @type {Array} */ (col), f, opt_obj);
    } else {
      var keys = goog.structs.getKeys(col);
      var values = goog.structs.getValues(col);
      var l = values.length;
      for (var i = 0; i < l; i++) {
        f.call(opt_obj, values[i], keys && keys[i], col);
      }
    }
  };
  
  
  /**
   * Calls a function for every value in the collection. When a call returns true,
   * adds the value to a new collection (Array is returned by default).
   *
   * @param {Object} col The collection-like object.
   * @param {Function} f The function to call for every value. This function takes
   *     3 arguments (the value, the key or undefined if the collection has no
   *     notion of keys, and the collection) and should return a Boolean. If the
   *     return value is true the value is added to the result collection. If it
   *     is false the value is not included.
   * @param {Object=} opt_obj The object to be used as the value of 'this'
   *     within {@code f}.
   * @return {!Object|!Array} A new collection where the passed values are
   *     present. If col is a key-less collection an array is returned.  If col
   *     has keys and values a plain old JS object is returned.
   */
  goog.structs.filter = function(col, f, opt_obj) {
    if (typeof col.filter == 'function') {
      return col.filter(f, opt_obj);
    }
    if (goog.isArrayLike(col) || goog.isString(col)) {
      return goog.array.filter(/** @type {!Array} */ (col), f, opt_obj);
    }
  
    var rv;
    var keys = goog.structs.getKeys(col);
    var values = goog.structs.getValues(col);
    var l = values.length;
    if (keys) {
      rv = {};
      for (var i = 0; i < l; i++) {
        if (f.call(opt_obj, values[i], keys[i], col)) {
          rv[keys[i]] = values[i];
        }
      }
    } else {
      // We should not use goog.array.filter here since we want to make sure that
      // the index is undefined as well as make sure that col is passed to the
      // function.
      rv = [];
      for (var i = 0; i < l; i++) {
        if (f.call(opt_obj, values[i], undefined, col)) {
          rv.push(values[i]);
        }
      }
    }
    return rv;
  };
  
  
  /**
   * Calls a function for every value in the collection and adds the result into a
   * new collection (defaults to creating a new Array).
   *
   * @param {Object} col The collection-like object.
   * @param {Function} f The function to call for every value. This function
   *     takes 3 arguments (the value, the key or undefined if the collection has
   *     no notion of keys, and the collection) and should return something. The
   *     result will be used as the value in the new collection.
   * @param {Object=} opt_obj  The object to be used as the value of 'this'
   *     within {@code f}.
   * @return {!Object|!Array} A new collection with the new values.  If col is a
   *     key-less collection an array is returned.  If col has keys and values a
   *     plain old JS object is returned.
   */
  goog.structs.map = function(col, f, opt_obj) {
    if (typeof col.map == 'function') {
      return col.map(f, opt_obj);
    }
    if (goog.isArrayLike(col) || goog.isString(col)) {
      return goog.array.map(/** @type {!Array} */ (col), f, opt_obj);
    }
  
    var rv;
    var keys = goog.structs.getKeys(col);
    var values = goog.structs.getValues(col);
    var l = values.length;
    if (keys) {
      rv = {};
      for (var i = 0; i < l; i++) {
        rv[keys[i]] = f.call(opt_obj, values[i], keys[i], col);
      }
    } else {
      // We should not use goog.array.map here since we want to make sure that
      // the index is undefined as well as make sure that col is passed to the
      // function.
      rv = [];
      for (var i = 0; i < l; i++) {
        rv[i] = f.call(opt_obj, values[i], undefined, col);
      }
    }
    return rv;
  };
  
  
  /**
   * Calls f for each value in a collection. If any call returns true this returns
   * true (without checking the rest). If all returns false this returns false.
   *
   * @param {Object|Array|string} col The collection-like object.
   * @param {Function} f The function to call for every value. This function takes
   *     3 arguments (the value, the key or undefined if the collection has no
   *     notion of keys, and the collection) and should return a Boolean.
   * @param {Object=} opt_obj  The object to be used as the value of 'this'
   *     within {@code f}.
   * @return {boolean} True if any value passes the test.
   */
  goog.structs.some = function(col, f, opt_obj) {
    if (typeof col.some == 'function') {
      return col.some(f, opt_obj);
    }
    if (goog.isArrayLike(col) || goog.isString(col)) {
      return goog.array.some(/** @type {!Array} */ (col), f, opt_obj);
    }
    var keys = goog.structs.getKeys(col);
    var values = goog.structs.getValues(col);
    var l = values.length;
    for (var i = 0; i < l; i++) {
      if (f.call(opt_obj, values[i], keys && keys[i], col)) {
        return true;
      }
    }
    return false;
  };
  
  
  /**
   * Calls f for each value in a collection. If all calls return true this return
   * true this returns true. If any returns false this returns false at this point
   *  and does not continue to check the remaining values.
   *
   * @param {Object} col The collection-like object.
   * @param {Function} f The function to call for every value. This function takes
   *     3 arguments (the value, the key or undefined if the collection has no
   *     notion of keys, and the collection) and should return a Boolean.
   * @param {Object=} opt_obj  The object to be used as the value of 'this'
   *     within {@code f}.
   * @return {boolean} True if all key-value pairs pass the test.
   */
  goog.structs.every = function(col, f, opt_obj) {
    if (typeof col.every == 'function') {
      return col.every(f, opt_obj);
    }
    if (goog.isArrayLike(col) || goog.isString(col)) {
      return goog.array.every(/** @type {!Array} */ (col), f, opt_obj);
    }
    var keys = goog.structs.getKeys(col);
    var values = goog.structs.getValues(col);
    var l = values.length;
    for (var i = 0; i < l; i++) {
      if (!f.call(opt_obj, values[i], keys && keys[i], col)) {
        return false;
      }
    }
    return true;
  };
  // 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 Datastructure: Queue.
   *
   *
   * This file provides the implementation of a FIFO Queue structure.
   * API is similar to that of com.google.common.collect.IntQueue
   */
  
  goog.provide('goog.structs.Queue');
  
  goog.require('goog.array');
  
  
  
  /**
   * Class for FIFO Queue data structure.
   *
   * @constructor
   */
  goog.structs.Queue = function() {
    this.elements_ = [];
  };
  
  
  /**
   * The index of the next element to be removed from the queue.
   * @private
   * @type {number}
   */
  goog.structs.Queue.prototype.head_ = 0;
  
  
  /**
   * The index at which the next element would be added to the queue.
   * @private
   * @type {number}
   */
  goog.structs.Queue.prototype.tail_ = 0;
  
  
  /**
   * Puts the specified element on this queue.
   * @param {*} element The element to be added to the queue.
   */
  goog.structs.Queue.prototype.enqueue = function(element) {
    this.elements_[this.tail_++] = element;
  };
  
  
  /**
   * Retrieves and removes the head of this queue.
   * @return {*} The element at the head of this queue. Returns undefined if the
   *     queue is empty.
   */
  goog.structs.Queue.prototype.dequeue = function() {
    if (this.head_ == this.tail_) {
      return undefined;
    }
    var result = this.elements_[this.head_];
    delete this.elements_[this.head_];
    this.head_++;
    return result;
  };
  
  
  /**
   * Retrieves but does not remove the head of this queue.
   * @return {*} The element at the head of this queue. Returns undefined if the
   *     queue is empty.
   */
  goog.structs.Queue.prototype.peek = function() {
    if (this.head_ == this.tail_) {
      return undefined;
    }
    return this.elements_[this.head_];
  };
  
  
  /**
   * Returns the number of elements in this queue.
   * @return {number} The number of elements in this queue.
   */
  goog.structs.Queue.prototype.getCount = function() {
    return this.tail_ - this.head_;
  };
  
  
  /**
   * Returns true if this queue contains no elements.
   * @return {boolean} true if this queue contains no elements.
   */
  goog.structs.Queue.prototype.isEmpty = function() {
    return this.tail_ - this.head_ == 0;
  };
  
  
  /**
   * Removes all elements from the queue.
   */
  goog.structs.Queue.prototype.clear = function() {
    this.elements_.length = 0;
    this.head_ = 0;
    this.tail_ = 0;
  };
  
  
  /**
   * Returns true if the given value is in the queue.
   * @param {*} obj The value to look for.
   * @return {boolean} Whether the object is in the queue.
   */
  goog.structs.Queue.prototype.contains = function(obj) {
    return goog.array.contains(this.elements_, obj);
  };
  
  
  /**
   * Removes the first occurrence of a particular value from the queue.
   * @param {*} obj Object to remove.
   * @return {boolean} True if an element was removed.
   */
  goog.structs.Queue.prototype.remove = function(obj) {
    var index = goog.array.indexOf(this.elements_, obj);
    if (index < 0) {
      return false;
    }
    if (index == this.head_) {
      this.dequeue();
    } else {
      goog.array.removeAt(this.elements_, index);
      this.tail_--;
    }
    return true;
  };
  
  
  /**
   * Returns all the values in the queue.
   * @return {Array} An array of the values in the queue.
   */
  goog.structs.Queue.prototype.getValues = function() {
    return this.elements_.slice(this.head_, this.tail_);
  };
  // Copyright 2007 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 Python style iteration utilities.
   */
  
  
  goog.provide('goog.iter');
  goog.provide('goog.iter.Iterator');
  goog.provide('goog.iter.StopIteration');
  
  goog.require('goog.array');
  goog.require('goog.asserts');
  
  
  // TODO(user): Add more functions from Python's itertools.
  // http://docs.python.org/library/itertools.html
  
  
  /**
   * @typedef {goog.iter.Iterator|{length:number}|{__iterator__}}
   */
  goog.iter.Iterable;
  
  
  // For script engines that already support iterators.
  if ('StopIteration' in goog.global) {
    /**
     * Singleton Error object that is used to terminate iterations.
     * @type {Error}
     */
    goog.iter.StopIteration = goog.global['StopIteration'];
  } else {
    /**
     * Singleton Error object that is used to terminate iterations.
     * @type {Error}
     * @suppress {duplicate}
     */
    goog.iter.StopIteration = Error('StopIteration');
  }
  
  
  
  /**
   * Class/interface for iterators.  An iterator needs to implement a {@code next}
   * method and it needs to throw a {@code goog.iter.StopIteration} when the
   * iteration passes beyond the end.  Iterators have no {@code hasNext} method.
   * It is recommended to always use the helper functions to iterate over the
   * iterator or in case you are only targeting JavaScript 1.7 for in loops.
   * @constructor
   */
  goog.iter.Iterator = function() {};
  
  
  /**
   * Returns the next value of the iteration.  This will throw the object
   * {@see goog.iter#StopIteration} when the iteration passes the end.
   * @return {*} Any object or value.
   */
  goog.iter.Iterator.prototype.next = function() {
    throw goog.iter.StopIteration;
  };
  
  
  /**
   * Returns the {@code Iterator} object itself.  This is used to implement
   * the iterator protocol in JavaScript 1.7
   * @param {boolean=} opt_keys  Whether to return the keys or values. Default is
   *     to only return the values.  This is being used by the for-in loop (true)
   *     and the for-each-in loop (false).  Even though the param gives a hint
   *     about what the iterator will return there is no guarantee that it will
   *     return the keys when true is passed.
   * @return {!goog.iter.Iterator} The object itself.
   */
  goog.iter.Iterator.prototype.__iterator__ = function(opt_keys) {
    return this;
  };
  
  
  /**
   * Returns an iterator that knows how to iterate over the values in the object.
   * @param {goog.iter.Iterable} iterable  If the object is an iterator it
   *     will be returned as is.  If the object has a {@code __iterator__} method
   *     that will be called to get the value iterator.  If the object is an
   *     array-like object we create an iterator for that.
   * @return {!goog.iter.Iterator} An iterator that knows how to iterate over the
   *     values in {@code iterable}.
   */
  goog.iter.toIterator = function(iterable) {
    if (iterable instanceof goog.iter.Iterator) {
      return iterable;
    }
    if (typeof iterable.__iterator__ == 'function') {
      return iterable.__iterator__(false);
    }
    if (goog.isArrayLike(iterable)) {
      var i = 0;
      var newIter = new goog.iter.Iterator;
      newIter.next = function() {
        while (true) {
          if (i >= iterable.length) {
            throw goog.iter.StopIteration;
          }
          // Don't include deleted elements.
          if (!(i in iterable)) {
            i++;
            continue;
          }
          return iterable[i++];
        }
      };
      return newIter;
    }
  
  
    // TODO(user): Should we fall back on goog.structs.getValues()?
    throw Error('Not implemented');
  };
  
  
  /**
   * Calls a function for each element in the iterator with the element of the
   * iterator passed as argument.
   *
   * @param {goog.iter.Iterable} iterable  The iterator to iterate
   *     over.  If the iterable is an object {@code toIterator} will be called on
   *     it.
   * @param {Function} f  The function to call for every element.  This function
   *     takes 3 arguments (the element, undefined, and the iterator) and the
   *     return value is irrelevant.  The reason for passing undefined as the
   *     second argument is so that the same function can be used in
   *     {@see goog.array#forEach} as well as others.
   * @param {Object=} opt_obj  The object to be used as the value of 'this' within
   *     {@code f}.
   */
  goog.iter.forEach = function(iterable, f, opt_obj) {
    if (goog.isArrayLike(iterable)) {
      /** @preserveTry */
      try {
        goog.array.forEach((/** @type {goog.array.ArrayLike} */ iterable), f,
                           opt_obj);
      } catch (ex) {
        if (ex !== goog.iter.StopIteration) {
          throw ex;
        }
      }
    } else {
      iterable = goog.iter.toIterator(iterable);
      /** @preserveTry */
      try {
        while (true) {
          f.call(opt_obj, iterable.next(), undefined, iterable);
        }
      } catch (ex) {
        if (ex !== goog.iter.StopIteration) {
          throw ex;
        }
      }
    }
  };
  
  
  /**
   * Calls a function for every element in the iterator, and if the function
   * returns true adds the element to a new iterator.
   *
   * @param {goog.iter.Iterable} iterable The iterator to iterate over.
   * @param {Function} f The function to call for every element.  This function
   *     takes 3 arguments (the element, undefined, and the iterator) and should
   *     return a boolean.  If the return value is true the element will be
   *     included  in the returned iteror.  If it is false the element is not
   *     included.
   * @param {Object=} opt_obj The object to be used as the value of 'this' within
   *     {@code f}.
   * @return {!goog.iter.Iterator} A new iterator in which only elements that
   *     passed the test are present.
   */
  goog.iter.filter = function(iterable, f, opt_obj) {
    iterable = goog.iter.toIterator(iterable);
    var newIter = new goog.iter.Iterator;
    newIter.next = function() {
      while (true) {
        var val = iterable.next();
        if (f.call(opt_obj, val, undefined, iterable)) {
          return val;
        }
      }
    };
    return newIter;
  };
  
  
  /**
   * Creates a new iterator that returns the values in a range.  This function
   * can take 1, 2 or 3 arguments:
   * <pre>
   * range(5) same as range(0, 5, 1)
   * range(2, 5) same as range(2, 5, 1)
   * </pre>
   *
   * @param {number} startOrStop  The stop value if only one argument is provided.
   *     The start value if 2 or more arguments are provided.  If only one
   *     argument is used the start value is 0.
   * @param {number=} opt_stop  The stop value.  If left out then the first
   *     argument is used as the stop value.
   * @param {number=} opt_step  The number to increment with between each call to
   *     next.  This can be negative.
   * @return {!goog.iter.Iterator} A new iterator that returns the values in the
   *     range.
   */
  goog.iter.range = function(startOrStop, opt_stop, opt_step) {
    var start = 0;
    var stop = startOrStop;
    var step = opt_step || 1;
    if (arguments.length > 1) {
      start = startOrStop;
      stop = opt_stop;
    }
    if (step == 0) {
      throw Error('Range step argument must not be zero');
    }
  
    var newIter = new goog.iter.Iterator;
    newIter.next = function() {
      if (step > 0 && start >= stop || step < 0 && start <= stop) {
        throw goog.iter.StopIteration;
      }
      var rv = start;
      start += step;
      return rv;
    };
    return newIter;
  };
  
  
  /**
   * Joins the values in a iterator with a delimiter.
   * @param {goog.iter.Iterable} iterable  The iterator to get the values from.
   * @param {string} deliminator  The text to put between the values.
   * @return {string} The joined value string.
   */
  goog.iter.join = function(iterable, deliminator) {
    return goog.iter.toArray(iterable).join(deliminator);
  };
  
  
  /**
   * For every element in the iterator call a function and return a new iterator
   * with that value.
   *
   * @param {goog.iter.Iterable} iterable The iterator to iterate over.
   * @param {Function} f The function to call for every element.  This function
   *     takes 3 arguments (the element, undefined, and the iterator) and should
   *     return a new value.
   * @param {Object=} opt_obj The object to be used as the value of 'this' within
   *     {@code f}.
   * @return {!goog.iter.Iterator} A new iterator that returns the results of
   *     applying the function to each element in the original iterator.
   */
  goog.iter.map = function(iterable, f, opt_obj) {
    iterable = goog.iter.toIterator(iterable);
    var newIter = new goog.iter.Iterator;
    newIter.next = function() {
      while (true) {
        var val = iterable.next();
        return f.call(opt_obj, val, undefined, iterable);
      }
    };
    return newIter;
  };
  
  
  /**
   * Passes every element of an iterator into a function and accumulates the
   * result.
   *
   * @param {goog.iter.Iterable} iterable The iterator to iterate over.
   * @param {Function} f The function to call for every element. This function
   *     takes 2 arguments (the function's previous result or the initial value,
   *     and the value of the current element).
   *     function(previousValue, currentElement) : newValue.
   * @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 iterator.
   */
  goog.iter.reduce = function(iterable, f, val, opt_obj) {
    var rval = val;
    goog.iter.forEach(iterable, function(val) {
      rval = f.call(opt_obj, rval, val);
    });
    return rval;
  };
  
  
  /**
   * Goes through the values in the iterator. Calls f for each these and if any of
   * them returns true, this returns true (without checking the rest). If all
   * return false this will return false.
   *
   * @param {goog.iter.Iterable} iterable  The iterator object.
   * @param {Function} f  The function to call for every value. This function
   *     takes 3 arguments (the value, undefined, and the iterator) and should
   *     return a boolean.
   * @param {Object=} opt_obj The object to be used as the value of 'this' within
   *     {@code f}.
   * @return {boolean} true if any value passes the test.
   */
  goog.iter.some = function(iterable, f, opt_obj) {
    iterable = goog.iter.toIterator(iterable);
    /** @preserveTry */
    try {
      while (true) {
        if (f.call(opt_obj, iterable.next(), undefined, iterable)) {
          return true;
        }
      }
    } catch (ex) {
      if (ex !== goog.iter.StopIteration) {
        throw ex;
      }
    }
    return false;
  };
  
  
  /**
   * Goes through the values in the iterator. Calls f for each these and if any of
   * them returns false this returns false (without checking the rest). If all
   * return true this will return true.
   *
   * @param {goog.iter.Iterable} iterable  The iterator object.
   * @param {Function} f  The function to call for every value. This function
   *     takes 3 arguments (the value, undefined, and the iterator) and should
   *     return a boolean.
   * @param {Object=} opt_obj The object to be used as the value of 'this' within
   *     {@code f}.
   * @return {boolean} true if every value passes the test.
   */
  goog.iter.every = function(iterable, f, opt_obj) {
    iterable = goog.iter.toIterator(iterable);
    /** @preserveTry */
    try {
      while (true) {
        if (!f.call(opt_obj, iterable.next(), undefined, iterable)) {
          return false;
        }
      }
    } catch (ex) {
      if (ex !== goog.iter.StopIteration) {
        throw ex;
      }
    }
    return true;
  };
  
  
  /**
   * Takes zero or more iterators and returns one iterator that will iterate over
   * them in the order chained.
   * @param {...goog.iter.Iterator} var_args  Any number of iterator objects.
   * @return {!goog.iter.Iterator} Returns a new iterator that will iterate over
   *     all the given iterators' contents.
   */
  goog.iter.chain = function(var_args) {
    var args = arguments;
    var length = args.length;
    var i = 0;
    var newIter = new goog.iter.Iterator;
  
    /**
     * @return {*} The next item in the iteration.
     * @this {goog.iter.Iterator}
     */
    newIter.next = function() {
      /** @preserveTry */
      try {
        if (i >= length) {
          throw goog.iter.StopIteration;
        }
        var current = goog.iter.toIterator(args[i]);
        return current.next();
      } catch (ex) {
        if (ex !== goog.iter.StopIteration || i >= length) {
          throw ex;
        } else {
          // In case we got a StopIteration increment counter and try again.
          i++;
          return this.next();
        }
      }
    };
  
    return newIter;
  };
  
  
  /**
   * Builds a new iterator that iterates over the original, but skips elements as
   * long as a supplied function returns true.
   * @param {goog.iter.Iterable} iterable  The iterator object.
   * @param {Function} f  The function to call for every value. This function
   *     takes 3 arguments (the value, undefined, and the iterator) and should
   *     return a boolean.
   * @param {Object=} opt_obj The object to be used as the value of 'this' within
   *     {@code f}.
   * @return {!goog.iter.Iterator} A new iterator that drops elements from the
   *     original iterator as long as {@code f} is true.
   */
  goog.iter.dropWhile = function(iterable, f, opt_obj) {
    iterable = goog.iter.toIterator(iterable);
    var newIter = new goog.iter.Iterator;
    var dropping = true;
    newIter.next = function() {
      while (true) {
        var val = iterable.next();
        if (dropping && f.call(opt_obj, val, undefined, iterable)) {
          continue;
        } else {
          dropping = false;
        }
        return val;
      }
    };
    return newIter;
  };
  
  
  /**
   * Builds a new iterator that iterates over the original, but only as long as a
   * supplied function returns true.
   * @param {goog.iter.Iterable} iterable  The iterator object.
   * @param {Function} f  The function to call for every value. This function
   *     takes 3 arguments (the value, undefined, and the iterator) and should
   *     return a boolean.
   * @param {Object=} opt_obj This is used as the 'this' object in f when called.
   * @return {!goog.iter.Iterator} A new iterator that keeps elements in the
   *     original iterator as long as the function is true.
   */
  goog.iter.takeWhile = function(iterable, f, opt_obj) {
    iterable = goog.iter.toIterator(iterable);
    var newIter = new goog.iter.Iterator;
    var taking = true;
    newIter.next = function() {
      while (true) {
        if (taking) {
          var val = iterable.next();
          if (f.call(opt_obj, val, undefined, iterable)) {
            return val;
          } else {
            taking = false;
          }
        } else {
          throw goog.iter.StopIteration;
        }
      }
    };
    return newIter;
  };
  
  
  /**
   * Converts the iterator to an array
   * @param {goog.iter.Iterable} iterable  The iterator to convert to an array.
   * @return {!Array} An array of the elements the iterator iterates over.
   */
  goog.iter.toArray = function(iterable) {
    // Fast path for array-like.
    if (goog.isArrayLike(iterable)) {
      return goog.array.toArray((/** @type {!goog.array.ArrayLike} */ iterable));
    }
    iterable = goog.iter.toIterator(iterable);
    var array = [];
    goog.iter.forEach(iterable, function(val) {
      array.push(val);
    });
    return array;
  };
  
  
  /**
   * Iterates over 2 iterators and returns true if they contain the same sequence
   * of elements and have the same length.
   * @param {goog.iter.Iterable} iterable1  The first iterable object.
   * @param {goog.iter.Iterable} iterable2  The second iterable object.
   * @return {boolean} true if the iterators contain the same sequence of
   *     elements and have the same length.
   */
  goog.iter.equals = function(iterable1, iterable2) {
    iterable1 = goog.iter.toIterator(iterable1);
    iterable2 = goog.iter.toIterator(iterable2);
    var b1, b2;
    /** @preserveTry */
    try {
      while (true) {
        b1 = b2 = false;
        var val1 = iterable1.next();
        b1 = true;
        var val2 = iterable2.next();
        b2 = true;
        if (val1 != val2) {
          return false;
        }
      }
    } catch (ex) {
      if (ex !== goog.iter.StopIteration) {
        throw ex;
      } else {
        if (b1 && !b2) {
          // iterable1 done but iterable2 is not done.
          return false;
        }
        if (!b2) {
          /** @preserveTry */
          try {
            // iterable2 not done?
            val2 = iterable2.next();
            // iterable2 not done but iterable1 is done
            return false;
          } catch (ex1) {
            if (ex1 !== goog.iter.StopIteration) {
              throw ex1;
            }
            // iterable2 done as well... They are equal
            return true;
          }
        }
      }
    }
    return false;
  };
  
  
  /**
   * Advances the iterator to the next position, returning the given default value
   * instead of throwing an exception if the iterator has no more entries.
   * @param {goog.iter.Iterable} iterable The iterable object.
   * @param {*} defaultValue The value to return if the iterator is empty.
   * @return {*} The next item in the iteration, or defaultValue if the iterator
   *     was empty.
   */
  goog.iter.nextOrValue = function(iterable, defaultValue) {
    try {
      return goog.iter.toIterator(iterable).next();
    } catch (e) {
      if (e != goog.iter.StopIteration) {
        throw e;
      }
      return defaultValue;
    }
  };
  
  
  /**
   * Cartesian product of zero or more sets.  Gives an iterator that gives every
   * combination of one element chosen from each set.  For example,
   * ([1, 2], [3, 4]) gives ([1, 3], [1, 4], [2, 3], [2, 4]).
   * @see http://docs.python.org/library/itertools.html#itertools.product
   * @param {...!goog.array.ArrayLike.<*>} var_args Zero or more sets, as arrays.
   * @return {!goog.iter.Iterator} An iterator that gives each n-tuple (as an
   *     array).
   */
  goog.iter.product = function(var_args) {
    var someArrayEmpty = goog.array.some(arguments, function(arr) {
      return !arr.length;
    });
  
    // An empty set in a cartesian product gives an empty set.
    if (someArrayEmpty || !arguments.length) {
      return new goog.iter.Iterator();
    }
  
    var iter = new goog.iter.Iterator();
    var arrays = arguments;
  
    // The first indicies are [0, 0, ...]
    var indicies = goog.array.repeat(0, arrays.length);
  
    iter.next = function() {
  
      if (indicies) {
        var retVal = goog.array.map(indicies, function(valueIndex, arrayIndex) {
          return arrays[arrayIndex][valueIndex];
        });
  
        // Generate the next-largest indicies for the next call.
        // Increase the rightmost index. If it goes over, increase the next
        // rightmost (like carry-over addition).
        for (var i = indicies.length - 1; i >= 0; i--) {
          // Assertion prevents compiler warning below.
          goog.asserts.assert(indicies);
          if (indicies[i] < arrays[i].length - 1) {
            indicies[i]++;
            break;
          }
  
          // We're at the last indicies (the last element of every array), so
          // the iteration is over on the next call.
          if (i == 0) {
            indicies = null;
            break;
          }
          // Reset the index in this column and loop back to increment the
          // next one.
          indicies[i] = 0;
        }
        return retVal;
      }
  
      throw goog.iter.StopIteration;
    };
  
    return iter;
  };
  // 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 Datastructure: Hash Map.
   *
   *
   * This file contains an implementation of a Map structure. It implements a lot
   * of the methods used in goog.structs so those functions work on hashes.  For
   * convenience with common usage the methods accept any type for the key, though
   * internally they will be cast to strings.
   */
  
  
  goog.provide('goog.structs.Map');
  
  goog.require('goog.iter.Iterator');
  goog.require('goog.iter.StopIteration');
  goog.require('goog.object');
  goog.require('goog.structs');
  
  
  
  /**
   * Class for Hash Map datastructure.
   * @param {*=} opt_map Map or Object to initialize the map with.
   * @param {...*} var_args If 2 or more arguments are present then they
   *     will be used as key-value pairs.
   * @constructor
   */
  goog.structs.Map = function(opt_map, var_args) {
  
    /**
     * Underlying JS object used to implement the map.
     * @type {!Object}
     * @private
     */
    this.map_ = {};
  
    /**
     * An array of keys. This is necessary for two reasons:
     *   1. Iterating the keys using for (var key in this.map_) allocates an
     *      object for every key in IE which is really bad for IE6 GC perf.
     *   2. Without a side data structure, we would need to escape all the keys
     *      as that would be the only way we could tell during iteration if the
     *      key was an internal key or a property of the object.
     *
     * This array can contain deleted keys so it's necessary to check the map
     * as well to see if the key is still in the map (this doesn't require a
     * memory allocation in IE).
     * @type {!Array.<string>}
     * @private
     */
    this.keys_ = [];
  
    var argLength = arguments.length;
  
    if (argLength > 1) {
      if (argLength % 2) {
        throw Error('Uneven number of arguments');
      }
      for (var i = 0; i < argLength; i += 2) {
        this.set(arguments[i], arguments[i + 1]);
      }
    } else if (opt_map) {
      this.addAll(/** @type {Object} */ (opt_map));
    }
  };
  
  
  /**
   * The number of key value pairs in the map.
   * @private
   * @type {number}
   */
  goog.structs.Map.prototype.count_ = 0;
  
  
  /**
   * Version used to detect changes while iterating.
   * @private
   * @type {number}
   */
  goog.structs.Map.prototype.version_ = 0;
  
  
  /**
   * @return {number} The number of key-value pairs in the map.
   */
  goog.structs.Map.prototype.getCount = function() {
    return this.count_;
  };
  
  
  /**
   * Returns the values of the map.
   * @return {!Array} The values in the map.
   */
  goog.structs.Map.prototype.getValues = function() {
    this.cleanupKeysArray_();
  
    var rv = [];
    for (var i = 0; i < this.keys_.length; i++) {
      var key = this.keys_[i];
      rv.push(this.map_[key]);
    }
    return rv;
  };
  
  
  /**
   * Returns the keys of the map.
   * @return {!Array.<string>} Array of string values.
   */
  goog.structs.Map.prototype.getKeys = function() {
    this.cleanupKeysArray_();
    return /** @type {!Array.<string>} */ (this.keys_.concat());
  };
  
  
  /**
   * Whether the map contains the given key.
   * @param {*} key The key to check for.
   * @return {boolean} Whether the map contains the key.
   */
  goog.structs.Map.prototype.containsKey = function(key) {
    return goog.structs.Map.hasKey_(this.map_, key);
  };
  
  
  /**
   * Whether the map contains the given value. This is O(n).
   * @param {*} val The value to check for.
   * @return {boolean} Whether the map contains the value.
   */
  goog.structs.Map.prototype.containsValue = function(val) {
    for (var i = 0; i < this.keys_.length; i++) {
      var key = this.keys_[i];
      if (goog.structs.Map.hasKey_(this.map_, key) && this.map_[key] == val) {
        return true;
      }
    }
    return false;
  };
  
  
  /**
   * Whether this map is equal to the argument map.
   * @param {goog.structs.Map} otherMap The map against which to test equality.
   * @param {function(*, *) : boolean=} opt_equalityFn Optional equality function
   *     to test equality of values. If not specified, this will test whether
   *     the values contained in each map are identical objects.
   * @return {boolean} Whether the maps are equal.
   */
  goog.structs.Map.prototype.equals = function(otherMap, opt_equalityFn) {
    if (this === otherMap) {
      return true;
    }
  
    if (this.count_ != otherMap.getCount()) {
      return false;
    }
  
    var equalityFn = opt_equalityFn || goog.structs.Map.defaultEquals;
  
    this.cleanupKeysArray_();
    for (var key, i = 0; key = this.keys_[i]; i++) {
      if (!equalityFn(this.get(key), otherMap.get(key))) {
        return false;
      }
    }
  
    return true;
  };
  
  
  /**
   * Default equality test for values.
   * @param {*} a The first value.
   * @param {*} b The second value.
   * @return {boolean} Whether a and b reference the same object.
   */
  goog.structs.Map.defaultEquals = function(a, b) {
    return a === b;
  };
  
  
  /**
   * @return {boolean} Whether the map is empty.
   */
  goog.structs.Map.prototype.isEmpty = function() {
    return this.count_ == 0;
  };
  
  
  /**
   * Removes all key-value pairs from the map.
   */
  goog.structs.Map.prototype.clear = function() {
    this.map_ = {};
    this.keys_.length = 0;
    this.count_ = 0;
    this.version_ = 0;
  };
  
  
  /**
   * Removes a key-value pair based on the key. This is O(logN) amortized due to
   * updating the keys array whenever the count becomes half the size of the keys
   * in the keys array.
   * @param {*} key  The key to remove.
   * @return {boolean} Whether object was removed.
   */
  goog.structs.Map.prototype.remove = function(key) {
    if (goog.structs.Map.hasKey_(this.map_, key)) {
      delete this.map_[key];
      this.count_--;
      this.version_++;
  
      // clean up the keys array if the threshhold is hit
      if (this.keys_.length > 2 * this.count_) {
        this.cleanupKeysArray_();
      }
  
      return true;
    }
    return false;
  };
  
  
  /**
   * Cleans up the temp keys array by removing entries that are no longer in the
   * map.
   * @private
   */
  goog.structs.Map.prototype.cleanupKeysArray_ = function() {
    if (this.count_ != this.keys_.length) {
      // First remove keys that are no longer in the map.
      var srcIndex = 0;
      var destIndex = 0;
      while (srcIndex < this.keys_.length) {
        var key = this.keys_[srcIndex];
        if (goog.structs.Map.hasKey_(this.map_, key)) {
          this.keys_[destIndex++] = key;
        }
        srcIndex++;
      }
      this.keys_.length = destIndex;
    }
  
    if (this.count_ != this.keys_.length) {
      // If the count still isn't correct, that means we have duplicates. This can
      // happen when the same key is added and removed multiple times. Now we have
      // to allocate one extra Object to remove the duplicates. This could have
      // been done in the first pass, but in the common case, we can avoid
      // allocating an extra object by only doing this when necessary.
      var seen = {};
      var srcIndex = 0;
      var destIndex = 0;
      while (srcIndex < this.keys_.length) {
        var key = this.keys_[srcIndex];
        if (!(goog.structs.Map.hasKey_(seen, key))) {
          this.keys_[destIndex++] = key;
          seen[key] = 1;
        }
        srcIndex++;
      }
      this.keys_.length = destIndex;
    }
  };
  
  
  /**
   * Returns the value for the given key.  If the key is not found and the default
   * value is not given this will return {@code undefined}.
   * @param {*} key The key to get the value for.
   * @param {*=} opt_val The value to return if no item is found for the given
   *     key, defaults to undefined.
   * @return {*} The value for the given key.
   */
  goog.structs.Map.prototype.get = function(key, opt_val) {
    if (goog.structs.Map.hasKey_(this.map_, key)) {
      return this.map_[key];
    }
    return opt_val;
  };
  
  
  /**
   * Adds a key-value pair to the map.
   * @param {*} key The key.
   * @param {*} value The value to add.
   */
  goog.structs.Map.prototype.set = function(key, value) {
    if (!(goog.structs.Map.hasKey_(this.map_, key))) {
      this.count_++;
      this.keys_.push(key);
      // Only change the version if we add a new key.
      this.version_++;
    }
    this.map_[key] = value;
  };
  
  
  /**
   * Adds multiple key-value pairs from another goog.structs.Map or Object.
   * @param {Object} map  Object containing the data to add.
   */
  goog.structs.Map.prototype.addAll = function(map) {
    var keys, values;
    if (map instanceof goog.structs.Map) {
      keys = map.getKeys();
      values = map.getValues();
    } else {
      keys = goog.object.getKeys(map);
      values = goog.object.getValues(map);
    }
    // we could use goog.array.forEach here but I don't want to introduce that
    // dependency just for this.
    for (var i = 0; i < keys.length; i++) {
      this.set(keys[i], values[i]);
    }
  };
  
  
  /**
   * Clones a map and returns a new map.
   * @return {!goog.structs.Map} A new map with the same key-value pairs.
   */
  goog.structs.Map.prototype.clone = function() {
    return new goog.structs.Map(this);
  };
  
  
  /**
   * Returns a new map in which all the keys and values are interchanged
   * (keys become values and values become keys). If multiple keys map to the
   * same value, the chosen transposed value is implementation-dependent.
   *
   * It acts very similarly to {goog.object.transpose(Object)}.
   *
   * @return {!goog.structs.Map} The transposed map.
   */
  goog.structs.Map.prototype.transpose = function() {
    var transposed = new goog.structs.Map();
    for (var i = 0; i < this.keys_.length; i++) {
      var key = this.keys_[i];
      var value = this.map_[key];
      transposed.set(value, key);
    }
  
    return transposed;
  };
  
  
  /**
   * @return {!Object} Object representation of the map.
   */
  goog.structs.Map.prototype.toObject = function() {
    this.cleanupKeysArray_();
    var obj = {};
    for (var i = 0; i < this.keys_.length; i++) {
      var key = this.keys_[i];
      obj[key] = this.map_[key];
    }
    return obj;
  };
  
  
  /**
   * Returns an iterator that iterates over the keys in the map.  Removal of keys
   * while iterating might have undesired side effects.
   * @return {!goog.iter.Iterator} An iterator over the keys in the map.
   */
  goog.structs.Map.prototype.getKeyIterator = function() {
    return this.__iterator__(true);
  };
  
  
  /**
   * Returns an iterator that iterates over the values in the map.  Removal of
   * keys while iterating might have undesired side effects.
   * @return {!goog.iter.Iterator} An iterator over the values in the map.
   */
  goog.structs.Map.prototype.getValueIterator = function() {
    return this.__iterator__(false);
  };
  
  
  /**
   * Returns an iterator that iterates over the values or the keys in the map.
   * This throws an exception if the map was mutated since the iterator was
   * created.
   * @param {boolean=} opt_keys True to iterate over the keys. False to iterate
   *     over the values.  The default value is false.
   * @return {!goog.iter.Iterator} An iterator over the values or keys in the map.
   */
  goog.structs.Map.prototype.__iterator__ = function(opt_keys) {
    // Clean up keys to minimize the risk of iterating over dead keys.
    this.cleanupKeysArray_();
  
    var i = 0;
    var keys = this.keys_;
    var map = this.map_;
    var version = this.version_;
    var selfObj = this;
  
    var newIter = new goog.iter.Iterator;
    newIter.next = function() {
      while (true) {
        if (version != selfObj.version_) {
          throw Error('The map has changed since the iterator was created');
        }
        if (i >= keys.length) {
          throw goog.iter.StopIteration;
        }
        var key = keys[i++];
        return opt_keys ? key : map[key];
      }
    };
    return newIter;
  };
  
  
  /**
   * Safe way to test for hasOwnProperty.  It even allows testing for
   * 'hasOwnProperty'.
   * @param {Object} obj The object to test for presence of the given key.
   * @param {*} key The key to check for.
   * @return {boolean} Whether the object has the key.
   * @private
   */
  goog.structs.Map.hasKey_ = function(obj, key) {
    return Object.prototype.hasOwnProperty.call(obj, key);
  };
  // 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 Datastructure: Set.
   *
   *
   * This class implements a set data structure. Adding and removing is O(1). It
   * supports both object and primitive values. Be careful because you can add
   * both 1 and new Number(1), because these are not the same. You can even add
   * multiple new Number(1) because these are not equal.
   */
  
  
  goog.provide('goog.structs.Set');
  
  goog.require('goog.structs');
  goog.require('goog.structs.Map');
  
  
  
  /**
   * A set that can contain both primitives and objects.  Adding and removing
   * elements is O(1).  Primitives are treated as identical if they have the same
   * type and convert to the same string.  Objects are treated as identical only
   * if they are references to the same object.  WARNING: A goog.structs.Set can
   * contain both 1 and (new Number(1)), because they are not the same.  WARNING:
   * Adding (new Number(1)) twice will yield two distinct elements, because they
   * are two different objects.  WARNING: Any object that is added to a
   * goog.structs.Set will be modified!  Because goog.getUid() is used to
   * identify objects, every object in the set will be mutated.
   * @param {Array|Object=} opt_values Initial values to start with.
   * @constructor
   */
  goog.structs.Set = function(opt_values) {
    this.map_ = new goog.structs.Map;
    if (opt_values) {
      this.addAll(opt_values);
    }
  };
  
  
  /**
   * Obtains a unique key for an element of the set.  Primitives will yield the
   * same key if they have the same type and convert to the same string.  Object
   * references will yield the same key only if they refer to the same object.
   * @param {*} val Object or primitive value to get a key for.
   * @return {string} A unique key for this value/object.
   * @private
   */
  goog.structs.Set.getKey_ = function(val) {
    var type = typeof val;
    if (type == 'object' && val || type == 'function') {
      return 'o' + goog.getUid(/** @type {Object} */ (val));
    } else {
      return type.substr(0, 1) + val;
    }
  };
  
  
  /**
   * @return {number} The number of elements in the set.
   */
  goog.structs.Set.prototype.getCount = function() {
    return this.map_.getCount();
  };
  
  
  /**
   * Add a primitive or an object to the set.
   * @param {*} element The primitive or object to add.
   */
  goog.structs.Set.prototype.add = function(element) {
    this.map_.set(goog.structs.Set.getKey_(element), element);
  };
  
  
  /**
   * Adds all the values in the given collection to this set.
   * @param {Array|Object} col A collection containing the elements to add.
   */
  goog.structs.Set.prototype.addAll = function(col) {
    var values = goog.structs.getValues(col);
    var l = values.length;
    for (var i = 0; i < l; i++) {
      this.add(values[i]);
    }
  };
  
  
  /**
   * Removes all values in the given collection from this set.
   * @param {Array|Object} col A collection containing the elements to remove.
   */
  goog.structs.Set.prototype.removeAll = function(col) {
    var values = goog.structs.getValues(col);
    var l = values.length;
    for (var i = 0; i < l; i++) {
      this.remove(values[i]);
    }
  };
  
  
  /**
   * Removes the given element from this set.
   * @param {*} element The primitive or object to remove.
   * @return {boolean} Whether the element was found and removed.
   */
  goog.structs.Set.prototype.remove = function(element) {
    return this.map_.remove(goog.structs.Set.getKey_(element));
  };
  
  
  /**
   * Removes all elements from this set.
   */
  goog.structs.Set.prototype.clear = function() {
    this.map_.clear();
  };
  
  
  /**
   * Tests whether this set is empty.
   * @return {boolean} True if there are no elements in this set.
   */
  goog.structs.Set.prototype.isEmpty = function() {
    return this.map_.isEmpty();
  };
  
  
  /**
   * Tests whether this set contains the given element.
   * @param {*} element The primitive or object to test for.
   * @return {boolean} True if this set contains the given element.
   */
  goog.structs.Set.prototype.contains = function(element) {
    return this.map_.containsKey(goog.structs.Set.getKey_(element));
  };
  
  
  /**
   * Tests whether this set contains all the values in a given collection.
   * Repeated elements in the collection are ignored, e.g.  (new
   * goog.structs.Set([1, 2])).containsAll([1, 1]) is True.
   * @param {Object} col A collection-like object.
   * @return {boolean} True if the set contains all elements.
   */
  goog.structs.Set.prototype.containsAll = function(col) {
    return goog.structs.every(col, this.contains, this);
  };
  
  
  /**
   * Finds all values that are present in both this set and the given collection.
   * @param {Array|Object} col A collection.
   * @return {goog.structs.Set} A new set containing all the values (primitives
   *     or objects) present in both this set and the given collection.
   */
  goog.structs.Set.prototype.intersection = function(col) {
    var result = new goog.structs.Set();
  
    var values = goog.structs.getValues(col);
    for (var i = 0; i < values.length; i++) {
      var value = values[i];
      if (this.contains(value)) {
        result.add(value);
      }
    }
  
    return result;
  };
  
  
  /**
   * Returns an array containing all the elements in this set.
   * @return {Array} An array containing all the elements in this set.
   */
  goog.structs.Set.prototype.getValues = function() {
    return this.map_.getValues();
  };
  
  
  /**
   * Creates a shallow clone of this set.
   * @return {goog.structs.Set} A new set containing all the same elements as
   *     this set.
   */
  goog.structs.Set.prototype.clone = function() {
    return new goog.structs.Set(this);
  };
  
  
  /**
   * Tests whether the given collection consists of the same elements as this set,
   * regardless of order, without repetition.  Primitives are treated as equal if
   * they have the same type and convert to the same string; objects are treated
   * as equal if they are references to the same object.  This operation is O(n).
   * @param {Object} col A collection.
   * @return {boolean} True if the given collection consists of the same elements
   *     as this set, regardless of order, without repetition.
   */
  goog.structs.Set.prototype.equals = function(col) {
    return this.getCount() == goog.structs.getCount(col) && this.isSubsetOf(col);
  };
  
  
  /**
   * Tests whether the given collection contains all the elements in this set.
   * Primitives are treated as equal if they have the same type and convert to the
   * same string; objects are treated as equal if they are references to the same
   * object.  This operation is O(n).
   * @param {Object} col A collection.
   * @return {boolean} True if this set is a subset of the given collection.
   */
  goog.structs.Set.prototype.isSubsetOf = function(col) {
    var colCount = goog.structs.getCount(col);
    if (this.getCount() > colCount) {
      return false;
    }
    // TODO(user) Find the minimal collection size where the conversion makes
    // the contains() method faster.
    if (!(col instanceof goog.structs.Set) && colCount > 5) {
      // Convert to a goog.structs.Set so that goog.structs.contains runs in
      // O(1) time instead of O(n) time.
      col = new goog.structs.Set(col);
    }
    return goog.structs.every(this, function(value) {
      return goog.structs.contains(col, value);
    });
  };
  
  
  /**
   * Returns an iterator that iterates over the elements in this set.
   * @param {boolean=} opt_keys This argument is ignored.
   * @return {goog.iter.Iterator} An iterator over the elements in this set.
   */
  goog.structs.Set.prototype.__iterator__ = function(opt_keys) {
    return this.map_.__iterator__(false);
  };
  // Copyright 2005 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 Implements the disposable interface. The dispose method is used
   * to clean up references and resources.
   */
  
  
  goog.provide('goog.Disposable');
  goog.provide('goog.dispose');
  
  
  
  /**
   * Class that provides the basic implementation for disposable objects. If your
   * class holds one or more references to COM objects, DOM nodes, or other
   * disposable objects, it should extend this class or implement the disposable
   * interface.
   * @constructor
   */
  goog.Disposable = function() {
    if (goog.Disposable.ENABLE_MONITORING) {
      goog.Disposable.instances_[goog.getUid(this)] = this;
    }
  };
  
  
  /**
   * @define {boolean} Whether to enable the monitoring of the goog.Disposable
   *     instances. Switching on the monitoring is only recommended for debugging
   *     because it has a significant impact on performance and memory usage.
   *     If switched off, the monitoring code compiles down to 0 bytes.
   *     The monitoring expects that all disposable objects call the
   *     {@code goog.Disposable} base constructor.
   */
  goog.Disposable.ENABLE_MONITORING = false;
  
  
  /**
   * Maps the unique ID of every undisposed {@code goog.Disposable} object to
   * the object itself.
   * @type {!Object.<number, !goog.Disposable>}
   * @private
   */
  goog.Disposable.instances_ = {};
  
  
  /**
   * @return {!Array.<!goog.Disposable>} All {@code goog.Disposable} objects that
   *     haven't been disposed of.
   */
  goog.Disposable.getUndisposedObjects = function() {
    var ret = [];
    for (var id in goog.Disposable.instances_) {
      if (goog.Disposable.instances_.hasOwnProperty(id)) {
        ret.push(goog.Disposable.instances_[Number(id)]);
      }
    }
    return ret;
  };
  
  
  /**
   * Clears the registry of undisposed objects but doesn't dispose of them.
   */
  goog.Disposable.clearUndisposedObjects = function() {
    goog.Disposable.instances_ = {};
  };
  
  
  /**
   * Whether the object has been disposed of.
   * @type {boolean}
   * @private
   */
  goog.Disposable.prototype.disposed_ = false;
  
  
  /**
   * @return {boolean} Whether the object has been disposed of.
   */
  goog.Disposable.prototype.isDisposed = function() {
    return this.disposed_;
  };
  
  
  /**
   * @return {boolean} Whether the object has been disposed of.
   * @deprecated Use {@link #isDisposed} instead.
   */
  goog.Disposable.prototype.getDisposed = goog.Disposable.prototype.isDisposed;
  
  
  /**
   * Disposes of the object. If the object hasn't already been disposed of, calls
   * {@link #disposeInternal}. Classes that extend {@code goog.Disposable} should
   * override {@link #disposeInternal} in order to delete references to COM
   * objects, DOM nodes, and other disposable objects.
   *
   * @return {void} Nothing.
   */
  goog.Disposable.prototype.dispose = function() {
    if (!this.disposed_) {
      // Set disposed_ to true first, in case during the chain of disposal this
      // gets disposed recursively.
      this.disposed_ = true;
      this.disposeInternal();
      if (goog.Disposable.ENABLE_MONITORING) {
        var uid = goog.getUid(this);
        if (!goog.Disposable.instances_.hasOwnProperty(uid)) {
          throw Error(this + ' did not call the goog.Disposable base ' +
              'constructor or was disposed of after a clearUndisposedObjects ' +
              'call');
        }
        delete goog.Disposable.instances_[uid];
      }
    }
  };
  
  
  /**
   * Deletes or nulls out any references to COM objects, DOM nodes, or other
   * disposable objects. Classes that extend {@code goog.Disposable} should
   * override this method.  For example:
   * <pre>
   *   mypackage.MyClass = function() {
   *     goog.Disposable.call(this);
   *     // Constructor logic specific to MyClass.
   *     ...
   *   };
   *   goog.inherits(mypackage.MyClass, goog.Disposable);
   *
   *   mypackage.MyClass.prototype.disposeInternal = function() {
   *     mypackage.MyClass.superClass_.disposeInternal.call(this);
   *     // Dispose logic specific to MyClass.
   *     ...
   *   };
   * </pre>
   * @protected
   */
  goog.Disposable.prototype.disposeInternal = function() {
    // No-op in the base class.
  };
  
  
  /**
   * Calls {@code dispose} on the argument if it supports it. If obj is not an
   *     object with a dispose() method, this is a no-op.
   * @param {*} obj The object to dispose of.
   */
  goog.dispose = function(obj) {
    if (obj && typeof obj.dispose == 'function') {
      obj.dispose();
    }
  };
  // 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 Datastructure: Pool.
   *
   *
   * A generic class for handling pools of objects.
   * When an object is released, it is attempted to be reused.
   */
  
  
  goog.provide('goog.structs.Pool');
  
  goog.require('goog.Disposable');
  goog.require('goog.structs.Queue');
  goog.require('goog.structs.Set');
  
  
  
  /**
   * A generic pool class. If max is greater than min, an error is thrown.
   * @param {number=} opt_minCount Min. number of objects (Default: 1).
   * @param {number=} opt_maxCount Max. number of objects (Default: 10).
   * @constructor
   * @extends {goog.Disposable}
   */
  goog.structs.Pool = function(opt_minCount, opt_maxCount) {
    goog.Disposable.call(this);
  
    /**
     * Minimum number of objects allowed
     * @type {number}
     * @private
     */
    this.minCount_ = opt_minCount || 0;
  
    /**
     * Maximum number of objects allowed
     * @type {number}
     * @private
     */
    this.maxCount_ = opt_maxCount || 10;
  
    // Make sure that the max and min constraints are valid.
    if (this.minCount_ > this.maxCount_) {
      throw Error(goog.structs.Pool.ERROR_MIN_MAX_);
    }
  
    /**
     * Set used to store objects that are currently in the pool and available
     * to be used.
     * @type {goog.structs.Queue}
     * @private
     */
    this.freeQueue_ = new goog.structs.Queue();
  
    /**
     * Set used to store objects that are currently in the pool and in use.
     * @type {goog.structs.Set}
     * @private
     */
    this.inUseSet_ = new goog.structs.Set();
  
    // Make sure that the minCount constraint is satisfied.
    this.adjustForMinMax();
  
  
    // TODO(user): Remove once JSCompiler's undefined properties warnings
    // don't error for guarded properties.
    var magicProps = {canBeReused: 0};
  };
  goog.inherits(goog.structs.Pool, goog.Disposable);
  
  
  /**
   * Error to throw when the max/min constraint is attempted to be invalidated.
   * I.e., when it is attempted for maxCount to be less than minCount.
   * @type {string}
   * @private
   */
  goog.structs.Pool.ERROR_MIN_MAX_ =
      '[goog.structs.Pool] Min can not be greater than max';
  
  
  /**
   * Error to throw when the Pool is attempted to be disposed and it is asked to
   * make sure that there are no objects that are in use (i.e., haven't been
   * released).
   * @type {string}
   * @private
   */
  goog.structs.Pool.ERROR_DISPOSE_UNRELEASED_OBJS_ =
      '[goog.structs.Pool] Objects not released';
  
  
  /**
   * Sets the minimum count of the pool.
   * If min is greater than the max count of the pool, an error is thrown.
   * @param {number} min The minimum count of the pool.
   */
  goog.structs.Pool.prototype.setMinimumCount = function(min) {
    // Check count constraints.
    if (min > this.maxCount_) {
      throw Error(goog.structs.Pool.ERROR_MIN_MAX_);
    }
    this.minCount_ = min;
  
    // Adjust the objects in the pool as needed.
    this.adjustForMinMax();
  };
  
  
  /**
   * Sets the maximum count of the pool.
   * If max is less than the max count of the pool, an error is thrown.
   * @param {number} max The maximium count of the pool.
   */
  goog.structs.Pool.prototype.setMaximumCount = function(max) {
    // Check count constraints.
    if (max < this.minCount_) {
      throw Error(goog.structs.Pool.ERROR_MIN_MAX_);
    }
    this.maxCount_ = max;
  
    // Adjust the objects in the pool as needed.
    this.adjustForMinMax();
  };
  
  
  /**
   * @return {Object|undefined} A new object from the pool if there is one
   *     available, otherwise undefined.
   */
  goog.structs.Pool.prototype.getObject = function() {
    var obj = this.removeFreeObject_();
    if (obj) {
      this.inUseSet_.add(obj);
    }
  
    return obj;
  };
  
  
  /**
   * Returns an object to the pool of available objects so that it can be reused.
   * @param {Object} obj The object to return to the pool of free objects.
   * @return {boolean} Whether the object was found in the Pool's set of in-use
   *     objects (in other words, whether any action was taken).
   */
  goog.structs.Pool.prototype.releaseObject = function(obj) {
    if (this.inUseSet_.remove(obj)) {
      this.addFreeObject(obj);
      return true;
    }
    return false;
  };
  
  
  /**
   * Removes a free object from the collection of objects that are free so that it
   * can be used.
   *
   * NOTE: This method does not mark the returned object as in use.
   *
   * @return {Object|undefined} The object removed from the free collection, if
   *     there is one available. Otherwise, undefined.
   * @private
   */
  goog.structs.Pool.prototype.removeFreeObject_ = function() {
    var obj;
    while (this.getFreeCount() > 0) {
      obj = /** @type {Object} */(this.freeQueue_.dequeue());
  
      if (!this.objectCanBeReused(obj)) {
        this.adjustForMinMax();
      } else {
        break;
      }
    }
  
    if (!obj && this.getCount() < this.maxCount_) {
      obj = this.createObject();
    }
  
    return obj;
  };
  
  
  /**
   * Adds an object to the collection of objects that are free. If the object can
   * not be added, then it is disposed.
   *
   * @param {Object} obj The object to add to collection of free objects.
   */
  goog.structs.Pool.prototype.addFreeObject = function(obj) {
    this.inUseSet_.remove(obj);
    if (this.objectCanBeReused(obj) && this.getCount() < this.maxCount_) {
      this.freeQueue_.enqueue(obj);
    } else {
      this.disposeObject(obj);
    }
  };
  
  
  /**
   * Adjusts the objects held in the pool to be within the min/max constraints.
   *
   * NOTE: It is possible that the number of objects in the pool will still be
   * greater than the maximum count of objects allowed. This will be the case
   * if no more free objects can be disposed of to get below the minimum count
   * (i.e., all objects are in use).
   */
  goog.structs.Pool.prototype.adjustForMinMax = function() {
    var freeQueue = this.freeQueue_;
  
    // Make sure the at least the minimum number of objects are created.
    while (this.getCount() < this.minCount_) {
      freeQueue.enqueue(this.createObject());
    }
  
    // Make sure no more than the maximum number of objects are created.
    while (this.getCount() > this.maxCount_ && this.getFreeCount() > 0) {
      this.disposeObject(/** @type {Object} */(freeQueue.dequeue()));
    }
  };
  
  
  /**
   * Should be overriden by sub-classes to return an instance of the object type
   * that is expected in the pool.
   * @return {Object} The created object.
   */
  goog.structs.Pool.prototype.createObject = function() {
    return {};
  };
  
  
  /**
   * Should be overriden to dispose of an object. Default implementation is to
   * remove all its members, which should render it useless. Calls the object's
   * {@code dispose()} method, if available.
   * @param {Object} obj The object to dispose.
   */
  goog.structs.Pool.prototype.disposeObject = function(obj) {
    if (typeof obj.dispose == 'function') {
      obj.dispose();
    } else {
      for (var i in obj) {
        obj[i] = null;
      }
    }
  };
  
  
  /**
   * Should be overriden to determine whether an object has become unusable and
   * should not be returned by getObject(). Calls the object's
   * {@code canBeReused()}  method, if available.
   * @param {Object} obj The object to test.
   * @return {boolean} Whether the object can be reused.
   */
  goog.structs.Pool.prototype.objectCanBeReused = function(obj) {
    if (typeof obj.canBeReused == 'function') {
      return obj.canBeReused();
    }
    return true;
  };
  
  
  /**
   * Returns true if the given object is in the pool.
   * @param {Object} obj The object to check the pool for.
   * @return {boolean} Whether the pool contains the object.
   */
  goog.structs.Pool.prototype.contains = function(obj) {
    return this.freeQueue_.contains(obj) || this.inUseSet_.contains(obj);
  };
  
  
  /**
   * Returns the number of objects currently in the pool.
   * @return {number} Number of objects currently in the pool.
   */
  goog.structs.Pool.prototype.getCount = function() {
    return this.freeQueue_.getCount() + this.inUseSet_.getCount();
  };
  
  
  /**
   * Returns the number of objects currently in use in the pool.
   * @return {number} Number of objects currently in use in the pool.
   */
  goog.structs.Pool.prototype.getInUseCount = function() {
    return this.inUseSet_.getCount();
  };
  
  
  /**
   * Returns the number of objects currently free in the pool.
   * @return {number} Number of objects currently free in the pool.
   */
  goog.structs.Pool.prototype.getFreeCount = function() {
    return this.freeQueue_.getCount();
  };
  
  
  /**
   * Determines if the pool contains no objects.
   * @return {boolean} Whether the pool contains no objects.
   */
  goog.structs.Pool.prototype.isEmpty = function() {
    return this.freeQueue_.isEmpty() && this.inUseSet_.isEmpty();
  };
  
  
  /**
   * Disposes of the pool and all objects currently held in the pool.
   */
  goog.structs.Pool.prototype.disposeInternal = function() {
    goog.structs.Pool.superClass_.disposeInternal.call(this);
    if (this.getInUseCount() > 0) {
      throw Error(goog.structs.Pool.ERROR_DISPOSE_UNRELEASED_OBJS_);
    }
    delete this.inUseSet_;
  
    // Call disposeObject on each object held by the pool.
    var freeQueue = this.freeQueue_;
    while (!freeQueue.isEmpty()) {
      this.disposeObject(/** @type {Object} */ (freeQueue.dequeue()));
    }
    delete this.freeQueue_;
  };
  // 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 Generic immutable node object to be used in collections.
   *
   */
  
  
  goog.provide('goog.structs.Node');
  
  
  
  /**
   * A generic immutable node. This can be used in various collections that
   * require a node object for its item (such as a heap).
   * @param {*} key Key.
   * @param {*} value Vaue.
   * @constructor
   */
  goog.structs.Node = function(key, value) {
    /**
     * The key.
     * @type {*}
     * @private
     */
    this.key_ = key;
  
    /**
     * The value.
     * @type {*}
     * @private
     */
    this.value_ = value;
  };
  
  
  /**
   * Gets the key.
   * @return {*} The key.
   */
  goog.structs.Node.prototype.getKey = function() {
    return this.key_;
  };
  
  
  /**
   * Gets the value.
   * @return {*} The value.
   */
  goog.structs.Node.prototype.getValue = function() {
    return this.value_;
  };
  
  
  /**
   * Clones a node and returns a new node.
   * @return {goog.structs.Node} A new goog.structs.Node with the same key value
   *     pair.
   */
  goog.structs.Node.prototype.clone = function() {
    return new goog.structs.Node(this.key_, this.value_);
  };
  // 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 Datastructure: Heap.
   *
   *
   * This file provides the implementation of a Heap datastructure. Smaller keys
   * rise to the top.
   *
   * The big-O notation for all operations are below:
   * <pre>
   *  Method          big-O
   * ----------------------------------------------------------------------------
   * - insert         O(logn)
   * - remove         O(logn)
   * - peek           O(1)
   * - contains       O(n)
   * </pre>
   */
  // TODO(user): Should this rely on natural ordering via some Comparable
  //     interface?
  
  
  goog.provide('goog.structs.Heap');
  
  goog.require('goog.array');
  goog.require('goog.structs.Node');
  
  
  
  /**
   * Class for a Heap datastructure.
   *
   * @param {goog.structs.Heap|Object=} opt_heap Optional goog.structs.Heap or
   *     Object to initialize heap with.
   * @constructor
   */
  goog.structs.Heap = function(opt_heap) {
    /**
     * The nodes of the heap.
     * @private
     * @type {Array.<goog.structs.Node>}
     */
    this.nodes_ = [];
  
    if (opt_heap) {
      this.insertAll(opt_heap);
    }
  };
  
  
  /**
   * Insert the given value into the heap with the given key.
   * @param {*} key The key.
   * @param {*} value The value.
   */
  goog.structs.Heap.prototype.insert = function(key, value) {
    var node = new goog.structs.Node(key, value);
    var nodes = this.nodes_;
    nodes.push(node);
    this.moveUp_(nodes.length - 1);
  };
  
  
  /**
   * Adds multiple key-value pairs from another goog.structs.Heap or Object
   * @param {goog.structs.Heap|Object} heap Object containing the data to add.
   */
  goog.structs.Heap.prototype.insertAll = function(heap) {
    var keys, values;
    if (heap instanceof goog.structs.Heap) {
      keys = heap.getKeys();
      values = heap.getValues();
  
      // If it is a heap and the current heap is empty, I can realy on the fact
      // that the keys/values are in the correct order to put in the underlying
      // structure.
      if (heap.getCount() <= 0) {
        var nodes = this.nodes_;
        for (var i = 0; i < keys.length; i++) {
          nodes.push(new goog.structs.Node(keys[i], values[i]));
        }
        return;
      }
    } else {
      keys = goog.object.getKeys(heap);
      values = goog.object.getValues(heap);
    }
  
    for (var i = 0; i < keys.length; i++) {
      this.insert(keys[i], values[i]);
    }
  };
  
  
  /**
   * Retrieves and removes the root value of this heap.
   * @return {*} The value removed from the root of the heap.  Returns
   *     undefined if the heap is empty.
   */
  goog.structs.Heap.prototype.remove = function() {
    var nodes = this.nodes_;
    var count = nodes.length;
    var rootNode = nodes[0];
    if (count <= 0) {
      return undefined;
    } else if (count == 1) {
      goog.array.clear(nodes);
    } else {
      nodes[0] = nodes.pop();
      this.moveDown_(0);
    }
    return rootNode.getValue();
  };
  
  
  /**
   * Retrieves but does not remove the root value of this heap.
   * @return {*} The value at the root of the heap. Returns
   *     undefined if the heap is empty.
   */
  goog.structs.Heap.prototype.peek = function() {
    var nodes = this.nodes_;
    if (nodes.length == 0) {
      return undefined;
    }
    return nodes[0].getValue();
  };
  
  
  /**
   * Retrieves but does not remove the key of the root node of this heap.
   * @return {*} The key at the root of the heap. Returns undefined if the
   *     heap is empty.
   */
  goog.structs.Heap.prototype.peekKey = function() {
    return this.nodes_[0] && this.nodes_[0].getKey();
  };
  
  
  /**
   * Moves the node at the given index down to its proper place in the heap.
   * @param {number} index The index of the node to move down.
   * @private
   */
  goog.structs.Heap.prototype.moveDown_ = function(index) {
    var nodes = this.nodes_;
    var count = nodes.length;
  
    // Save the node being moved down.
    var node = nodes[index];
    // While the current node has a child.
    while (index < Math.floor(count / 2)) {
      var leftChildIndex = this.getLeftChildIndex_(index);
      var rightChildIndex = this.getRightChildIndex_(index);
  
      // Determine the index of the smaller child.
      var smallerChildIndex = rightChildIndex < count &&
          nodes[rightChildIndex].getKey() < nodes[leftChildIndex].getKey() ?
          rightChildIndex : leftChildIndex;
  
      // If the node being moved down is smaller than its children, the node
      // has found the correct index it should be at.
      if (nodes[smallerChildIndex].getKey() > node.getKey()) {
        break;
      }
  
      // If not, then take the smaller child as the current node.
      nodes[index] = nodes[smallerChildIndex];
      index = smallerChildIndex;
    }
    nodes[index] = node;
  };
  
  
  /**
   * Moves the node at the given index up to its proper place in the heap.
   * @param {number} index The index of the node to move up.
   * @private
   */
  goog.structs.Heap.prototype.moveUp_ = function(index) {
    var nodes = this.nodes_;
    var node = nodes[index];
  
    // While the node being moved up is not at the root.
    while (index > 0) {
      // If the parent is less than the node being moved up, move the parent down.
      var parentIndex = this.getParentIndex_(index);
      if (nodes[parentIndex].getKey() > node.getKey()) {
        nodes[index] = nodes[parentIndex];
        index = parentIndex;
      } else {
        break;
      }
    }
    nodes[index] = node;
  };
  
  
  /**
   * Gets the index of the left child of the node at the given index.
   * @param {number} index The index of the node to get the left child for.
   * @return {number} The index of the left child.
   * @private
   */
  goog.structs.Heap.prototype.getLeftChildIndex_ = function(index) {
    return index * 2 + 1;
  };
  
  
  /**
   * Gets the index of the right child of the node at the given index.
   * @param {number} index The index of the node to get the right child for.
   * @return {number} The index of the right child.
   * @private
   */
  goog.structs.Heap.prototype.getRightChildIndex_ = function(index) {
    return index * 2 + 2;
  };
  
  
  /**
   * Gets the index of the parent of the node at the given index.
   * @param {number} index The index of the node to get the parent for.
   * @return {number} The index of the parent.
   * @private
   */
  goog.structs.Heap.prototype.getParentIndex_ = function(index) {
    return Math.floor((index - 1) / 2);
  };
  
  
  /**
   * Gets the values of the heap.
   * @return {Array} The values in the heap.
   */
  goog.structs.Heap.prototype.getValues = function() {
    var nodes = this.nodes_;
    var rv = [];
    var l = nodes.length;
    for (var i = 0; i < l; i++) {
      rv.push(nodes[i].getValue());
    }
    return rv;
  };
  
  
  /**
   * Gets the keys of the heap.
   * @return {Array} The keys in the heap.
   */
  goog.structs.Heap.prototype.getKeys = function() {
    var nodes = this.nodes_;
    var rv = [];
    var l = nodes.length;
    for (var i = 0; i < l; i++) {
      rv.push(nodes[i].getKey());
    }
    return rv;
  };
  
  
  /**
   * Whether the heap contains the given value.
   * @param {Object} val The value to check for.
   * @return {boolean} Whether the heap contains the value.
   */
  goog.structs.Heap.prototype.containsValue = function(val) {
    return goog.array.some(this.nodes_, function(node) {
      return node.getValue() == val;
    });
  };
  
  
  /**
   * Whether the heap contains the given key.
   * @param {Object} key The key to check for.
   * @return {boolean} Whether the heap contains the key.
   */
  goog.structs.Heap.prototype.containsKey = function(key) {
    return goog.array.some(this.nodes_, function(node) {
      return node.getKey() == key;
    });
  };
  
  
  /**
   * Clones a heap and returns a new heap
   * @return {goog.structs.Heap} A new goog.structs.Heap with the same key-value
   *     pairs.
   */
  goog.structs.Heap.prototype.clone = function() {
    return new goog.structs.Heap(this);
  };
  
  
  /**
   * The number of key-value pairs in the map
   * @return {number} The number of pairs.
   */
  goog.structs.Heap.prototype.getCount = function() {
    return this.nodes_.length;
  };
  
  
  /**
   * Returns true if this heap contains no elements.
   * @return {boolean} Whether this heap contains no elements.
   */
  goog.structs.Heap.prototype.isEmpty = function() {
    return goog.array.isEmpty(this.nodes_);
  };
  
  
  /**
   * Removes all elements from the heap.
   */
  goog.structs.Heap.prototype.clear = function() {
    goog.array.clear(this.nodes_);
  };
  // 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 Datastructure: Priority Queue.
   *
   *
   * This file provides the implementation of a Priority Queue. Smaller priorities
   * move to the front of the queue. If two values have the same priority,
   * it is arbitrary which value will come to the front of the queue first.
   */
  
  // TODO(user): Should this rely on natural ordering via some Comparable
  //     interface?
  
  
  goog.provide('goog.structs.PriorityQueue');
  
  goog.require('goog.structs');
  goog.require('goog.structs.Heap');
  
  
  
  /**
   * Class for Priority Queue datastructure.
   *
   * @constructor
   * @extends {goog.structs.Heap}
   */
  goog.structs.PriorityQueue = function() {
    goog.structs.Heap.call(this);
  };
  goog.inherits(goog.structs.PriorityQueue, goog.structs.Heap);
  
  
  /**
   * Puts the specified value in the queue.
   * @param {*} priority The priority of the value.
   * @param {*} value The value.
   */
  goog.structs.PriorityQueue.prototype.enqueue = function(priority, value) {
    this.insert(priority, value);
  };
  
  
  /**
   * Retrieves and removes the head of this queue.
   * @return {*} The element at the head of this queue. Returns
   *     undefined if the queue is empty.
   */
  goog.structs.PriorityQueue.prototype.dequeue = function() {
    return this.remove();
  };
  // 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 Datastructure: Priority Pool.
   *
   *
   * An extending of Pool that handles queueing and prioritization.
   */
  
  
  goog.provide('goog.structs.PriorityPool');
  
  goog.require('goog.structs.Pool');
  goog.require('goog.structs.PriorityQueue');
  
  
  
  /**
   * A generic pool class. If max is greater than min, an error is thrown.
   * @param {number=} opt_minCount Min. number of objects (Default: 1).
   * @param {number=} opt_maxCount Max. number of objects (Default: 10).
   * @constructor
   * @extends {goog.structs.Pool}
   */
  goog.structs.PriorityPool = function(opt_minCount, opt_maxCount) {
    /**
     * Queue of requests for pool objects.
     * @type {goog.structs.PriorityQueue}
     * @private
     */
    this.requestQueue_ = new goog.structs.PriorityQueue();
  
    // Must break convention of putting the super-class's constructor first. This
    // is because the super-class constructor calls adjustForMinMax, which this
    // class overrides. In this class's implementation, it assumes that there
    // is a requestQueue_, and will error if not present.
    goog.structs.Pool.call(this, opt_minCount, opt_maxCount);
  };
  goog.inherits(goog.structs.PriorityPool, goog.structs.Pool);
  
  
  /**
   * Default priority for pool objects requests.
   * @type {number}
   * @private
   */
  goog.structs.PriorityPool.DEFAULT_PRIORITY_ = 100;
  
  
  /**
   * Get a new object from the the pool, if there is one available, otherwise
   * return undefined.
   * @param {Function=} opt_callback The function to callback when an object is
   *     available. This could be immediately. If this is not present, then an
   *     object is immediately returned if available, or undefined if not.
   * @param {*=} opt_priority The priority of the request.
   * @return {Object|undefined} The new object from the pool if there is one
   *     available and a callback is not given. Otherwise, undefined.
   */
  goog.structs.PriorityPool.prototype.getObject = function(opt_callback,
                                                          opt_priority) {
    if (!opt_callback) {
      return goog.structs.PriorityPool.superClass_.getObject.call(this);
    }
  
    var priority = opt_priority || goog.structs.PriorityPool.DEFAULT_PRIORITY_;
    this.requestQueue_.enqueue(priority, opt_callback);
  
    // Handle all requests.
    this.handleQueueRequests_();
  
    return undefined;
  };
  
  
  /**
   * Handles the request queue. Tries to fires off as many queued requests as
   * possible.
   * @private
   */
  goog.structs.PriorityPool.prototype.handleQueueRequests_ = function() {
    var requestQueue = this.requestQueue_;
    while (requestQueue.getCount() > 0) {
      var obj = this.getObject();
  
      if (!obj) {
        return;
      } else {
        var requestCallback = requestQueue.dequeue();
        requestCallback.apply(this, [obj]);
      }
    }
  };
  
  
  /**
   * Adds an object to the collection of objects that are free. If the object can
   * not be added, then it is disposed.
   *
   * NOTE: This method does not remove the object from the in use collection.
   *
   * @param {Object} obj The object to add to the collection of free objects.
   */
  goog.structs.PriorityPool.prototype.addFreeObject = function(obj) {
    goog.structs.PriorityPool.superClass_.addFreeObject.call(this, obj);
  
    // Handle all requests.
    this.handleQueueRequests_();
  };
  
  
  /**
   * Adjusts the objects held in the pool to be within the min/max constraints.
   *
   * NOTE: It is possible that the number of objects in the pool will still be
   * greater than the maximum count of objects allowed. This will be the case
   * if no more free objects can be disposed of to get below the minimum count
   * (i.e., all objects are in use).
   */
  goog.structs.PriorityPool.prototype.adjustForMinMax = function() {
    goog.structs.PriorityPool.superClass_.adjustForMinMax.call(this);
  
    // Handle all requests.
    this.handleQueueRequests_();
  };
  
  
  /**
   * Disposes of the pool.
   */
  goog.structs.PriorityPool.prototype.disposeInternal = function() {
    goog.structs.PriorityPool.superClass_.disposeInternal.call(this);
    this.requestQueue_.clear();
    this.requestQueue_ = null;
  };
  
  function assertIsObject(v) {
    assertFalse(v === null);
    assertEquals("object", typeof v);
  }
  
  goog.require('goog.structs');
  goog.require('goog.structs.PriorityPool');
  
  // Implementation of the Pool class with isObjectDead() always returning TRUE,
  // so that the the Pool will not reuse any objects.
  function NoObjectReusePriorityPool(opt_min, opt_max) {
    goog.structs.PriorityPool.call(this, opt_min, opt_max);
  };
  goog.inherits(NoObjectReusePriorityPool, goog.structs.PriorityPool);
  
  NoObjectReusePriorityPool.prototype.objectCanBeReused = function(obj) {
    return false;
  };
  
  
  function testExceedMax1() {
    var p = new goog.structs.PriorityPool(0, 3);
  
    var getCount1 = 0;
    var callback1 = function(obj) {
      assertIsObject(obj);
      getCount1++;
    };
  
    var getCount2 = 0;
    var callback2 = function(obj) {
      getCount2++;
    };
  
    p.getObject(callback1);
    p.getObject(callback1);
    p.getObject(callback1);
    p.getObject(callback2);
    p.getObject(callback2);
    p.getObject(callback2);
  
    assertEquals(3, getCount1);
    assertEquals(0, getCount2);
  }
  
  
  function testExceedMax2() {
    var p = new goog.structs.PriorityPool(0, 1);
  
    var getCount1 = 0;
    var callback1 = function(obj) {
      assertIsObject(obj);
      getCount1++;
    };
  
    var getCount2 = 0;
    var callback2 = function(obj) {
      getCount2++;
    };
  
    p.getObject(callback1);
    p.getObject(callback2);
    p.getObject(callback2);
    p.getObject(callback2);
    p.getObject(callback2);
    p.getObject(callback2);
  
    assertEquals(1, getCount1);
    assertEquals(0, getCount2);
  }
  
  function testExceedMax3() {
    var p = new goog.structs.PriorityPool(0, 2);
  
    var obj1 = null;
    var callback1 = function(obj) {
      obj1 = obj;
    };
  
    var obj2 = null;
    var callback2 = function(obj) {
      obj2 = obj;
    };
  
    var obj3 = null;
    var callback3 = function(obj) {
      obj3 = obj;
    };
  
    p.getObject(callback1);
    p.getObject(callback2);
    p.getObject(callback3);
  
    assertIsObject(obj1);
    assertIsObject(obj2);
    assertNull(obj3);
  }
  
  function testExceedMax4() {
    var p = new goog.structs.PriorityPool(); // default: 10
    var objs = [];
  
    var getCount1 = 0;
    var callback1 = function(obj) {
      assertIsObject(obj);
      getCount1++;
    };
  
    var getCount2 = 0;
    var callback2 = function(obj) {
      getCount2++;
    };
  
    for (var i = 0; i < 12; i++) {
      p.getObject(i < 10 ? callback1 : callback2);
    }
  
    assertEquals(10, getCount1);
    assertEquals(0, getCount2);
  }
  
  
  function testReleaseAndGet1() {
    var p = new goog.structs.PriorityPool(0, 10);
  
    var o = null;
    var callback = function(obj) {
      o = obj;
    };
  
    p.getObject(callback);
    assertEquals(1, p.getCount());
    assertEquals(1, p.getInUseCount());
    assertEquals(0, p.getFreeCount());
    assertTrue(p.releaseObject(o));
    assertEquals(1, p.getCount());
    assertEquals(0, p.getInUseCount());
    assertEquals(1, p.getFreeCount());
  }
  
  
  function testReleaseAndGet2() {
    var p = new NoObjectReusePriorityPool(0, 10);
  
    var o = null;
    var callback = function(obj) {
      o = obj;
    };
  
    p.getObject(callback);
    assertEquals(1, p.getCount());
    assertEquals(1, p.getInUseCount());
    assertEquals(0, p.getFreeCount());
    assertTrue(p.releaseObject(o));
    assertEquals(0, p.getCount());
    assertEquals(0, p.getInUseCount());
    assertEquals(0, p.getFreeCount());
  }
  
  
  function testReleaseAndGet3() {
    var p = new goog.structs.PriorityPool(0, 10);
    var o1 = null;
    var callback1 = function(obj) {
      o1 = obj;
    };
  
    var o2 = null;
    var callback2 = function(obj) {
      o2 = obj;
    };
  
    var o3 = null;
    var callback3 = function(obj) {
      o3 = obj;
    };
  
    var o4 = {};
  
    p.getObject(callback1);
    p.getObject(callback2);
    p.getObject(callback3);
  
    assertEquals(3, p.getCount());
    assertEquals(3, p.getInUseCount());
    assertEquals(0, p.getFreeCount());
    assertTrue(p.releaseObject(o1));
    assertTrue(p.releaseObject(o2));
    assertFalse(p.releaseObject(o4));
    assertEquals(3, p.getCount());
    assertEquals(1, p.getInUseCount());
    assertEquals(2, p.getFreeCount());
  }
  
  
  function testReleaseAndGet4() {
    var p = new NoObjectReusePriorityPool(0, 10);
  
    var o1 = null;
    var callback1 = function(obj) {
      o1 = obj;
    };
  
    var o2 = null;
    var callback2 = function(obj) {
      o2 = obj;
    };
  
    var o3 = null;
    var callback3 = function(obj) {
      o3 = obj;
    };
  
    var o4 = {};
  
    p.getObject(callback1);
    p.getObject(callback2);
    p.getObject(callback3);
    assertEquals(3, p.getCount());
    assertEquals(3, p.getInUseCount());
    assertEquals(0, p.getFreeCount());
    assertTrue(p.releaseObject(o1));
    assertTrue(p.releaseObject(o2));
    assertFalse(p.releaseObject(o4));
    assertEquals(1, p.getCount());
    assertEquals(1, p.getInUseCount());
    assertEquals(0, p.getFreeCount());
  }
  
  
  function testIsInPool1() {
    var p = new goog.structs.PriorityPool();
    var o1 = null;
    var callback1 = function(obj) {
      o1 = obj;
    };
  
    var o2 = null;
    var callback2 = function(obj) {
      o2 = obj;
    };
  
    var o3 = null;
    var callback3 = function(obj) {
      o3 = obj;
    };
  
    var o4 = {};
    var o5 = {};
  
    p.getObject(callback1);
    p.getObject(callback2);
    p.getObject(callback3);
    var o6 = o1;
  
    assertTrue(p.contains(o1));
    assertTrue(p.contains(o2));
    assertTrue(p.contains(o3));
    assertFalse(p.contains(o4));
    assertFalse(p.contains(o5));
    assertTrue(p.contains(o6));
  }
  
  
  function testSetMin1() {
    var p = new goog.structs.PriorityPool(0, 10);
  
    assertEquals(0, p.getCount());
    assertEquals(0, p.getInUseCount());
    assertEquals(0, p.getFreeCount());
  
    p.setMinimumCount(10);
  
    assertEquals(10, p.getCount());
    assertEquals(0, p.getInUseCount());
    assertEquals(10, p.getFreeCount());
  }
  
  
  function testSetMin2() {
    var p = new goog.structs.PriorityPool(0, 10);
  
    assertEquals(0, p.getCount());
    assertEquals(0, p.getInUseCount());
    assertEquals(0, p.getFreeCount());
  
    var o1 = null;
    var callback1 = function(obj) {
      o1 = obj;
    };
    p.getObject(callback1);
  
    assertEquals(1, p.getCount());
    assertEquals(1, p.getInUseCount());
    assertEquals(0, p.getFreeCount());
  
    p.setMinimumCount(10);
  
    assertEquals(10, p.getCount());
    assertEquals(1, p.getInUseCount());
    assertEquals(9, p.getFreeCount());
  }
  
  
  function testSetMax1() {
    var p = new goog.structs.PriorityPool(0, 10);
  
    assertEquals(0, p.getCount());
    assertEquals(0, p.getInUseCount());
    assertEquals(0, p.getFreeCount());
  
    var o1 = null;
    var callback1 = function(obj) {
      o1 = obj;
    };
  
    var o2 = null;
    var callback2 = function(obj) {
      o2 = obj;
    };
  
    var o3 = null;
    var callback3 = function(obj) {
      o3 = obj;
    };
  
    var o4 = null;
    var callback4 = function(obj) {
      o4 = obj;
    };
  
    var o5 = null;
    var callback5 = function(obj) {
      o5 = obj;
    };
  
    p.getObject(callback1);
    p.getObject(callback2);
    p.getObject(callback3);
    p.getObject(callback4);
    p.getObject(callback5);
  
    assertEquals(5, p.getCount());
    assertEquals(5, p.getInUseCount());
    assertEquals(0, p.getFreeCount());
  
    assertTrue(p.releaseObject(o5));
  
    assertEquals(5, p.getCount());
    assertEquals(4, p.getInUseCount());
    assertEquals(1, p.getFreeCount());
  
    p.setMaximumCount(4);
  
    assertEquals(4, p.getCount());
    assertEquals(4, p.getInUseCount());
    assertEquals(0, p.getFreeCount());
  }
  
  
  function testInvalidMinMax1() {
    var p = new goog.structs.PriorityPool(0, 10);
  
    assertEquals(0, p.getCount());
    assertEquals(0, p.getInUseCount());
    assertEquals(0, p.getFreeCount());
  
    assertThrows(Error, function() {
      p.setMinimumCount(11);
    });
  }
  
  
  function testInvalidMinMax2() {
    var p = new goog.structs.PriorityPool(5, 10);
  
    assertEquals(5, p.getCount());
    assertEquals(0, p.getInUseCount());
    assertEquals(5, p.getFreeCount());
  
    assertThrows(Error, function() {
      p.setMaximumCount(4);
    });
  }
  
  
  function testInvalidMinMax3() {
    assertThrows(Error, function() {
      new goog.structs.PriorityPool(10, 1);
    });
  }
  
  function testQueue1() {
    var p = new goog.structs.PriorityPool(0, 2);
  
    var o1 = null;
    var callback1 = function(obj) {
      o1 = obj;
    };
  
    var o2 = null;
    var callback2 = function(obj) {
      o2 = obj;
    };
  
    var o3 = null;
    var callback3 = function(obj) {
      o3 = obj;
    };
  
    p.getObject(callback1);
    p.getObject(callback2);
    p.getObject(callback3);
  
    assertIsObject(o1);
    assertIsObject(o2);
    assertNull(o3);
  
    p.releaseObject(o1);
    assertIsObject(o3);
  }
  
  
  function testPriority1() {
    var p = new goog.structs.PriorityPool(0, 2);
  
    var o1 = null;
    var callback1 = function(obj) {
      o1 = obj;
    };
  
    var o2 = null;
    var callback2 = function(obj) {
      o2 = obj;
    };
  
    var o3 = null;
    var callback3 = function(obj) {
      o3 = obj;
    };
  
    var o4 = null;
    var callback4 = function(obj) {
      o4 = obj;
    };
  
    p.getObject(callback1);
    p.getObject(callback2);
    p.getObject(callback3, 10);
    p.getObject(callback4, 5);
  
    assertIsObject(o1);
    assertIsObject(o2);
    assertNull(o3);
    assertNull(o4);
  
    p.releaseObject(o1);
    assertNull(o3);
    assertIsObject(o4);
  }
  
  