src/vs/base/common/ternarySearchTree.ts/TernarySearchTree/set
class TernarySearchTree:	set(key: K, element: V): V | undefined {
		const iter = this._iter.reset(key);
		let node: TernarySearchTreeNode<K, V>;

		if (!this._root) {
			this._root = new TernarySearchTreeNode<K, V>();
			this._root.segment = iter.value();
		}
		const stack: [Dir, TernarySearchTreeNode<K, V>][] = [];

		// find insert_node
		node = this._root;
		while (true) {
			const val = iter.cmp(node.segment);
			if (val > 0) {
				// left
				if (!node.left) {
					node.left = new TernarySearchTreeNode<K, V>();
					node.left.segment = iter.value();
				}
				stack.push([Dir.Left, node]);
				node = node.left;

			} else if (val < 0) {
				// right
				if (!node.right) {
					node.right = new TernarySearchTreeNode<K, V>();
					node.right.segment = iter.value();
				}
				stack.push([Dir.Right, node]);
				node = node.right;

			} else if (iter.hasNext()) {
				// mid
				iter.next();
				if (!node.mid) {
					node.mid = new TernarySearchTreeNode<K, V>();
					node.mid.segment = iter.value();
				}
				stack.push([Dir.Mid, node]);
				node = node.mid;
			} else {
				break;
			}
		}

		// set value
		const oldElement = node.value;
		node.value = element;
		node.key = key;

		// balance
		for (let i = stack.length - 1; i >= 0; i--) {
			const node = stack[i][1];

			node.updateHeight();
			const bf = node.balanceFactor();

			if (bf < -1 || bf > 1) {
				// needs rotate
				const d1 = stack[i][0];
				const d2 = stack[i + 1][0];

				if (d1 === Dir.Right && d2 === Dir.Right) {
					//right, right -> rotate left
					stack[i][1] = node.rotateLeft();

				} else if (d1 === Dir.Left && d2 === Dir.Left) {
					// left, left -> rotate right
					stack[i][1] = node.rotateRight();

				} else if (d1 === Dir.Right && d2 === Dir.Left) {
					// right, left -> double rotate right, left
					node.right = stack[i + 1][1] = stack[i + 1][1].rotateRight();
					stack[i][1] = node.rotateLeft();

				} else if (d1 === Dir.Left && d2 === Dir.Right) {
					// left, right -> double rotate left, right
					node.left = stack[i + 1][1] = stack[i + 1][1].rotateLeft();
					stack[i][1] = node.rotateRight();

				} else {
					throw new Error();
				}

				// patch path to parent
				if (i > 0) {
					switch (stack[i - 1][0]) {
						case Dir.Left:
							stack[i - 1][1].left = stack[i][1];
							break;
						case Dir.Right:
							stack[i - 1][1].right = stack[i][1];
							break;
						case Dir.Mid:
							stack[i - 1][1].mid = stack[i][1];
							break;
					}
				} else {
					this._root = stack[0][1];
				}
			}
		}

		return oldElement;
	}