b-tree with typescript

typescriptで組んだB木です。
便利ですよー。
<<<<<<< HEAD

```text：btree.ts
=======

```btree.ts
>>>>>>> EDIT_REQUEST
class bNode{
    barray: bArray;
    key: any;
    parentNode: bNode = null;
    isLeafNode: bool;
    data:any[];
    constructor (barray: bArray, isleaf: bool) {
        this.barray = barray;
        this.isLeafNode = isleaf;
        this.data = [];
        if (isleaf == true) this.barray.leaf_nodes.push(this);
    }

    split () : bNode {
        var tmp = new bNode(this.barray, this.isLeafNode);
        var m = Math.ceil(this.data.length / 2);
        // Copy & shift data
        for (var i = 0; i < m; i++) {
            if (this.data[0].parentNode !== undefined) this.data[0].parentNode = tmp;
            tmp.data.push(this.data.shift());
        }
        var key = tmp.key = tmp.data[tmp.data.length - 1].key;
        if (this.parentNode == null) {
            var p = new bNode(this.barray, false);
            this.parentNode = tmp.parentNode = p;
            this.parentNode.data.push(tmp);
            this.parentNode.data.push(this);
            p.key = p.data[p.data.length - 1].key;
            return p;
        }
        return this.parentNode.insert_node(key, tmp);
    }
    insert (key, value) : bNode {
        var pos = 0;
        for (; pos < this.data.length; pos++) {
            if (this.data[pos].key == key) {
                this.data[pos].value = value;
                return null;
            }
            if (this.data[pos].key > key) break;
        }
        this.data.splice(pos, 0, { "key": key, "value": value, parentNode: this });
        this.key = this.data[this.data.length - 1].key;
        // Split
        if (this.data.length > this.barray.order) return this.split();
        return null;
    }
    insert_node(key, node): bNode {
        node.parentNode = this;
        var pos = 0;
        for (; pos < this.data.length; pos++) {
            if (this.data[pos].key > key) break;
        }
        this.data.splice(pos, 0, node);
        this.key = this.data[this.data.length - 1].key;
        if (this.data.length > this.barray.order) {
            return this.split();
        }
        return null;
    }
    delete (obj: { trace: number[]; node: bNode; }) {
        obj.node = obj.node.parentNode;
        for (; ;) {
            if (obj.node.data.length == 1) {
                obj.node = obj.node.parentNode;
                if (obj.node == null) {
                    this.barray.root = null;
                    return;
                }
                obj.trace.shift();
            }
            else break;
        }
        if (obj.trace[0] == obj.node.data.length - 1) obj.node.key = obj.node.data[obj.node.data.length - 2].key;
        obj.node.data.splice(obj.trace[0], 1);
    }
}
class bArray {
    order: number = 100;
    root: bNode;
    leaf_nodes: bNode[] = [];
    constructor (order?: number) {
        this.order = order;
        this.root = new bNode(this, true);
    }
    restruct() {
        if (this.leaf_nodes.length > 10);
        var n = Math.floor(this.leaf_nodes.length / 2);
        this.root = new bNode(this, false);
        this.root.insert_node(this.leaf_nodes[0].key, this.leaf_nodes[0]);
        for (var i = 1;  i < this.leaf_nodes.length; i++) {
            var leaf_node = this.leaf_nodes[(n + i) * 9998797 % this.leaf_nodes.length];
            var ret = this._search(leaf_node.key).node.parentNode.insert_node(leaf_node.key, leaf_node);
            if (ret != null) this.root = ret;
        }
    }
    set (key: any, value: any) {
        var node = this._search(key).node;
        var ret = node.insert(key, value);
        if (ret != null) this.root = ret;
    }
    set_with_array(datas: { key: any; value: any; }[]) {
        for (var i = 0; i < datas.length; i++) {
            var n = i * 9998797 % datas.length;
            this.set(datas[n].key, datas[i].value);
        }
    }
    get (key: any): any{
        var node = this._search(key).node;
        for (var i = 0; i < node.data.length; i++) {
            if (node.data[i].key == key) return node.data[i].value;
        }
        return null;
    }
    delete (key: any): any {
        var node = this._search(key);
        var ret;
        for (var i = 0; i < node.node.data.length; i++) {
            if (node.node.data[i].key == key) {
                if (i == node.node.data.length - 1) {
                    if (node.node.data[0].length == 1) {
                        node.node.delete (node);
                        return node.node.data[0].value;
                    }
                    else node.node.key = node.node.data[node.node.data.length - 2].key;
                }
                ret = node.node.data[i].value;
                node.node.data.splice(i, 1);
                return ret;
            }
        }
        return null;
    }
    delete_in(from: any, to: any) {
        var from_node = this._search(from);
        var to_node = this._search(to);
        var array = [];
        var i = 0;
        for (; i < from_node.node.data.length; i++) {
            if (from_node.node.data[i].key > from) {
                break;
            }
        }
        var now = from_node.node;
        for (; ;) {
            if (now == to_node.node) break;
            //
            now.data.splice(i, now.data.length - i);
            if (now.data.length == 0) {
                from_node.node = now;
                now.delete (from_node);
                from_node.trace[0]--;
            }
            //
            for (; ;) {
                from_node.trace[0]++;
                if (from_node.trace[0] >= now.parentNode.data.length) {
                    now = now.parentNode;
                    if (now == null) return array;
                    from_node.trace.shift();
                }
                else {
                    now = now.parentNode.data[from_node.trace[0]];
                    break;
                }
            }
            for (; now.isLeafNode == false;) {
                now = now.data[0];
            }
            i = 0;
        }
        for (; i < to_node.node.data.length; i++) {
            if (i == to_node.node.data.length || to_node.node.data[i].key > to) {
                to_node.node.data.splice(0, i - 1);
                if (to_node.node.data.length == 0) to_node.node.delete(to_node);
                break;
            }
        }
    }
    in (from: any, to: any) : any[]{
        var from_node = this._search(from);
        var to_node = this._search(to);
        var array = [];
        var i = 0;
        for(; i < from_node.node.data.length; i++) {
            if (from_node.node.data[i].key > from) {
                break;
            }
        }
        var now = from_node.node;
        for (; ;) {
            if (now == to_node.node) break;
            //
            for (; i < now.data.length; i++) array.push(now.data[i].value);
            //
            for (; ;) {
                from_node.trace[0]++;
                if (from_node.trace[0] >= now.parentNode.data.length) {
                    now = now.parentNode;
                    if (now == null) return array;
                    from_node.trace.shift();
                }
                else {
                    now = now.parentNode.data[from_node.trace[0]];
                    break;
                }
            }
            for (; now.isLeafNode == false;) {
                now = now.data[0];
                from_node.trace.push(0);
            }
            i = 0;
        }
        for (; i < to_node.node.data.length; i++) {
            if (to_node.node.data[i].key > to) break;
            array.push(to_node.node.data[i].value);
        }
        return array;
    }
    getNode (key: any) : bNode{
        return this._search(key).node;
    }
    _search(key: any): { trace: number[]; node: bNode; } {
        var current = this.root;
        var found = false;
        var array = [];
        while (current.isLeafNode == false) {
            found = false;
            var len = current.data.length;
            for (var i = 0; i < len; i++) {
                if (current.data[i].key >= key) {
                    current = current.data[i];
                    found = true;
                    array.unshift(i);
                    break;
                }
            }

            // Follow infinity pointer
            if (found == false) {
                current = current.data[len - 1];
                array.unshift(len - 1);
            }
        }
        return { trace: array, node: current };
    }
}
```