min-heap-typed - npm Package Compare versions

Comparing version 1.41.0 to 1.41.1

dist/data-structures/binary-tree/binary-tree.d.ts

@@ -180,5 +180,8 @@ /**
     has<C extends BTNCallback<N>>(identifier: ReturnType<C> | null, callback: C, beginRoot?: N, iterationType?: IterationType): boolean;
-    get<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: N, iterationType?: IterationType): N | null;
-    get<C extends BTNCallback<N, N>>(identifier: N | null, callback?: C, beginRoot?: N, iterationType?: IterationType): N | null;
-    get<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: N, iterationType?: IterationType): N | null;
+    getNode<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: N, iterationType?: IterationType): N | null;
+    getNode<C extends BTNCallback<N, N>>(identifier: N | null, callback?: C, beginRoot?: N, iterationType?: IterationType): N | null;
+    getNode<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: N, iterationType?: IterationType): N | null;
+    get<C extends BTNCallback<N, BTNKey>>(identifier: BTNKey, callback?: C, beginRoot?: N, iterationType?: IterationType): V | undefined;
+    get<C extends BTNCallback<N, N>>(identifier: N | null, callback?: C, beginRoot?: N, iterationType?: IterationType): V | undefined;
+    get<C extends BTNCallback<N>>(identifier: ReturnType<C>, callback: C, beginRoot?: N, iterationType?: IterationType): V | undefined;
     /**
@@ -185,0 +188,0 @@ * The function `getPathToRoot` returns an array of nodes starting from a given node and traversing

dist/data-structures/binary-tree/binary-tree.js

@@ -174,3 +174,3 @@ "use strict";
         const key = typeof keyOrNode === 'number' ? keyOrNode : keyOrNode ? keyOrNode.key : undefined;
-        const existNode = key !== undefined ? this.get(key, (node) => node.key) : undefined;
+        const existNode = key !== undefined ? this.getNode(key, (node) => node.key) : undefined;
         if (this.root) {
@@ -253,3 +253,3 @@ if (existNode) {
             callback = (node => node);
-        const curr = this.get(identifier, callback);
+        const curr = this.getNode(identifier, callback);
         if (!curr)
@@ -307,5 +307,5 @@ return bstDeletedResult;
         if (typeof distNode === 'number')
-            distNode = this.get(distNode);
+            distNode = this.getNode(distNode);
         if (typeof beginRoot === 'number')
-            beginRoot = this.get(beginRoot);
+            beginRoot = this.getNode(beginRoot);
         let depth = 0;
@@ -335,3 +335,3 @@ while (distNode === null || distNode === void 0 ? void 0 : distNode.parent) {
         if (typeof beginRoot === 'number')
-            beginRoot = this.get(beginRoot);
+            beginRoot = this.getNode(beginRoot);
         if (!beginRoot)
@@ -528,3 +528,3 @@ return -1;
      */
-    get(identifier, callback = ((node) => node.key), beginRoot = this.root, iterationType = this.iterationType) {
+    getNode(identifier, callback = ((node) => node.key), beginRoot = this.root, iterationType = this.iterationType) {
         var _a;
@@ -537,2 +537,24 @@ if (identifier instanceof BinaryTreeNode)
     /**
+     * The function `get` returns the first node value in a binary tree that matches the given property or key.
+     * @param {BTNKey | N} identifier - The `identifier` parameter is the key or value of
+     * the node that you want to find in the binary tree. It can be either a `BTNKey` or `N`
+     * type.
+     * @param callback - The `callback` parameter is a function that is used to determine whether a node
+     * matches the desired criteria. It takes a node as input and returns a boolean value indicating
+     * whether the node matches the criteria or not. The default callback function
+     * (`((node: N) => node.key)`) is used if no callback function is
+     * @param beginRoot - The `beginRoot` parameter is the starting point for the search. It specifies
+     * the root node from which the search should begin.
+     * @param iterationType - The `iterationType` parameter specifies the type of iteration to be
+     * performed when searching for a node in the binary tree. It can have one of the following values:
+     * @returns either the found value (of type V) or undefined if no node value is found.
+     */
+    get(identifier, callback = ((node) => node.key), beginRoot = this.root, iterationType = this.iterationType) {
+        var _a;
+        if (identifier instanceof BinaryTreeNode)
+            callback = (node => node);
+        // TODO may support finding node by value equal
+        return (_a = this.getNodes(identifier, callback, true, beginRoot, iterationType)[0].value) !== null && _a !== void 0 ? _a : undefined;
+    }
+    /**
      * The function `getPathToRoot` returns an array of nodes starting from a given node and traversing
@@ -572,3 +594,3 @@ * up to the root node, with the option to reverse the order of the nodes.
         if (typeof beginRoot === 'number')
-            beginRoot = this.get(beginRoot);
+            beginRoot = this.getNode(beginRoot);
         if (!beginRoot)
@@ -696,3 +718,3 @@ return beginRoot;
         if (typeof beginRoot === 'number')
-            beginRoot = this.get(beginRoot);
+            beginRoot = this.getNode(beginRoot);
         const ans = [];
@@ -699,0 +721,0 @@ if (!beginRoot)

dist/data-structures/binary-tree/bst.d.ts

@@ -75,3 +75,3 @@ /**
      */
-    get<C extends BTNCallback<N>>(identifier: ReturnType<C> | null, callback?: C, beginRoot?: N | null, iterationType?: IterationType): N | null;
+    getNode<C extends BTNCallback<N>>(identifier: ReturnType<C> | null, callback?: C, beginRoot?: N | null, iterationType?: IterationType): N | null;
     /**
@@ -78,0 +78,0 @@ * The function `lastKey` returns the key of the rightmost node if the comparison result is less

dist/data-structures/binary-tree/bst.js

@@ -226,3 +226,3 @@ "use strict";
      */
-    get(identifier, callback = ((node) => node.key), beginRoot = this.root, iterationType = this.iterationType) {
+    getNode(identifier, callback = ((node) => node.key), beginRoot = this.root, iterationType = this.iterationType) {
         var _a;
@@ -351,3 +351,3 @@ return (_a = this.getNodes(identifier, callback, true, beginRoot, iterationType)[0]) !== null && _a !== void 0 ? _a : null;
         if (typeof targetNode === 'number')
-            targetNode = this.get(targetNode);
+            targetNode = this.getNode(targetNode);
         const ans = [];
@@ -354,0 +354,0 @@ if (!targetNode)

dist/data-structures/binary-tree/rb-tree.d.ts

@@ -0,1 +1,2 @@
+import { RBTNColor } from '../../types';
 export declare class RBTreeNode {
@@ -7,4 +8,5 @@ key: number;
     color: number;
-    constructor();
+    constructor(key: number, color?: RBTNColor);
 }
+export declare const SN: RBTreeNode;
 export declare class RedBlackTree {
@@ -14,4 +16,2 @@ constructor();
     get root(): RBTreeNode;
-    protected _NIL: RBTreeNode;
-    get NIL(): RBTreeNode;
     /**
@@ -33,2 +33,3 @@ * The `insert` function inserts a new node with a given key into a red-black tree and fixes any
     delete(key: number): void;
+    isRealNode(node: RBTreeNode): node is RBTreeNode;
     /**
@@ -51,3 +52,3 @@ * The function `getNode` is a recursive depth-first search algorithm that searches for a node with a
      */
-    getLeftMost(node: RBTreeNode): RBTreeNode;
+    getLeftMost(node?: RBTreeNode): RBTreeNode;
     /**
@@ -54,0 +55,0 @@ * The function returns the rightmost node in a red-black tree.

dist/data-structures/binary-tree/rb-tree.js

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
-exports.RedBlackTree = exports.RBTreeNode = void 0;
+exports.RedBlackTree = exports.SN = exports.RBTreeNode = void 0;
 const types_1 = require("../../types");
 class RBTreeNode {
-    constructor() {
-        this.key = 0;
+    constructor(key, color = types_1.RBTNColor.BLACK) {
         this.color = types_1.RBTNColor.BLACK;
+        this.key = key;
+        this.color = color;
         this.parent = null;
@@ -15,9 +16,6 @@ this.left = null;
 exports.RBTreeNode = RBTreeNode;
+exports.SN = new RBTreeNode(0);
 class RedBlackTree {
     constructor() {
-        this._NIL = new RBTreeNode();
-        this.NIL.color = types_1.RBTNColor.BLACK;
-        this.NIL.left = null;
-        this.NIL.right = null;
-        this._root = this.NIL;
+        this._root = exports.SN;
     }
@@ -27,5 +25,2 @@ get root() {
     }
-    get NIL() {
-        return this._NIL;
-    }
     /**
@@ -39,11 +34,8 @@ * The `insert` function inserts a new node with a given key into a red-black tree and fixes any
     insert(key) {
-        const node = new RBTreeNode();
-        node.parent = null;
-        node.key = key;
-        node.left = this.NIL;
-        node.right = this.NIL;
-        node.color = types_1.RBTNColor.RED;
+        const node = new RBTreeNode(key, types_1.RBTNColor.RED);
+        node.left = exports.SN;
+        node.right = exports.SN;
         let y = null;
         let x = this.root;
-        while (x !== this.NIL) {
+        while (x !== exports.SN) {
             y = x;
@@ -85,5 +77,5 @@ if (node.key < x.key) {
         const helper = (node) => {
-            let z = this.NIL;
+            let z = exports.SN;
             let x, y;
-            while (node !== this.NIL) {
+            while (node !== exports.SN) {
                 if (node.key === key) {
@@ -99,4 +91,3 @@ z = node;
             }
-            if (z === this.NIL) {
-                console.log("Couldn't find key in the tree");
+            if (z === exports.SN) {
                 return;
@@ -106,7 +97,7 @@ }
             let yOriginalColor = y.color;
-            if (z.left === this.NIL) {
+            if (z.left === exports.SN) {
                 x = z.right;
                 this._rbTransplant(z, z.right);
             }
-            else if (z.right === this.NIL) {
+            else if (z.right === exports.SN) {
                 x = z.left;
@@ -132,3 +123,3 @@ this._rbTransplant(z, z.left);
             }
-            if (yOriginalColor === 0) {
+            if (yOriginalColor === types_1.RBTNColor.BLACK) {
                 this._fixDelete(x);
@@ -139,2 +130,5 @@ }
     }
+    isRealNode(node) {
+        return node !== exports.SN && node !== null;
+    }
     /**
@@ -152,9 +146,13 @@ * The function `getNode` is a recursive depth-first search algorithm that searches for a node with a
         const dfs = (node) => {
-            if (node === this.NIL || key === node.key) {
-                return node;
+            if (this.isRealNode(node)) {
+                if (key === node.key) {
+                    return node;
+                }
+                if (key < node.key)
+                    return dfs(node.left);
+                return dfs(node.right);
             }
-            if (key < node.key) {
-                return dfs(node.left);
+            else {
+                return null;
             }
-            return dfs(node.right);
         };
@@ -169,4 +167,4 @@ return dfs(beginRoot);
      */
-    getLeftMost(node) {
-        while (node.left !== null && node.left !== this.NIL) {
+    getLeftMost(node = this.root) {
+        while (node.left !== null && node.left !== exports.SN) {
             node = node.left;
@@ -182,3 +180,3 @@ }
     getRightMost(node) {
-        while (node.right !== null && node.right !== this.NIL) {
+        while (node.right !== null && node.right !== exports.SN) {
             node = node.right;
@@ -194,7 +192,7 @@ }
     getSuccessor(x) {
-        if (x.right !== this.NIL) {
+        if (x.right !== exports.SN) {
             return this.getLeftMost(x.right);
         }
         let y = x.parent;
-        while (y !== this.NIL && y !== null && x === y.right) {
+        while (y !== exports.SN && y !== null && x === y.right) {
             x = y;
@@ -212,7 +210,7 @@ y = y.parent;
     getPredecessor(x) {
-        if (x.left !== this.NIL) {
+        if (x.left !== exports.SN) {
             return this.getRightMost(x.left);
         }
         let y = x.parent;
-        while (y !== this.NIL && x === y.left) {
+        while (y !== exports.SN && x === y.left) {
             x = y;
@@ -230,3 +228,3 @@ y = y.parent;
         x.right = y.left;
-        if (y.left !== this.NIL) {
+        if (y.left !== exports.SN) {
             y.left.parent = x;
@@ -255,3 +253,3 @@ }
         x.left = y.right;
-        if (y.right !== this.NIL) {
+        if (y.right !== exports.SN) {
             y.right.parent = x;
@@ -279,3 +277,3 @@ }
         let s;
-        while (x !== this.root && x.color === 0) {
+        while (x !== this.root && x.color === types_1.RBTNColor.BLACK) {
             if (x === x.parent.left) {
@@ -289,3 +287,3 @@ s = x.parent.right;
                 }
-                if (s.left.color === 0 && s.right.color === 0) {
+                if (s.left !== null && s.left.color === types_1.RBTNColor.BLACK && s.right.color === types_1.RBTNColor.BLACK) {
                     s.color = types_1.RBTNColor.RED;
@@ -295,3 +293,3 @@ x = x.parent;
                 else {
-                    if (s.right.color === 0) {
+                    if (s.right.color === types_1.RBTNColor.BLACK) {
                         s.left.color = types_1.RBTNColor.BLACK;
@@ -317,3 +315,3 @@ s.color = types_1.RBTNColor.RED;
                 }
-                if (s.right.color === 0 && s.right.color === 0) {
+                if (s.right.color === types_1.RBTNColor.BLACK && s.right.color === types_1.RBTNColor.BLACK) {
                     s.color = types_1.RBTNColor.RED;
@@ -323,3 +321,3 @@ x = x.parent;
                 else {
-                    if (s.left.color === 0) {
+                    if (s.left.color === types_1.RBTNColor.BLACK) {
                         s.right.color = types_1.RBTNColor.BLACK;
@@ -326,0 +324,0 @@ s.color = types_1.RBTNColor.RED;

dist/data-structures/binary-tree/tree-multiset.js

@@ -162,3 +162,3 @@ "use strict";
                 if (newNode !== null) {
-                    this._size = (this.size + 1);
+                    this._size = this.size + 1;
                     this._setCount(this.count + newNode.count);
@@ -266,3 +266,3 @@ }
             return bstDeletedResult;
-        const curr = this.get(identifier, callback);
+        const curr = this.getNode(identifier, callback);
         if (!curr)
@@ -269,0 +269,0 @@ return bstDeletedResult;

package.json

 {
   "name": "min-heap-typed",
-  "version": "1.41.0",
+  "version": "1.41.1",
   "description": "Min Heap. Javascript & Typescript Data Structure.",
@@ -134,4 +134,4 @@ "main": "dist/index.js",
   "dependencies": {
-    "data-structure-typed": "^1.41.0"
+    "data-structure-typed": "^1.41.1"
   }
 }

src/data-structures/binary-tree/avl-tree.ts

@@ -24,3 +24,4 @@ /**
   extends BST<V, N>
-  implements IBinaryTree<V, N> {
+  implements IBinaryTree<V, N>
+{
   /**
@@ -164,3 +165,3 @@ * This is a constructor function for an AVL tree data structure in TypeScript.
         this._balanceFactor(A) // second O(1)
-        ) {
+      ) {
         case -2:
@@ -167,0 +168,0 @@ if (A && A.left) {

src/data-structures/binary-tree/binary-indexed-tree.ts

@@ -20,3 +20,3 @@ /**
    */
-  constructor({frequency = 0, max}: { frequency?: number; max: number }) {
+  constructor({frequency = 0, max}: {frequency?: number; max: number}) {
     this._freq = frequency;
@@ -23,0 +23,0 @@ this._max = max;

src/data-structures/binary-tree/binary-tree.ts

@@ -111,3 +111,4 @@ /**
 export class BinaryTree<V = any, N extends BinaryTreeNode<V, N> = BinaryTreeNode<V, BinaryTreeNodeNested<V>>>
-  implements IBinaryTree<V, N> {
+  implements IBinaryTree<V, N>
+{
   iterationType: IterationType = IterationType.ITERATIVE;
@@ -205,3 +206,3 @@
     const key = typeof keyOrNode === 'number' ? keyOrNode : keyOrNode ? keyOrNode.key : undefined;
-    const existNode = key !== undefined ? this.get(key, (node: N) => node.key) : undefined;
+    const existNode = key !== undefined ? this.getNode(key, (node: N) => node.key) : undefined;
 
@@ -295,3 +296,3 @@ if (this.root) {
 
-    const curr = this.get(identifier, callback);
+    const curr = this.getNode(identifier, callback);
     if (!curr) return bstDeletedResult;
@@ -348,4 +349,4 @@
   getDepth(distNode: BTNKey | N | null, beginRoot: BTNKey | N | null = this.root): number {
-    if (typeof distNode === 'number') distNode = this.get(distNode);
-    if (typeof beginRoot === 'number') beginRoot = this.get(beginRoot);
+    if (typeof distNode === 'number') distNode = this.getNode(distNode);
+    if (typeof beginRoot === 'number') beginRoot = this.getNode(beginRoot);
     let depth = 0;
@@ -375,3 +376,3 @@ while (distNode?.parent) {
   getHeight(beginRoot: BTNKey | N | null = this.root, iterationType = this.iterationType): number {
-    if (typeof beginRoot === 'number') beginRoot = this.get(beginRoot);
+    if (typeof beginRoot === 'number') beginRoot = this.getNode(beginRoot);
     if (!beginRoot) return -1;
@@ -393,3 +394,3 @@
 
-      const stack: { node: N; depth: number }[] = [{node: beginRoot, depth: 0}];
+      const stack: {node: N; depth: number}[] = [{node: beginRoot, depth: 0}];
       let maxHeight = 0;
@@ -613,3 +614,3 @@
 
-  get<C extends BTNCallback<N, BTNKey>>(
+  getNode<C extends BTNCallback<N, BTNKey>>(
     identifier: BTNKey,
@@ -621,3 +622,3 @@ callback?: C,
 
-  get<C extends BTNCallback<N, N>>(
+  getNode<C extends BTNCallback<N, N>>(
     identifier: N | null,
@@ -629,3 +630,3 @@ callback?: C,
 
-  get<C extends BTNCallback<N>>(
+  getNode<C extends BTNCallback<N>>(
     identifier: ReturnType<C>,
@@ -652,3 +653,3 @@ callback: C,
    */
-  get<C extends BTNCallback<N>>(
+  getNode<C extends BTNCallback<N>>(
     identifier: ReturnType<C> | null,
@@ -664,3 +665,50 @@ callback: C = ((node: N) => node.key) as C,
 
+  get<C extends BTNCallback<N, BTNKey>>(
+    identifier: BTNKey,
+    callback?: C,
+    beginRoot?: N,
+    iterationType?: IterationType
+  ): V | undefined;
+
+  get<C extends BTNCallback<N, N>>(
+    identifier: N | null,
+    callback?: C,
+    beginRoot?: N,
+    iterationType?: IterationType
+  ): V | undefined;
+
+  get<C extends BTNCallback<N>>(
+    identifier: ReturnType<C>,
+    callback: C,
+    beginRoot?: N,
+    iterationType?: IterationType
+  ): V | undefined;
+
   /**
+   * The function `get` returns the first node value in a binary tree that matches the given property or key.
+   * @param {BTNKey | N} identifier - The `identifier` parameter is the key or value of
+   * the node that you want to find in the binary tree. It can be either a `BTNKey` or `N`
+   * type.
+   * @param callback - The `callback` parameter is a function that is used to determine whether a node
+   * matches the desired criteria. It takes a node as input and returns a boolean value indicating
+   * whether the node matches the criteria or not. The default callback function
+   * (`((node: N) => node.key)`) is used if no callback function is
+   * @param beginRoot - The `beginRoot` parameter is the starting point for the search. It specifies
+   * the root node from which the search should begin.
+   * @param iterationType - The `iterationType` parameter specifies the type of iteration to be
+   * performed when searching for a node in the binary tree. It can have one of the following values:
+   * @returns either the found value (of type V) or undefined if no node value is found.
+   */
+  get<C extends BTNCallback<N>>(
+    identifier: ReturnType<C> | null,
+    callback: C = ((node: N) => node.key) as C,
+    beginRoot = this.root,
+    iterationType = this.iterationType
+  ): V | undefined {
+    if ((identifier as any) instanceof BinaryTreeNode) callback = (node => node) as C;
+    // TODO may support finding node by value equal
+    return this.getNodes(identifier, callback, true, beginRoot, iterationType)[0].value ?? undefined;
+  }
+
+  /**
    * The function `getPathToRoot` returns an array of nodes starting from a given node and traversing
@@ -700,3 +748,3 @@ * up to the root node, with the option to reverse the order of the nodes.
   getLeftMost(beginRoot: BTNKey | N | null = this.root, iterationType = this.iterationType): N | null {
-    if (typeof beginRoot === 'number') beginRoot = this.get(beginRoot);
+    if (typeof beginRoot === 'number') beginRoot = this.getNode(beginRoot);
 
@@ -827,3 +875,3 @@ if (!beginRoot) return beginRoot;
   ): ReturnType<C>[] {
-    if (typeof beginRoot === 'number') beginRoot = this.get(beginRoot);
+    if (typeof beginRoot === 'number') beginRoot = this.getNode(beginRoot);
 
@@ -904,3 +952,3 @@ const ans: ReturnType<BTNCallback<N>>[] = [];
       // 0: visit, 1: print
-      const stack: { opt: 0 | 1; node: N | null | undefined }[] = [{opt: 0, node: beginRoot}];
+      const stack: {opt: 0 | 1; node: N | null | undefined}[] = [{opt: 0, node: beginRoot}];
 
@@ -977,3 +1025,3 @@ while (stack.length > 0) {
         traverse(level + 1);
-      }
+      };
 
@@ -1073,3 +1121,3 @@ traverse(0);
    */
-  getSuccessor(x: N): N | null | undefined{
+  getSuccessor(x: N): N | null | undefined {
     if (x.right) {
@@ -1197,3 +1245,3 @@ return this.getLeftMost(x.right);
    */
-  * [Symbol.iterator](node = this.root): Generator<BTNKey, void, undefined> {
+  *[Symbol.iterator](node = this.root): Generator<BTNKey, void, undefined> {
     if (!node) {
@@ -1200,0 +1248,0 @@ return;

src/data-structures/binary-tree/bst.ts

@@ -22,3 +22,4 @@ /**
   extends BinaryTree<V, N>
-  implements IBinaryTree<V, N> {
+  implements IBinaryTree<V, N>
+{
   /**
@@ -157,3 +158,5 @@ * The constructor function initializes a binary search tree object with an optional comparator
     const inserted: (N | null | undefined)[] = [];
-    const combinedArr: [BTNKey | N, V][] = keysOrNodes.map((value:(BTNKey | N), index) => [value, data?.[index]] as [BTNKey | N, V]);
+    const combinedArr: [BTNKey | N, V][] = keysOrNodes.map(
+      (value: BTNKey | N, index) => [value, data?.[index]] as [BTNKey | N, V]
+    );
     let sorted = [];
@@ -236,3 +239,3 @@
    */
-  override get<C extends BTNCallback<N>>(
+  override getNode<C extends BTNCallback<N>>(
     identifier: ReturnType<C> | null,
@@ -368,3 +371,3 @@ callback: C = ((node: N) => node.key) as C,
   ): ReturnType<C>[] {
-    if (typeof targetNode === 'number') targetNode = this.get(targetNode);
+    if (typeof targetNode === 'number') targetNode = this.getNode(targetNode);
     const ans: ReturnType<BTNCallback<N>>[] = [];
@@ -371,0 +374,0 @@ if (!targetNode) return ans;

src/data-structures/binary-tree/rb-tree.ts

@@ -1,5 +0,5 @@
-import {RBTNColor} from "../../types";
+import {RBTNColor} from '../../types';
 
 export class RBTreeNode {
-  key: number = 0;
+  key: number;
   parent: RBTreeNode;
@@ -10,3 +10,5 @@ left: RBTreeNode;
 
-  constructor() {
+  constructor(key: number, color: RBTNColor = RBTNColor.BLACK) {
+    this.key = key;
+    this.color = color;
     this.parent = null as unknown as RBTreeNode;
@@ -18,10 +20,7 @@ this.left = null as unknown as RBTreeNode;
 
+export const SN = new RBTreeNode(0);
+
 export class RedBlackTree {
-  
   constructor() {
-    this._NIL = new RBTreeNode();
-    this.NIL.color = RBTNColor.BLACK;
-    this.NIL.left = null as unknown as RBTreeNode;
-    this.NIL.right = null as unknown as RBTreeNode;
-    this._root = this.NIL;
+    this._root = SN;
   }
@@ -35,8 +34,2 @@
 
-  protected _NIL: RBTreeNode;
-
-  get NIL(): RBTreeNode {
-    return this._NIL;
-  }
-
   /**
@@ -50,14 +43,10 @@ * The `insert` function inserts a new node with a given key into a red-black tree and fixes any
   insert(key: number): void {
+    const node: RBTreeNode = new RBTreeNode(key, RBTNColor.RED);
+    node.left = SN;
+    node.right = SN;
 
-    const node: RBTreeNode = new RBTreeNode();
-    node.parent = null as unknown as RBTreeNode;
-    node.key = key;
-    node.left = this.NIL;
-    node.right = this.NIL;
-    node.color = RBTNColor.RED;
-
     let y: RBTreeNode = null as unknown as RBTreeNode;
     let x: RBTreeNode = this.root;
 
-    while (x !== this.NIL) {
+    while (x !== SN) {
       y = x;
@@ -101,6 +90,5 @@ if (node.key < x.key) {
     const helper = (node: RBTreeNode): void => {
-
-      let z: RBTreeNode = this.NIL;
+      let z: RBTreeNode = SN;
       let x: RBTreeNode, y: RBTreeNode;
-      while (node !== this.NIL) {
+      while (node !== SN) {
         if (node.key === key) {
@@ -117,4 +105,3 @@ z = node;
 
-      if (z === this.NIL) {
-        console.log("Couldn't find key in the tree");
+      if (z === SN) {
         return;
@@ -125,6 +112,6 @@ }
       let yOriginalColor: number = y.color;
-      if (z.left === this.NIL) {
+      if (z.left === SN) {
         x = z.right;
         this._rbTransplant(z, z.right);
-      } else if (z.right === this.NIL) {
+      } else if (z.right === SN) {
         x = z.left;
@@ -149,9 +136,13 @@ this._rbTransplant(z, z.left);
       }
-      if (yOriginalColor === 0) {
+      if (yOriginalColor === RBTNColor.BLACK) {
         this._fixDelete(x);
       }
-    }
+    };
     helper(this.root);
   }
 
+  isRealNode(node: RBTreeNode): node is RBTreeNode {
+    return node !== SN && node !== null;
+  }
+
   /**
@@ -169,15 +160,16 @@ * The function `getNode` is a recursive depth-first search algorithm that searches for a node with a
     const dfs = (node: RBTreeNode): RBTreeNode => {
-      if (node === this.NIL || key === node.key) {
-        return node;
-      }
+      if (this.isRealNode(node)) {
+        if (key === node.key) {
+          return node;
+        }
 
-      if (key < node.key) {
-        return dfs(node.left);
+        if (key < node.key) return dfs(node.left);
+        return dfs(node.right);
+      } else {
+        return null as unknown as RBTreeNode;
       }
-      return dfs(node.right);
-    }
+    };
     return dfs(beginRoot);
   }
 
-
   /**
@@ -189,4 +181,4 @@ * The function returns the leftmost node in a red-black tree.
    */
-  getLeftMost(node: RBTreeNode): RBTreeNode {
-    while (node.left !== null && node.left !== this.NIL) {
+  getLeftMost(node: RBTreeNode = this.root): RBTreeNode {
+    while (node.left !== null && node.left !== SN) {
       node = node.left;
@@ -197,3 +189,2 @@ }
 
-
   /**
@@ -205,3 +196,3 @@ * The function returns the rightmost node in a red-black tree.
   getRightMost(node: RBTreeNode): RBTreeNode {
-    while (node.right !== null && node.right !== this.NIL) {
+    while (node.right !== null && node.right !== SN) {
       node = node.right;
@@ -218,4 +209,3 @@ }
   getSuccessor(x: RBTreeNode): RBTreeNode {
-
-    if (x.right !== this.NIL) {
+    if (x.right !== SN) {
       return this.getLeftMost(x.right);
@@ -225,3 +215,3 @@ }
     let y: RBTreeNode = x.parent;
-    while (y !== this.NIL && y !== null && x === y.right) {
+    while (y !== SN && y !== null && x === y.right) {
       x = y;
@@ -240,4 +230,3 @@ y = y.parent;
   getPredecessor(x: RBTreeNode): RBTreeNode {
-
-    if (x.left !== this.NIL) {
+    if (x.left !== SN) {
       return this.getRightMost(x.left);
@@ -247,3 +236,3 @@ }
     let y: RBTreeNode = x.parent;
-    while (y !== this.NIL && x === y.left) {
+    while (y !== SN && x === y.left) {
       x = y;
@@ -263,3 +252,3 @@ y = y.parent;
     x.right = y.left;
-    if (y.left !== this.NIL) {
+    if (y.left !== SN) {
       y.left.parent = x;
@@ -287,3 +276,3 @@ }
     x.left = y.right;
-    if (y.right !== this.NIL) {
+    if (y.right !== SN) {
       y.right.parent = x;
@@ -310,7 +299,6 @@ }
     let s: RBTreeNode;
-    while (x !== this.root && x.color === 0) {
+    while (x !== this.root && x.color === RBTNColor.BLACK) {
       if (x === x.parent.left) {
         s = x.parent.right;
         if (s.color === 1) {
-
           s.color = RBTNColor.BLACK;
@@ -322,9 +310,7 @@ x.parent.color = RBTNColor.RED;
 
-        if (s.left.color === 0 && s.right.color === 0) {
-
+        if (s.left !== null && s.left.color === RBTNColor.BLACK && s.right.color === RBTNColor.BLACK) {
           s.color = RBTNColor.RED;
           x = x.parent;
         } else {
-          if (s.right.color === 0) {
-
+          if (s.right.color === RBTNColor.BLACK) {
             s.left.color = RBTNColor.BLACK;
@@ -345,3 +331,2 @@ s.color = RBTNColor.RED;
         if (s.color === 1) {
-
           s.color = RBTNColor.BLACK;
@@ -353,9 +338,7 @@ x.parent.color = RBTNColor.RED;
 
-        if (s.right.color === 0 && s.right.color === 0) {
-
+        if (s.right.color === RBTNColor.BLACK && s.right.color === RBTNColor.BLACK) {
           s.color = RBTNColor.RED;
           x = x.parent;
         } else {
-          if (s.left.color === 0) {
-
+          if (s.left.color === RBTNColor.BLACK) {
             s.right.color = RBTNColor.BLACK;
@@ -405,3 +388,2 @@ s.color = RBTNColor.RED;
         if (u.color === 1) {
-
           u.color = RBTNColor.BLACK;
@@ -413,3 +395,2 @@ k.parent.color = RBTNColor.BLACK;
           if (k === k.parent.left) {
-
             k = k.parent;
@@ -427,3 +408,2 @@ this._rightRotate(k);
         if (u.color === 1) {
-
           u.color = RBTNColor.BLACK;
@@ -435,3 +415,2 @@ k.parent.color = RBTNColor.BLACK;
           if (k === k.parent.right) {
-
             k = k.parent;
@@ -452,2 +431,2 @@ this._leftRotate(k);
   }
-}
+}

src/data-structures/binary-tree/tree-multiset.ts

@@ -40,3 +40,4 @@ /**
   extends AVLTree<V, N>
-  implements IBinaryTree<V, N> {
+  implements IBinaryTree<V, N>
+{
   /**
@@ -173,3 +174,3 @@ * The constructor function for a TreeMultiset class in TypeScript, which extends another class and sets an option to
         if (newNode !== null) {
-          this._size = (this.size + 1);
+          this._size = this.size + 1;
           this._setCount(this.count + newNode.count);
@@ -287,3 +288,3 @@ }
 
-    const curr: N | null = this.get(identifier, callback);
+    const curr: N | null = this.getNode(identifier, callback);
     if (!curr) return bstDeletedResult;
@@ -290,0 +291,0 @@

src/data-structures/graph/abstract-graph.ts

@@ -29,3 +29,2 @@ /**
   }
-
 }
@@ -69,3 +68,4 @@
   EO extends AbstractEdge<E> = AbstractEdge<E>
-> implements IGraph<V, E, VO, EO> {
+> implements IGraph<V, E, VO, EO>
+{
   protected _vertices: Map<VertexKey, VO> = new Map<VertexKey, VO>();
@@ -518,10 +518,10 @@
     getMinDist &&
-    distMap.forEach((d, v) => {
-      if (v !== srcVertex) {
-        if (d < minDist) {
-          minDist = d;
-          if (genPaths) minDest = v;
+      distMap.forEach((d, v) => {
+        if (v !== srcVertex) {
+          if (d < minDist) {
+            minDist = d;
+            if (genPaths) minDest = v;
+          }
         }
-      }
-    });
+      });
 
@@ -588,3 +588,3 @@ genPaths && getPaths(minDest);
 
-    const heap = new PriorityQueue<{ key: number; value: VO }>({comparator: (a, b) => a.key - b.key});
+    const heap = new PriorityQueue<{key: number; value: VO}>({comparator: (a, b) => a.key - b.key});
     heap.add({key: 0, value: srcVertex});
@@ -818,3 +818,3 @@
    */
-  floyd(): { costs: number[][]; predecessor: (VO | null)[][] } {
+  floyd(): {costs: number[][]; predecessor: (VO | null)[][]} {
     const idAndVertices = [...this._vertices];
@@ -1004,3 +1004,2 @@ const n = idAndVertices.length;
   }
-
 }

src/data-structures/graph/directed-graph.ts

@@ -49,9 +49,10 @@ /**
 export class DirectedGraph<
-  V = any,
-  E = any,
-  VO extends DirectedVertex<V> = DirectedVertex<V>,
-  EO extends DirectedEdge<E> = DirectedEdge<E>
->
+    V = any,
+    E = any,
+    VO extends DirectedVertex<V> = DirectedVertex<V>,
+    EO extends DirectedEdge<E> = DirectedEdge<E>
+  >
   extends AbstractGraph<V, E, VO, EO>
-  implements IGraph<V, E, VO, EO> {
+  implements IGraph<V, E, VO, EO>
+{
   /**
@@ -58,0 +59,0 @@ * The constructor function initializes an instance of a class.

src/data-structures/graph/undirected-graph.ts

@@ -46,9 +46,10 @@ /**
 export class UndirectedGraph<
-  V = any,
-  E = any,
-  VO extends UndirectedVertex<V> = UndirectedVertex<V>,
-  EO extends UndirectedEdge<E> = UndirectedEdge<E>
->
+    V = any,
+    E = any,
+    VO extends UndirectedVertex<V> = UndirectedVertex<V>,
+    EO extends UndirectedEdge<E> = UndirectedEdge<E>
+  >
   extends AbstractGraph<V, E, VO, EO>
-  implements IGraph<V, E, VO, EO> {
+  implements IGraph<V, E, VO, EO>
+{
   /**
@@ -55,0 +56,0 @@ * The constructor initializes a new Map object to store edges.

src/data-structures/hash/hash-map.ts

@@ -136,3 +136,3 @@ import {HashFunction} from '../../types';
 
-  * entries(): IterableIterator<[K, V]> {
+  *entries(): IterableIterator<[K, V]> {
     for (const bucket of this.table) {
@@ -139,0 +139,0 @@ if (bucket) {

src/data-structures/hash/tree-map.ts

@@ -1,2 +0,1 @@
-export class TreeMap {
-}
+export class TreeMap {}

src/data-structures/hash/tree-set.ts

@@ -1,2 +0,1 @@
-export class TreeSet {
-}
+export class TreeSet {}

src/data-structures/heap/heap.ts

@@ -11,3 +11,3 @@ /**
 export class Heap<E = any> {
-  constructor(options: { comparator: Comparator<E>; nodes?: E[] }) {
+  constructor(options: {comparator: Comparator<E>; nodes?: E[]}) {
     this._comparator = options.comparator;
@@ -52,3 +52,3 @@ if (options.nodes && options.nodes.length > 0) {
    */
-  static heapify<E>(options: { nodes: E[]; comparator: Comparator<E> }): Heap<E> {
+  static heapify<E>(options: {nodes: E[]; comparator: Comparator<E>}): Heap<E> {
     return new Heap<E>(options);
@@ -55,0 +55,0 @@ }

src/data-structures/heap/max-heap.ts

@@ -14,3 +14,3 @@ /**
   constructor(
-    options: { comparator: Comparator<E>; nodes?: E[] } = {
+    options: {comparator: Comparator<E>; nodes?: E[]} = {
       comparator: (a: E, b: E) => {
@@ -17,0 +17,0 @@ if (!(typeof a === 'number' && typeof b === 'number')) {

src/data-structures/heap/min-heap.ts

@@ -14,3 +14,3 @@ /**
   constructor(
-    options: { comparator: Comparator<E>; nodes?: E[] } = {
+    options: {comparator: Comparator<E>; nodes?: E[]} = {
       comparator: (a: E, b: E) => {
@@ -17,0 +17,0 @@ if (!(typeof a === 'number' && typeof b === 'number')) {

src/data-structures/linked-list/doubly-linked-list.ts

@@ -597,3 +597,3 @@ /**
    */
-  * [Symbol.iterator]() {
+  *[Symbol.iterator]() {
     let current = this.head;
@@ -600,0 +600,0 @@

src/data-structures/linked-list/singly-linked-list.ts

@@ -568,3 +568,3 @@ /**
    */
-  * [Symbol.iterator]() {
+  *[Symbol.iterator]() {
     let current = this.head;
@@ -571,0 +571,0 @@

src/data-structures/matrix/matrix.ts

@@ -17,3 +17,3 @@ /**
    */
-  constructor(options: { row: number; col: number; initialVal?: V }) {
+  constructor(options: {row: number; col: number; initialVal?: V}) {
     const {row, col, initialVal} = options;
@@ -20,0 +20,0 @@ this._matrix = new Array(row).fill(undefined).map(() => new Array(col).fill(initialVal || 0));

src/data-structures/matrix/vector2d.ts

@@ -13,4 +13,3 @@ /**
     public w: number = 1 // needed for matrix multiplication
-  ) {
-  }
+  ) {}
 
@@ -17,0 +16,0 @@ /**

src/data-structures/priority-queue/max-priority-queue.ts

@@ -13,3 +13,3 @@ /**
   constructor(
-    options: { comparator: Comparator<E>; nodes?: E[] } = {
+    options: {comparator: Comparator<E>; nodes?: E[]} = {
       comparator: (a: E, b: E) => {
@@ -16,0 +16,0 @@ if (!(typeof a === 'number' && typeof b === 'number')) {

src/data-structures/priority-queue/min-priority-queue.ts

@@ -13,3 +13,3 @@ /**
   constructor(
-    options: { comparator: Comparator<E>; nodes?: E[] } = {
+    options: {comparator: Comparator<E>; nodes?: E[]} = {
       comparator: (a: E, b: E) => {
@@ -16,0 +16,0 @@ if (!(typeof a === 'number' && typeof b === 'number')) {

src/data-structures/priority-queue/priority-queue.ts

@@ -13,5 +13,5 @@ /**
 export class PriorityQueue<E = any> extends Heap<E> {
-  constructor(options: { comparator: Comparator<E>; nodes?: E[] }) {
+  constructor(options: {comparator: Comparator<E>; nodes?: E[]}) {
     super(options);
   }
 }

src/data-structures/queue/deque.ts

@@ -12,4 +12,3 @@ /**
 // O(1) time complexity of adding at the beginning and the end
-export class Deque<E = any> extends DoublyLinkedList<E> {
-}
+export class Deque<E = any> extends DoublyLinkedList<E> {}
 
@@ -24,5 +23,5 @@ // O(1) time complexity of obtaining the value
 
-  protected _nodes: { [key: number]: E } = {};
+  protected _nodes: {[key: number]: E} = {};
 
-  get nodes(): { [p: number]: E } {
+  get nodes(): {[p: number]: E} {
     return this._nodes;
@@ -29,0 +28,0 @@ }

src/data-structures/queue/queue.ts

@@ -204,3 +204,3 @@ /**
 
-  * [Symbol.iterator]() {
+  *[Symbol.iterator]() {
     for (const item of this.nodes) {
@@ -207,0 +207,0 @@ yield item;

src/types/data-structures/matrix/navigator.ts

 export type Direction = 'up' | 'right' | 'down' | 'left';
 
-export type Turning = { [key in Direction]: Direction };
+export type Turning = {[key in Direction]: Direction};
 
@@ -5,0 +5,0 @@ export type NavigatorParams<T = any> = {

src/types/utils/utils.ts

 export type ToThunkFn = () => ReturnType<TrlFn>;
-export type Thunk = () => ReturnType<ToThunkFn> & { __THUNK__: symbol };
+export type Thunk = () => ReturnType<ToThunkFn> & {__THUNK__: symbol};
 export type TrlFn = (...args: any[]) => any;
@@ -4,0 +4,0 @@ export type TrlAsyncFn = (...args: any[]) => any;

src/types/utils/validate-type.ts

@@ -1,4 +0,4 @@
-export type KeyValueObject = { [key: string]: any };
+export type KeyValueObject = {[key: string]: any};
 
-export type KeyValueObjectWithKey = { [key: string]: any; key: string | number | symbol };
+export type KeyValueObjectWithKey = {[key: string]: any; key: string | number | symbol};
 
@@ -5,0 +5,0 @@ export type NonNumberNonObjectButDefined = string | boolean | symbol | null;

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

1289962

increased by0.34%

Lines of code

25425

increased by0.27%

Dependency changes

• Updateddata-structure-typed@^1.41.1