/*
 * Copyright (C) 2007 Apple Inc.  All rights reserved.
 * Copyright (C) 2012 Google Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1.  Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 * 2.  Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
 *     its contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @typedef {Array|NodeList|Arguments|{length: number}} */
let ArrayLike;

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
function mod(m, n) {
  return ((m % n) + n) % n;
}

/**
 * @param {string} string
 * @return {!Array.<number>}
 */
String.prototype.findAll = function(string) {
  const matches = [];
  let i = this.indexOf(string);
  while (i !== -1) {
    matches.push(i);
    i = this.indexOf(string, i + string.length);
  }
  return matches;
};

/**
 * @return {string}
 */
String.prototype.reverse = function() {
  return this.split('').reverse().join('');
};

/**
 * @return {string}
 */
String.prototype.replaceControlCharacters = function() {
  // Replace C0 and C1 control character sets with printable character.
  // Do not replace '\t', \n' and '\r'.
  return this.replace(/[\u0000-\u0008\u000b\u000c\u000e-\u001f\u0080-\u009f]/g, '�');
};

/**
 * @return {boolean}
 */
String.prototype.isWhitespace = function() {
  return /^\s*$/.test(this);
};

/**
 * @return {!Array.<number>}
 */
String.prototype.computeLineEndings = function() {
  const endings = this.findAll('\n');
  endings.push(this.length);
  return endings;
};

/**
 * @param {string} chars
 * @return {string}
 */
String.prototype.escapeCharacters = function(chars) {
  let foundChar = false;
  for (let i = 0; i < chars.length; ++i) {
    if (this.indexOf(chars.charAt(i)) !== -1) {
      foundChar = true;
      break;
    }
  }

  if (!foundChar)
    return String(this);

  let result = '';
  for (let i = 0; i < this.length; ++i) {
    if (chars.indexOf(this.charAt(i)) !== -1)
      result += '\\';
    result += this.charAt(i);
  }

  return result;
};

/**
 * @return {string}
 */
String.regexSpecialCharacters = function() {
  return '^[]{}()\\.^$*+?|-,';
};

/**
 * @return {string}
 */
String.prototype.escapeForRegExp = function() {
  return this.escapeCharacters(String.regexSpecialCharacters());
};

/**
 * @param {string} query
 * @return {!RegExp}
 */
String.filterRegex = function(query) {
  const toEscape = String.regexSpecialCharacters();
  let regexString = '';
  for (let i = 0; i < query.length; ++i) {
    let c = query.charAt(i);
    if (toEscape.indexOf(c) !== -1)
      c = '\\' + c;
    if (i)
      regexString += '[^\\0' + c + ']*';
    regexString += c;
  }
  return new RegExp(regexString, 'i');
};

/**
 * @return {string}
 */
String.prototype.escapeHTML = function() {
  return this.replace(/&/g, '&amp;')
      .replace(/</g, '&lt;')
      .replace(/>/g, '&gt;')
      .replace(/"/g, '&quot;');  // " doublequotes just for editor
};

/**
 * @return {string}
 */
String.prototype.unescapeHTML = function() {
  return this.replace(/&lt;/g, '<')
      .replace(/&gt;/g, '>')
      .replace(/&#58;/g, ':')
      .replace(/&quot;/g, '"')
      .replace(/&#60;/g, '<')
      .replace(/&#62;/g, '>')
      .replace(/&amp;/g, '&');
};

/**
 * @return {string}
 */
String.prototype.collapseWhitespace = function() {
  return this.replace(/[\s\xA0]+/g, ' ');
};

/**
 * @param {number} maxLength
 * @return {string}
 */
String.prototype.trimMiddle = function(maxLength) {
  if (this.length <= maxLength)
    return String(this);
  let leftHalf = maxLength >> 1;
  let rightHalf = maxLength - leftHalf - 1;
  if (this.codePointAt(this.length - rightHalf - 1) >= 0x10000) {
    --rightHalf;
    ++leftHalf;
  }
  if (leftHalf > 0 && this.codePointAt(leftHalf - 1) >= 0x10000)
    --leftHalf;
  return this.substr(0, leftHalf) + '\u2026' + this.substr(this.length - rightHalf, rightHalf);
};

/**
 * @param {number} maxLength
 * @return {string}
 */
String.prototype.trimEnd = function(maxLength) {
  if (this.length <= maxLength)
    return String(this);
  return this.substr(0, maxLength - 1) + '\u2026';
};

/**
 * @param {?string=} baseURLDomain
 * @return {string}
 */
String.prototype.trimURL = function(baseURLDomain) {
  let result = this.replace(/^(https|http|file):\/\//i, '');
  if (baseURLDomain) {
    if (result.toLowerCase().startsWith(baseURLDomain.toLowerCase()))
      result = result.substr(baseURLDomain.length);
  }
  return result;
};

/**
 * @return {string}
 */
String.prototype.toTitleCase = function() {
  return this.substring(0, 1).toUpperCase() + this.substring(1);
};

/**
 * @param {string} other
 * @return {number}
 */
String.prototype.compareTo = function(other) {
  if (this > other)
    return 1;
  if (this < other)
    return -1;
  return 0;
};

/**
 * @return {string}
 */
String.prototype.removeURLFragment = function() {
  let fragmentIndex = this.indexOf('#');
  if (fragmentIndex === -1)
    fragmentIndex = this.length;
  return this.substring(0, fragmentIndex);
};

/**
 * @param {string|undefined} string
 * @return {number}
 */
String.hashCode = function(string) {
  if (!string)
    return 0;
  // Hash algorithm for substrings is described in "Über die Komplexität der Multiplikation in
  // eingeschränkten Branchingprogrammmodellen" by Woelfe.
  // http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECTION00832000000000000000
  const p = ((1 << 30) * 4 - 5);  // prime: 2^32 - 5
  const z = 0x5033d967;           // 32 bits from random.org
  const z2 = 0x59d2f15d;          // random odd 32 bit number
  let s = 0;
  let zi = 1;
  for (let i = 0; i < string.length; i++) {
    const xi = string.charCodeAt(i) * z2;
    s = (s + zi * xi) % p;
    zi = (zi * z) % p;
  }
  s = (s + zi * (p - 1)) % p;
  return Math.abs(s | 0);
};

/**
 * @param {string} string
 * @param {number} index
 * @return {boolean}
 */
String.isDigitAt = function(string, index) {
  const c = string.charCodeAt(index);
  return (48 <= c && c <= 57);
};

/**
 * @return {string}
 */
String.prototype.toBase64 = function() {
  /**
   * @param {number} b
   * @return {number}
   */
  function encodeBits(b) {
    return b < 26 ? b + 65 : b < 52 ? b + 71 : b < 62 ? b - 4 : b === 62 ? 43 : b === 63 ? 47 : 65;
  }
  const encoder = new TextEncoder();
  const data = encoder.encode(this.toString());
  const n = data.length;
  let encoded = '';
  if (n === 0)
    return encoded;
  let shift;
  let v = 0;
  for (let i = 0; i < n; i++) {
    shift = i % 3;
    v |= data[i] << (16 >>> shift & 24);
    if (shift === 2) {
      encoded += String.fromCharCode(
          encodeBits(v >>> 18 & 63), encodeBits(v >>> 12 & 63), encodeBits(v >>> 6 & 63), encodeBits(v & 63));
      v = 0;
    }
  }
  if (shift === 0)
    encoded += String.fromCharCode(encodeBits(v >>> 18 & 63), encodeBits(v >>> 12 & 63), 61, 61);
  else if (shift === 1)
    encoded += String.fromCharCode(encodeBits(v >>> 18 & 63), encodeBits(v >>> 12 & 63), encodeBits(v >>> 6 & 63), 61);
  return encoded;
};

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
String.naturalOrderComparator = function(a, b) {
  const chunk = /^\d+|^\D+/;
  let chunka, chunkb, anum, bnum;
  while (1) {
    if (a) {
      if (!b)
        return 1;
    } else {
      if (b)
        return -1;
      else
        return 0;
    }
    chunka = a.match(chunk)[0];
    chunkb = b.match(chunk)[0];
    anum = !isNaN(chunka);
    bnum = !isNaN(chunkb);
    if (anum && !bnum)
      return -1;
    if (bnum && !anum)
      return 1;
    if (anum && bnum) {
      const diff = chunka - chunkb;
      if (diff)
        return diff;
      if (chunka.length !== chunkb.length) {
        if (! + chunka && ! + chunkb)  // chunks are strings of all 0s (special case)
          return chunka.length - chunkb.length;
        else
          return chunkb.length - chunka.length;
      }
    } else if (chunka !== chunkb) {
      return (chunka < chunkb) ? -1 : 1;
    }
    a = a.substring(chunka.length);
    b = b.substring(chunkb.length);
  }
};

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
String.caseInsensetiveComparator = function(a, b) {
  a = a.toUpperCase();
  b = b.toUpperCase();
  if (a === b)
    return 0;
  return a > b ? 1 : -1;
};

/**
 * @param {number} num
 * @param {number} min
 * @param {number} max
 * @return {number}
 */
Number.constrain = function(num, min, max) {
  if (num < min)
    num = min;
  else if (num > max)
    num = max;
  return num;
};

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
Number.gcd = function(a, b) {
  if (b === 0)
    return a;
  else
    return Number.gcd(b, a % b);
};

/**
 * @param {string} value
 * @return {string}
 */
Number.toFixedIfFloating = function(value) {
  if (!value || isNaN(value))
    return value;
  const number = Number(value);
  return number % 1 ? number.toFixed(3) : String(number);
};

/**
 * @return {boolean}
 */
Date.prototype.isValid = function() {
  return !isNaN(this.getTime());
};

/**
 * @return {string}
 */
Date.prototype.toISO8601Compact = function() {
  /**
   * @param {number} x
   * @return {string}
   */
  function leadZero(x) {
    return (x > 9 ? '' : '0') + x;
  }
  return this.getFullYear() + leadZero(this.getMonth() + 1) + leadZero(this.getDate()) + 'T' +
      leadZero(this.getHours()) + leadZero(this.getMinutes()) + leadZero(this.getSeconds());
};

Object.defineProperty(Array.prototype, 'remove', {
  /**
   * @param {!T} value
   * @param {boolean=} firstOnly
   * @return {boolean}
   * @this {Array.<!T>}
   * @template T
   */
  value: function(value, firstOnly) {
    let index = this.indexOf(value);
    if (index === -1)
      return false;
    if (firstOnly) {
      this.splice(index, 1);
      return true;
    }
    for (let i = index + 1, n = this.length; i < n; ++i) {
      if (this[i] !== value)
        this[index++] = this[i];
    }
    this.length = index;
    return true;
  }
});

Object.defineProperty(Array.prototype, 'pushAll', {
  /**
   * @param {!Array<!T>} array
   * @this {Array<!T>}
   * @template T
   */
  value: function(array) {
    for (let i = 0; i < array.length; ++i)
      this.push(array[i]);
  }
});

Object.defineProperty(Array.prototype, 'rotate', {
  /**
   * @param {number} index
   * @return {!Array.<!T>}
   * @this {Array.<!T>}
   * @template T
   */
  value: function(index) {
    const result = [];
    for (let i = index; i < index + this.length; ++i)
      result.push(this[i % this.length]);
    return result;
  }
});

Object.defineProperty(Array.prototype, 'sortNumbers', {
  /**
   * @this {Array.<number>}
   */
  value: function() {
    /**
     * @param {number} a
     * @param {number} b
     * @return {number}
     */
    function numericComparator(a, b) {
      return a - b;
    }

    this.sort(numericComparator);
  }
});

Object.defineProperty(Uint32Array.prototype, 'sort', {value: Array.prototype.sort});

(function() {
const partition = {
  /**
     * @this {Array.<number>}
     * @param {function(number, number): number} comparator
     * @param {number} left
     * @param {number} right
     * @param {number} pivotIndex
     */
  value: function(comparator, left, right, pivotIndex) {
    function swap(array, i1, i2) {
      const temp = array[i1];
      array[i1] = array[i2];
      array[i2] = temp;
    }

    const pivotValue = this[pivotIndex];
    swap(this, right, pivotIndex);
    let storeIndex = left;
    for (let i = left; i < right; ++i) {
      if (comparator(this[i], pivotValue) < 0) {
        swap(this, storeIndex, i);
        ++storeIndex;
      }
    }
    swap(this, right, storeIndex);
    return storeIndex;
  }
};
Object.defineProperty(Array.prototype, 'partition', partition);
Object.defineProperty(Uint32Array.prototype, 'partition', partition);

const sortRange = {
  /**
     * @param {function(number, number): number} comparator
     * @param {number} leftBound
     * @param {number} rightBound
     * @param {number} sortWindowLeft
     * @param {number} sortWindowRight
     * @return {!Array.<number>}
     * @this {Array.<number>}
     */
  value: function(comparator, leftBound, rightBound, sortWindowLeft, sortWindowRight) {
    function quickSortRange(array, comparator, left, right, sortWindowLeft, sortWindowRight) {
      if (right <= left)
        return;
      const pivotIndex = Math.floor(Math.random() * (right - left)) + left;
      const pivotNewIndex = array.partition(comparator, left, right, pivotIndex);
      if (sortWindowLeft < pivotNewIndex)
        quickSortRange(array, comparator, left, pivotNewIndex - 1, sortWindowLeft, sortWindowRight);
      if (pivotNewIndex < sortWindowRight)
        quickSortRange(array, comparator, pivotNewIndex + 1, right, sortWindowLeft, sortWindowRight);
    }
    if (leftBound === 0 && rightBound === (this.length - 1) && sortWindowLeft === 0 && sortWindowRight >= rightBound)
      this.sort(comparator);
    else
      quickSortRange(this, comparator, leftBound, rightBound, sortWindowLeft, sortWindowRight);
    return this;
  }
};
Object.defineProperty(Array.prototype, 'sortRange', sortRange);
Object.defineProperty(Uint32Array.prototype, 'sortRange', sortRange);
})();

Object.defineProperty(Array.prototype, 'stableSort', {
  /**
   * @param {function(?T, ?T): number=} comparator
   * @return {!Array.<?T>}
   * @this {Array.<?T>}
   * @template T
   */
  value: function(comparator) {
    function defaultComparator(a, b) {
      return a < b ? -1 : (a > b ? 1 : 0);
    }
    comparator = comparator || defaultComparator;

    const indices = new Array(this.length);
    for (let i = 0; i < this.length; ++i)
      indices[i] = i;
    const self = this;
    /**
     * @param {number} a
     * @param {number} b
     * @return {number}
     */
    function indexComparator(a, b) {
      const result = comparator(self[a], self[b]);
      return result ? result : a - b;
    }
    indices.sort(indexComparator);

    for (let i = 0; i < this.length; ++i) {
      if (indices[i] < 0 || i === indices[i])
        continue;
      let cyclical = i;
      const saved = this[i];
      while (true) {
        const next = indices[cyclical];
        indices[cyclical] = -1;
        if (next === i) {
          this[cyclical] = saved;
          break;
        } else {
          this[cyclical] = this[next];
          cyclical = next;
        }
      }
    }
    return this;
  }
});

Object.defineProperty(Array.prototype, 'qselect', {
  /**
   * @param {number} k
   * @param {function(number, number): number=} comparator
   * @return {number|undefined}
   * @this {Array.<number>}
   */
  value: function(k, comparator) {
    if (k < 0 || k >= this.length)
      return;
    if (!comparator) {
      comparator = function(a, b) {
        return a - b;
      };
    }

    let low = 0;
    let high = this.length - 1;
    for (;;) {
      const pivotPosition = this.partition(comparator, low, high, Math.floor((high + low) / 2));
      if (pivotPosition === k)
        return this[k];
      else if (pivotPosition > k)
        high = pivotPosition - 1;
      else
        low = pivotPosition + 1;
    }
  }
});

Object.defineProperty(Array.prototype, 'lowerBound', {
  /**
   * Return index of the leftmost element that is equal or greater
   * than the specimen object. If there's no such element (i.e. all
   * elements are smaller than the specimen) returns right bound.
   * The function works for sorted array.
   * When specified, |left| (inclusive) and |right| (exclusive) indices
   * define the search window.
   *
   * @param {!T} object
   * @param {function(!T,!S):number=} comparator
   * @param {number=} left
   * @param {number=} right
   * @return {number}
   * @this {Array.<!S>}
   * @template T,S
   */
  value: function(object, comparator, left, right) {
    function defaultComparator(a, b) {
      return a < b ? -1 : (a > b ? 1 : 0);
    }
    comparator = comparator || defaultComparator;
    let l = left || 0;
    let r = right !== undefined ? right : this.length;
    while (l < r) {
      const m = (l + r) >> 1;
      if (comparator(object, this[m]) > 0)
        l = m + 1;
      else
        r = m;
    }
    return r;
  }
});

Object.defineProperty(Array.prototype, 'upperBound', {
  /**
   * Return index of the leftmost element that is greater
   * than the specimen object. If there's no such element (i.e. all
   * elements are smaller or equal to the specimen) returns right bound.
   * The function works for sorted array.
   * When specified, |left| (inclusive) and |right| (exclusive) indices
   * define the search window.
   *
   * @param {!T} object
   * @param {function(!T,!S):number=} comparator
   * @param {number=} left
   * @param {number=} right
   * @return {number}
   * @this {Array.<!S>}
   * @template T,S
   */
  value: function(object, comparator, left, right) {
    function defaultComparator(a, b) {
      return a < b ? -1 : (a > b ? 1 : 0);
    }
    comparator = comparator || defaultComparator;
    let l = left || 0;
    let r = right !== undefined ? right : this.length;
    while (l < r) {
      const m = (l + r) >> 1;
      if (comparator(object, this[m]) >= 0)
        l = m + 1;
      else
        r = m;
    }
    return r;
  }
});

Object.defineProperty(Uint32Array.prototype, 'lowerBound', {value: Array.prototype.lowerBound});

Object.defineProperty(Uint32Array.prototype, 'upperBound', {value: Array.prototype.upperBound});

Object.defineProperty(Int32Array.prototype, 'lowerBound', {value: Array.prototype.lowerBound});

Object.defineProperty(Int32Array.prototype, 'upperBound', {value: Array.prototype.upperBound});

Object.defineProperty(Float64Array.prototype, 'lowerBound', {value: Array.prototype.lowerBound});

Object.defineProperty(Array.prototype, 'binaryIndexOf', {
  /**
   * @param {!T} value
   * @param {function(!T,!S):number} comparator
   * @return {number}
   * @this {Array.<!S>}
   * @template T,S
   */
  value: function(value, comparator) {
    const index = this.lowerBound(value, comparator);
    return index < this.length && comparator(value, this[index]) === 0 ? index : -1;
  }
});

Object.defineProperty(Array.prototype, 'select', {
  /**
   * @param {string} field
   * @return {!Array.<!T>}
   * @this {Array.<!Object.<string,!T>>}
   * @template T
   */
  value: function(field) {
    const result = new Array(this.length);
    for (let i = 0; i < this.length; ++i)
      result[i] = this[i][field];
    return result;
  }
});

Object.defineProperty(Array.prototype, 'peekLast', {
  /**
   * @return {!T|undefined}
   * @this {Array.<!T>}
   * @template T
   */
  value: function() {
    return this[this.length - 1];
  }
});

(function() {
  /**
   * @param {!Array.<T>} array1
   * @param {!Array.<T>} array2
   * @param {function(T,T):number} comparator
   * @param {boolean} mergeNotIntersect
   * @return {!Array.<T>}
   * @template T
   */
  function mergeOrIntersect(array1, array2, comparator, mergeNotIntersect) {
    const result = [];
    let i = 0;
    let j = 0;
    while (i < array1.length && j < array2.length) {
      const compareValue = comparator(array1[i], array2[j]);
      if (mergeNotIntersect || !compareValue)
        result.push(compareValue <= 0 ? array1[i] : array2[j]);
      if (compareValue <= 0)
        i++;
      if (compareValue >= 0)
        j++;
    }
    if (mergeNotIntersect) {
      while (i < array1.length)
        result.push(array1[i++]);
      while (j < array2.length)
        result.push(array2[j++]);
    }
    return result;
  }

  Object.defineProperty(Array.prototype, 'intersectOrdered', {
    /**
     * @param {!Array.<T>} array
     * @param {function(T,T):number} comparator
     * @return {!Array.<T>}
     * @this {!Array.<T>}
     * @template T
     */
    value: function(array, comparator) {
      return mergeOrIntersect(this, array, comparator, false);
    }
  });

  Object.defineProperty(Array.prototype, 'mergeOrdered', {
    /**
     * @param {!Array.<T>} array
     * @param {function(T,T):number} comparator
     * @return {!Array.<T>}
     * @this {!Array.<T>}
     * @template T
     */
    value: function(array, comparator) {
      return mergeOrIntersect(this, array, comparator, true);
    }
  });
})();

/**
 * @param {string} format
 * @param {...*} var_arg
 * @return {string}
 */
String.sprintf = function(format, var_arg) {
  return String.vsprintf(format, Array.prototype.slice.call(arguments, 1));
};

/**
 * @param {string} format
 * @param {!Object.<string, function(string, ...):*>} formatters
 * @return {!Array.<!Object>}
 */
String.tokenizeFormatString = function(format, formatters) {
  const tokens = [];
  let substitutionIndex = 0;

  function addStringToken(str) {
    if (!str)
      return;
    if (tokens.length && tokens[tokens.length - 1].type === 'string')
      tokens[tokens.length - 1].value += str;
    else
      tokens.push({type: 'string', value: str});
  }

  function addSpecifierToken(specifier, precision, substitutionIndex) {
    tokens.push({type: 'specifier', specifier: specifier, precision: precision, substitutionIndex: substitutionIndex});
  }

  let index = 0;
  for (let precentIndex = format.indexOf('%', index); precentIndex !== -1; precentIndex = format.indexOf('%', index)) {
    if (format.length === index)  // unescaped % sign at the end of the format string.
      break;
    addStringToken(format.substring(index, precentIndex));
    index = precentIndex + 1;

    if (format[index] === '%') {
      // %% escape sequence.
      addStringToken('%');
      ++index;
      continue;
    }

    if (String.isDigitAt(format, index)) {
      // The first character is a number, it might be a substitution index.
      const number = parseInt(format.substring(index), 10);
      while (String.isDigitAt(format, index))
        ++index;

      // If the number is greater than zero and ends with a "$",
      // then this is a substitution index.
      if (number > 0 && format[index] === '$') {
        substitutionIndex = (number - 1);
        ++index;
      }
    }

    let precision = -1;
    if (format[index] === '.') {
      // This is a precision specifier. If no digit follows the ".",
      // then the precision should be zero.
      ++index;
      precision = parseInt(format.substring(index), 10);
      if (isNaN(precision))
        precision = 0;

      while (String.isDigitAt(format, index))
        ++index;
    }

    if (!(format[index] in formatters)) {
      addStringToken(format.substring(precentIndex, index + 1));
      ++index;
      continue;
    }

    addSpecifierToken(format[index], precision, substitutionIndex);

    ++substitutionIndex;
    ++index;
  }

  addStringToken(format.substring(index));

  return tokens;
};

String.standardFormatters = {
  /**
   * @return {number}
   */
  d: function(substitution) {
    return !isNaN(substitution) ? substitution : 0;
  },

  /**
   * @return {number}
   */
  f: function(substitution, token) {
    if (substitution && token.precision > -1)
      substitution = substitution.toFixed(token.precision);
    return !isNaN(substitution) ? substitution : (token.precision > -1 ? Number(0).toFixed(token.precision) : 0);
  },

  /**
   * @return {string}
   */
  s: function(substitution) {
    return substitution;
  }
};

/**
 * @param {string} format
 * @param {!Array.<*>} substitutions
 * @return {string}
 */
String.vsprintf = function(format, substitutions) {
  return String
      .format(
          format, substitutions, String.standardFormatters, '',
          function(a, b) {
            return a + b;
          })
      .formattedResult;
};

/**
 * @param {string} format
 * @param {?ArrayLike} substitutions
 * @param {!Object.<string, function(string, ...):Q>} formatters
 * @param {!T} initialValue
 * @param {function(T, Q): T|undefined} append
 * @param {!Array.<!Object>=} tokenizedFormat
 * @return {!{formattedResult: T, unusedSubstitutions: ?ArrayLike}};
 * @template T, Q
 */
String.format = function(format, substitutions, formatters, initialValue, append, tokenizedFormat) {
  if (!format || !substitutions || !substitutions.length)
    return {formattedResult: append(initialValue, format), unusedSubstitutions: substitutions};

  function prettyFunctionName() {
    return 'String.format("' + format + '", "' + Array.prototype.join.call(substitutions, '", "') + '")';
  }

  function warn(msg) {
    console.warn(prettyFunctionName() + ': ' + msg);
  }

  function error(msg) {
    console.error(prettyFunctionName() + ': ' + msg);
  }

  let result = initialValue;
  const tokens = tokenizedFormat || String.tokenizeFormatString(format, formatters);
  const usedSubstitutionIndexes = {};

  for (let i = 0; i < tokens.length; ++i) {
    const token = tokens[i];

    if (token.type === 'string') {
      result = append(result, token.value);
      continue;
    }

    if (token.type !== 'specifier') {
      error('Unknown token type "' + token.type + '" found.');
      continue;
    }

    if (token.substitutionIndex >= substitutions.length) {
      // If there are not enough substitutions for the current substitutionIndex
      // just output the format specifier literally and move on.
      error(
          'not enough substitution arguments. Had ' + substitutions.length + ' but needed ' +
          (token.substitutionIndex + 1) + ', so substitution was skipped.');
      result = append(result, '%' + (token.precision > -1 ? token.precision : '') + token.specifier);
      continue;
    }

    usedSubstitutionIndexes[token.substitutionIndex] = true;

    if (!(token.specifier in formatters)) {
      // Encountered an unsupported format character, treat as a string.
      warn('unsupported format character \u201C' + token.specifier + '\u201D. Treating as a string.');
      result = append(result, substitutions[token.substitutionIndex]);
      continue;
    }

    result = append(result, formatters[token.specifier](substitutions[token.substitutionIndex], token));
  }

  const unusedSubstitutions = [];
  for (let i = 0; i < substitutions.length; ++i) {
    if (i in usedSubstitutionIndexes)
      continue;
    unusedSubstitutions.push(substitutions[i]);
  }

  return {formattedResult: result, unusedSubstitutions: unusedSubstitutions};
};

/**
 * @param {string} query
 * @param {boolean} caseSensitive
 * @param {boolean} isRegex
 * @return {!RegExp}
 */
function createSearchRegex(query, caseSensitive, isRegex) {
  const regexFlags = caseSensitive ? 'g' : 'gi';
  let regexObject;

  if (isRegex) {
    try {
      regexObject = new RegExp(query, regexFlags);
    } catch (e) {
      // Silent catch.
    }
  }

  if (!regexObject)
    regexObject = createPlainTextSearchRegex(query, regexFlags);

  return regexObject;
}

/**
 * @param {string} query
 * @param {string=} flags
 * @return {!RegExp}
 */
function createPlainTextSearchRegex(query, flags) {
  // This should be kept the same as the one in StringUtil.cpp.
  const regexSpecialCharacters = String.regexSpecialCharacters();
  let regex = '';
  for (let i = 0; i < query.length; ++i) {
    const c = query.charAt(i);
    if (regexSpecialCharacters.indexOf(c) !== -1)
      regex += '\\';
    regex += c;
  }
  return new RegExp(regex, flags || '');
}

/**
 * @param {!RegExp} regex
 * @param {string} content
 * @return {number}
 */
function countRegexMatches(regex, content) {
  let text = content;
  let result = 0;
  let match;
  while (text && (match = regex.exec(text))) {
    if (match[0].length > 0)
      ++result;
    text = text.substring(match.index + 1);
  }
  return result;
}

/**
 * @param {number} spacesCount
 * @return {string}
 */
function spacesPadding(spacesCount) {
  return '\u00a0'.repeat(spacesCount);
}

/**
 * @param {number} value
 * @param {number} symbolsCount
 * @return {string}
 */
function numberToStringWithSpacesPadding(value, symbolsCount) {
  const numberString = value.toString();
  const paddingLength = Math.max(0, symbolsCount - numberString.length);
  return spacesPadding(paddingLength) + numberString;
}

/**
 * @return {!Array.<T>}
 * @template T
 */
Set.prototype.valuesArray = function() {
  return Array.from(this.values());
};

/**
 * @return {?T}
 * @template T
 */
Set.prototype.firstValue = function() {
  if (!this.size)
    return null;
  return this.values().next().value;
};

/**
 * @param {!Iterable<T>|!Array<!T>} iterable
 * @template T
 */
Set.prototype.addAll = function(iterable) {
  for (const e of iterable)
    this.add(e);
};

/**
 * @param {!Iterable<T>|!Array<!T>} iterable
 * @return {boolean}
 * @template T
 */
Set.prototype.containsAll = function(iterable) {
  for (const e of iterable) {
    if (!this.has(e))
      return false;
  }
  return true;
};

/**
 * @return {T}
 * @template T
 */
Map.prototype.remove = function(key) {
  const value = this.get(key);
  this.delete(key);
  return value;
};

/**
 * @return {!Array<!VALUE>}
 */
Map.prototype.valuesArray = function() {
  return Array.from(this.values());
};

/**
 * @return {!Array<!KEY>}
 */
Map.prototype.keysArray = function() {
  return Array.from(this.keys());
};

/**
 * @return {!Multimap<!KEY, !VALUE>}
 */
Map.prototype.inverse = function() {
  const result = new Multimap();
  for (const key of this.keys()) {
    const value = this.get(key);
    result.set(value, key);
  }
  return result;
};

/**
 * @constructor
 * @template K, V
 */
var Multimap = function() {  // eslint-disable-line
  /** @type {!Map.<K, !Set.<!V>>} */
  this._map = new Map();
};

Multimap.prototype = {
  /**
   * @param {K} key
   * @param {V} value
   */
  set: function(key, value) {
    let set = this._map.get(key);
    if (!set) {
      set = new Set();
      this._map.set(key, set);
    }
    set.add(value);
  },

  /**
   * @param {K} key
   * @return {!Set<!V>}
   */
  get: function(key) {
    return this._map.get(key) || new Set();
  },

  /**
   * @param {K} key
   * @return {boolean}
   */
  has: function(key) {
    return this._map.has(key);
  },

  /**
   * @param {K} key
   * @param {V} value
   * @return {boolean}
   */
  hasValue: function(key, value) {
    const set = this._map.get(key);
    if (!set)
      return false;
    return set.has(value);
  },

  /**
   * @return {number}
   */
  get size() {
    return this._map.size;
  },

  /**
   * @param {K} key
   * @param {V} value
   * @return {boolean}
   */
  delete: function(key, value) {
    const values = this.get(key);
    if (!values)
      return false;
    const result = values.delete(value);
    if (!values.size)
      this._map.delete(key);
    return result;
  },

  /**
   * @param {K} key
   */
  deleteAll: function(key) {
    this._map.delete(key);
  },

  /**
   * @return {!Array.<K>}
   */
  keysArray: function() {
    return this._map.keysArray();
  },

  /**
   * @return {!Array.<!V>}
   */
  valuesArray: function() {
    const result = [];
    const keys = this.keysArray();
    for (let i = 0; i < keys.length; ++i)
      result.pushAll(this.get(keys[i]).valuesArray());
    return result;
  },

  clear: function() {
    this._map.clear();
  }
};

/**
 * @param {string} url
 * @return {!Promise.<string>}
 */
function loadXHR(url) {
  return new Promise(load);

  function load(successCallback, failureCallback) {
    function onReadyStateChanged() {
      if (xhr.readyState !== XMLHttpRequest.DONE)
        return;
      if (xhr.status !== 200) {
        xhr.onreadystatechange = null;
        failureCallback(new Error(xhr.status));
        return;
      }
      xhr.onreadystatechange = null;
      successCallback(xhr.responseText);
    }

    const xhr = new XMLHttpRequest();
    xhr.withCredentials = false;
    xhr.open('GET', url, true);
    xhr.onreadystatechange = onReadyStateChanged;
    xhr.send(null);
  }
}

/**
 * @param {*} value
 */
function suppressUnused(value) {
}

/**
 * @param {function()} callback
 * @return {number}
 */
self.setImmediate = function(callback) {
  const args = [...arguments].slice(1);
  Promise.resolve().then(() => callback(...args));
  return 0;
};

/**
 * @param {function(...?)} callback
 * @return {!Promise.<T>}
 * @template T
 */
Promise.prototype.spread = function(callback) {
  return this.then(spreadPromise);

  function spreadPromise(arg) {
    return callback.apply(null, arg);
  }
};

/**
 * @param {T} defaultValue
 * @return {!Promise.<T>}
 * @template T
 */
Promise.prototype.catchException = function(defaultValue) {
  return this.catch(function(error) {
    console.error(error);
    return defaultValue;
  });
};

/**
 * @param {!Map<number, ?>} other
 * @param {function(!VALUE,?):boolean} isEqual
 * @return {!{removed: !Array<!VALUE>, added: !Array<?>, equal: !Array<!VALUE>}}
 * @this {Map<number, VALUE>}
 */
Map.prototype.diff = function(other, isEqual) {
  const leftKeys = this.keysArray();
  const rightKeys = other.keysArray();
  leftKeys.sort((a, b) => a - b);
  rightKeys.sort((a, b) => a - b);

  const removed = [];
  const added = [];
  const equal = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while (leftIndex < leftKeys.length && rightIndex < rightKeys.length) {
    const leftKey = leftKeys[leftIndex];
    const rightKey = rightKeys[rightIndex];
    if (leftKey === rightKey && isEqual(this.get(leftKey), other.get(rightKey))) {
      equal.push(this.get(leftKey));
      ++leftIndex;
      ++rightIndex;
      continue;
    }
    if (leftKey <= rightKey) {
      removed.push(this.get(leftKey));
      ++leftIndex;
      continue;
    }
    added.push(other.get(rightKey));
    ++rightIndex;
  }
  while (leftIndex < leftKeys.length) {
    const leftKey = leftKeys[leftIndex++];
    removed.push(this.get(leftKey));
  }
  while (rightIndex < rightKeys.length) {
    const rightKey = rightKeys[rightIndex++];
    added.push(other.get(rightKey));
  }
  return {added: added, removed: removed, equal: equal};
};

/**
 * TODO: move into its own module
 * @param {function()} callback
 * @suppressGlobalPropertiesCheck
 */
function runOnWindowLoad(callback) {
  /**
   * @suppressGlobalPropertiesCheck
   */
  function windowLoaded() {
    self.removeEventListener('DOMContentLoaded', windowLoaded, false);
    callback();
  }

  if (document.readyState === 'complete' || document.readyState === 'interactive')
    callback();
  else
    self.addEventListener('DOMContentLoaded', windowLoaded, false);
}

const _singletonSymbol = Symbol('singleton');

/**
 * @template T
 * @param {function(new:T, ...)} constructorFunction
 * @return {!T}
 */
function singleton(constructorFunction) {
  if (_singletonSymbol in constructorFunction)
    return constructorFunction[_singletonSymbol];
  const instance = new constructorFunction();
  constructorFunction[_singletonSymbol] = instance;
  return instance;
}