js-sdsl - npm Package Compare versions

Comparing version 1.2.1 to 1.2.2

dist/cjs/Base/Base.d.ts

@@ -6,12 +6,14 @@ export declare type BaseType = {
 } & Record<string, never>;
-export declare type SequentialContainerType<T> = {
+export declare type ContainerType<T> = {
     front: () => T | undefined;
     back: () => T | undefined;
-    push_back: (element: T) => void;
-    pop_back: () => void;
     forEach: (callback: (element: T, index: number) => void) => void;
     getElementByPos: (pos: number) => T;
-    setElementByPos: (pos: number, element: T) => void;
     eraseElementByPos: (pos: number) => void;
     eraseElementByValue: (value: T) => void;
+} & BaseType;
+export declare type SequentialContainerType<T> = {
+    push_back: (element: T) => void;
+    pop_back: () => void;
+    setElementByPos: (pos: number, element: T) => void;
     insert: (pos: number, element: T, num?: number) => void;
@@ -21,2 +23,8 @@ reverse: () => void;
     sort: (cmp?: (x: T, y: T) => number) => void;
-} & BaseType;
+} & ContainerType<T>;
+export declare type AssociativeContainersType<T> = {
+    insert: (element: T) => void;
+    find: (element: T) => boolean;
+    union: (other: AssociativeContainersType<T>) => void;
+    getHeight: () => number;
+} & ContainerType<T>;

dist/cjs/Deque/Deque.js

@@ -47,35 +47,2 @@ "use strict";
     };
-    var reAllocate = function (originalSize) {
-        var newMap = [];
-        var needSize = originalSize * Deque.sigma;
-        var newBucketNum = Math.max(Math.ceil(needSize / Deque.bucketSize), 2);
-        for (var i = 0; i < newBucketNum; ++i) {
-            newMap.push(new Array(Deque.bucketSize));
-        }
-        var needBucketNum = Math.ceil(originalSize / Deque.bucketSize);
-        var newFirst = Math.floor(newBucketNum / 2) - Math.floor(needBucketNum / 2);
-        var newLast = newFirst, newCurLast = 0;
-        if (this.size()) {
-            for (var i = 0; i < needBucketNum; ++i) {
-                for (var j = 0; j < Deque.bucketSize; ++j) {
-                    newMap[newFirst + i][j] = this.front();
-                    this.pop_front();
-                    if (this.empty()) {
-                        newLast = newFirst + i;
-                        newCurLast = j;
-                        break;
-                    }
-                }
-                if (this.empty())
-                    break;
-            }
-        }
-        map = newMap;
-        first = newFirst;
-        curFirst = 0;
-        last = newLast;
-        curLast = newCurLast;
-        bucketNum = newBucketNum;
-        len = originalSize;
-    };
     this.front = function () {
@@ -87,33 +54,2 @@ return map[first][curFirst];
     };
-    this.push_back = function (element) {
-        if (!this.empty()) {
-            if (last === bucketNum - 1 && curLast === Deque.bucketSize - 1) {
-                reAllocate.call(this, this.size());
-            }
-            if (curLast < Deque.bucketSize - 1) {
-                ++curLast;
-            }
-            else if (last < bucketNum - 1) {
-                ++last;
-                curLast = 0;
-            }
-        }
-        ++len;
-        map[last][curLast] = element;
-    };
-    this.pop_back = function () {
-        if (this.empty())
-            return;
-        if (this.size() !== 1) {
-            if (curLast > 0) {
-                --curLast;
-            }
-            else if (first < last) {
-                --last;
-                curLast = Deque.bucketSize - 1;
-            }
-        }
-        if (len > 0)
-            --len;
-    };
     this.forEach = function (callback) {
@@ -158,6 +94,2 @@ if (this.empty())
     };
-    this.setElementByPos = function (pos, element) {
-        var _a = getElementIndex(pos), curNodeBucketIndex = _a.curNodeBucketIndex, curNodePointerIndex = _a.curNodePointerIndex;
-        map[curNodeBucketIndex][curNodePointerIndex] = element;
-    };
     this.eraseElementByPos = function (pos) {
@@ -191,2 +123,70 @@ var _this = this;
     };
+    var reAllocate = function (originalSize) {
+        var newMap = [];
+        var needSize = originalSize * Deque.sigma;
+        var newBucketNum = Math.max(Math.ceil(needSize / Deque.bucketSize), 2);
+        for (var i = 0; i < newBucketNum; ++i) {
+            newMap.push(new Array(Deque.bucketSize));
+        }
+        var needBucketNum = Math.ceil(originalSize / Deque.bucketSize);
+        var newFirst = Math.floor(newBucketNum / 2) - Math.floor(needBucketNum / 2);
+        var newLast = newFirst, newCurLast = 0;
+        if (this.size()) {
+            for (var i = 0; i < needBucketNum; ++i) {
+                for (var j = 0; j < Deque.bucketSize; ++j) {
+                    newMap[newFirst + i][j] = this.front();
+                    this.pop_front();
+                    if (this.empty()) {
+                        newLast = newFirst + i;
+                        newCurLast = j;
+                        break;
+                    }
+                }
+                if (this.empty())
+                    break;
+            }
+        }
+        map = newMap;
+        first = newFirst;
+        curFirst = 0;
+        last = newLast;
+        curLast = newCurLast;
+        bucketNum = newBucketNum;
+        len = originalSize;
+    };
+    this.push_back = function (element) {
+        if (!this.empty()) {
+            if (last === bucketNum - 1 && curLast === Deque.bucketSize - 1) {
+                reAllocate.call(this, this.size());
+            }
+            if (curLast < Deque.bucketSize - 1) {
+                ++curLast;
+            }
+            else if (last < bucketNum - 1) {
+                ++last;
+                curLast = 0;
+            }
+        }
+        ++len;
+        map[last][curLast] = element;
+    };
+    this.pop_back = function () {
+        if (this.empty())
+            return;
+        if (this.size() !== 1) {
+            if (curLast > 0) {
+                --curLast;
+            }
+            else if (first < last) {
+                --last;
+                curLast = Deque.bucketSize - 1;
+            }
+        }
+        if (len > 0)
+            --len;
+    };
+    this.setElementByPos = function (pos, element) {
+        var _a = getElementIndex(pos), curNodeBucketIndex = _a.curNodeBucketIndex, curNodePointerIndex = _a.curNodePointerIndex;
+        map[curNodeBucketIndex][curNodePointerIndex] = element;
+    };
     /**
@@ -193,0 +193,0 @@ * @param {number} pos insert element before pos, should in [0, queue.size]

dist/cjs/LinkList/LinkList.js

@@ -43,28 +43,2 @@ "use strict";
     };
-    this.push_back = function (element) {
-        ++len;
-        var newTail = new LinkNode(element);
-        if (!tail) {
-            head = tail = newTail;
-        }
-        else {
-            tail.next = newTail;
-            newTail.pre = tail;
-            tail = newTail;
-        }
-    };
-    this.pop_back = function () {
-        if (len > 0)
-            --len;
-        if (!tail)
-            return;
-        if (head === tail) {
-            head = tail = null;
-        }
-        else {
-            tail = tail.pre;
-            if (tail)
-                tail.next = null;
-        }
-    };
     this.forEach = function (callback) {
@@ -91,14 +65,2 @@ if (typeof callback !== 'function')
     };
-    this.setElementByPos = function (pos, element) {
-        if (pos < 0 || pos >= len)
-            throw new Error("pos must more then 0 and less then the list length");
-        var curNode = head;
-        while (pos--) {
-            if (!curNode)
-                break;
-            curNode = curNode.next;
-        }
-        if (curNode)
-            curNode.val = element;
-    };
     this.eraseElementByPos = function (pos) {
@@ -151,2 +113,40 @@ if (pos < 0 || pos >= len)
     };
+    this.push_back = function (element) {
+        ++len;
+        var newTail = new LinkNode(element);
+        if (!tail) {
+            head = tail = newTail;
+        }
+        else {
+            tail.next = newTail;
+            newTail.pre = tail;
+            tail = newTail;
+        }
+    };
+    this.pop_back = function () {
+        if (len > 0)
+            --len;
+        if (!tail)
+            return;
+        if (head === tail) {
+            head = tail = null;
+        }
+        else {
+            tail = tail.pre;
+            if (tail)
+                tail.next = null;
+        }
+    };
+    this.setElementByPos = function (pos, element) {
+        if (pos < 0 || pos >= len)
+            throw new Error("pos must more then 0 and less then the list length");
+        var curNode = head;
+        while (pos--) {
+            if (!curNode)
+                break;
+            curNode = curNode.next;
+        }
+        if (curNode)
+            curNode.val = element;
+    };
     /**
@@ -153,0 +153,0 @@ * @param {number} pos insert element before pos, should in [0, list.size]

dist/cjs/Set/Set.d.ts

@@ -1,11 +0,4 @@
-import { BaseType } from "../Base/Base";
-export declare type SetType<T> = {
-    forEach: (callback: (element: T, index: number) => void) => void;
-    insert: (element: T) => void;
-    erase: (element: T) => void;
-    find: (element: T) => boolean;
-    union: (other: SetType<T>) => void;
-    getHeight: () => number;
-} & BaseType;
+import { AssociativeContainersType } from "../Base/Base";
+export declare type SetType<T> = AssociativeContainersType<T>;
 declare const _default: new <T>(arr?: T[] | undefined, cmp?: ((x: T, y: T) => number) | undefined) => SetType<T>;
 export default _default;

dist/cjs/Set/Set.js

@@ -138,110 +138,64 @@ "use strict";
     };
-    this.forEach = function (callback) {
-        var index = 0;
-        var inOrderTraversal = function (curNode) {
-            if (!curNode)
-                return;
-            inOrderTraversal(curNode.leftChild);
-            if (curNode.value !== null)
-                callback(curNode.value, index++);
-            inOrderTraversal(curNode.rightChild);
-        };
-        inOrderTraversal(root);
+    var findSubTreeMinNode = function (curNode) {
+        if (!curNode || curNode.value === null)
+            throw new Error("unknown error");
+        return curNode.leftChild ? findSubTreeMinNode(curNode.leftChild) : curNode;
     };
-    var findInsertPos = function (curNode, element) {
+    var findSubTreeMaxNode = function (curNode) {
         if (!curNode || curNode.value === null)
             throw new Error("unknown error");
-        var cmpResult = cmp(element, curNode.value);
-        if (cmpResult < 0) {
-            if (!curNode.leftChild) {
-                curNode.leftChild = new TreeNode();
-                curNode.leftChild.parent = curNode;
-                curNode.leftChild.brother = curNode.rightChild;
-                if (curNode.rightChild)
-                    curNode.rightChild.brother = curNode.leftChild;
-                return curNode.leftChild;
-            }
-            return findInsertPos(curNode.leftChild, element);
-        }
-        else if (cmpResult > 0) {
-            if (!curNode.rightChild) {
-                curNode.rightChild = new TreeNode();
-                curNode.rightChild.parent = curNode;
-                curNode.rightChild.brother = curNode.leftChild;
-                if (curNode.leftChild)
-                    curNode.leftChild.brother = curNode.rightChild;
-                return curNode.rightChild;
-            }
-            return findInsertPos(curNode.rightChild, element);
-        }
-        return curNode;
+        return curNode.rightChild ? findSubTreeMaxNode(curNode.rightChild) : curNode;
     };
-    var insertNodeSelfBalance = function (curNode) {
-        var parentNode = curNode.parent;
-        if (!parentNode) {
-            if (curNode === root)
-                return;
-            throw new Error("unknown error");
-        }
-        if (parentNode.color === TreeNode.TreeNodeColorType.black)
-            return;
-        if (parentNode.color === TreeNode.TreeNodeColorType.red) {
-            var uncleNode = parentNode.brother;
-            var grandParent = parentNode.parent;
-            if (!grandParent)
+    this.front = function () {
+        if (this.empty())
+            return undefined;
+        var minNode = findSubTreeMinNode(root);
+        if (minNode.value === null)
+            return undefined;
+        return minNode.value;
+    };
+    this.back = function () {
+        if (this.empty())
+            return undefined;
+        var maxNode = findSubTreeMaxNode(root);
+        if (maxNode.value === null)
+            return undefined;
+        return maxNode.value;
+    };
+    var inOrderTraversal = function (curNode, callback) {
+        if (!curNode || curNode.value === null)
+            return false;
+        var ifReturn = inOrderTraversal(curNode.leftChild, callback);
+        if (ifReturn)
+            return true;
+        if (callback(curNode))
+            return true;
+        return inOrderTraversal(curNode.rightChild, callback);
+    };
+    this.forEach = function (callback) {
+        var index = 0;
+        inOrderTraversal(root, function (curNode) {
+            if (curNode.value === null)
                 throw new Error("unknown error");
-            if (uncleNode && uncleNode.color === TreeNode.TreeNodeColorType.red) {
-                uncleNode.color = parentNode.color = TreeNode.TreeNodeColorType.black;
-                grandParent.color = TreeNode.TreeNodeColorType.red;
-                insertNodeSelfBalance(grandParent);
+            callback(curNode.value, index++);
+            return false;
+        });
+    };
+    this.getElementByPos = function (pos) {
+        if (pos < 0 || pos >= this.size())
+            throw new Error("pos must more than 0 and less than set's size");
+        var index = 0;
+        var element = null;
+        inOrderTraversal(root, function (curNode) {
+            if (pos === index) {
+                element = curNode.value;
+                return true;
             }
-            else if (!uncleNode || uncleNode.color === TreeNode.TreeNodeColorType.black) {
-                if (parentNode === grandParent.leftChild) {
-                    if (curNode === parentNode.leftChild) {
-                        parentNode.color = TreeNode.TreeNodeColorType.black;
-                        grandParent.color = TreeNode.TreeNodeColorType.red;
-                        var newRoot = grandParent.rotateRight();
-                        if (grandParent === root)
-                            root = newRoot;
-                    }
-                    else if (curNode === parentNode.rightChild) {
-                        var newRoot = parentNode.rotateLeft();
-                        if (grandParent === root)
-                            root = newRoot;
-                        insertNodeSelfBalance(parentNode);
-                    }
-                }
-                else if (parentNode === grandParent.rightChild) {
-                    if (curNode === parentNode.leftChild) {
-                        var newRoot = parentNode.rotateRight();
-                        if (grandParent === root)
-                            root = newRoot;
-                        insertNodeSelfBalance(parentNode);
-                    }
-                    else if (curNode === parentNode.rightChild) {
-                        parentNode.color = TreeNode.TreeNodeColorType.black;
-                        grandParent.color = TreeNode.TreeNodeColorType.red;
-                        var newRoot = grandParent.rotateLeft();
-                        if (grandParent === root)
-                            root = newRoot;
-                    }
-                }
-            }
-        }
+            ++index;
+            return false;
+        });
+        if (element === null)
+            throw new Error("unknown error");
+        return element;
     };
-    this.insert = function (element) {
-        if (this.empty()) {
-            ++len;
-            root.value = element;
-            root.color = TreeNode.TreeNodeColorType.black;
-            return;
-        }
-        var curNode = findInsertPos(root, element);
-        if (curNode.value && cmp(curNode.value, element) === 0)
-            return;
-        ++len;
-        curNode.value = element;
-        insertNodeSelfBalance(curNode);
-        root.color = TreeNode.TreeNodeColorType.black;
-    };
     var eraseNodeSelfBalance = function (curNode) {
@@ -254,8 +208,9 @@ var parentNode = curNode.parent;
         }
-        if (curNode.color === TreeNode.TreeNodeColorType.red)
+        if (curNode.color === TreeNode.TreeNodeColorType.red) {
+            curNode.color = TreeNode.TreeNodeColorType.black;
             return;
+        }
         var brotherNode = curNode.brother;
-        if (!brotherNode) {
+        if (!brotherNode)
             throw new Error("unknown error");
-        }
         if (curNode === parentNode.leftChild) {
@@ -279,2 +234,3 @@ if (brotherNode.color === TreeNode.TreeNodeColorType.red) {
                         root = newRoot;
+                    curNode.color = TreeNode.TreeNodeColorType.black;
                 }
@@ -292,3 +248,3 @@ else if ((!brotherNode.rightChild || brotherNode.rightChild.color === TreeNode.TreeNodeColorType.black) && brotherNode.leftChild && brotherNode.leftChild.color === TreeNode.TreeNodeColorType.red) {
                     brotherNode.color = TreeNode.TreeNodeColorType.red;
-                    parentNode.color = TreeNode.TreeNodeColorType.black;
+                    eraseNodeSelfBalance(parentNode);
                 }
@@ -315,2 +271,3 @@ }
                         root = newRoot;
+                    curNode.color = TreeNode.TreeNodeColorType.black;
                 }
@@ -328,3 +285,3 @@ else if ((!brotherNode.leftChild || brotherNode.leftChild.color === TreeNode.TreeNodeColorType.black) && brotherNode.rightChild && brotherNode.rightChild.color === TreeNode.TreeNodeColorType.red) {
                     brotherNode.color = TreeNode.TreeNodeColorType.red;
-                    parentNode.color = TreeNode.TreeNodeColorType.black;
+                    eraseNodeSelfBalance(parentNode);
                 }
@@ -334,18 +291,3 @@ }
     };
-    var findSubTreeMinNode = function (curNode) {
-        if (!curNode || curNode.value === null)
-            throw new Error("unknown error");
-        return curNode.leftChild ? findSubTreeMinNode(curNode.leftChild) : curNode;
-    };
-    var findSubTreeMaxNode = function (curNode) {
-        if (!curNode || curNode.value === null)
-            throw new Error("unknown error");
-        return curNode.rightChild ? findSubTreeMaxNode(curNode.rightChild) : curNode;
-    };
-    this.erase = function (element) {
-        if (this.empty())
-            return;
-        var curNode = findElementPos(root, element);
-        if (curNode === null || curNode.value === null || cmp(curNode.value, element) !== 0)
-            return;
+    var eraseNode = function (curNode) {
         var swapNode = curNode;
@@ -374,2 +316,122 @@ while (swapNode.leftChild || swapNode.rightChild) {
     };
+    this.eraseElementByPos = function (pos) {
+        if (pos < 0 || pos >= len)
+            throw new Error("pos must more than 0 and less than set's size");
+        var index = 0;
+        inOrderTraversal(root, function (curNode) {
+            if (pos === index) {
+                eraseNode(curNode);
+                return true;
+            }
+            ++index;
+            return false;
+        });
+    };
+    this.eraseElementByValue = function (element) {
+        if (this.empty())
+            return;
+        var curNode = findElementPos(root, element);
+        if (curNode === null || curNode.value === null || cmp(curNode.value, element) !== 0)
+            return;
+        eraseNode(curNode);
+    };
+    var findInsertPos = function (curNode, element) {
+        if (!curNode || curNode.value === null)
+            throw new Error("unknown error");
+        var cmpResult = cmp(element, curNode.value);
+        if (cmpResult < 0) {
+            if (!curNode.leftChild) {
+                curNode.leftChild = new TreeNode();
+                curNode.leftChild.parent = curNode;
+                curNode.leftChild.brother = curNode.rightChild;
+                if (curNode.rightChild)
+                    curNode.rightChild.brother = curNode.leftChild;
+                return curNode.leftChild;
+            }
+            return findInsertPos(curNode.leftChild, element);
+        }
+        else if (cmpResult > 0) {
+            if (!curNode.rightChild) {
+                curNode.rightChild = new TreeNode();
+                curNode.rightChild.parent = curNode;
+                curNode.rightChild.brother = curNode.leftChild;
+                if (curNode.leftChild)
+                    curNode.leftChild.brother = curNode.rightChild;
+                return curNode.rightChild;
+            }
+            return findInsertPos(curNode.rightChild, element);
+        }
+        return curNode;
+    };
+    var insertNodeSelfBalance = function (curNode) {
+        var parentNode = curNode.parent;
+        if (!parentNode) {
+            if (curNode === root)
+                return;
+            throw new Error("unknown error");
+        }
+        if (parentNode.color === TreeNode.TreeNodeColorType.black)
+            return;
+        if (parentNode.color === TreeNode.TreeNodeColorType.red) {
+            var uncleNode = parentNode.brother;
+            var grandParent = parentNode.parent;
+            if (!grandParent)
+                throw new Error("unknown error");
+            if (uncleNode && uncleNode.color === TreeNode.TreeNodeColorType.red) {
+                uncleNode.color = parentNode.color = TreeNode.TreeNodeColorType.black;
+                grandParent.color = TreeNode.TreeNodeColorType.red;
+                insertNodeSelfBalance(grandParent);
+            }
+            else if (!uncleNode || uncleNode.color === TreeNode.TreeNodeColorType.black) {
+                if (parentNode === grandParent.leftChild) {
+                    if (curNode === parentNode.leftChild) {
+                        parentNode.color = TreeNode.TreeNodeColorType.black;
+                        grandParent.color = TreeNode.TreeNodeColorType.red;
+                        var newRoot = grandParent.rotateRight();
+                        if (grandParent === root)
+                            root = newRoot;
+                    }
+                    else if (curNode === parentNode.rightChild) {
+                        var newRoot = parentNode.rotateLeft();
+                        if (grandParent === root)
+                            root = newRoot;
+                        insertNodeSelfBalance(parentNode);
+                    }
+                }
+                else if (parentNode === grandParent.rightChild) {
+                    if (curNode === parentNode.leftChild) {
+                        var newRoot = parentNode.rotateRight();
+                        if (grandParent === root)
+                            root = newRoot;
+                        insertNodeSelfBalance(parentNode);
+                    }
+                    else if (curNode === parentNode.rightChild) {
+                        parentNode.color = TreeNode.TreeNodeColorType.black;
+                        grandParent.color = TreeNode.TreeNodeColorType.red;
+                        var newRoot = grandParent.rotateLeft();
+                        if (grandParent === root)
+                            root = newRoot;
+                    }
+                }
+            }
+        }
+    };
+    this.insert = function (element) {
+        if (element === null || element === undefined) {
+            throw new Error("to avoid some unnecessary errors, we don't suggest you insert null or undefined here");
+        }
+        if (this.empty()) {
+            ++len;
+            root.value = element;
+            root.color = TreeNode.TreeNodeColorType.black;
+            return;
+        }
+        var curNode = findInsertPos(root, element);
+        if (curNode.value && cmp(curNode.value, element) === 0)
+            return;
+        ++len;
+        curNode.value = element;
+        insertNodeSelfBalance(curNode);
+        root.color = TreeNode.TreeNodeColorType.black;
+    };
     var findElementPos = function (curNode, element) {
@@ -389,3 +451,3 @@ if (!curNode || curNode.value === null)
     };
-    // waiting for optimization, this is O(mlogn) algorithm now, but we expect it be O(mlog(n/m+1)).
+    // waiting for optimization, this is O(mlog(n+m)) algorithm now, but we expect it to be O(mlog(n/m+1)).
     // (https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Set_operations_and_bulk_operations)
@@ -392,0 +454,0 @@ this.union = function (other) {

dist/cjs/Vector/Vector.js

@@ -36,11 +36,2 @@ "use strict";
     };
-    this.push_back = function (element) {
-        vector.push(element);
-        ++len;
-    };
-    this.pop_back = function () {
-        vector.pop();
-        if (len > 0)
-            --len;
-    };
     this.forEach = function (callback) {
@@ -54,7 +45,2 @@ vector.forEach(callback);
     };
-    this.setElementByPos = function (pos, element) {
-        if (pos < 0 || pos >= len)
-            throw new Error("pos muse more than 0 and less than vector's size");
-        vector[pos] = element;
-    };
     this.eraseElementByPos = function (pos) {
@@ -80,2 +66,16 @@ if (pos < 0 || pos >= len)
     };
+    this.push_back = function (element) {
+        vector.push(element);
+        ++len;
+    };
+    this.pop_back = function () {
+        vector.pop();
+        if (len > 0)
+            --len;
+    };
+    this.setElementByPos = function (pos, element) {
+        if (pos < 0 || pos >= len)
+            throw new Error("pos muse more than 0 and less than vector's size");
+        vector[pos] = element;
+    };
     this.insert = function (pos, element, num) {
@@ -82,0 +82,0 @@ if (num === void 0) { num = 1; }

dist/esm/Base/Base.d.ts

@@ -6,12 +6,14 @@ export declare type BaseType = {
 } & Record<string, never>;
-export declare type SequentialContainerType<T> = {
+export declare type ContainerType<T> = {
     front: () => T | undefined;
     back: () => T | undefined;
-    push_back: (element: T) => void;
-    pop_back: () => void;
     forEach: (callback: (element: T, index: number) => void) => void;
     getElementByPos: (pos: number) => T;
-    setElementByPos: (pos: number, element: T) => void;
     eraseElementByPos: (pos: number) => void;
     eraseElementByValue: (value: T) => void;
+} & BaseType;
+export declare type SequentialContainerType<T> = {
+    push_back: (element: T) => void;
+    pop_back: () => void;
+    setElementByPos: (pos: number, element: T) => void;
     insert: (pos: number, element: T, num?: number) => void;
@@ -21,2 +23,8 @@ reverse: () => void;
     sort: (cmp?: (x: T, y: T) => number) => void;
-} & BaseType;
+} & ContainerType<T>;
+export declare type AssociativeContainersType<T> = {
+    insert: (element: T) => void;
+    find: (element: T) => boolean;
+    union: (other: AssociativeContainersType<T>) => void;
+    getHeight: () => number;
+} & ContainerType<T>;

dist/esm/Deque/Deque.js

@@ -45,35 +45,2 @@ Deque.sigma = 3; // growth factor
     };
-    var reAllocate = function (originalSize) {
-        var newMap = [];
-        var needSize = originalSize * Deque.sigma;
-        var newBucketNum = Math.max(Math.ceil(needSize / Deque.bucketSize), 2);
-        for (var i = 0; i < newBucketNum; ++i) {
-            newMap.push(new Array(Deque.bucketSize));
-        }
-        var needBucketNum = Math.ceil(originalSize / Deque.bucketSize);
-        var newFirst = Math.floor(newBucketNum / 2) - Math.floor(needBucketNum / 2);
-        var newLast = newFirst, newCurLast = 0;
-        if (this.size()) {
-            for (var i = 0; i < needBucketNum; ++i) {
-                for (var j = 0; j < Deque.bucketSize; ++j) {
-                    newMap[newFirst + i][j] = this.front();
-                    this.pop_front();
-                    if (this.empty()) {
-                        newLast = newFirst + i;
-                        newCurLast = j;
-                        break;
-                    }
-                }
-                if (this.empty())
-                    break;
-            }
-        }
-        map = newMap;
-        first = newFirst;
-        curFirst = 0;
-        last = newLast;
-        curLast = newCurLast;
-        bucketNum = newBucketNum;
-        len = originalSize;
-    };
     this.front = function () {
@@ -85,33 +52,2 @@ return map[first][curFirst];
     };
-    this.push_back = function (element) {
-        if (!this.empty()) {
-            if (last === bucketNum - 1 && curLast === Deque.bucketSize - 1) {
-                reAllocate.call(this, this.size());
-            }
-            if (curLast < Deque.bucketSize - 1) {
-                ++curLast;
-            }
-            else if (last < bucketNum - 1) {
-                ++last;
-                curLast = 0;
-            }
-        }
-        ++len;
-        map[last][curLast] = element;
-    };
-    this.pop_back = function () {
-        if (this.empty())
-            return;
-        if (this.size() !== 1) {
-            if (curLast > 0) {
-                --curLast;
-            }
-            else if (first < last) {
-                --last;
-                curLast = Deque.bucketSize - 1;
-            }
-        }
-        if (len > 0)
-            --len;
-    };
     this.forEach = function (callback) {
@@ -156,6 +92,2 @@ if (this.empty())
     };
-    this.setElementByPos = function (pos, element) {
-        var _a = getElementIndex(pos), curNodeBucketIndex = _a.curNodeBucketIndex, curNodePointerIndex = _a.curNodePointerIndex;
-        map[curNodeBucketIndex][curNodePointerIndex] = element;
-    };
     this.eraseElementByPos = function (pos) {
@@ -189,2 +121,70 @@ var _this = this;
     };
+    var reAllocate = function (originalSize) {
+        var newMap = [];
+        var needSize = originalSize * Deque.sigma;
+        var newBucketNum = Math.max(Math.ceil(needSize / Deque.bucketSize), 2);
+        for (var i = 0; i < newBucketNum; ++i) {
+            newMap.push(new Array(Deque.bucketSize));
+        }
+        var needBucketNum = Math.ceil(originalSize / Deque.bucketSize);
+        var newFirst = Math.floor(newBucketNum / 2) - Math.floor(needBucketNum / 2);
+        var newLast = newFirst, newCurLast = 0;
+        if (this.size()) {
+            for (var i = 0; i < needBucketNum; ++i) {
+                for (var j = 0; j < Deque.bucketSize; ++j) {
+                    newMap[newFirst + i][j] = this.front();
+                    this.pop_front();
+                    if (this.empty()) {
+                        newLast = newFirst + i;
+                        newCurLast = j;
+                        break;
+                    }
+                }
+                if (this.empty())
+                    break;
+            }
+        }
+        map = newMap;
+        first = newFirst;
+        curFirst = 0;
+        last = newLast;
+        curLast = newCurLast;
+        bucketNum = newBucketNum;
+        len = originalSize;
+    };
+    this.push_back = function (element) {
+        if (!this.empty()) {
+            if (last === bucketNum - 1 && curLast === Deque.bucketSize - 1) {
+                reAllocate.call(this, this.size());
+            }
+            if (curLast < Deque.bucketSize - 1) {
+                ++curLast;
+            }
+            else if (last < bucketNum - 1) {
+                ++last;
+                curLast = 0;
+            }
+        }
+        ++len;
+        map[last][curLast] = element;
+    };
+    this.pop_back = function () {
+        if (this.empty())
+            return;
+        if (this.size() !== 1) {
+            if (curLast > 0) {
+                --curLast;
+            }
+            else if (first < last) {
+                --last;
+                curLast = Deque.bucketSize - 1;
+            }
+        }
+        if (len > 0)
+            --len;
+    };
+    this.setElementByPos = function (pos, element) {
+        var _a = getElementIndex(pos), curNodeBucketIndex = _a.curNodeBucketIndex, curNodePointerIndex = _a.curNodePointerIndex;
+        map[curNodeBucketIndex][curNodePointerIndex] = element;
+    };
     /**
@@ -191,0 +191,0 @@ * @param {number} pos insert element before pos, should in [0, queue.size]

dist/esm/LinkList/LinkList.js

@@ -41,28 +41,2 @@ var LinkNode = /** @class */ (function () {
     };
-    this.push_back = function (element) {
-        ++len;
-        var newTail = new LinkNode(element);
-        if (!tail) {
-            head = tail = newTail;
-        }
-        else {
-            tail.next = newTail;
-            newTail.pre = tail;
-            tail = newTail;
-        }
-    };
-    this.pop_back = function () {
-        if (len > 0)
-            --len;
-        if (!tail)
-            return;
-        if (head === tail) {
-            head = tail = null;
-        }
-        else {
-            tail = tail.pre;
-            if (tail)
-                tail.next = null;
-        }
-    };
     this.forEach = function (callback) {
@@ -89,14 +63,2 @@ if (typeof callback !== 'function')
     };
-    this.setElementByPos = function (pos, element) {
-        if (pos < 0 || pos >= len)
-            throw new Error("pos must more then 0 and less then the list length");
-        var curNode = head;
-        while (pos--) {
-            if (!curNode)
-                break;
-            curNode = curNode.next;
-        }
-        if (curNode)
-            curNode.val = element;
-    };
     this.eraseElementByPos = function (pos) {
@@ -149,2 +111,40 @@ if (pos < 0 || pos >= len)
     };
+    this.push_back = function (element) {
+        ++len;
+        var newTail = new LinkNode(element);
+        if (!tail) {
+            head = tail = newTail;
+        }
+        else {
+            tail.next = newTail;
+            newTail.pre = tail;
+            tail = newTail;
+        }
+    };
+    this.pop_back = function () {
+        if (len > 0)
+            --len;
+        if (!tail)
+            return;
+        if (head === tail) {
+            head = tail = null;
+        }
+        else {
+            tail = tail.pre;
+            if (tail)
+                tail.next = null;
+        }
+    };
+    this.setElementByPos = function (pos, element) {
+        if (pos < 0 || pos >= len)
+            throw new Error("pos must more then 0 and less then the list length");
+        var curNode = head;
+        while (pos--) {
+            if (!curNode)
+                break;
+            curNode = curNode.next;
+        }
+        if (curNode)
+            curNode.val = element;
+    };
     /**
@@ -151,0 +151,0 @@ * @param {number} pos insert element before pos, should in [0, list.size]

dist/esm/Set/Set.d.ts

@@ -1,11 +0,4 @@
-import { BaseType } from "../Base/Base";
-export declare type SetType<T> = {
-    forEach: (callback: (element: T, index: number) => void) => void;
-    insert: (element: T) => void;
-    erase: (element: T) => void;
-    find: (element: T) => boolean;
-    union: (other: SetType<T>) => void;
-    getHeight: () => number;
-} & BaseType;
+import { AssociativeContainersType } from "../Base/Base";
+export declare type SetType<T> = AssociativeContainersType<T>;
 declare const _default: new <T>(arr?: T[] | undefined, cmp?: ((x: T, y: T) => number) | undefined) => SetType<T>;
 export default _default;

dist/esm/Set/Set.js

@@ -136,110 +136,64 @@ var TreeNode = /** @class */ (function () {
     };
-    this.forEach = function (callback) {
-        var index = 0;
-        var inOrderTraversal = function (curNode) {
-            if (!curNode)
-                return;
-            inOrderTraversal(curNode.leftChild);
-            if (curNode.value !== null)
-                callback(curNode.value, index++);
-            inOrderTraversal(curNode.rightChild);
-        };
-        inOrderTraversal(root);
+    var findSubTreeMinNode = function (curNode) {
+        if (!curNode || curNode.value === null)
+            throw new Error("unknown error");
+        return curNode.leftChild ? findSubTreeMinNode(curNode.leftChild) : curNode;
     };
-    var findInsertPos = function (curNode, element) {
+    var findSubTreeMaxNode = function (curNode) {
         if (!curNode || curNode.value === null)
             throw new Error("unknown error");
-        var cmpResult = cmp(element, curNode.value);
-        if (cmpResult < 0) {
-            if (!curNode.leftChild) {
-                curNode.leftChild = new TreeNode();
-                curNode.leftChild.parent = curNode;
-                curNode.leftChild.brother = curNode.rightChild;
-                if (curNode.rightChild)
-                    curNode.rightChild.brother = curNode.leftChild;
-                return curNode.leftChild;
-            }
-            return findInsertPos(curNode.leftChild, element);
-        }
-        else if (cmpResult > 0) {
-            if (!curNode.rightChild) {
-                curNode.rightChild = new TreeNode();
-                curNode.rightChild.parent = curNode;
-                curNode.rightChild.brother = curNode.leftChild;
-                if (curNode.leftChild)
-                    curNode.leftChild.brother = curNode.rightChild;
-                return curNode.rightChild;
-            }
-            return findInsertPos(curNode.rightChild, element);
-        }
-        return curNode;
+        return curNode.rightChild ? findSubTreeMaxNode(curNode.rightChild) : curNode;
     };
-    var insertNodeSelfBalance = function (curNode) {
-        var parentNode = curNode.parent;
-        if (!parentNode) {
-            if (curNode === root)
-                return;
-            throw new Error("unknown error");
-        }
-        if (parentNode.color === TreeNode.TreeNodeColorType.black)
-            return;
-        if (parentNode.color === TreeNode.TreeNodeColorType.red) {
-            var uncleNode = parentNode.brother;
-            var grandParent = parentNode.parent;
-            if (!grandParent)
+    this.front = function () {
+        if (this.empty())
+            return undefined;
+        var minNode = findSubTreeMinNode(root);
+        if (minNode.value === null)
+            return undefined;
+        return minNode.value;
+    };
+    this.back = function () {
+        if (this.empty())
+            return undefined;
+        var maxNode = findSubTreeMaxNode(root);
+        if (maxNode.value === null)
+            return undefined;
+        return maxNode.value;
+    };
+    var inOrderTraversal = function (curNode, callback) {
+        if (!curNode || curNode.value === null)
+            return false;
+        var ifReturn = inOrderTraversal(curNode.leftChild, callback);
+        if (ifReturn)
+            return true;
+        if (callback(curNode))
+            return true;
+        return inOrderTraversal(curNode.rightChild, callback);
+    };
+    this.forEach = function (callback) {
+        var index = 0;
+        inOrderTraversal(root, function (curNode) {
+            if (curNode.value === null)
                 throw new Error("unknown error");
-            if (uncleNode && uncleNode.color === TreeNode.TreeNodeColorType.red) {
-                uncleNode.color = parentNode.color = TreeNode.TreeNodeColorType.black;
-                grandParent.color = TreeNode.TreeNodeColorType.red;
-                insertNodeSelfBalance(grandParent);
+            callback(curNode.value, index++);
+            return false;
+        });
+    };
+    this.getElementByPos = function (pos) {
+        if (pos < 0 || pos >= this.size())
+            throw new Error("pos must more than 0 and less than set's size");
+        var index = 0;
+        var element = null;
+        inOrderTraversal(root, function (curNode) {
+            if (pos === index) {
+                element = curNode.value;
+                return true;
             }
-            else if (!uncleNode || uncleNode.color === TreeNode.TreeNodeColorType.black) {
-                if (parentNode === grandParent.leftChild) {
-                    if (curNode === parentNode.leftChild) {
-                        parentNode.color = TreeNode.TreeNodeColorType.black;
-                        grandParent.color = TreeNode.TreeNodeColorType.red;
-                        var newRoot = grandParent.rotateRight();
-                        if (grandParent === root)
-                            root = newRoot;
-                    }
-                    else if (curNode === parentNode.rightChild) {
-                        var newRoot = parentNode.rotateLeft();
-                        if (grandParent === root)
-                            root = newRoot;
-                        insertNodeSelfBalance(parentNode);
-                    }
-                }
-                else if (parentNode === grandParent.rightChild) {
-                    if (curNode === parentNode.leftChild) {
-                        var newRoot = parentNode.rotateRight();
-                        if (grandParent === root)
-                            root = newRoot;
-                        insertNodeSelfBalance(parentNode);
-                    }
-                    else if (curNode === parentNode.rightChild) {
-                        parentNode.color = TreeNode.TreeNodeColorType.black;
-                        grandParent.color = TreeNode.TreeNodeColorType.red;
-                        var newRoot = grandParent.rotateLeft();
-                        if (grandParent === root)
-                            root = newRoot;
-                    }
-                }
-            }
-        }
+            ++index;
+            return false;
+        });
+        if (element === null)
+            throw new Error("unknown error");
+        return element;
     };
-    this.insert = function (element) {
-        if (this.empty()) {
-            ++len;
-            root.value = element;
-            root.color = TreeNode.TreeNodeColorType.black;
-            return;
-        }
-        var curNode = findInsertPos(root, element);
-        if (curNode.value && cmp(curNode.value, element) === 0)
-            return;
-        ++len;
-        curNode.value = element;
-        insertNodeSelfBalance(curNode);
-        root.color = TreeNode.TreeNodeColorType.black;
-    };
     var eraseNodeSelfBalance = function (curNode) {
@@ -252,8 +206,9 @@ var parentNode = curNode.parent;
         }
-        if (curNode.color === TreeNode.TreeNodeColorType.red)
+        if (curNode.color === TreeNode.TreeNodeColorType.red) {
+            curNode.color = TreeNode.TreeNodeColorType.black;
             return;
+        }
         var brotherNode = curNode.brother;
-        if (!brotherNode) {
+        if (!brotherNode)
             throw new Error("unknown error");
-        }
         if (curNode === parentNode.leftChild) {
@@ -277,2 +232,3 @@ if (brotherNode.color === TreeNode.TreeNodeColorType.red) {
                         root = newRoot;
+                    curNode.color = TreeNode.TreeNodeColorType.black;
                 }
@@ -290,3 +246,3 @@ else if ((!brotherNode.rightChild || brotherNode.rightChild.color === TreeNode.TreeNodeColorType.black) && brotherNode.leftChild && brotherNode.leftChild.color === TreeNode.TreeNodeColorType.red) {
                     brotherNode.color = TreeNode.TreeNodeColorType.red;
-                    parentNode.color = TreeNode.TreeNodeColorType.black;
+                    eraseNodeSelfBalance(parentNode);
                 }
@@ -313,2 +269,3 @@ }
                         root = newRoot;
+                    curNode.color = TreeNode.TreeNodeColorType.black;
                 }
@@ -326,3 +283,3 @@ else if ((!brotherNode.leftChild || brotherNode.leftChild.color === TreeNode.TreeNodeColorType.black) && brotherNode.rightChild && brotherNode.rightChild.color === TreeNode.TreeNodeColorType.red) {
                     brotherNode.color = TreeNode.TreeNodeColorType.red;
-                    parentNode.color = TreeNode.TreeNodeColorType.black;
+                    eraseNodeSelfBalance(parentNode);
                 }
@@ -332,18 +289,3 @@ }
     };
-    var findSubTreeMinNode = function (curNode) {
-        if (!curNode || curNode.value === null)
-            throw new Error("unknown error");
-        return curNode.leftChild ? findSubTreeMinNode(curNode.leftChild) : curNode;
-    };
-    var findSubTreeMaxNode = function (curNode) {
-        if (!curNode || curNode.value === null)
-            throw new Error("unknown error");
-        return curNode.rightChild ? findSubTreeMaxNode(curNode.rightChild) : curNode;
-    };
-    this.erase = function (element) {
-        if (this.empty())
-            return;
-        var curNode = findElementPos(root, element);
-        if (curNode === null || curNode.value === null || cmp(curNode.value, element) !== 0)
-            return;
+    var eraseNode = function (curNode) {
         var swapNode = curNode;
@@ -372,2 +314,122 @@ while (swapNode.leftChild || swapNode.rightChild) {
     };
+    this.eraseElementByPos = function (pos) {
+        if (pos < 0 || pos >= len)
+            throw new Error("pos must more than 0 and less than set's size");
+        var index = 0;
+        inOrderTraversal(root, function (curNode) {
+            if (pos === index) {
+                eraseNode(curNode);
+                return true;
+            }
+            ++index;
+            return false;
+        });
+    };
+    this.eraseElementByValue = function (element) {
+        if (this.empty())
+            return;
+        var curNode = findElementPos(root, element);
+        if (curNode === null || curNode.value === null || cmp(curNode.value, element) !== 0)
+            return;
+        eraseNode(curNode);
+    };
+    var findInsertPos = function (curNode, element) {
+        if (!curNode || curNode.value === null)
+            throw new Error("unknown error");
+        var cmpResult = cmp(element, curNode.value);
+        if (cmpResult < 0) {
+            if (!curNode.leftChild) {
+                curNode.leftChild = new TreeNode();
+                curNode.leftChild.parent = curNode;
+                curNode.leftChild.brother = curNode.rightChild;
+                if (curNode.rightChild)
+                    curNode.rightChild.brother = curNode.leftChild;
+                return curNode.leftChild;
+            }
+            return findInsertPos(curNode.leftChild, element);
+        }
+        else if (cmpResult > 0) {
+            if (!curNode.rightChild) {
+                curNode.rightChild = new TreeNode();
+                curNode.rightChild.parent = curNode;
+                curNode.rightChild.brother = curNode.leftChild;
+                if (curNode.leftChild)
+                    curNode.leftChild.brother = curNode.rightChild;
+                return curNode.rightChild;
+            }
+            return findInsertPos(curNode.rightChild, element);
+        }
+        return curNode;
+    };
+    var insertNodeSelfBalance = function (curNode) {
+        var parentNode = curNode.parent;
+        if (!parentNode) {
+            if (curNode === root)
+                return;
+            throw new Error("unknown error");
+        }
+        if (parentNode.color === TreeNode.TreeNodeColorType.black)
+            return;
+        if (parentNode.color === TreeNode.TreeNodeColorType.red) {
+            var uncleNode = parentNode.brother;
+            var grandParent = parentNode.parent;
+            if (!grandParent)
+                throw new Error("unknown error");
+            if (uncleNode && uncleNode.color === TreeNode.TreeNodeColorType.red) {
+                uncleNode.color = parentNode.color = TreeNode.TreeNodeColorType.black;
+                grandParent.color = TreeNode.TreeNodeColorType.red;
+                insertNodeSelfBalance(grandParent);
+            }
+            else if (!uncleNode || uncleNode.color === TreeNode.TreeNodeColorType.black) {
+                if (parentNode === grandParent.leftChild) {
+                    if (curNode === parentNode.leftChild) {
+                        parentNode.color = TreeNode.TreeNodeColorType.black;
+                        grandParent.color = TreeNode.TreeNodeColorType.red;
+                        var newRoot = grandParent.rotateRight();
+                        if (grandParent === root)
+                            root = newRoot;
+                    }
+                    else if (curNode === parentNode.rightChild) {
+                        var newRoot = parentNode.rotateLeft();
+                        if (grandParent === root)
+                            root = newRoot;
+                        insertNodeSelfBalance(parentNode);
+                    }
+                }
+                else if (parentNode === grandParent.rightChild) {
+                    if (curNode === parentNode.leftChild) {
+                        var newRoot = parentNode.rotateRight();
+                        if (grandParent === root)
+                            root = newRoot;
+                        insertNodeSelfBalance(parentNode);
+                    }
+                    else if (curNode === parentNode.rightChild) {
+                        parentNode.color = TreeNode.TreeNodeColorType.black;
+                        grandParent.color = TreeNode.TreeNodeColorType.red;
+                        var newRoot = grandParent.rotateLeft();
+                        if (grandParent === root)
+                            root = newRoot;
+                    }
+                }
+            }
+        }
+    };
+    this.insert = function (element) {
+        if (element === null || element === undefined) {
+            throw new Error("to avoid some unnecessary errors, we don't suggest you insert null or undefined here");
+        }
+        if (this.empty()) {
+            ++len;
+            root.value = element;
+            root.color = TreeNode.TreeNodeColorType.black;
+            return;
+        }
+        var curNode = findInsertPos(root, element);
+        if (curNode.value && cmp(curNode.value, element) === 0)
+            return;
+        ++len;
+        curNode.value = element;
+        insertNodeSelfBalance(curNode);
+        root.color = TreeNode.TreeNodeColorType.black;
+    };
     var findElementPos = function (curNode, element) {
@@ -387,3 +449,3 @@ if (!curNode || curNode.value === null)
     };
-    // waiting for optimization, this is O(mlogn) algorithm now, but we expect it be O(mlog(n/m+1)).
+    // waiting for optimization, this is O(mlog(n+m)) algorithm now, but we expect it to be O(mlog(n/m+1)).
     // (https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Set_operations_and_bulk_operations)
@@ -390,0 +452,0 @@ this.union = function (other) {

dist/esm/Vector/Vector.js

@@ -34,11 +34,2 @@ var __spreadArray = (this && this.__spreadArray) || function (to, from, pack) {
     };
-    this.push_back = function (element) {
-        vector.push(element);
-        ++len;
-    };
-    this.pop_back = function () {
-        vector.pop();
-        if (len > 0)
-            --len;
-    };
     this.forEach = function (callback) {
@@ -52,7 +43,2 @@ vector.forEach(callback);
     };
-    this.setElementByPos = function (pos, element) {
-        if (pos < 0 || pos >= len)
-            throw new Error("pos muse more than 0 and less than vector's size");
-        vector[pos] = element;
-    };
     this.eraseElementByPos = function (pos) {
@@ -78,2 +64,16 @@ if (pos < 0 || pos >= len)
     };
+    this.push_back = function (element) {
+        vector.push(element);
+        ++len;
+    };
+    this.pop_back = function () {
+        vector.pop();
+        if (len > 0)
+            --len;
+    };
+    this.setElementByPos = function (pos, element) {
+        if (pos < 0 || pos >= len)
+            throw new Error("pos muse more than 0 and less than vector's size");
+        vector[pos] = element;
+    };
     this.insert = function (pos, element, num) {
@@ -80,0 +80,0 @@ if (num === void 0) { num = 1; }

package.json

 {
   "name": "js-sdsl",
-  "version": "1.2.1",
-  "description": "javascript standard data structure library",
+  "version": "1.2.2",
+  "description": "javascript standard data structure library， which benchmark against C++ STL",
   "main": "./dist/cjs/index.js",
@@ -30,3 +30,5 @@ "module": "./dist/esm/index.js",
     "Set",
-    "RBTree"
+    "RBTree",
+    "c++",
+    "STL"
   ],
@@ -33,0 +35,0 @@ "bugs": {

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

105719

increased by4.47%

Lines of code

2952

increased by4.46%

No dependency changes