masonic - npm Package Compare versions

Comparing version 2.0.15 to 2.0.16

dist/cjs/IntervalTree.d.ts

 declare type Color = 0 | 1 | 2
-interface Interval {
-  high: number
-  index: number
-}
 interface TreeNode {
@@ -14,3 +10,3 @@ max: number
   left: TreeNode
-  list: Interval[]
+  list: number[]
 }
@@ -17,0 +13,0 @@ interface IIntervalTree {

dist/cjs/IntervalTree.js

@@ -14,6 +14,3 @@ 'use strict'
   if (treeNode.list.length === 0) {
-    treeNode.list.push({
-      index,
-      high,
-    })
+    treeNode.list.push(index, high)
     return true
@@ -23,8 +20,5 @@ }
   for (let i = 0; i < treeNode.list.length; i++)
-    if (treeNode.list[i].index === index) return false
+    if (treeNode.list[i] === index && i % 2 === 0) return false
 
-  treeNode.list.push({
-    index,
-    high,
-  })
+  treeNode.list.push(index, high)
   return true
@@ -36,5 +30,5 @@ }
 
-  for (let i = treeNode.list.length - 1; i > -1; i--)
-    if (treeNode.list[i].index === index) {
-      treeNode.list.splice(i, 1)
+  for (let i = 0; i < treeNode.list.length; i++)
+    if (treeNode.list[i] === index && i % 2 === 0) {
+      treeNode.list.splice(i, 2)
       break
@@ -115,15 +109,10 @@ }
 
-const rbTransplant = (tree, u, v) => {
-  if (u.parent === NULL_NODE) {
-    tree.root = v
-  } else if (u === u.parent.left) {
-    u.parent.left = v
-  } else {
-    u.parent.right = v
-  }
-
-  v.parent = u.parent
+const replaceNode = (tree, x, y) => {
+  if (x.parent === NULL_NODE) tree.root = y
+  else if (x === x.parent.left) x.parent.left = y
+  else x.parent.right = y
+  y.parent = x.parent
 }
 
-const rbDeleteFixup = (tree, x) => {
+const fixRemove = (tree, x) => {
   let w
@@ -196,14 +185,11 @@
   return x
-}
+} // const searchNode = (x: TreeNode, low: number) => {
+//   while (x !== NULL_NODE && low !== x.low) {
+//     if (low < x.low) x = x.left
+//     else x = x.right
+//   }
+//   return x
+// }
 
-const searchNode = (x, low) => {
-  while (x !== NULL_NODE && low !== x.low) {
-    if (low < x.low) x = x.left
-    else x = x.right
-  }
-
-  return x
-}
-
-const rbInsertFixup = (tree, z) => {
+const fixInsert = (tree, z) => {
   let y
@@ -258,2 +244,6 @@
     size: 0,
+    // we know these indexes are a consistent, safe way to make look ups
+    // for our case so it's a solid O(1) alternative to
+    // the O(log n) searchNode()
+    indexMap: {},
   }
@@ -277,2 +267,3 @@ return {
         updateMaxUp(y)
+        tree.indexMap[index] = y
         tree.size++
@@ -290,8 +281,3 @@ return
         right: NULL_NODE,
-        list: [
-          {
-            index,
-            high,
-          },
-        ],
+        list: [index, high],
       }
@@ -307,3 +293,4 @@
 
-      rbInsertFixup(tree, z)
+      fixInsert(tree, z)
+      tree.indexMap[index] = z
       tree.size++
@@ -313,4 +300,5 @@ },
     remove(low, high, index) {
-      const z = searchNode(tree.root, low)
-      if (z === void 0) return
+      const z = tree.indexMap[index]
+      if (z === void 0 || z.low !== low) return
+      delete tree.indexMap[index]
       const intervalResult = removeInterval(z, index)
@@ -320,3 +308,3 @@ if (intervalResult === NOT_FOUND) return
       if (intervalResult === KEEP) {
-        z.high = z.list[0].high
+        z.high = z.list[1]
         updateMax(z)
@@ -334,6 +322,6 @@ updateMaxUp(z)
         x = z.right
-        rbTransplant(tree, z, z.right)
+        replaceNode(tree, z, z.right)
       } else if (z.right === NULL_NODE) {
         x = z.left
-        rbTransplant(tree, z, z.left)
+        replaceNode(tree, z, z.left)
       } else {
@@ -347,3 +335,3 @@ y = minimumTree(z.right)
         } else {
-          rbTransplant(tree, y, y.right)
+          replaceNode(tree, y, y.right)
           y.right = z.right
@@ -353,3 +341,3 @@ y.right.parent = y
 
-        rbTransplant(tree, z, y)
+        replaceNode(tree, z, y)
         y.left = z.left
@@ -362,3 +350,3 @@ y.left.parent = y
       updateMaxUp(x)
-      if (originalYColor === BLACK) rbDeleteFixup(tree, x)
+      if (originalYColor === BLACK) fixRemove(tree, x)
       tree.size--
@@ -374,5 +362,5 @@ },
           for (let i = 0; i < node.list.length; i++) {
-            const interval = node.list[i]
-            if (interval.high >= low)
-              callback(interval.index, node.low, interval.high)
+            const index = node.list[i]
+            const nodeHigh = node.list[++i]
+            if (nodeHigh >= low) callback(index, node.low, nodeHigh)
           }
@@ -379,0 +367,0 @@ }

dist/es/IntervalTree.d.ts

 declare type Color = 0 | 1 | 2
-interface Interval {
-  high: number
-  index: number
-}
 interface TreeNode {
@@ -14,3 +10,3 @@ max: number
   left: TreeNode
-  list: Interval[]
+  list: number[]
 }
@@ -17,0 +13,0 @@ interface IIntervalTree {

dist/es/IntervalTree.js

@@ -10,6 +10,3 @@ const RED = 0
   if (treeNode.list.length === 0) {
-    treeNode.list.push({
-      index,
-      high,
-    })
+    treeNode.list.push(index, high)
     return true
@@ -19,8 +16,5 @@ }
   for (let i = 0; i < treeNode.list.length; i++)
-    if (treeNode.list[i].index === index) return false
+    if (treeNode.list[i] === index && i % 2 === 0) return false
 
-  treeNode.list.push({
-    index,
-    high,
-  })
+  treeNode.list.push(index, high)
   return true
@@ -32,5 +26,5 @@ }
 
-  for (let i = treeNode.list.length - 1; i > -1; i--)
-    if (treeNode.list[i].index === index) {
-      treeNode.list.splice(i, 1)
+  for (let i = 0; i < treeNode.list.length; i++)
+    if (treeNode.list[i] === index && i % 2 === 0) {
+      treeNode.list.splice(i, 2)
       break
@@ -111,15 +105,10 @@ }
 
-const rbTransplant = (tree, u, v) => {
-  if (u.parent === NULL_NODE) {
-    tree.root = v
-  } else if (u === u.parent.left) {
-    u.parent.left = v
-  } else {
-    u.parent.right = v
-  }
-
-  v.parent = u.parent
+const replaceNode = (tree, x, y) => {
+  if (x.parent === NULL_NODE) tree.root = y
+  else if (x === x.parent.left) x.parent.left = y
+  else x.parent.right = y
+  y.parent = x.parent
 }
 
-const rbDeleteFixup = (tree, x) => {
+const fixRemove = (tree, x) => {
   let w
@@ -192,14 +181,11 @@
   return x
-}
+} // const searchNode = (x: TreeNode, low: number) => {
+//   while (x !== NULL_NODE && low !== x.low) {
+//     if (low < x.low) x = x.left
+//     else x = x.right
+//   }
+//   return x
+// }
 
-const searchNode = (x, low) => {
-  while (x !== NULL_NODE && low !== x.low) {
-    if (low < x.low) x = x.left
-    else x = x.right
-  }
-
-  return x
-}
-
-const rbInsertFixup = (tree, z) => {
+const fixInsert = (tree, z) => {
   let y
@@ -254,2 +240,6 @@
     size: 0,
+    // we know these indexes are a consistent, safe way to make look ups
+    // for our case so it's a solid O(1) alternative to
+    // the O(log n) searchNode()
+    indexMap: {},
   }
@@ -273,2 +263,3 @@ return {
         updateMaxUp(y)
+        tree.indexMap[index] = y
         tree.size++
@@ -286,8 +277,3 @@ return
         right: NULL_NODE,
-        list: [
-          {
-            index,
-            high,
-          },
-        ],
+        list: [index, high],
       }
@@ -303,3 +289,4 @@
 
-      rbInsertFixup(tree, z)
+      fixInsert(tree, z)
+      tree.indexMap[index] = z
       tree.size++
@@ -309,4 +296,5 @@ },
     remove(low, high, index) {
-      const z = searchNode(tree.root, low)
-      if (z === void 0) return
+      const z = tree.indexMap[index]
+      if (z === void 0 || z.low !== low) return
+      delete tree.indexMap[index]
       const intervalResult = removeInterval(z, index)
@@ -316,3 +304,3 @@ if (intervalResult === NOT_FOUND) return
       if (intervalResult === KEEP) {
-        z.high = z.list[0].high
+        z.high = z.list[1]
         updateMax(z)
@@ -330,6 +318,6 @@ updateMaxUp(z)
         x = z.right
-        rbTransplant(tree, z, z.right)
+        replaceNode(tree, z, z.right)
       } else if (z.right === NULL_NODE) {
         x = z.left
-        rbTransplant(tree, z, z.left)
+        replaceNode(tree, z, z.left)
       } else {
@@ -343,3 +331,3 @@ y = minimumTree(z.right)
         } else {
-          rbTransplant(tree, y, y.right)
+          replaceNode(tree, y, y.right)
           y.right = z.right
@@ -349,3 +337,3 @@ y.right.parent = y
 
-        rbTransplant(tree, z, y)
+        replaceNode(tree, z, y)
         y.left = z.left
@@ -358,3 +346,3 @@ y.left.parent = y
       updateMaxUp(x)
-      if (originalYColor === BLACK) rbDeleteFixup(tree, x)
+      if (originalYColor === BLACK) fixRemove(tree, x)
       tree.size--
@@ -370,5 +358,5 @@ },
           for (let i = 0; i < node.list.length; i++) {
-            const interval = node.list[i]
-            if (interval.high >= low)
-              callback(interval.index, node.low, interval.high)
+            const index = node.list[i]
+            const nodeHigh = node.list[++i]
+            if (nodeHigh >= low) callback(index, node.low, nodeHigh)
           }
@@ -375,0 +363,0 @@ }

package.json

 {
   "name": "masonic",
-  "version": "2.0.15",
+  "version": "2.0.16",
   "homepage": "https://github.com/jaredLunde/masonic#readme",
@@ -5,0 +5,0 @@ "repository": "github:jaredLunde/masonic",

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

93046

increased by0.31%

Worsened metrics

Lines of code

2529

decreased by-1.02%

No dependency changes