graph-typed - npm Package Compare versions

Comparing version 1.50.3 to 1.50.4

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

@@ -627,7 +627,5 @@ "use strict";
                     ans.push(callback(cur));
-                if (!cur.left && !cur.right)
-                    return;
-                if (cur.left && this._compare(cur.left.key, targetKey) === lesserOrGreater)
+                if (this.isRealNode(cur.left))
                     _traverse(cur.left);
-                if (cur.right && this._compare(cur.right.key, targetKey) === lesserOrGreater)
+                if (this.isRealNode(cur.right))
                     _traverse(cur.right);
@@ -642,9 +640,9 @@ };
                 const cur = queue.shift();
-                if (cur) {
+                if (this.isRealNode(cur)) {
                     const compared = this._compare(cur.key, targetKey);
                     if (compared === lesserOrGreater)
                         ans.push(callback(cur));
-                    if (cur.left && this._compare(cur.left.key, targetKey) === lesserOrGreater)
+                    if (this.isRealNode(cur.left))
                         queue.push(cur.left);
-                    if (cur.right && this._compare(cur.right.key, targetKey) === lesserOrGreater)
+                    if (this.isRealNode(cur.right))
                         queue.push(cur.right);
@@ -651,0 +649,0 @@ }

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

@@ -7,2 +7,3 @@ export * from './binary-tree';
 export * from './rb-tree';
-export * from './tree-multimap';
+export * from './avl-tree-multi-map';
+export * from './tree-multi-map';

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

@@ -23,2 +23,3 @@ "use strict";
 __exportStar(require("./rb-tree"), exports);
-__exportStar(require("./tree-multimap"), exports);
+__exportStar(require("./avl-tree-multi-map"), exports);
+__exportStar(require("./tree-multi-map"), exports);

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

@@ -476,8 +476,9 @@ "use strict";
         let u;
-        while (k.parent && k.parent.color === 1) {
+        while (k.parent && k.parent.color === types_1.RBTNColor.RED) {
             if (k.parent.parent && k.parent === k.parent.parent.right) {
                 u = k.parent.parent.left;
-                if (u && u.color === 1) {
+                if (u && u.color === types_1.RBTNColor.RED) {
+                    // Delay color flip
+                    k.parent.color = types_1.RBTNColor.BLACK;
                     u.color = types_1.RBTNColor.BLACK;
-                    k.parent.color = types_1.RBTNColor.BLACK;
                     k.parent.parent.color = types_1.RBTNColor.RED;
@@ -491,4 +492,7 @@ k = k.parent.parent;
                     }
-                    k.parent.color = types_1.RBTNColor.BLACK;
-                    k.parent.parent.color = types_1.RBTNColor.RED;
+                    // Check color before rotation
+                    if (k.parent.color === types_1.RBTNColor.RED) {
+                        k.parent.color = types_1.RBTNColor.BLACK;
+                        k.parent.parent.color = types_1.RBTNColor.RED;
+                    }
                     this._leftRotate(k.parent.parent);
@@ -499,5 +503,6 @@ }
                 u = k.parent.parent.right;
-                if (u && u.color === 1) {
+                if (u && u.color === types_1.RBTNColor.RED) {
+                    // Delay color flip
+                    k.parent.color = types_1.RBTNColor.BLACK;
                     u.color = types_1.RBTNColor.BLACK;
-                    k.parent.color = types_1.RBTNColor.BLACK;
                     k.parent.parent.color = types_1.RBTNColor.RED;
@@ -511,4 +516,7 @@ k = k.parent.parent;
                     }
-                    k.parent.color = types_1.RBTNColor.BLACK;
-                    k.parent.parent.color = types_1.RBTNColor.RED;
+                    // Check color before rotation
+                    if (k.parent.color === types_1.RBTNColor.RED) {
+                        k.parent.color = types_1.RBTNColor.BLACK;
+                        k.parent.parent.color = types_1.RBTNColor.RED;
+                    }
                     this._rightRotate(k.parent.parent);
@@ -515,0 +523,0 @@ }

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

@@ -5,3 +5,4 @@ export * from './binary-tree';
 export * from './segment-tree';
-export * from './tree-multimap';
+export * from './avl-tree-multi-map';
 export * from './rb-tree';
+export * from './tree-multi-map';

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

@@ -21,3 +21,4 @@ "use strict";
 __exportStar(require("./segment-tree"), exports);
-__exportStar(require("./tree-multimap"), exports);
+__exportStar(require("./avl-tree-multi-map"), exports);
 __exportStar(require("./rb-tree"), exports);
+__exportStar(require("./tree-multi-map"), exports);

package.json

 {
   "name": "graph-typed",
-  "version": "1.50.3",
+  "version": "1.50.4",
   "description": "Graph. Javascript & Typescript Data Structure.",
@@ -139,4 +139,4 @@ "main": "dist/index.js",
   "dependencies": {
-    "data-structure-typed": "^1.50.3"
+    "data-structure-typed": "^1.50.4"
   }
 }

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

@@ -711,5 +711,4 @@ /**
 
-        if (!cur.left && !cur.right) return;
-        if (cur.left && this._compare(cur.left.key, targetKey) === lesserOrGreater) _traverse(cur.left);
-        if (cur.right && this._compare(cur.right.key, targetKey) === lesserOrGreater) _traverse(cur.right);
+        if (this.isRealNode(cur.left)) _traverse(cur.left);
+        if (this.isRealNode(cur.right)) _traverse(cur.right);
       };
@@ -723,8 +722,8 @@
         const cur = queue.shift();
-        if (cur) {
+        if (this.isRealNode(cur)) {
           const compared = this._compare(cur.key, targetKey);
           if (compared === lesserOrGreater) ans.push(callback(cur));
 
-          if (cur.left && this._compare(cur.left.key, targetKey) === lesserOrGreater) queue.push(cur.left);
-          if (cur.right && this._compare(cur.right.key, targetKey) === lesserOrGreater) queue.push(cur.right);
+          if (this.isRealNode(cur.left)) queue.push(cur.left);
+          if (this.isRealNode(cur.right)) queue.push(cur.right);
         }
@@ -731,0 +730,0 @@ }

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

@@ -7,2 +7,3 @@ export * from './binary-tree';
 export * from './rb-tree';
-export * from './tree-multimap';
+export * from './avl-tree-multi-map';
+export * from './tree-multi-map';

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

@@ -530,8 +530,10 @@ /**
     let u: NODE | undefined;
-    while (k.parent && k.parent.color === 1) {
+    while (k.parent && k.parent.color === RBTNColor.RED) {
       if (k.parent.parent && k.parent === k.parent.parent.right) {
         u = k.parent.parent.left;
-        if (u && u.color === 1) {
+
+        if (u && u.color === RBTNColor.RED) {
+          // Delay color flip
+          k.parent.color = RBTNColor.BLACK;
           u.color = RBTNColor.BLACK;
-          k.parent.color = RBTNColor.BLACK;
           k.parent.parent.color = RBTNColor.RED;
@@ -545,12 +547,16 @@ k = k.parent.parent;
 
-          k.parent!.color = RBTNColor.BLACK;
-          k.parent!.parent!.color = RBTNColor.RED;
+          // Check color before rotation
+          if (k.parent!.color === RBTNColor.RED) {
+            k.parent!.color = RBTNColor.BLACK;
+            k.parent!.parent!.color = RBTNColor.RED;
+          }
           this._leftRotate(k.parent!.parent!);
         }
       } else {
-        u = k.parent.parent!.right;
+        u = k.parent!.parent!.right;
 
-        if (u && u.color === 1) {
+        if (u && u.color === RBTNColor.RED) {
+          // Delay color flip
+          k.parent.color = RBTNColor.BLACK;
           u.color = RBTNColor.BLACK;
-          k.parent.color = RBTNColor.BLACK;
           k.parent.parent!.color = RBTNColor.RED;
@@ -564,7 +570,11 @@ k = k.parent.parent!;
 
-          k.parent!.color = RBTNColor.BLACK;
-          k.parent!.parent!.color = RBTNColor.RED;
+          // Check color before rotation
+          if (k.parent!.color === RBTNColor.RED) {
+            k.parent!.color = RBTNColor.BLACK;
+            k.parent!.parent!.color = RBTNColor.RED;
+          }
           this._rightRotate(k.parent!.parent!);
         }
       }
+
       if (k === this.root) {
@@ -571,0 +581,0 @@ break;

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

@@ -5,3 +5,4 @@ export * from './binary-tree';
 export * from './segment-tree';
-export * from './tree-multimap';
+export * from './avl-tree-multi-map';
 export * from './rb-tree';
+export * from './tree-multi-map';

No alert changes

Improved metrics

Total package byte prevSize

2886996

1.91%

Number of package files

352

1.73%

Lines of code

41588

2.64%

Dependency changes

• Updated

  data-structure-typed@^1.50.4