// splaytree-ts v1.0.2 Copyright (c) 2022, Luiz Felipe Machado Barboza
(function (global, factory) {
typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
typeof define === 'function' && define.amd ? define(['exports'], factory) :
(global = typeof globalThis !== 'undefined' ? globalThis : global || self, factory(global["splaytree-ts"] = global["splaytree-ts"] || {}));
})(this, (function (exports) { 'use strict';

var version = "1.0.2";

class SplayTreeNode {
    key;
    left = null;
    right = null;
    constructor(key) {
        this.key = key;
    }
}
class SplayTreeSetNode extends SplayTreeNode {
    constructor(key) {
        super(key);
    }
}
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;
    }
}
class SplayTree {
    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); },
        };
    }
}
class SplayTreeMap extends SplayTree {
    root = null;
    compare;
    validKey;
    constructor(compare, isValidKey) {
        super();
        this.compare = compare ?? this.defaultCompare();
        this.validKey = isValidKey ?? ((a) => a != null && a != undefined);
    }
    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 undefined;
        if (this.root != null) {
            const comp = this.splay(key);
            if (comp == 0) {
                return this.root.value;
            }
        }
        return undefined;
    }
    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]';
}
class SplayTreeSet extends SplayTree {
    root = null;
    compare;
    validKey;
    constructor(compare, isValidKey) {
        super();
        this.compare = compare ?? this.defaultCompare();
        this.validKey = isValidKey ?? ((v) => v != null && v != undefined);
    }
    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(node, dest) {
            let left;
            let right;
            do {
                left = node.left;
                right = node.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;
                    node = 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]';
}
class SplayTreeIterableIterator {
    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 node = this.tree.getRoot();
                while (node != null) {
                    this.path.push(node);
                    node = node.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;
    }
}
class SplayTreeKeyIterableIterator extends SplayTreeIterableIterator {
    getValue(node) {
        return node.key;
    }
}
class SplayTreeSetEntryIterableIterator extends SplayTreeIterableIterator {
    getValue(node) {
        return [node.key, node.key];
    }
}
class SplayTreeValueIterableIterator extends SplayTreeIterableIterator {
    constructor(map) {
        super(map);
    }
    getValue(node) {
        return node.value;
    }
}
class SplayTreeMapEntryIterableIterator 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;
    }
}

exports.SplayTreeMap = SplayTreeMap;
exports.SplayTreeSet = SplayTreeSet;
exports.version = version;

Object.defineProperty(exports, '__esModule', { value: true });

}));