"use strict"; var __defProp = Object.defineProperty; var __getOwnPropDesc = Object.getOwnPropertyDescriptor; var __getOwnPropNames = Object.getOwnPropertyNames; var __hasOwnProp = Object.prototype.hasOwnProperty; var __export = (target, all) => { for (var name in all) __defProp(target, name, { get: all[name], enumerable: true }); }; var __copyProps = (to, from, except, desc) => { if (from && typeof from === "object" || typeof from === "function") { for (let key of __getOwnPropNames(from)) if (!__hasOwnProp.call(to, key) && key !== except) __defProp(to, key, { get: () => from[key], enumerable: !(desc = __getOwnPropDesc(from, key)) || desc.enumerable }); } return to; }; var __toCommonJS = (mod) => __copyProps(__defProp({}, "__esModule", { value: true }), mod); // src/index.ts var src_exports = {}; __export(src_exports, { SplayTreeMap: () => SplayTreeMap, SplayTreeSet: () => SplayTreeSet }); module.exports = __toCommonJS(src_exports); var SplayTreeNode = class { key; left = null; right = null; constructor(key) { this.key = key; } }; var SplayTreeSetNode = class extends SplayTreeNode { constructor(key) { super(key); } }; var SplayTreeMapNode = class _SplayTreeMapNode extends SplayTreeNode { value; constructor(key, value) { super(key); this.value = value; } replaceValue(value) { const node = new _SplayTreeMapNode(this.key, value); node.left = this.left; node.right = this.right; return node; } }; var SplayTree = class { size = 0; modificationCount = 0; splayCount = 0; splay(key) { const root = this.root; if (root == null) { this.compare(key, key); return -1; } let right = null; let newTreeRight = null; let left = null; let newTreeLeft = null; let current = root; const compare = this.compare; let comp; while (true) { comp = compare(current.key, key); if (comp > 0) { let currentLeft = current.left; if (currentLeft == null) break; comp = compare(currentLeft.key, key); if (comp > 0) { current.left = currentLeft.right; currentLeft.right = current; current = currentLeft; currentLeft = current.left; if (currentLeft == null) break; } if (right == null) { newTreeRight = current; } else { right.left = current; } right = current; current = currentLeft; } else if (comp < 0) { let currentRight = current.right; if (currentRight == null) break; comp = compare(currentRight.key, key); if (comp < 0) { current.right = currentRight.left; currentRight.left = current; current = currentRight; currentRight = current.right; if (currentRight == null) break; } if (left == null) { newTreeLeft = current; } else { left.right = current; } left = current; current = currentRight; } else { break; } } if (left != null) { left.right = current.left; current.left = newTreeLeft; } if (right != null) { right.left = current.right; current.right = newTreeRight; } if (this.root !== current) { this.root = current; this.splayCount++; } return comp; } splayMin(node) { let current = node; let nextLeft = current.left; while (nextLeft != null) { const left = nextLeft; current.left = left.right; left.right = current; current = left; nextLeft = current.left; } return current; } splayMax(node) { let current = node; let nextRight = current.right; while (nextRight != null) { const right = nextRight; current.right = right.left; right.left = current; current = right; nextRight = current.right; } return current; } _delete(key) { if (this.root == null) return null; const comp = this.splay(key); if (comp != 0) return null; let root = this.root; const result = root; const left = root.left; this.size--; if (left == null) { this.root = root.right; } else { const right = root.right; root = this.splayMax(left); root.right = right; this.root = root; } this.modificationCount++; return result; } addNewRoot(node, comp) { this.size++; this.modificationCount++; const root = this.root; if (root == null) { this.root = node; return; } if (comp < 0) { node.left = root; node.right = root.right; root.right = null; } else { node.right = root; node.left = root.left; root.left = null; } this.root = node; } _first() { const root = this.root; if (root == null) return null; this.root = this.splayMin(root); return this.root; } _last() { const root = this.root; if (root == null) return null; this.root = this.splayMax(root); return this.root; } clear() { this.root = null; this.size = 0; this.modificationCount++; } has(key) { return this.validKey(key) && this.splay(key) == 0; } defaultCompare() { return (a, b) => a < b ? -1 : a > b ? 1 : 0; } wrap() { return { getRoot: () => { return this.root; }, setRoot: (root) => { this.root = root; }, getSize: () => { return this.size; }, getModificationCount: () => { return this.modificationCount; }, getSplayCount: () => { return this.splayCount; }, setSplayCount: (count) => { this.splayCount = count; }, splay: (key) => { return this.splay(key); }, has: (key) => { return this.has(key); } }; } }; var SplayTreeMap = class extends SplayTree { root = null; compare; validKey; constructor(compare, isValidKey) { super(); this.compare = compare ?? this.defaultCompare(); this.validKey = isValidKey ?? ((a) => a != null && a != void 0); } delete(key) { if (!this.validKey(key)) return false; return this._delete(key) != null; } forEach(f) { const nodes = new SplayTreeMapEntryIterableIterator(this.wrap()); let result; while (result = nodes.next(), !result.done) { f(result.value[1], result.value[0], this); } } get(key) { if (!this.validKey(key)) return void 0; if (this.root != null) { const comp = this.splay(key); if (comp == 0) { return this.root.value; } } return void 0; } hasValue(value) { const initialSplayCount = this.splayCount; const visit = (node) => { while (node != null) { if (node.value == value) return true; if (initialSplayCount != this.splayCount) { throw "Concurrent modification during iteration."; } if (node.right != null && visit(node.right)) { return true; } node = node.left; } return false; }; return visit(this.root); } set(key, value) { const comp = this.splay(key); if (comp == 0) { this.root = this.root.replaceValue(value); this.splayCount += 1; return this; } this.addNewRoot(new SplayTreeMapNode(key, value), comp); return this; } setAll(other) { other.forEach((value, key) => { this.set(key, value); }); } setIfAbsent(key, ifAbsent) { let comp = this.splay(key); if (comp == 0) { return this.root.value; } const modificationCount = this.modificationCount; const splayCount = this.splayCount; const value = ifAbsent(); if (modificationCount != this.modificationCount) { throw "Concurrent modification during iteration."; } if (splayCount != this.splayCount) { comp = this.splay(key); } this.addNewRoot(new SplayTreeMapNode(key, value), comp); return value; } isEmpty() { return this.root == null; } isNotEmpty() { return !this.isEmpty(); } firstKey() { if (this.root == null) return null; return this._first().key; } lastKey() { if (this.root == null) return null; return this._last().key; } lastKeyBefore(key) { if (key == null) throw "Invalid arguments(s)"; if (this.root == null) return null; const comp = this.splay(key); if (comp < 0) return this.root.key; let node = this.root.left; if (node == null) return null; let nodeRight = node.right; while (nodeRight != null) { node = nodeRight; nodeRight = node.right; } return node.key; } firstKeyAfter(key) { if (key == null) throw "Invalid arguments(s)"; if (this.root == null) return null; const comp = this.splay(key); if (comp > 0) return this.root.key; let node = this.root.right; if (node == null) return null; let nodeLeft = node.left; while (nodeLeft != null) { node = nodeLeft; nodeLeft = node.left; } return node.key; } update(key, update, ifAbsent) { let comp = this.splay(key); if (comp == 0) { const modificationCount = this.modificationCount; const splayCount = this.splayCount; const newValue = update(this.root.value); if (modificationCount != this.modificationCount) { throw "Concurrent modification during iteration."; } if (splayCount != this.splayCount) { this.splay(key); } this.root = this.root.replaceValue(newValue); this.splayCount += 1; return newValue; } if (ifAbsent != null) { const modificationCount = this.modificationCount; const splayCount = this.splayCount; const newValue = ifAbsent(); if (modificationCount != this.modificationCount) { throw "Concurrent modification during iteration."; } if (splayCount != this.splayCount) { comp = this.splay(key); } this.addNewRoot(new SplayTreeMapNode(key, newValue), comp); return newValue; } throw "Invalid argument (key): Key not in map."; } updateAll(update) { const root = this.root; if (root == null) return; const iterator = new SplayTreeMapEntryIterableIterator(this.wrap()); let node; while (node = iterator.next(), !node.done) { const newValue = update(...node.value); iterator.replaceValue(newValue); } } keys() { return new SplayTreeKeyIterableIterator(this.wrap()); } values() { return new SplayTreeValueIterableIterator(this.wrap()); } entries() { return this[Symbol.iterator](); } [Symbol.iterator]() { return new SplayTreeMapEntryIterableIterator(this.wrap()); } [Symbol.toStringTag] = "[object Map]"; }; var SplayTreeSet = class _SplayTreeSet extends SplayTree { root = null; compare; validKey; constructor(compare, isValidKey) { super(); this.compare = compare ?? this.defaultCompare(); this.validKey = isValidKey ?? ((v) => v != null && v != void 0); } delete(element) { if (!this.validKey(element)) return false; return this._delete(element) != null; } deleteAll(elements) { for (const element of elements) { this.delete(element); } } forEach(f) { const nodes = this[Symbol.iterator](); let result; while (result = nodes.next(), !result.done) { f(result.value, result.value, this); } } add(element) { const compare = this.splay(element); if (compare != 0) this.addNewRoot(new SplayTreeSetNode(element), compare); return this; } addAndReturn(element) { const compare = this.splay(element); if (compare != 0) this.addNewRoot(new SplayTreeSetNode(element), compare); return this.root.key; } addAll(elements) { for (const element of elements) { this.add(element); } } isEmpty() { return this.root == null; } isNotEmpty() { return this.root != null; } single() { if (this.size == 0) throw "Bad state: No element"; if (this.size > 1) throw "Bad state: Too many element"; return this.root.key; } first() { if (this.size == 0) throw "Bad state: No element"; return this._first().key; } last() { if (this.size == 0) throw "Bad state: No element"; return this._last().key; } lastBefore(element) { if (element == null) throw "Invalid arguments(s)"; if (this.root == null) return null; const comp = this.splay(element); if (comp < 0) return this.root.key; let node = this.root.left; if (node == null) return null; let nodeRight = node.right; while (nodeRight != null) { node = nodeRight; nodeRight = node.right; } return node.key; } firstAfter(element) { if (element == null) throw "Invalid arguments(s)"; if (this.root == null) return null; const comp = this.splay(element); if (comp > 0) return this.root.key; let node = this.root.right; if (node == null) return null; let nodeLeft = node.left; while (nodeLeft != null) { node = nodeLeft; nodeLeft = node.left; } return node.key; } retainAll(elements) { const retainSet = new _SplayTreeSet(this.compare, this.validKey); const modificationCount = this.modificationCount; for (const object of elements) { if (modificationCount != this.modificationCount) { throw "Concurrent modification during iteration."; } if (this.validKey(object) && this.splay(object) == 0) { retainSet.add(this.root.key); } } if (retainSet.size != this.size) { this.root = retainSet.root; this.size = retainSet.size; this.modificationCount++; } } lookup(object) { if (!this.validKey(object)) return null; const comp = this.splay(object); if (comp != 0) return null; return this.root.key; } intersection(other) { const result = new _SplayTreeSet(this.compare, this.validKey); for (const element of this) { if (other.has(element)) result.add(element); } return result; } difference(other) { const result = new _SplayTreeSet(this.compare, this.validKey); for (const element of this) { if (!other.has(element)) result.add(element); } return result; } union(other) { const u = this.clone(); u.addAll(other); return u; } clone() { const set = new _SplayTreeSet(this.compare, this.validKey); set.size = this.size; set.root = this.copyNode(this.root); return set; } copyNode(node) { if (node == null) return null; function copyChildren(node2, dest) { let left; let right; do { left = node2.left; right = node2.right; if (left != null) { const newLeft = new SplayTreeSetNode(left.key); dest.left = newLeft; copyChildren(left, newLeft); } if (right != null) { const newRight = new SplayTreeSetNode(right.key); dest.right = newRight; node2 = right; dest = newRight; } } while (right != null); } const result = new SplayTreeSetNode(node.key); copyChildren(node, result); return result; } toSet() { return this.clone(); } entries() { return new SplayTreeSetEntryIterableIterator(this.wrap()); } keys() { return this[Symbol.iterator](); } values() { return this[Symbol.iterator](); } [Symbol.iterator]() { return new SplayTreeKeyIterableIterator(this.wrap()); } [Symbol.toStringTag] = "[object Set]"; }; var SplayTreeIterableIterator = class { tree; path = new Array(); modificationCount = null; splayCount; constructor(tree) { this.tree = tree; this.splayCount = tree.getSplayCount(); } [Symbol.iterator]() { return this; } next() { if (this.moveNext()) return { done: false, value: this.current() }; return { done: true, value: null }; } current() { if (!this.path.length) return null; const node = this.path[this.path.length - 1]; return this.getValue(node); } rebuildPath(key) { this.path.splice(0, this.path.length); this.tree.splay(key); this.path.push(this.tree.getRoot()); this.splayCount = this.tree.getSplayCount(); } findLeftMostDescendent(node) { while (node != null) { this.path.push(node); node = node.left; } } moveNext() { if (this.modificationCount != this.tree.getModificationCount()) { if (this.modificationCount == null) { this.modificationCount = this.tree.getModificationCount(); let node2 = this.tree.getRoot(); while (node2 != null) { this.path.push(node2); node2 = node2.left; } return this.path.length > 0; } throw "Concurrent modification during iteration."; } if (!this.path.length) return false; if (this.splayCount != this.tree.getSplayCount()) { this.rebuildPath(this.path[this.path.length - 1].key); } let node = this.path[this.path.length - 1]; let next = node.right; if (next != null) { while (next != null) { this.path.push(next); next = next.left; } return true; } this.path.pop(); while (this.path.length && this.path[this.path.length - 1].right === node) { node = this.path.pop(); } return this.path.length > 0; } }; var SplayTreeKeyIterableIterator = class extends SplayTreeIterableIterator { getValue(node) { return node.key; } }; var SplayTreeSetEntryIterableIterator = class extends SplayTreeIterableIterator { getValue(node) { return [node.key, node.key]; } }; var SplayTreeValueIterableIterator = class extends SplayTreeIterableIterator { constructor(map) { super(map); } getValue(node) { return node.value; } }; var SplayTreeMapEntryIterableIterator = class extends SplayTreeIterableIterator { constructor(map) { super(map); } getValue(node) { return [node.key, node.value]; } replaceValue(value) { if (this.modificationCount != this.tree.getModificationCount()) { throw "Concurrent modification during iteration."; } if (this.splayCount != this.tree.getSplayCount()) { this.rebuildPath(this.path[this.path.length - 1].key); } const last = this.path.pop(); const newLast = last.replaceValue(value); if (!this.path.length) { this.tree.setRoot(newLast); } else { const parent = this.path[this.path.length - 1]; if (last === parent.left) { parent.left = newLast; } else { parent.right = newLast; } } this.path.push(newLast); const count = this.tree.getSplayCount() + 1; this.tree.setSplayCount(count); this.splayCount = count; } }; // Annotate the CommonJS export names for ESM import in node: 0 && (module.exports = { SplayTreeMap, SplayTreeSet }); //# sourceMappingURL=index.cjs.map