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

import * as assert from 'assert';
import { shuffle } from 'vs/base/common/arrays';
import { randomPath } from 'vs/base/common/extpath';
import { ConfigKeysIterator, LinkedMap, LRUCache, PathIterator, ResourceMap, StringIterator, TernarySearchTree, Touch, UriIterator } from 'vs/base/common/map';
import { extUriIgnorePathCase } from 'vs/base/common/resources';
import { StopWatch } from 'vs/base/common/stopwatch';
import { URI } from 'vs/base/common/uri';

suite('Map', () => {

	test('LinkedMap - Simple', () => {
		const map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('bk', 'bv');
		assert.deepStrictEqual([...map.keys()], ['ak', 'bk']);
		assert.deepStrictEqual([...map.values()], ['av', 'bv']);
		assert.strictEqual(map.first, 'av');
		assert.strictEqual(map.last, 'bv');
	});

	test('LinkedMap - Touch Old one', () => {
		const map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('ak', 'av', Touch.AsOld);
		assert.deepStrictEqual([...map.keys()], ['ak']);
		assert.deepStrictEqual([...map.values()], ['av']);
	});

	test('LinkedMap - Touch New one', () => {
		const map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('ak', 'av', Touch.AsNew);
		assert.deepStrictEqual([...map.keys()], ['ak']);
		assert.deepStrictEqual([...map.values()], ['av']);
	});

	test('LinkedMap - Touch Old two', () => {
		const map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('bk', 'bv');
		map.set('bk', 'bv', Touch.AsOld);
		assert.deepStrictEqual([...map.keys()], ['bk', 'ak']);
		assert.deepStrictEqual([...map.values()], ['bv', 'av']);
	});

	test('LinkedMap - Touch New two', () => {
		const map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('bk', 'bv');
		map.set('ak', 'av', Touch.AsNew);
		assert.deepStrictEqual([...map.keys()], ['bk', 'ak']);
		assert.deepStrictEqual([...map.values()], ['bv', 'av']);
	});

	test('LinkedMap - Touch Old from middle', () => {
		const map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('bk', 'bv');
		map.set('ck', 'cv');
		map.set('bk', 'bv', Touch.AsOld);
		assert.deepStrictEqual([...map.keys()], ['bk', 'ak', 'ck']);
		assert.deepStrictEqual([...map.values()], ['bv', 'av', 'cv']);
	});

	test('LinkedMap - Touch New from middle', () => {
		const map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('bk', 'bv');
		map.set('ck', 'cv');
		map.set('bk', 'bv', Touch.AsNew);
		assert.deepStrictEqual([...map.keys()], ['ak', 'ck', 'bk']);
		assert.deepStrictEqual([...map.values()], ['av', 'cv', 'bv']);
	});

	test('LinkedMap - basics', function () {
		const map = new LinkedMap<string, any>();

		assert.strictEqual(map.size, 0);

		map.set('1', 1);
		map.set('2', '2');
		map.set('3', true);

		const obj = Object.create(null);
		map.set('4', obj);

		const date = Date.now();
		map.set('5', date);

		assert.strictEqual(map.size, 5);
		assert.strictEqual(map.get('1'), 1);
		assert.strictEqual(map.get('2'), '2');
		assert.strictEqual(map.get('3'), true);
		assert.strictEqual(map.get('4'), obj);
		assert.strictEqual(map.get('5'), date);
		assert.ok(!map.get('6'));

		map.delete('6');
		assert.strictEqual(map.size, 5);
		assert.strictEqual(map.delete('1'), true);
		assert.strictEqual(map.delete('2'), true);
		assert.strictEqual(map.delete('3'), true);
		assert.strictEqual(map.delete('4'), true);
		assert.strictEqual(map.delete('5'), true);

		assert.strictEqual(map.size, 0);
		assert.ok(!map.get('5'));
		assert.ok(!map.get('4'));
		assert.ok(!map.get('3'));
		assert.ok(!map.get('2'));
		assert.ok(!map.get('1'));

		map.set('1', 1);
		map.set('2', '2');
		map.set('3', true);

		assert.ok(map.has('1'));
		assert.strictEqual(map.get('1'), 1);
		assert.strictEqual(map.get('2'), '2');
		assert.strictEqual(map.get('3'), true);

		map.clear();

		assert.strictEqual(map.size, 0);
		assert.ok(!map.get('1'));
		assert.ok(!map.get('2'));
		assert.ok(!map.get('3'));
		assert.ok(!map.has('1'));
	});

	test('LinkedMap - Iterators', () => {
		const map = new LinkedMap<number, any>();
		map.set(1, 1);
		map.set(2, 2);
		map.set(3, 3);

		for (const elem of map.keys()) {
			assert.ok(elem);
		}

		for (const elem of map.values()) {
			assert.ok(elem);
		}

		for (const elem of map.entries()) {
			assert.ok(elem);
		}

		{
			const keys = map.keys();
			const values = map.values();
			const entries = map.entries();
			map.get(1);
			keys.next();
			values.next();
			entries.next();
		}

		{
			const keys = map.keys();
			const values = map.values();
			const entries = map.entries();
			map.get(1, Touch.AsNew);

			let exceptions: number = 0;
			try {
				keys.next();
			} catch (err) {
				exceptions++;
			}
			try {
				values.next();
			} catch (err) {
				exceptions++;
			}
			try {
				entries.next();
			} catch (err) {
				exceptions++;
			}

			assert.strictEqual(exceptions, 3);
		}
	});

	test('LinkedMap - LRU Cache simple', () => {
		const cache = new LRUCache<number, number>(5);

		[1, 2, 3, 4, 5].forEach(value => cache.set(value, value));
		assert.strictEqual(cache.size, 5);
		cache.set(6, 6);
		assert.strictEqual(cache.size, 5);
		assert.deepStrictEqual([...cache.keys()], [2, 3, 4, 5, 6]);
		cache.set(7, 7);
		assert.strictEqual(cache.size, 5);
		assert.deepStrictEqual([...cache.keys()], [3, 4, 5, 6, 7]);
		const values: number[] = [];
		[3, 4, 5, 6, 7].forEach(key => values.push(cache.get(key)!));
		assert.deepStrictEqual(values, [3, 4, 5, 6, 7]);
	});

	test('LinkedMap - LRU Cache get', () => {
		const cache = new LRUCache<number, number>(5);

		[1, 2, 3, 4, 5].forEach(value => cache.set(value, value));
		assert.strictEqual(cache.size, 5);
		assert.deepStrictEqual([...cache.keys()], [1, 2, 3, 4, 5]);
		cache.get(3);
		assert.deepStrictEqual([...cache.keys()], [1, 2, 4, 5, 3]);
		cache.peek(4);
		assert.deepStrictEqual([...cache.keys()], [1, 2, 4, 5, 3]);
		const values: number[] = [];
		[1, 2, 3, 4, 5].forEach(key => values.push(cache.get(key)!));
		assert.deepStrictEqual(values, [1, 2, 3, 4, 5]);
	});

	test('LinkedMap - LRU Cache limit', () => {
		const cache = new LRUCache<number, number>(10);

		for (let i = 1; i <= 10; i++) {
			cache.set(i, i);
		}
		assert.strictEqual(cache.size, 10);
		cache.limit = 5;
		assert.strictEqual(cache.size, 5);
		assert.deepStrictEqual([...cache.keys()], [6, 7, 8, 9, 10]);
		cache.limit = 20;
		assert.strictEqual(cache.size, 5);
		for (let i = 11; i <= 20; i++) {
			cache.set(i, i);
		}
		assert.deepStrictEqual(cache.size, 15);
		const values: number[] = [];
		for (let i = 6; i <= 20; i++) {
			values.push(cache.get(i)!);
			assert.strictEqual(cache.get(i), i);
		}
		assert.deepStrictEqual([...cache.values()], values);
	});

	test('LinkedMap - LRU Cache limit with ratio', () => {
		const cache = new LRUCache<number, number>(10, 0.5);

		for (let i = 1; i <= 10; i++) {
			cache.set(i, i);
		}
		assert.strictEqual(cache.size, 10);
		cache.set(11, 11);
		assert.strictEqual(cache.size, 5);
		assert.deepStrictEqual([...cache.keys()], [7, 8, 9, 10, 11]);
		const values: number[] = [];
		[...cache.keys()].forEach(key => values.push(cache.get(key)!));
		assert.deepStrictEqual(values, [7, 8, 9, 10, 11]);
		assert.deepStrictEqual([...cache.values()], values);
	});

	test('LinkedMap - toJSON / fromJSON', () => {
		let map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('bk', 'bv');
		map.set('ck', 'cv');

		const json = map.toJSON();
		map = new LinkedMap<string, string>();
		map.fromJSON(json);

		let i = 0;
		map.forEach((value, key) => {
			if (i === 0) {
				assert.strictEqual(key, 'ak');
				assert.strictEqual(value, 'av');
			} else if (i === 1) {
				assert.strictEqual(key, 'bk');
				assert.strictEqual(value, 'bv');
			} else if (i === 2) {
				assert.strictEqual(key, 'ck');
				assert.strictEqual(value, 'cv');
			}
			i++;
		});
	});

	test('LinkedMap - delete Head and Tail', function () {
		const map = new LinkedMap<string, number>();

		assert.strictEqual(map.size, 0);

		map.set('1', 1);
		assert.strictEqual(map.size, 1);
		map.delete('1');
		assert.strictEqual(map.get('1'), undefined);
		assert.strictEqual(map.size, 0);
		assert.strictEqual([...map.keys()].length, 0);
	});

	test('LinkedMap - delete Head', function () {
		const map = new LinkedMap<string, number>();

		assert.strictEqual(map.size, 0);

		map.set('1', 1);
		map.set('2', 2);
		assert.strictEqual(map.size, 2);
		map.delete('1');
		assert.strictEqual(map.get('2'), 2);
		assert.strictEqual(map.size, 1);
		assert.strictEqual([...map.keys()].length, 1);
		assert.strictEqual([...map.keys()][0], '2');
	});

	test('LinkedMap - delete Tail', function () {
		const map = new LinkedMap<string, number>();

		assert.strictEqual(map.size, 0);

		map.set('1', 1);
		map.set('2', 2);
		assert.strictEqual(map.size, 2);
		map.delete('2');
		assert.strictEqual(map.get('1'), 1);
		assert.strictEqual(map.size, 1);
		assert.strictEqual([...map.keys()].length, 1);
		assert.strictEqual([...map.keys()][0], '1');
	});


	test('PathIterator', () => {
		const iter = new PathIterator();
		iter.reset('file:///usr/bin/file.txt');

		assert.strictEqual(iter.value(), 'file:');
		assert.strictEqual(iter.hasNext(), true);
		assert.strictEqual(iter.cmp('file:'), 0);
		assert.ok(iter.cmp('a') < 0);
		assert.ok(iter.cmp('aile:') < 0);
		assert.ok(iter.cmp('z') > 0);
		assert.ok(iter.cmp('zile:') > 0);

		iter.next();
		assert.strictEqual(iter.value(), 'usr');
		assert.strictEqual(iter.hasNext(), true);

		iter.next();
		assert.strictEqual(iter.value(), 'bin');
		assert.strictEqual(iter.hasNext(), true);

		iter.next();
		assert.strictEqual(iter.value(), 'file.txt');
		assert.strictEqual(iter.hasNext(), false);

		iter.next();
		assert.strictEqual(iter.value(), '');
		assert.strictEqual(iter.hasNext(), false);
		iter.next();
		assert.strictEqual(iter.value(), '');
		assert.strictEqual(iter.hasNext(), false);

		//
		iter.reset('/foo/bar/');
		assert.strictEqual(iter.value(), 'foo');
		assert.strictEqual(iter.hasNext(), true);

		iter.next();
		assert.strictEqual(iter.value(), 'bar');
		assert.strictEqual(iter.hasNext(), false);
	});

	test('URIIterator', function () {
		const iter = new UriIterator(() => false, () => false);
		iter.reset(URI.parse('file:///usr/bin/file.txt'));

		assert.strictEqual(iter.value(), 'file');
		// assert.strictEqual(iter.cmp('FILE'), 0);
		assert.strictEqual(iter.cmp('file'), 0);
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		assert.strictEqual(iter.value(), 'usr');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		assert.strictEqual(iter.value(), 'bin');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		assert.strictEqual(iter.value(), 'file.txt');
		assert.strictEqual(iter.hasNext(), false);


		iter.reset(URI.parse('file://share/usr/bin/file.txt?foo'));

		// scheme
		assert.strictEqual(iter.value(), 'file');
		// assert.strictEqual(iter.cmp('FILE'), 0);
		assert.strictEqual(iter.cmp('file'), 0);
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// authority
		assert.strictEqual(iter.value(), 'share');
		assert.strictEqual(iter.cmp('SHARe'), 0);
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// path
		assert.strictEqual(iter.value(), 'usr');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// path
		assert.strictEqual(iter.value(), 'bin');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// path
		assert.strictEqual(iter.value(), 'file.txt');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// query
		assert.strictEqual(iter.value(), 'foo');
		assert.strictEqual(iter.cmp('z') > 0, true);
		assert.strictEqual(iter.cmp('a') < 0, true);
		assert.strictEqual(iter.hasNext(), false);
	});

	test('URIIterator - ignore query/fragment', function () {
		const iter = new UriIterator(() => false, () => true);
		iter.reset(URI.parse('file:///usr/bin/file.txt'));

		assert.strictEqual(iter.value(), 'file');
		// assert.strictEqual(iter.cmp('FILE'), 0);
		assert.strictEqual(iter.cmp('file'), 0);
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		assert.strictEqual(iter.value(), 'usr');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		assert.strictEqual(iter.value(), 'bin');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		assert.strictEqual(iter.value(), 'file.txt');
		assert.strictEqual(iter.hasNext(), false);


		iter.reset(URI.parse('file://share/usr/bin/file.txt?foo'));

		// scheme
		assert.strictEqual(iter.value(), 'file');
		// assert.strictEqual(iter.cmp('FILE'), 0);
		assert.strictEqual(iter.cmp('file'), 0);
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// authority
		assert.strictEqual(iter.value(), 'share');
		assert.strictEqual(iter.cmp('SHARe'), 0);
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// path
		assert.strictEqual(iter.value(), 'usr');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// path
		assert.strictEqual(iter.value(), 'bin');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// path
		assert.strictEqual(iter.value(), 'file.txt');
		assert.strictEqual(iter.hasNext(), false);
	});

	function assertTstDfs<E>(trie: TernarySearchTree<string, E>, ...elements: [string, E][]) {

		assert.ok(trie._isBalanced(), 'TST is not balanced');

		let i = 0;
		for (const [key, value] of trie) {
			const expected = elements[i++];
			assert.ok(expected);
			assert.strictEqual(key, expected[0]);
			assert.strictEqual(value, expected[1]);
		}

		assert.strictEqual(i, elements.length);

		const map = new Map<string, E>();
		for (const [key, value] of elements) {
			map.set(key, value);
		}
		map.forEach((value, key) => {
			assert.strictEqual(trie.get(key), value);
		});

		// forEach
		let forEachCount = 0;
		trie.forEach((element, key) => {
			assert.strictEqual(element, map.get(key));
			forEachCount++;
		});
		assert.strictEqual(map.size, forEachCount);

		// iterator
		let iterCount = 0;
		for (const [key, value] of trie) {
			assert.strictEqual(value, map.get(key));
			iterCount++;
		}
		assert.strictEqual(map.size, iterCount);

	}

	test('TernarySearchTree - set', function () {

		let trie = TernarySearchTree.forStrings<number>();
		trie.set('foobar', 1);
		trie.set('foobaz', 2);

		assertTstDfs(trie, ['foobar', 1], ['foobaz', 2]); // longer

		trie = TernarySearchTree.forStrings<number>();
		trie.set('foobar', 1);
		trie.set('fooba', 2);
		assertTstDfs(trie, ['fooba', 2], ['foobar', 1]); // shorter

		trie = TernarySearchTree.forStrings<number>();
		trie.set('foo', 1);
		trie.set('foo', 2);
		assertTstDfs(trie, ['foo', 2]);

		trie = TernarySearchTree.forStrings<number>();
		trie.set('foo', 1);
		trie.set('foobar', 2);
		trie.set('bar', 3);
		trie.set('foob', 4);
		trie.set('bazz', 5);

		assertTstDfs(trie,
			['bar', 3],
			['bazz', 5],
			['foo', 1],
			['foob', 4],
			['foobar', 2],
		);
	});

	test('TernarySearchTree - findLongestMatch', function () {

		const trie = TernarySearchTree.forStrings<number>();
		trie.set('foo', 1);
		trie.set('foobar', 2);
		trie.set('foobaz', 3);
		assertTstDfs(trie, ['foo', 1], ['foobar', 2], ['foobaz', 3]);

		assert.strictEqual(trie.findSubstr('f'), undefined);
		assert.strictEqual(trie.findSubstr('z'), undefined);
		assert.strictEqual(trie.findSubstr('foo'), 1);
		assert.strictEqual(trie.findSubstr('fooö'), 1);
		assert.strictEqual(trie.findSubstr('fooba'), 1);
		assert.strictEqual(trie.findSubstr('foobarr'), 2);
		assert.strictEqual(trie.findSubstr('foobazrr'), 3);
	});

	test('TernarySearchTree - basics', function () {
		const trie = new TernarySearchTree<string, number>(new StringIterator());

		trie.set('foo', 1);
		trie.set('bar', 2);
		trie.set('foobar', 3);
		assertTstDfs(trie, ['bar', 2], ['foo', 1], ['foobar', 3]);

		assert.strictEqual(trie.get('foo'), 1);
		assert.strictEqual(trie.get('bar'), 2);
		assert.strictEqual(trie.get('foobar'), 3);
		assert.strictEqual(trie.get('foobaz'), undefined);
		assert.strictEqual(trie.get('foobarr'), undefined);

		assert.strictEqual(trie.findSubstr('fo'), undefined);
		assert.strictEqual(trie.findSubstr('foo'), 1);
		assert.strictEqual(trie.findSubstr('foooo'), 1);


		trie.delete('foobar');
		trie.delete('bar');
		assert.strictEqual(trie.get('foobar'), undefined);
		assert.strictEqual(trie.get('bar'), undefined);

		trie.set('foobar', 17);
		trie.set('barr', 18);
		assert.strictEqual(trie.get('foobar'), 17);
		assert.strictEqual(trie.get('barr'), 18);
		assert.strictEqual(trie.get('bar'), undefined);
	});

	test('TernarySearchTree - delete & cleanup', function () {
		// normal delete
		let trie = new TernarySearchTree<string, number>(new StringIterator());
		trie.set('foo', 1);
		trie.set('foobar', 2);
		trie.set('bar', 3);
		assertTstDfs(trie, ['bar', 3], ['foo', 1], ['foobar', 2]);
		trie.delete('foo');
		assertTstDfs(trie, ['bar', 3], ['foobar', 2]);
		trie.delete('foobar');
		assertTstDfs(trie, ['bar', 3]);

		// superstr-delete
		trie = new TernarySearchTree<string, number>(new StringIterator());
		trie.set('foo', 1);
		trie.set('foobar', 2);
		trie.set('bar', 3);
		trie.set('foobarbaz', 4);
		trie.deleteSuperstr('foo');
		assertTstDfs(trie, ['bar', 3], ['foo', 1]);

		trie = new TernarySearchTree<string, number>(new StringIterator());
		trie.set('foo', 1);
		trie.set('foobar', 2);
		trie.set('bar', 3);
		trie.set('foobarbaz', 4);
		trie.deleteSuperstr('fo');
		assertTstDfs(trie, ['bar', 3]);

		// trie = new TernarySearchTree<string, number>(new StringIterator());
		// trie.set('foo', 1);
		// trie.set('foobar', 2);
		// trie.set('bar', 3);
		// trie.deleteSuperStr('f');
		// assertTernarySearchTree(trie, ['bar', 3]);
	});

	test('TernarySearchTree (PathSegments) - basics', function () {
		const trie = new TernarySearchTree<string, number>(new PathIterator());

		trie.set('/user/foo/bar', 1);
		trie.set('/user/foo', 2);
		trie.set('/user/foo/flip/flop', 3);

		assert.strictEqual(trie.get('/user/foo/bar'), 1);
		assert.strictEqual(trie.get('/user/foo'), 2);
		assert.strictEqual(trie.get('/user//foo'), 2);
		assert.strictEqual(trie.get('/user\\foo'), 2);
		assert.strictEqual(trie.get('/user/foo/flip/flop'), 3);

		assert.strictEqual(trie.findSubstr('/user/bar'), undefined);
		assert.strictEqual(trie.findSubstr('/user/foo'), 2);
		assert.strictEqual(trie.findSubstr('\\user\\foo'), 2);
		assert.strictEqual(trie.findSubstr('/user//foo'), 2);
		assert.strictEqual(trie.findSubstr('/user/foo/ba'), 2);
		assert.strictEqual(trie.findSubstr('/user/foo/far/boo'), 2);
		assert.strictEqual(trie.findSubstr('/user/foo/bar'), 1);
		assert.strictEqual(trie.findSubstr('/user/foo/bar/far/boo'), 1);
	});

	test('TernarySearchTree - (AVL) set', function () {
		{
			// rotate left
			const trie = new TernarySearchTree<string, number>(new PathIterator());
			trie.set('/fileA', 1);
			trie.set('/fileB', 2);
			trie.set('/fileC', 3);
			assertTstDfs(trie, ['/fileA', 1], ['/fileB', 2], ['/fileC', 3]);
		}

		{
			// rotate left (inside middle)
			const trie = new TernarySearchTree<string, number>(new PathIterator());
			trie.set('/foo/fileA', 1);
			trie.set('/foo/fileB', 2);
			trie.set('/foo/fileC', 3);
			assertTstDfs(trie, ['/foo/fileA', 1], ['/foo/fileB', 2], ['/foo/fileC', 3]);
		}

		{
			// rotate right
			const trie = new TernarySearchTree<string, number>(new PathIterator());
			trie.set('/fileC', 3);
			trie.set('/fileB', 2);
			trie.set('/fileA', 1);
			assertTstDfs(trie, ['/fileA', 1], ['/fileB', 2], ['/fileC', 3]);
		}

		{
			// rotate right (inside middle)
			const trie = new TernarySearchTree<string, number>(new PathIterator());
			trie.set('/mid/fileC', 3);
			trie.set('/mid/fileB', 2);
			trie.set('/mid/fileA', 1);
			assertTstDfs(trie, ['/mid/fileA', 1], ['/mid/fileB', 2], ['/mid/fileC', 3]);
		}

		{
			// rotate right, left
			const trie = new TernarySearchTree<string, number>(new PathIterator());
			trie.set('/fileD', 7);
			trie.set('/fileB', 2);
			trie.set('/fileG', 42);
			trie.set('/fileF', 24);
			trie.set('/fileZ', 73);
			trie.set('/fileE', 15);
			assertTstDfs(trie, ['/fileB', 2], ['/fileD', 7], ['/fileE', 15], ['/fileF', 24], ['/fileG', 42], ['/fileZ', 73]);
		}

		{
			// rotate left, right
			const trie = new TernarySearchTree<string, number>(new PathIterator());
			trie.set('/fileJ', 42);
			trie.set('/fileZ', 73);
			trie.set('/fileE', 15);
			trie.set('/fileB', 2);
			trie.set('/fileF', 7);
			trie.set('/fileG', 1);
			assertTstDfs(trie, ['/fileB', 2], ['/fileE', 15], ['/fileF', 7], ['/fileG', 1], ['/fileJ', 42], ['/fileZ', 73]);
		}
	});

	test('TernarySearchTree - (BST) delete', function () {

		const trie = new TernarySearchTree<string, number>(new StringIterator());

		// delete root
		trie.set('d', 1);
		assertTstDfs(trie, ['d', 1]);
		trie.delete('d');
		assertTstDfs(trie);

		// delete node with two element
		trie.clear();
		trie.set('d', 1);
		trie.set('b', 1);
		trie.set('f', 1);
		assertTstDfs(trie, ['b', 1], ['d', 1], ['f', 1]);
		trie.delete('d');
		assertTstDfs(trie, ['b', 1], ['f', 1]);

		// single child node
		trie.clear();
		trie.set('d', 1);
		trie.set('b', 1);
		trie.set('f', 1);
		trie.set('e', 1);
		assertTstDfs(trie, ['b', 1], ['d', 1], ['e', 1], ['f', 1]);
		trie.delete('f');
		assertTstDfs(trie, ['b', 1], ['d', 1], ['e', 1]);
	});

	test('TernarySearchTree - (AVL) delete', function () {

		const trie = new TernarySearchTree<string, number>(new StringIterator());

		trie.clear();
		trie.set('d', 1);
		trie.set('b', 1);
		trie.set('f', 1);
		trie.set('e', 1);
		trie.set('z', 1);
		assertTstDfs(trie, ['b', 1], ['d', 1], ['e', 1], ['f', 1], ['z', 1]);

		// right, right
		trie.delete('b');
		assertTstDfs(trie, ['d', 1], ['e', 1], ['f', 1], ['z', 1]);

		trie.clear();
		trie.set('d', 1);
		trie.set('c', 1);
		trie.set('f', 1);
		trie.set('a', 1);
		trie.set('b', 1);
		assertTstDfs(trie, ['a', 1], ['b', 1], ['c', 1], ['d', 1], ['f', 1]);

		// left, left
		trie.delete('f');
		assertTstDfs(trie, ['a', 1], ['b', 1], ['c', 1], ['d', 1]);

		// mid
		trie.clear();
		trie.set('a', 1);
		trie.set('ad', 1);
		trie.set('ab', 1);
		trie.set('af', 1);
		trie.set('ae', 1);
		trie.set('az', 1);
		assertTstDfs(trie, ['a', 1], ['ab', 1], ['ad', 1], ['ae', 1], ['af', 1], ['az', 1]);

		trie.delete('ab');
		assertTstDfs(trie, ['a', 1], ['ad', 1], ['ae', 1], ['af', 1], ['az', 1]);

		trie.delete('a');
		assertTstDfs(trie, ['ad', 1], ['ae', 1], ['af', 1], ['az', 1]);
	});

	test('TernarySearchTree: Cannot read property \'1\' of undefined #138284', function () {

		const keys = [
			URI.parse('fake-fs:/C'),
			URI.parse('fake-fs:/A'),
			URI.parse('fake-fs:/D'),
			URI.parse('fake-fs:/B'),
		];

		const tst = TernarySearchTree.forUris<boolean>();

		for (const item of keys) {
			tst.set(item, true);
		}

		assert.ok(tst._isBalanced());
		tst.delete(keys[0]);
		assert.ok(tst._isBalanced());
	});

	test('TernarySearchTree: Cannot read property \'1\' of undefined #138284 (simple)', function () {

		const keys = ['C', 'A', 'D', 'B',];
		const tst = TernarySearchTree.forStrings<boolean>();
		for (const item of keys) {
			tst.set(item, true);
		}
		assertTstDfs(tst, ['A', true], ['B', true], ['C', true], ['D', true]);

		tst.delete(keys[0]);
		assertTstDfs(tst, ['A', true], ['B', true], ['D', true]);

		{
			const tst = TernarySearchTree.forStrings<boolean>();
			tst.set('C', true);
			tst.set('A', true);
			tst.set('B', true);
			assertTstDfs(tst, ['A', true], ['B', true], ['C', true]);
		}

	});

	test('TernarySearchTree: Cannot read property \'1\' of undefined #138284 (random)', function () {
		for (let round = 10; round >= 0; round--) {
			const keys: URI[] = [];
			for (let i = 0; i < 100; i++) {
				keys.push(URI.from({ scheme: 'fake-fs', path: randomPath(undefined, undefined, 10) }));
			}
			const tst = TernarySearchTree.forUris<boolean>();

			for (const item of keys) {
				tst.set(item, true);
				assert.ok(tst._isBalanced());
			}

			for (const item of keys) {
				tst.delete(item);
				assert.ok(tst._isBalanced());
			}
		}
	});

	test('TernarySearchTree (PathSegments) - lookup', function () {

		const map = new TernarySearchTree<string, number>(new PathIterator());
		map.set('/user/foo/bar', 1);
		map.set('/user/foo', 2);<commit_msg>add logging to understand why/how test sometimes fails, https://github.com/microsoft/vscode/issues/154237 (#154514)<commit_after>/*---------------------------------------------------------------------------------------------
 *  Copyright (c) Microsoft Corporation. All rights reserved.
 *  Licensed under the MIT License. See License.txt in the project root for license information.
 *--------------------------------------------------------------------------------------------*/

import * as assert from 'assert';
import { shuffle } from 'vs/base/common/arrays';
import { randomPath } from 'vs/base/common/extpath';
import { ConfigKeysIterator, LinkedMap, LRUCache, PathIterator, ResourceMap, StringIterator, TernarySearchTree, Touch, UriIterator } from 'vs/base/common/map';
import { extUriIgnorePathCase } from 'vs/base/common/resources';
import { StopWatch } from 'vs/base/common/stopwatch';
import { URI } from 'vs/base/common/uri';

suite('Map', () => {

	test('LinkedMap - Simple', () => {
		const map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('bk', 'bv');
		assert.deepStrictEqual([...map.keys()], ['ak', 'bk']);
		assert.deepStrictEqual([...map.values()], ['av', 'bv']);
		assert.strictEqual(map.first, 'av');
		assert.strictEqual(map.last, 'bv');
	});

	test('LinkedMap - Touch Old one', () => {
		const map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('ak', 'av', Touch.AsOld);
		assert.deepStrictEqual([...map.keys()], ['ak']);
		assert.deepStrictEqual([...map.values()], ['av']);
	});

	test('LinkedMap - Touch New one', () => {
		const map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('ak', 'av', Touch.AsNew);
		assert.deepStrictEqual([...map.keys()], ['ak']);
		assert.deepStrictEqual([...map.values()], ['av']);
	});

	test('LinkedMap - Touch Old two', () => {
		const map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('bk', 'bv');
		map.set('bk', 'bv', Touch.AsOld);
		assert.deepStrictEqual([...map.keys()], ['bk', 'ak']);
		assert.deepStrictEqual([...map.values()], ['bv', 'av']);
	});

	test('LinkedMap - Touch New two', () => {
		const map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('bk', 'bv');
		map.set('ak', 'av', Touch.AsNew);
		assert.deepStrictEqual([...map.keys()], ['bk', 'ak']);
		assert.deepStrictEqual([...map.values()], ['bv', 'av']);
	});

	test('LinkedMap - Touch Old from middle', () => {
		const map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('bk', 'bv');
		map.set('ck', 'cv');
		map.set('bk', 'bv', Touch.AsOld);
		assert.deepStrictEqual([...map.keys()], ['bk', 'ak', 'ck']);
		assert.deepStrictEqual([...map.values()], ['bv', 'av', 'cv']);
	});

	test('LinkedMap - Touch New from middle', () => {
		const map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('bk', 'bv');
		map.set('ck', 'cv');
		map.set('bk', 'bv', Touch.AsNew);
		assert.deepStrictEqual([...map.keys()], ['ak', 'ck', 'bk']);
		assert.deepStrictEqual([...map.values()], ['av', 'cv', 'bv']);
	});

	test('LinkedMap - basics', function () {
		const map = new LinkedMap<string, any>();

		assert.strictEqual(map.size, 0);

		map.set('1', 1);
		map.set('2', '2');
		map.set('3', true);

		const obj = Object.create(null);
		map.set('4', obj);

		const date = Date.now();
		map.set('5', date);

		assert.strictEqual(map.size, 5);
		assert.strictEqual(map.get('1'), 1);
		assert.strictEqual(map.get('2'), '2');
		assert.strictEqual(map.get('3'), true);
		assert.strictEqual(map.get('4'), obj);
		assert.strictEqual(map.get('5'), date);
		assert.ok(!map.get('6'));

		map.delete('6');
		assert.strictEqual(map.size, 5);
		assert.strictEqual(map.delete('1'), true);
		assert.strictEqual(map.delete('2'), true);
		assert.strictEqual(map.delete('3'), true);
		assert.strictEqual(map.delete('4'), true);
		assert.strictEqual(map.delete('5'), true);

		assert.strictEqual(map.size, 0);
		assert.ok(!map.get('5'));
		assert.ok(!map.get('4'));
		assert.ok(!map.get('3'));
		assert.ok(!map.get('2'));
		assert.ok(!map.get('1'));

		map.set('1', 1);
		map.set('2', '2');
		map.set('3', true);

		assert.ok(map.has('1'));
		assert.strictEqual(map.get('1'), 1);
		assert.strictEqual(map.get('2'), '2');
		assert.strictEqual(map.get('3'), true);

		map.clear();

		assert.strictEqual(map.size, 0);
		assert.ok(!map.get('1'));
		assert.ok(!map.get('2'));
		assert.ok(!map.get('3'));
		assert.ok(!map.has('1'));
	});

	test('LinkedMap - Iterators', () => {
		const map = new LinkedMap<number, any>();
		map.set(1, 1);
		map.set(2, 2);
		map.set(3, 3);

		for (const elem of map.keys()) {
			assert.ok(elem);
		}

		for (const elem of map.values()) {
			assert.ok(elem);
		}

		for (const elem of map.entries()) {
			assert.ok(elem);
		}

		{
			const keys = map.keys();
			const values = map.values();
			const entries = map.entries();
			map.get(1);
			keys.next();
			values.next();
			entries.next();
		}

		{
			const keys = map.keys();
			const values = map.values();
			const entries = map.entries();
			map.get(1, Touch.AsNew);

			let exceptions: number = 0;
			try {
				keys.next();
			} catch (err) {
				exceptions++;
			}
			try {
				values.next();
			} catch (err) {
				exceptions++;
			}
			try {
				entries.next();
			} catch (err) {
				exceptions++;
			}

			assert.strictEqual(exceptions, 3);
		}
	});

	test('LinkedMap - LRU Cache simple', () => {
		const cache = new LRUCache<number, number>(5);

		[1, 2, 3, 4, 5].forEach(value => cache.set(value, value));
		assert.strictEqual(cache.size, 5);
		cache.set(6, 6);
		assert.strictEqual(cache.size, 5);
		assert.deepStrictEqual([...cache.keys()], [2, 3, 4, 5, 6]);
		cache.set(7, 7);
		assert.strictEqual(cache.size, 5);
		assert.deepStrictEqual([...cache.keys()], [3, 4, 5, 6, 7]);
		const values: number[] = [];
		[3, 4, 5, 6, 7].forEach(key => values.push(cache.get(key)!));
		assert.deepStrictEqual(values, [3, 4, 5, 6, 7]);
	});

	test('LinkedMap - LRU Cache get', () => {
		const cache = new LRUCache<number, number>(5);

		[1, 2, 3, 4, 5].forEach(value => cache.set(value, value));
		assert.strictEqual(cache.size, 5);
		assert.deepStrictEqual([...cache.keys()], [1, 2, 3, 4, 5]);
		cache.get(3);
		assert.deepStrictEqual([...cache.keys()], [1, 2, 4, 5, 3]);
		cache.peek(4);
		assert.deepStrictEqual([...cache.keys()], [1, 2, 4, 5, 3]);
		const values: number[] = [];
		[1, 2, 3, 4, 5].forEach(key => values.push(cache.get(key)!));
		assert.deepStrictEqual(values, [1, 2, 3, 4, 5]);
	});

	test('LinkedMap - LRU Cache limit', () => {
		const cache = new LRUCache<number, number>(10);

		for (let i = 1; i <= 10; i++) {
			cache.set(i, i);
		}
		assert.strictEqual(cache.size, 10);
		cache.limit = 5;
		assert.strictEqual(cache.size, 5);
		assert.deepStrictEqual([...cache.keys()], [6, 7, 8, 9, 10]);
		cache.limit = 20;
		assert.strictEqual(cache.size, 5);
		for (let i = 11; i <= 20; i++) {
			cache.set(i, i);
		}
		assert.deepStrictEqual(cache.size, 15);
		const values: number[] = [];
		for (let i = 6; i <= 20; i++) {
			values.push(cache.get(i)!);
			assert.strictEqual(cache.get(i), i);
		}
		assert.deepStrictEqual([...cache.values()], values);
	});

	test('LinkedMap - LRU Cache limit with ratio', () => {
		const cache = new LRUCache<number, number>(10, 0.5);

		for (let i = 1; i <= 10; i++) {
			cache.set(i, i);
		}
		assert.strictEqual(cache.size, 10);
		cache.set(11, 11);
		assert.strictEqual(cache.size, 5);
		assert.deepStrictEqual([...cache.keys()], [7, 8, 9, 10, 11]);
		const values: number[] = [];
		[...cache.keys()].forEach(key => values.push(cache.get(key)!));
		assert.deepStrictEqual(values, [7, 8, 9, 10, 11]);
		assert.deepStrictEqual([...cache.values()], values);
	});

	test('LinkedMap - toJSON / fromJSON', () => {
		let map = new LinkedMap<string, string>();
		map.set('ak', 'av');
		map.set('bk', 'bv');
		map.set('ck', 'cv');

		const json = map.toJSON();
		map = new LinkedMap<string, string>();
		map.fromJSON(json);

		let i = 0;
		map.forEach((value, key) => {
			if (i === 0) {
				assert.strictEqual(key, 'ak');
				assert.strictEqual(value, 'av');
			} else if (i === 1) {
				assert.strictEqual(key, 'bk');
				assert.strictEqual(value, 'bv');
			} else if (i === 2) {
				assert.strictEqual(key, 'ck');
				assert.strictEqual(value, 'cv');
			}
			i++;
		});
	});

	test('LinkedMap - delete Head and Tail', function () {
		const map = new LinkedMap<string, number>();

		assert.strictEqual(map.size, 0);

		map.set('1', 1);
		assert.strictEqual(map.size, 1);
		map.delete('1');
		assert.strictEqual(map.get('1'), undefined);
		assert.strictEqual(map.size, 0);
		assert.strictEqual([...map.keys()].length, 0);
	});

	test('LinkedMap - delete Head', function () {
		const map = new LinkedMap<string, number>();

		assert.strictEqual(map.size, 0);

		map.set('1', 1);
		map.set('2', 2);
		assert.strictEqual(map.size, 2);
		map.delete('1');
		assert.strictEqual(map.get('2'), 2);
		assert.strictEqual(map.size, 1);
		assert.strictEqual([...map.keys()].length, 1);
		assert.strictEqual([...map.keys()][0], '2');
	});

	test('LinkedMap - delete Tail', function () {
		const map = new LinkedMap<string, number>();

		assert.strictEqual(map.size, 0);

		map.set('1', 1);
		map.set('2', 2);
		assert.strictEqual(map.size, 2);
		map.delete('2');
		assert.strictEqual(map.get('1'), 1);
		assert.strictEqual(map.size, 1);
		assert.strictEqual([...map.keys()].length, 1);
		assert.strictEqual([...map.keys()][0], '1');
	});


	test('PathIterator', () => {
		const iter = new PathIterator();
		iter.reset('file:///usr/bin/file.txt');

		assert.strictEqual(iter.value(), 'file:');
		assert.strictEqual(iter.hasNext(), true);
		assert.strictEqual(iter.cmp('file:'), 0);
		assert.ok(iter.cmp('a') < 0);
		assert.ok(iter.cmp('aile:') < 0);
		assert.ok(iter.cmp('z') > 0);
		assert.ok(iter.cmp('zile:') > 0);

		iter.next();
		assert.strictEqual(iter.value(), 'usr');
		assert.strictEqual(iter.hasNext(), true);

		iter.next();
		assert.strictEqual(iter.value(), 'bin');
		assert.strictEqual(iter.hasNext(), true);

		iter.next();
		assert.strictEqual(iter.value(), 'file.txt');
		assert.strictEqual(iter.hasNext(), false);

		iter.next();
		assert.strictEqual(iter.value(), '');
		assert.strictEqual(iter.hasNext(), false);
		iter.next();
		assert.strictEqual(iter.value(), '');
		assert.strictEqual(iter.hasNext(), false);

		//
		iter.reset('/foo/bar/');
		assert.strictEqual(iter.value(), 'foo');
		assert.strictEqual(iter.hasNext(), true);

		iter.next();
		assert.strictEqual(iter.value(), 'bar');
		assert.strictEqual(iter.hasNext(), false);
	});

	test('URIIterator', function () {
		const iter = new UriIterator(() => false, () => false);
		iter.reset(URI.parse('file:///usr/bin/file.txt'));

		assert.strictEqual(iter.value(), 'file');
		// assert.strictEqual(iter.cmp('FILE'), 0);
		assert.strictEqual(iter.cmp('file'), 0);
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		assert.strictEqual(iter.value(), 'usr');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		assert.strictEqual(iter.value(), 'bin');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		assert.strictEqual(iter.value(), 'file.txt');
		assert.strictEqual(iter.hasNext(), false);


		iter.reset(URI.parse('file://share/usr/bin/file.txt?foo'));

		// scheme
		assert.strictEqual(iter.value(), 'file');
		// assert.strictEqual(iter.cmp('FILE'), 0);
		assert.strictEqual(iter.cmp('file'), 0);
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// authority
		assert.strictEqual(iter.value(), 'share');
		assert.strictEqual(iter.cmp('SHARe'), 0);
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// path
		assert.strictEqual(iter.value(), 'usr');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// path
		assert.strictEqual(iter.value(), 'bin');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// path
		assert.strictEqual(iter.value(), 'file.txt');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// query
		assert.strictEqual(iter.value(), 'foo');
		assert.strictEqual(iter.cmp('z') > 0, true);
		assert.strictEqual(iter.cmp('a') < 0, true);
		assert.strictEqual(iter.hasNext(), false);
	});

	test('URIIterator - ignore query/fragment', function () {
		const iter = new UriIterator(() => false, () => true);
		iter.reset(URI.parse('file:///usr/bin/file.txt'));

		assert.strictEqual(iter.value(), 'file');
		// assert.strictEqual(iter.cmp('FILE'), 0);
		assert.strictEqual(iter.cmp('file'), 0);
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		assert.strictEqual(iter.value(), 'usr');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		assert.strictEqual(iter.value(), 'bin');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		assert.strictEqual(iter.value(), 'file.txt');
		assert.strictEqual(iter.hasNext(), false);


		iter.reset(URI.parse('file://share/usr/bin/file.txt?foo'));

		// scheme
		assert.strictEqual(iter.value(), 'file');
		// assert.strictEqual(iter.cmp('FILE'), 0);
		assert.strictEqual(iter.cmp('file'), 0);
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// authority
		assert.strictEqual(iter.value(), 'share');
		assert.strictEqual(iter.cmp('SHARe'), 0);
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// path
		assert.strictEqual(iter.value(), 'usr');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// path
		assert.strictEqual(iter.value(), 'bin');
		assert.strictEqual(iter.hasNext(), true);
		iter.next();

		// path
		assert.strictEqual(iter.value(), 'file.txt');
		assert.strictEqual(iter.hasNext(), false);
	});

	function assertTstDfs<E>(trie: TernarySearchTree<string, E>, ...elements: [string, E][]) {

		assert.ok(trie._isBalanced(), 'TST is not balanced');

		let i = 0;
		for (const [key, value] of trie) {
			const expected = elements[i++];
			assert.ok(expected);
			assert.strictEqual(key, expected[0]);
			assert.strictEqual(value, expected[1]);
		}

		assert.strictEqual(i, elements.length);

		const map = new Map<string, E>();
		for (const [key, value] of elements) {
			map.set(key, value);
		}
		map.forEach((value, key) => {
			assert.strictEqual(trie.get(key), value);
		});

		// forEach
		let forEachCount = 0;
		trie.forEach((element, key) => {
			assert.strictEqual(element, map.get(key));
			forEachCount++;
		});
		assert.strictEqual(map.size, forEachCount);

		// iterator
		let iterCount = 0;
		for (const [key, value] of trie) {
			assert.strictEqual(value, map.get(key));
			iterCount++;
		}
		assert.strictEqual(map.size, iterCount);

	}

	test('TernarySearchTree - set', function () {

		let trie = TernarySearchTree.forStrings<number>();
		trie.set('foobar', 1);
		trie.set('foobaz', 2);

		assertTstDfs(trie, ['foobar', 1], ['foobaz', 2]); // longer

		trie = TernarySearchTree.forStrings<number>();
		trie.set('foobar', 1);
		trie.set('fooba', 2);
		assertTstDfs(trie, ['fooba', 2], ['foobar', 1]); // shorter

		trie = TernarySearchTree.forStrings<number>();
		trie.set('foo', 1);
		trie.set('foo', 2);
		assertTstDfs(trie, ['foo', 2]);

		trie = TernarySearchTree.forStrings<number>();
		trie.set('foo', 1);
		trie.set('foobar', 2);
		trie.set('bar', 3);
		trie.set('foob', 4);
		trie.set('bazz', 5);

		assertTstDfs(trie,
			['bar', 3],
			['bazz', 5],
			['foo', 1],
			['foob', 4],
			['foobar', 2],
		);
	});

	test('TernarySearchTree - findLongestMatch', function () {

		const trie = TernarySearchTree.forStrings<number>();
		trie.set('foo', 1);
		trie.set('foobar', 2);
		trie.set('foobaz', 3);
		assertTstDfs(trie, ['foo', 1], ['foobar', 2], ['foobaz', 3]);

		assert.strictEqual(trie.findSubstr('f'), undefined);
		assert.strictEqual(trie.findSubstr('z'), undefined);
		assert.strictEqual(trie.findSubstr('foo'), 1);
		assert.strictEqual(trie.findSubstr('fooö'), 1);
		assert.strictEqual(trie.findSubstr('fooba'), 1);
		assert.strictEqual(trie.findSubstr('foobarr'), 2);
		assert.strictEqual(trie.findSubstr('foobazrr'), 3);
	});

	test('TernarySearchTree - basics', function () {
		const trie = new TernarySearchTree<string, number>(new StringIterator());

		trie.set('foo', 1);
		trie.set('bar', 2);
		trie.set('foobar', 3);
		assertTstDfs(trie, ['bar', 2], ['foo', 1], ['foobar', 3]);

		assert.strictEqual(trie.get('foo'), 1);
		assert.strictEqual(trie.get('bar'), 2);
		assert.strictEqual(trie.get('foobar'), 3);
		assert.strictEqual(trie.get('foobaz'), undefined);
		assert.strictEqual(trie.get('foobarr'), undefined);

		assert.strictEqual(trie.findSubstr('fo'), undefined);
		assert.strictEqual(trie.findSubstr('foo'), 1);
		assert.strictEqual(trie.findSubstr('foooo'), 1);


		trie.delete('foobar');
		trie.delete('bar');
		assert.strictEqual(trie.get('foobar'), undefined);
		assert.strictEqual(trie.get('bar'), undefined);

		trie.set('foobar', 17);
		trie.set('barr', 18);
		assert.strictEqual(trie.get('foobar'), 17);
		assert.strictEqual(trie.get('barr'), 18);
		assert.strictEqual(trie.get('bar'), undefined);
	});

	test('TernarySearchTree - delete & cleanup', function () {
		// normal delete
		let trie = new TernarySearchTree<string, number>(new StringIterator());
		trie.set('foo', 1);
		trie.set('foobar', 2);
		trie.set('bar', 3);
		assertTstDfs(trie, ['bar', 3], ['foo', 1], ['foobar', 2]);
		trie.delete('foo');
		assertTstDfs(trie, ['bar', 3], ['foobar', 2]);
		trie.delete('foobar');
		assertTstDfs(trie, ['bar', 3]);

		// superstr-delete
		trie = new TernarySearchTree<string, number>(new StringIterator());
		trie.set('foo', 1);
		trie.set('foobar', 2);
		trie.set('bar', 3);
		trie.set('foobarbaz', 4);
		trie.deleteSuperstr('foo');
		assertTstDfs(trie, ['bar', 3], ['foo', 1]);

		trie = new TernarySearchTree<string, number>(new StringIterator());
		trie.set('foo', 1);
		trie.set('foobar', 2);
		trie.set('bar', 3);
		trie.set('foobarbaz', 4);
		trie.deleteSuperstr('fo');
		assertTstDfs(trie, ['bar', 3]);

		// trie = new TernarySearchTree<string, number>(new StringIterator());
		// trie.set('foo', 1);
		// trie.set('foobar', 2);
		// trie.set('bar', 3);
		// trie.deleteSuperStr('f');
		// assertTernarySearchTree(trie, ['bar', 3]);
	});

	test('TernarySearchTree (PathSegments) - basics', function () {
		const trie = new TernarySearchTree<string, number>(new PathIterator());

		trie.set('/user/foo/bar', 1);
		trie.set('/user/foo', 2);
		trie.set('/user/foo/flip/flop', 3);

		assert.strictEqual(trie.get('/user/foo/bar'), 1);
		assert.strictEqual(trie.get('/user/foo'), 2);
		assert.strictEqual(trie.get('/user//foo'), 2);
		assert.strictEqual(trie.get('/user\\foo'), 2);
		assert.strictEqual(trie.get('/user/foo/flip/flop'), 3);

		assert.strictEqual(trie.findSubstr('/user/bar'), undefined);
		assert.strictEqual(trie.findSubstr('/user/foo'), 2);
		assert.strictEqual(trie.findSubstr('\\user\\foo'), 2);
		assert.strictEqual(trie.findSubstr('/user//foo'), 2);
		assert.strictEqual(trie.findSubstr('/user/foo/ba'), 2);
		assert.strictEqual(trie.findSubstr('/user/foo/far/boo'), 2);
		assert.strictEqual(trie.findSubstr('/user/foo/bar'), 1);
		assert.strictEqual(trie.findSubstr('/user/foo/bar/far/boo'), 1);
	});

	test('TernarySearchTree - (AVL) set', function () {
		{
			// rotate left
			const trie = new TernarySearchTree<string, number>(new PathIterator());
			trie.set('/fileA', 1);
			trie.set('/fileB', 2);
			trie.set('/fileC', 3);
			assertTstDfs(trie, ['/fileA', 1], ['/fileB', 2], ['/fileC', 3]);
		}

		{
			// rotate left (inside middle)
			const trie = new TernarySearchTree<string, number>(new PathIterator());
			trie.set('/foo/fileA', 1);
			trie.set('/foo/fileB', 2);
			trie.set('/foo/fileC', 3);
			assertTstDfs(trie, ['/foo/fileA', 1], ['/foo/fileB', 2], ['/foo/fileC', 3]);
		}

		{
			// rotate right
			const trie = new TernarySearchTree<string, number>(new PathIterator());
			trie.set('/fileC', 3);
			trie.set('/fileB', 2);
			trie.set('/fileA', 1);
			assertTstDfs(trie, ['/fileA', 1], ['/fileB', 2], ['/fileC', 3]);
		}

		{
			// rotate right (inside middle)
			const trie = new TernarySearchTree<string, number>(new PathIterator());
			trie.set('/mid/fileC', 3);
			trie.set('/mid/fileB', 2);
			trie.set('/mid/fileA', 1);
			assertTstDfs(trie, ['/mid/fileA', 1], ['/mid/fileB', 2], ['/mid/fileC', 3]);
		}

		{
			// rotate right, left
			const trie = new TernarySearchTree<string, number>(new PathIterator());
			trie.set('/fileD', 7);
			trie.set('/fileB', 2);
			trie.set('/fileG', 42);
			trie.set('/fileF', 24);
			trie.set('/fileZ', 73);
			trie.set('/fileE', 15);
			assertTstDfs(trie, ['/fileB', 2], ['/fileD', 7], ['/fileE', 15], ['/fileF', 24], ['/fileG', 42], ['/fileZ', 73]);
		}

		{
			// rotate left, right
			const trie = new TernarySearchTree<string, number>(new PathIterator());
			trie.set('/fileJ', 42);
			trie.set('/fileZ', 73);
			trie.set('/fileE', 15);
			trie.set('/fileB', 2);
			trie.set('/fileF', 7);
			trie.set('/fileG', 1);
			assertTstDfs(trie, ['/fileB', 2], ['/fileE', 15], ['/fileF', 7], ['/fileG', 1], ['/fileJ', 42], ['/fileZ', 73]);
		}
	});

	test('TernarySearchTree - (BST) delete', function () {

		const trie = new TernarySearchTree<string, number>(new StringIterator());

		// delete root
		trie.set('d', 1);
		assertTstDfs(trie, ['d', 1]);
		trie.delete('d');
		assertTstDfs(trie);

		// delete node with two element
		trie.clear();
		trie.set('d', 1);
		trie.set('b', 1);
		trie.set('f', 1);
		assertTstDfs(trie, ['b', 1], ['d', 1], ['f', 1]);
		trie.delete('d');
		assertTstDfs(trie, ['b', 1], ['f', 1]);

		// single child node
		trie.clear();
		trie.set('d', 1);
		trie.set('b', 1);
		trie.set('f', 1);
		trie.set('e', 1);
		assertTstDfs(trie, ['b', 1], ['d', 1], ['e', 1], ['f', 1]);
		trie.delete('f');
		assertTstDfs(trie, ['b', 1], ['d', 1], ['e', 1]);
	});

	test('TernarySearchTree - (AVL) delete', function () {

		const trie = new TernarySearchTree<string, number>(new StringIterator());

		trie.clear();
		trie.set('d', 1);
		trie.set('b', 1);
		trie.set('f', 1);
		trie.set('e', 1);
		trie.set('z', 1);
		assertTstDfs(trie, ['b', 1], ['d', 1], ['e', 1], ['f', 1], ['z', 1]);

		// right, right
		trie.delete('b');
		assertTstDfs(trie, ['d', 1], ['e', 1], ['f', 1], ['z', 1]);

		trie.clear();
		trie.set('d', 1);
		trie.set('c', 1);
		trie.set('f', 1);
		trie.set('a', 1);
		trie.set('b', 1);
		assertTstDfs(trie, ['a', 1], ['b', 1], ['c', 1], ['d', 1], ['f', 1]);

		// left, left
		trie.delete('f');
		assertTstDfs(trie, ['a', 1], ['b', 1], ['c', 1], ['d', 1]);

		// mid
		trie.clear();
		trie.set('a', 1);
		trie.set('ad', 1);
		trie.set('ab', 1);
		trie.set('af', 1);
		trie.set('ae', 1);
		trie.set('az', 1);
		assertTstDfs(trie, ['a', 1], ['ab', 1], ['ad', 1], ['ae', 1], ['af', 1], ['az', 1]);

		trie.delete('ab');
		assertTstDfs(trie, ['a', 1], ['ad', 1], ['ae', 1], ['af', 1], ['az', 1]);

		trie.delete('a');
		assertTstDfs(trie, ['ad', 1], ['ae', 1], ['af', 1], ['az', 1]);
	});

	test('TernarySearchTree: Cannot read property \'1\' of undefined #138284', function () {

		const keys = [
			URI.parse('fake-fs:/C'),
			URI.parse('fake-fs:/A'),
			URI.parse('fake-fs:/D'),
			URI.parse('fake-fs:/B'),
		];

		const tst = TernarySearchTree.forUris<boolean>();

		for (const item of keys) {
			tst.set(item, true);
		}

		assert.ok(tst._isBalanced());
		tst.delete(keys[0]);
		assert.ok(tst._isBalanced());
	});

	test('TernarySearchTree: Cannot read property \'1\' of undefined #138284 (simple)', function () {

		const keys = ['C', 'A', 'D', 'B',];
		const tst = TernarySearchTree.forStrings<boolean>();
		for (const item of keys) {
			tst.set(item, true);
		}
		assertTstDfs(tst, ['A', true], ['B', true], ['C', true], ['D', true]);

		tst.delete(keys[0]);
		assertTstDfs(tst, ['A', true], ['B', true], ['D', true]);

		{
			const tst = TernarySearchTree.forStrings<boolean>();
			tst.set('C', true);
			tst.set('A', true);
			tst.set('B', true);
			assertTstDfs(tst, ['A', true], ['B', true], ['C', true]);
		}

	});

	test('TernarySearchTree: Cannot read property \'1\' of undefined #138284 (random)', function () {
		for (let round = 10; round >= 0; round--) {
			const keys: URI[] = [];
			for (let i = 0; i < 100; i++) {
				keys.push(URI.from({ scheme: 'fake-fs', path: randomPath(undefined, undefined, 10) }));
			}
			const tst = TernarySearchTree.forUris<boolean>();

			for (const item of keys) {
				tst.set(item, true);
				assert.ok(tst._isBalanced(), `SET${item}|${keys.map(String).join()}`);
			}

			for (const item of keys) {
				tst.delete(item);
				assert.ok(tst._isBalanced(), `DEL${item}|${keys.map(String).join()}`);
			}
		}
	});

	test('TernarySearchTree (PathSegments) - lookup', function () {

		const map = new TernarySearchTree<string, number>(new PathIterator());
		map.set('/user/foo/bar', 1);
		map.set('/user/foo', 2);
{'fraction_non_alphanumeric': 0.24477690501255162, 'fraction_numerical': 0.020244554214916187, 'mean_word_length': 3.862866706044497, 'pattern_counts': {'":': 0, '<': 109, '<?xml version=': 0, '>': 155, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3728995', 'n_tokens_mistral': 21352, 'n_tokens_neox': 18490, 'n_words': 3566}