// Copyright 2019 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

const { assert } = chai;

// FIXME: Convert to pure functions as these utilities have side effects.
import '../../../../front_end/platform/utilities.js';

declare global {
  interface Array<T> {
    remove(value: T, firstOnly: boolean): boolean;
    mergeOrdered(array: T[], comparator: (a: T, b: T) => number): T[];
    intersectOrdered(array: T[], comparator: (a: T, b: T) => number): T[];
    upperBound(value: T, comparator?: (a: T, b: T) => number): number;
    lowerBound(value: T, comparator?: (a: T, b: T) => number): number;
    binaryIndexOf(value: T, comparator: (a: T, b: T) => number): number;
    sortRange(comparator: (a: T, b: T) => number, leftBound: number, rightBound: number, sortWindowLeft: number, sortWindowRight: number): T[];
  }

  interface String {
    trimURL(base: string): string;
    toBase64(): string;
    trimMiddle(maxLength: number): string;
    repeat(length: number): string;
  }

  interface StringConstructor {
    hashCode(value: string): number;
    naturalOrderComparator(a: string, b: string): number;
  }
}

describe('Utilities', () => {
  it('removes values', () => {
    const testArrays = [
      [], [], [], [1], [1], [1], [1, 2, 3, 4, 5, 4, 3, 2, 1], [1, 3, 4, 5, 4, 3, 2, 1], [1, 3, 4, 5, 4, 3, 1],
      [2, 2, 2, 2, 2], [2, 2, 2, 2], [], [2, 2, 2, 1, 2, 2, 3, 2], [2, 2, 1, 2, 2, 3, 2], [1, 3]
    ];

    for (let i = 0; i < testArrays.length; i += 3) {
      let actual = testArrays[i].slice(0);
      let expected = testArrays[i + 1];
      actual.remove(2, true);
      assert.deepStrictEqual(expected, actual, 'Removing firstOnly (true) failed');

      actual = testArrays[i].slice(0);
      expected = testArrays[i + 2];
      actual.remove(2, false);
      assert.deepStrictEqual(expected, actual, 'Removing firstOnly (false) failed');
    }
  });

  it('orders merge intersect', () => {
    function comparator(a: number, b: number) {
      return a - b;
    }

    function count(a: number[], x: number) {
      return a.upperBound(x) - a.lowerBound(x);
    }

    function testAll(a: number[], b: number[]) {
      testOperation(a, b, a.mergeOrdered(b, comparator), Math.max, 'U');
      testOperation(a, b, a.intersectOrdered(b, comparator), Math.min, 'x');
    }

    function testOperation(a: number[], b: number[], actual: number[], checkOperation: (...values: number[]) => number, opName: string) {
      const allValues = a.concat(b).concat(actual);
      let expectedCount: number;
      let actualCount: number;

      for (let i = 0; i < allValues.length; ++i) {
        let value = allValues[i];
        expectedCount = checkOperation(count(a, value), count(b, value));
        actualCount = count(actual, value);
        assert.equal(expectedCount, actualCount,
            'Incorrect result for value: ' + value + ' at [' + a + '] ' + opName + ' [' + b + '] -> [' + actual +
                ']');
      }

      // FIXME: This appears to be a no-op given the fact that sort works in-place.
      assert.deepStrictEqual(actual.sort(), actual, 'Result array is ordered');
    }

    const testArrays = [
      [], [], [1], [], [1, 2, 2, 2, 3], [], [4, 5, 5, 8, 8], [1, 1, 1, 2, 6], [1, 2, 2, 2, 2, 3, 3, 4],
      [2, 2, 2, 3, 3, 3, 3], [1, 2, 3, 4, 5], [1, 2, 3]
    ];

    for (let i = 0; i < testArrays.length; i += 2) {
      testAll(testArrays[i], testArrays[i + 1]);
      testAll(testArrays[i + 1], testArrays[i]);
    }
  });

  it('calculates the binary index', () => {
    const testArrays = [
      [], [1], [1, 10], [1, 10, 11, 12, 13, 14, 100], [-100, -50, 0, 50, 100], [-100, -14, -13, -12, -11, -10, -1]
    ];

    function testArray(array: number[]) {
      function comparator(a: number, b: number) {
        return a < b ? -1 : (a > b ? 1 : 0);
      }

      for (let i = -100; i <= 100; ++i) {
        let reference = array.indexOf(i);
        let actual = array.binaryIndexOf(i, comparator);
        assert.deepStrictEqual(reference, actual);
      }
      return true;
    }

    for (let i = 0, l = testArrays.length; i < l; ++i) {
      testArray(testArrays[i]);
    }
  });

  it('calculates the lower bound', () => {
    const testArrays = [[], [1], [-1, -1, 0, 0, 0, 0, 2, 3, 4, 4, 4, 7, 9, 9, 9]];

    function testArray(array: number[], useComparator: boolean) {
      function comparator(a: number, b: number) {
        return a < b ? -1 : (a > b ? 1 : 0);
      }

      for (let value = -2; value <= 12; ++value) {
        let index = useComparator ? array.lowerBound(value, comparator) : array.lowerBound(value);
        assert.isTrue(0 <= index && index <= array.length, 'index is not within bounds');
        assert.isTrue(index === 0 || array[index - 1] < value, 'array[index - 1] >= value');
        assert.isTrue(index === array.length || array[index] >= value, 'array[index] < value');
      }
    }

    for (let i = 0, l = testArrays.length; i < l; ++i) {
      testArray(testArrays[i], false);
      testArray(testArrays[i], true);
    }
  });

  it('calculates the upper bound', () => {
    const testArrays = [[], [1], [-1, -1, 0, 0, 0, 0, 2, 3, 4, 4, 4, 7, 9, 9, 9]];

    function testArray(array: number[], useComparator: boolean) {
      function comparator(a: number, b: number) {
        return a < b ? -1 : (a > b ? 1 : 0);
      }

      for (let value = -2; value <= 12; ++value) {
        let index = useComparator ? array.upperBound(value, comparator) : array.upperBound(value);
        assert.isTrue(0 <= index && index <= array.length, 'index is out of bounds');
        assert.isTrue(index === 0 || array[index - 1] <= value, 'array[index - 1] > value');
        assert.isTrue(index === array.length || array[index] > value, 'array[index] <= value');
      }
    }

    for (let i = 0, l = testArrays.length; i < l; ++i) {
      testArray(testArrays[i], false);
      testArray(testArrays[i], true);
    }
  });

  it('sorts ranges', () => {
    const testArrays = [[], [1], [2, 1], [6, 4, 2, 7, 10, 15, 1], [10, 44, 3, 6, 56, 66, 10, 55, 32, 56, 2, 5]];

    function testArray(array: number[]) {
      function comparator(a: number, b: number) {
        return a < b ? -1 : (a > b ? 1 : 0);
      }

      for (let left = 0, l = array.length - 1; left < l; ++left) {
        for (let right = left, r = array.length; right < r; ++right) {
          for (let first = left; first <= right; ++first) {
            for (let count = 1, k = right - first + 1; count <= k; ++count) {
              let actual = array.slice(0);
              actual.sortRange(comparator, left, right, first, first + count - 1);
              assert.deepStrictEqual(array.slice(0, left), actual.slice(0, left), 'left ' + left + ' ' + right + ' ' + count);
              assert.deepStrictEqual(
                  array.slice(right + 1), actual.slice(right + 1), 'right ' + left + ' ' + right + ' ' + count);

              let middle = array.slice(left, right + 1);
              middle.sort(comparator);
              assert.deepStrictEqual(
                  middle.slice(first - left, first - left + count), actual.slice(first, first + count),
                  'sorted ' + left + ' ' + right + ' ' + first + ' ' + count);

              const actualRest = actual.slice(first + count, right + 1);
              actualRest.sort(comparator);
              assert.deepStrictEqual(
                  middle.slice(first - left + count), actualRest,
                  'unsorted ' + left + ' ' + right + ' ' + first + ' ' + count);
            }
          }
        }
      }
    }

    for (let i = 0, len = testArrays.length; i < len; ++i) {
      testArray(testArrays[i]);
    }
  });

  it('sorts natural order', () => {
    const testArray = [
      'dup', 'a1',   'a4222',  'a91',       'a07',      'dup', 'a7',        'a007',      'abc00',     'abc0',
      'abc', 'abcd', 'abc000', 'x10y20z30', 'x9y19z29', 'dup', 'x09y19z29', 'x10y22z23', 'x10y19z43', '1',
      '10',  '11',   'dup',    '2',         '2',        '2',   '555555',    '5',         '5555',      'dup',
    ];

    for (let i = 0, n = testArray.length; i < n; ++i) {
      assert.equal(0, String.naturalOrderComparator(testArray[i], testArray[i]), 'comparing equal strings');
    }

    testArray.sort(String.naturalOrderComparator);

    // Check comparator's transitivity.
    for (let i = 0, n = testArray.length; i < n; ++i) {
      for (let j = 0; j < n; ++j) {
        const a = testArray[i];
        const b = testArray[j];
        const diff = String.naturalOrderComparator(a, b);
        if (diff === 0)
          assert.equal(a, b, 'zero diff');
        else if (diff < 0)
          assert.isTrue(i < j);
        else
          assert.isTrue(i > j);
      }
    }
  });

  it('hashes strings', () => {
    const stringA = ' '.repeat(10000);
    const stringB = stringA + ' ';
    const hashA = String.hashCode(stringA);
    assert.isTrue(hashA !== String.hashCode(stringB));
    assert.isTrue(isFinite(hashA));
    assert.isTrue(hashA + 1 !== hashA);
  });

  it('trims URLs', () => {
    const baseURLDomain = 'www.chromium.org';
    const testArray = [
      'http://www.chromium.org/foo/bar',
      '/foo/bar',
      'https://www.CHromium.ORG/BAZ/zoo',
      '/BAZ/zoo',
      'https://example.com/foo[]',
      'example.com/foo[]',
    ];
    for (let i = 0; i < testArray.length; i += 2) {
      const url = testArray[i];
      const expected = testArray[i + 1];
      assert.equal(expected, url.trimURL(baseURLDomain), url);
    }
  });

  it('converts to base64', () => {
    const testArray = [
      '', '', 'a', 'YQ==', 'bc', 'YmM=', 'def', 'ZGVm', 'ghij', 'Z2hpag==', 'klmno', 'a2xtbm8=', 'pqrstu', 'cHFyc3R1',
      String.fromCharCode(0x444, 0x5555, 0x66666, 0x777777), '0YTllZXmmabnnbc='
    ];
    for (let i = 0; i < testArray.length; i += 2) {
      const string = testArray[i];
      const encodedString = testArray[i + 1];
      assert.equal(encodedString, string.toBase64());
    }
  });

  it('trims the middle of strings', () => {
    const testArray = [
      '', '!', '\uD83D\uDE48A\uD83D\uDE48L\uD83D\uDE48I\uD83D\uDE48N\uD83D\uDE48A\uD83D\uDE48\uD83D\uDE48', 'test'
    ];
    for (let string of testArray) {
      for (let maxLength = string.length + 1; maxLength > 0; --maxLength) {
        const trimmed = string.trimMiddle(maxLength);
        assert.isTrue(trimmed.length <= maxLength);
      }
    }
  });
});