/*---------------------------------------------------------------------------------------------
 *  Copyright (c) Microsoft Corporation. All rights reserved.
 *  Licensed under the MIT License. See License.txt in the project root for license information.
 *--------------------------------------------------------------------------------------------*/

import assert from 'assert';
import { consolidate, groupIntersect, RangeMap } from '../../../../browser/ui/list/rangeMap.js';
import { Range } from '../../../../common/range.js';
import { ensureNoDisposablesAreLeakedInTestSuite } from '../../../common/utils.js';

suite('RangeMap', () => {

	ensureNoDisposablesAreLeakedInTestSuite();

	test('intersection', () => {
		assert.deepStrictEqual(Range.intersect({ start: 0, end: 0 }, { start: 0, end: 0 }), { start: 0, end: 0 });
		assert.deepStrictEqual(Range.intersect({ start: 0, end: 0 }, { start: 5, end: 5 }), { start: 0, end: 0 });
		assert.deepStrictEqual(Range.intersect({ start: 0, end: 1 }, { start: 5, end: 6 }), { start: 0, end: 0 });
		assert.deepStrictEqual(Range.intersect({ start: 5, end: 6 }, { start: 0, end: 1 }), { start: 0, end: 0 });
		assert.deepStrictEqual(Range.intersect({ start: 0, end: 5 }, { start: 2, end: 2 }), { start: 0, end: 0 });
		assert.deepStrictEqual(Range.intersect({ start: 0, end: 1 }, { start: 0, end: 1 }), { start: 0, end: 1 });
		assert.deepStrictEqual(Range.intersect({ start: 0, end: 10 }, { start: 0, end: 5 }), { start: 0, end: 5 });
		assert.deepStrictEqual(Range.intersect({ start: 0, end: 5 }, { start: 0, end: 10 }), { start: 0, end: 5 });
		assert.deepStrictEqual(Range.intersect({ start: 0, end: 10 }, { start: 5, end: 10 }), { start: 5, end: 10 });
		assert.deepStrictEqual(Range.intersect({ start: 5, end: 10 }, { start: 0, end: 10 }), { start: 5, end: 10 });
		assert.deepStrictEqual(Range.intersect({ start: 0, end: 10 }, { start: 2, end: 8 }), { start: 2, end: 8 });
		assert.deepStrictEqual(Range.intersect({ start: 2, end: 8 }, { start: 0, end: 10 }), { start: 2, end: 8 });
		assert.deepStrictEqual(Range.intersect({ start: 0, end: 10 }, { start: 5, end: 15 }), { start: 5, end: 10 });
		assert.deepStrictEqual(Range.intersect({ start: 5, end: 15 }, { start: 0, end: 10 }), { start: 5, end: 10 });
	});

	test('multiIntersect', () => {
		assert.deepStrictEqual(
			groupIntersect(
				{ start: 0, end: 0 },
				[{ range: { start: 0, end: 10 }, size: 1 }]
			),
			[]
		);

		assert.deepStrictEqual(
			groupIntersect(
				{ start: 10, end: 20 },
				[{ range: { start: 0, end: 10 }, size: 1 }]
			),
			[]
		);

		assert.deepStrictEqual(
			groupIntersect(
				{ start: 2, end: 8 },
				[{ range: { start: 0, end: 10 }, size: 1 }]
			),
			[{ range: { start: 2, end: 8 }, size: 1 }]
		);

		assert.deepStrictEqual(
			groupIntersect(
				{ start: 2, end: 8 },
				[{ range: { start: 0, end: 10 }, size: 1 }, { range: { start: 10, end: 20 }, size: 5 }]
			),
			[{ range: { start: 2, end: 8 }, size: 1 }]
		);

		assert.deepStrictEqual(
			groupIntersect(
				{ start: 12, end: 18 },
				[{ range: { start: 0, end: 10 }, size: 1 }, { range: { start: 10, end: 20 }, size: 5 }]
			),
			[{ range: { start: 12, end: 18 }, size: 5 }]
		);

		assert.deepStrictEqual(
			groupIntersect(
				{ start: 2, end: 18 },
				[{ range: { start: 0, end: 10 }, size: 1 }, { range: { start: 10, end: 20 }, size: 5 }]
			),
			[{ range: { start: 2, end: 10 }, size: 1 }, { range: { start: 10, end: 18 }, size: 5 }]
		);

		assert.deepStrictEqual(
			groupIntersect(
				{ start: 2, end: 28 },
				[{ range: { start: 0, end: 10 }, size: 1 }, { range: { start: 10, end: 20 }, size: 5 }, { range: { start: 20, end: 30 }, size: 10 }]
			),
			[{ range: { start: 2, end: 10 }, size: 1 }, { range: { start: 10, end: 20 }, size: 5 }, { range: { start: 20, end: 28 }, size: 10 }]
		);
	});

	test('consolidate', () => {
		assert.deepStrictEqual(consolidate([]), []);

		assert.deepStrictEqual(
			consolidate([{ range: { start: 0, end: 10 }, size: 1 }]),
			[{ range: { start: 0, end: 10 }, size: 1 }]
		);

		assert.deepStrictEqual(
			consolidate([
				{ range: { start: 0, end: 10 }, size: 1 },
				{ range: { start: 10, end: 20 }, size: 1 }
			]),
			[{ range: { start: 0, end: 20 }, size: 1 }]
		);

		assert.deepStrictEqual(
			consolidate([
				{ range: { start: 0, end: 10 }, size: 1 },
				{ range: { start: 10, end: 20 }, size: 1 },
				{ range: { start: 20, end: 100 }, size: 1 }
			]),
			[{ range: { start: 0, end: 100 }, size: 1 }]
		);

		assert.deepStrictEqual(
			consolidate([
				{ range: { start: 0, end: 10 }, size: 1 },
				{ range: { start: 10, end: 20 }, size: 5 },
				{ range: { start: 20, end: 30 }, size: 10 }
			]),
			[
				{ range: { start: 0, end: 10 }, size: 1 },
				{ range: { start: 10, end: 20 }, size: 5 },
				{ range: { start: 20, end: 30 }, size: 10 }
			]
		);

		assert.deepStrictEqual(
			consolidate([
				{ range: { start: 0, end: 10 }, size: 1 },
				{ range: { start: 10, end: 20 }, size: 2 },
				{ range: { start: 20, end: 100 }, size: 2 }
			]),
			[
				{ range: { start: 0, end: 10 }, size: 1 },
				{ range: { start: 10, end: 100 }, size: 2 }
			]
		);
	});

	test('empty', () => {
		const rangeMap = new RangeMap();
		assert.strictEqual(rangeMap.size, 0);
		assert.strictEqual(rangeMap.count, 0);
	});

	const one = { size: 1 };
	const two = { size: 2 };
	const three = { size: 3 };
	const five = { size: 5 };
	const ten = { size: 10 };

	test('length & count', () => {
		const rangeMap = new RangeMap();
		rangeMap.splice(0, 0, [one]);
		assert.strictEqual(rangeMap.size, 1);
		assert.strictEqual(rangeMap.count, 1);
	});

	test('length & count #2', () => {
		const rangeMap = new RangeMap();
		rangeMap.splice(0, 0, [one, one, one, one, one]);
		assert.strictEqual(rangeMap.size, 5);
		assert.strictEqual(rangeMap.count, 5);
	});

	test('length & count #3', () => {
		const rangeMap = new RangeMap();
		rangeMap.splice(0, 0, [five]);
		assert.strictEqual(rangeMap.size, 5);
		assert.strictEqual(rangeMap.count, 1);
	});

	test('length & count #4', () => {
		const rangeMap = new RangeMap();
		rangeMap.splice(0, 0, [five, five, five, five, five]);
		assert.strictEqual(rangeMap.size, 25);
		assert.strictEqual(rangeMap.count, 5);
	});

	test('insert', () => {
		const rangeMap = new RangeMap();
		rangeMap.splice(0, 0, [five, five, five, five, five]);
		assert.strictEqual(rangeMap.size, 25);
		assert.strictEqual(rangeMap.count, 5);

		rangeMap.splice(0, 0, [five, five, five, five, five]);
		assert.strictEqual(rangeMap.size, 50);
		assert.strictEqual(rangeMap.count, 10);

		rangeMap.splice(5, 0, [ten, ten]);
		assert.strictEqual(rangeMap.size, 70);
		assert.strictEqual(rangeMap.count, 12);

		rangeMap.splice(12, 0, [{ size: 200 }]);
		assert.strictEqual(rangeMap.size, 270);
		assert.strictEqual(rangeMap.count, 13);
	});

	test('delete', () => {
		const rangeMap = new RangeMap();
		rangeMap.splice(0, 0, [five, five, five, five, five,
			five, five, five, five, five,
			five, five, five, five, five,
			five, five, five, five, five]);
		assert.strictEqual(rangeMap.size, 100);
		assert.strictEqual(rangeMap.count, 20);

		rangeMap.splice(10, 5);
		assert.strictEqual(rangeMap.size, 75);
		assert.strictEqual(rangeMap.count, 15);

		rangeMap.splice(0, 1);
		assert.strictEqual(rangeMap.size, 70);
		assert.strictEqual(rangeMap.count, 14);

		rangeMap.splice(1, 13);
		assert.strictEqual(rangeMap.size, 5);
		assert.strictEqual(rangeMap.count, 1);

		rangeMap.splice(1, 1);
		assert.strictEqual(rangeMap.size, 5);
		assert.strictEqual(rangeMap.count, 1);
	});

	test('insert & delete', () => {
		const rangeMap = new RangeMap();
		assert.strictEqual(rangeMap.size, 0);
		assert.strictEqual(rangeMap.count, 0);

		rangeMap.splice(0, 0, [one]);
		assert.strictEqual(rangeMap.size, 1);
		assert.strictEqual(rangeMap.count, 1);

		rangeMap.splice(0, 1);
		assert.strictEqual(rangeMap.size, 0);
		assert.strictEqual(rangeMap.count, 0);
	});

	test('insert & delete #2', () => {
		const rangeMap = new RangeMap();
		rangeMap.splice(0, 0, [one, one, one, one, one,
			one, one, one, one, one]);
		rangeMap.splice(2, 6);
		assert.strictEqual(rangeMap.count, 4);
		assert.strictEqual(rangeMap.size, 4);
	});

	test('insert & delete #3', () => {
		const rangeMap = new RangeMap();
		rangeMap.splice(0, 0, [one, one, one, one, one,
			one, one, one, one, one,
			two, two, two, two, two,
			two, two, two, two, two]);
		rangeMap.splice(8, 4);
		assert.strictEqual(rangeMap.count, 16);
		assert.strictEqual(rangeMap.size, 24);
	});

	test('insert & delete #4', () => {
		const rangeMap = new RangeMap();
		rangeMap.splice(0, 0, [one, one, one, one, one,
			one, one, one, one, one,
			two, two, two, two, two,
			two, two, two, two, two]);
		rangeMap.splice(5, 0, [three, three, three, three, three]);
		assert.strictEqual(rangeMap.count, 25);
		assert.strictEqual(rangeMap.size, 45);

		rangeMap.splice(4, 7);
		assert.strictEqual(rangeMap.count, 18);
		assert.strictEqual(rangeMap.size, 28);
	});

	suite('indexAt, positionAt', () => {
		test('empty', () => {
			const rangeMap = new RangeMap();
			assert.strictEqual(rangeMap.indexAt(0), 0);
			assert.strictEqual(rangeMap.indexAt(10), 0);
			assert.strictEqual(rangeMap.indexAt(-1), -1);
			assert.strictEqual(rangeMap.positionAt(0), -1);
			assert.strictEqual(rangeMap.positionAt(10), -1);
			assert.strictEqual(rangeMap.positionAt(-1), -1);
		});

		test('simple', () => {
			const rangeMap = new RangeMap();
			rangeMap.splice(0, 0, [one]);
			assert.strictEqual(rangeMap.indexAt(0), 0);
			assert.strictEqual(rangeMap.indexAt(1), 1);
			assert.strictEqual(rangeMap.positionAt(0), 0);
			assert.strictEqual(rangeMap.positionAt(1), -1);
		});

		test('simple #2', () => {
			const rangeMap = new RangeMap();
			rangeMap.splice(0, 0, [ten]);
			assert.strictEqual(rangeMap.indexAt(0), 0);
			assert.strictEqual(rangeMap.indexAt(5), 0);
			assert.strictEqual(rangeMap.indexAt(9), 0);
			assert.strictEqual(rangeMap.indexAt(10), 1);
			assert.strictEqual(rangeMap.positionAt(0), 0);
			assert.strictEqual(rangeMap.positionAt(1), -1);
		});

		test('insert', () => {
			const rangeMap = new RangeMap();
			rangeMap.splice(0, 0, [one, one, one, one, one, one, one, one, one, one]);
			assert.strictEqual(rangeMap.indexAt(0), 0);
			assert.strictEqual(rangeMap.indexAt(1), 1);
			assert.strictEqual(rangeMap.indexAt(5), 5);
			assert.strictEqual(rangeMap.indexAt(9), 9);
			assert.strictEqual(rangeMap.indexAt(10), 10);
			assert.strictEqual(rangeMap.indexAt(11), 10);

			rangeMap.splice(10, 0, [one, one, one, one, one, one, one, one, one, one]);
			assert.strictEqual(rangeMap.indexAt(10), 10);
			assert.strictEqual(rangeMap.indexAt(19), 19);
			assert.strictEqual(rangeMap.indexAt(20), 20);
			assert.strictEqual(rangeMap.indexAt(21), 20);
			assert.strictEqual(rangeMap.positionAt(0), 0);
			assert.strictEqual(rangeMap.positionAt(1), 1);
			assert.strictEqual(rangeMap.positionAt(19), 19);
			assert.strictEqual(rangeMap.positionAt(20), -1);
		});

		test('delete', () => {
			const rangeMap = new RangeMap();
			rangeMap.splice(0, 0, [one, one, one, one, one, one, one, one, one, one]);
			rangeMap.splice(2, 6);

			assert.strictEqual(rangeMap.indexAt(0), 0);
			assert.strictEqual(rangeMap.indexAt(1), 1);
			assert.strictEqual(rangeMap.indexAt(3), 3);
			assert.strictEqual(rangeMap.indexAt(4), 4);
			assert.strictEqual(rangeMap.indexAt(5), 4);
			assert.strictEqual(rangeMap.positionAt(0), 0);
			assert.strictEqual(rangeMap.positionAt(1), 1);
			assert.strictEqual(rangeMap.positionAt(3), 3);
			assert.strictEqual(rangeMap.positionAt(4), -1);
		});

		test('delete #2', () => {
			const rangeMap = new RangeMap();
			rangeMap.splice(0, 0, [ten, ten, ten, ten, ten, ten, ten, ten, ten, ten]);
			rangeMap.splice(2, 6);

			assert.strictEqual(rangeMap.indexAt(0), 0);
			assert.strictEqual(rangeMap.indexAt(1), 0);
			assert.strictEqual(rangeMap.indexAt(30), 3);
			assert.strictEqual(rangeMap.indexAt(40), 4);
			assert.strictEqual(rangeMap.indexAt(50), 4);
			assert.strictEqual(rangeMap.positionAt(0), 0);
			assert.strictEqual(rangeMap.positionAt(1), 10);
			assert.strictEqual(rangeMap.positionAt(2), 20);
			assert.strictEqual(rangeMap.positionAt(3), 30);
			assert.strictEqual(rangeMap.positionAt(4), -1);
		});
	});
});

suite('RangeMap with top padding', () => {

	ensureNoDisposablesAreLeakedInTestSuite();

	test('empty', () => {
		const rangeMap = new RangeMap(10);
		assert.strictEqual(rangeMap.size, 10);
		assert.strictEqual(rangeMap.count, 0);
	});

	const one = { size: 1 };
	const five = { size: 5 };
	const ten = { size: 10 };

	test('length & count', () => {
		const rangeMap = new RangeMap(10);
		rangeMap.splice(0, 0, [one]);
		assert.strictEqual(rangeMap.size, 11);
		assert.strictEqual(rangeMap.count, 1);
	});

	test('length & count #2', () => {
		const rangeMap = new RangeMap(10);
		rangeMap.splice(0, 0, [one, one, one, one, one]);
		assert.strictEqual(rangeMap.size, 15);
		assert.strictEqual(rangeMap.count, 5);
	});

	test('length & count #3', () => {
		const rangeMap = new RangeMap(10);
		rangeMap.splice(0, 0, [five]);
		assert.strictEqual(rangeMap.size, 15);
		assert.strictEqual(rangeMap.count, 1);
	});

	test('length & count #4', () => {
		const rangeMap = new RangeMap(10);
		rangeMap.splice(0, 0, [five, five, five, five, five]);
		assert.strictEqual(rangeMap.size, 35);
		assert.strictEqual(rangeMap.count, 5);
	});

	test('insert', () => {
		const rangeMap = new RangeMap(10);
		rangeMap.splice(0, 0, [five, five, five, five, five]);
		assert.strictEqual(rangeMap.size, 35);
		assert.strictEqual(rangeMap.count, 5);

		rangeMap.splice(0, 0, [five, five, five, five, five]);
		assert.strictEqual(rangeMap.size, 60);
		assert.strictEqual(rangeMap.count, 10);

		rangeMap.splice(5, 0, [ten, ten]);
		assert.strictEqual(rangeMap.size, 80);
		assert.strictEqual(rangeMap.count, 12);

		rangeMap.splice(12, 0, [{ size: 200 }]);
		assert.strictEqual(rangeMap.size, 280);
		assert.strictEqual(rangeMap.count, 13);
	});

	suite('indexAt, positionAt', () => {
		test('empty', () => {
			const rangeMap = new RangeMap(10);
			assert.strictEqual(rangeMap.indexAt(0), 0);
			assert.strictEqual(rangeMap.indexAt(10), 0);
			assert.strictEqual(rangeMap.indexAt(-1), -1);
			assert.strictEqual(rangeMap.positionAt(0), -1);
			assert.strictEqual(rangeMap.positionAt(10), -1);
			assert.strictEqual(rangeMap.positionAt(-1), -1);
		});

		test('simple', () => {
			const rangeMap = new RangeMap(10);
			rangeMap.splice(0, 0, [one]);
			assert.strictEqual(rangeMap.indexAt(0), 0);
			assert.strictEqual(rangeMap.indexAt(1), 0);
			assert.strictEqual(rangeMap.indexAt(10), 0);
			assert.strictEqual(rangeMap.indexAt(11), 1);
			assert.strictEqual(rangeMap.positionAt(0), 10);
			assert.strictEqual(rangeMap.positionAt(1), -1);
		});
	});
});
