src/third_party/devtools/test/unittests/front_end/platform/utilities.ts - cobalt - Git at Google

 // 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);
       }
     }
   });
 });
	// 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);
	}
	}
	});
	});