masonic - npm Package Compare versions

Comparing version 2.1.4 to 2.1.5

dist/cjs/IntervalTree.d.ts

@@ -1,12 +0,1 @@
-declare type Color = 0 | 1 | 2
-interface TreeNode {
-  max: number
-  low: number
-  high: number
-  color: Color
-  parent: TreeNode
-  right: TreeNode
-  left: TreeNode
-  list: number[]
-}
 interface IIntervalTree {
@@ -21,5 +10,4 @@ insert(low: number, high: number, index: number): void
   size: number
-  root: TreeNode
 }
 declare const IntervalTree: () => IIntervalTree
 export default IntervalTree

dist/cjs/IntervalTree.js

@@ -10,14 +10,26 @@ 'use strict'
 const KEEP = 1
-const NOT_FOUND = 2
 
 const addInterval = (treeNode, high, index) => {
-  if (treeNode.list.length === 0) {
-    treeNode.list.push(index, high)
-    return true
+  let node = treeNode.list
+  let prevNode
+
+  while (node) {
+    if (node.index === index) return false
+    if (high > node.high) break
+    prevNode = node
+    node = node.next
   }
 
-  for (let i = 0; i < treeNode.list.length; i++)
-    if (treeNode.list[i] === index && i % 2 === 0) return false
-
-  treeNode.list.push(index, high)
+  if (!prevNode)
+    treeNode.list = {
+      index,
+      high,
+      next: node,
+    }
+  if (prevNode)
+    prevNode.next = {
+      index,
+      high,
+      next: prevNode.next,
+    }
   return true
@@ -27,11 +39,22 @@ }
 const removeInterval = (treeNode, index) => {
-  if (treeNode.list === void 0) return NOT_FOUND
+  let node = treeNode.list
 
-  for (let i = 0; i < treeNode.list.length; i++)
-    if (treeNode.list[i] === index && i % 2 === 0) {
-      treeNode.list.splice(i, 2)
-      break
+  if (node.index === index) {
+    if (node.next === null) return DELETE
+    treeNode.list = node.next
+    return KEEP
+  }
+
+  let prevNode = node
+  node = node.next
+
+  while (node !== null) {
+    if (node.index === index) {
+      prevNode.next = node.next
+      return KEEP
     }
 
-  return treeNode.list.length > 0 ? KEEP : DELETE
+    prevNode = node
+    node = node.next
+  }
 }
@@ -183,9 +206,3 @@
   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
-// }
+}
 
@@ -244,3 +261,3 @@ const fixInsert = (tree, z) => {
     // for our case so it's a solid O(1) alternative to
-    // the O(log n) searchNode()
+    // the O(log n) searchNode() in typical interval trees
     indexMap: {},
@@ -278,3 +295,7 @@ }
         right: NULL_NODE,
-        list: [index, high],
+        list: {
+          index,
+          high,
+          next: null,
+        },
       }
@@ -300,6 +321,6 @@
       const intervalResult = removeInterval(z, index)
-      if (intervalResult === NOT_FOUND) return
+      if (intervalResult === void 0) return
 
       if (intervalResult === KEEP) {
-        z.high = z.list[1]
+        z.high = z.list.high
         updateMax(z)
@@ -356,7 +377,7 @@ updateMaxUp(z)
         if (node.low <= high && node.high >= low) {
-          for (let i = 0, len = node.list.length; i < len; i++) {
-            const index = node.list[i++] // normally we'd include the high bound here, too, but since we
-            // don't need it in practice, it makes sense to just leave it out
+          let curr = node.list
 
-            if (node.list[i] >= low) callback(index, node.low)
+          while (curr !== null) {
+            if (curr.high >= low) callback(curr.index, node.low)
+            curr = curr.next
           }
@@ -370,6 +391,2 @@ }
     },
-
-    get root() {
-      return tree.root
-    },
   }
@@ -376,0 +393,0 @@ }

dist/es/IntervalTree.d.ts

@@ -1,12 +0,1 @@
-declare type Color = 0 | 1 | 2
-interface TreeNode {
-  max: number
-  low: number
-  high: number
-  color: Color
-  parent: TreeNode
-  right: TreeNode
-  left: TreeNode
-  list: number[]
-}
 interface IIntervalTree {
@@ -21,5 +10,4 @@ insert(low: number, high: number, index: number): void
   size: number
-  root: TreeNode
 }
 declare const IntervalTree: () => IIntervalTree
 export default IntervalTree

dist/es/IntervalTree.js

@@ -6,14 +6,26 @@ const RED = 0
 const KEEP = 1
-const NOT_FOUND = 2
 
 const addInterval = (treeNode, high, index) => {
-  if (treeNode.list.length === 0) {
-    treeNode.list.push(index, high)
-    return true
+  let node = treeNode.list
+  let prevNode
+
+  while (node) {
+    if (node.index === index) return false
+    if (high > node.high) break
+    prevNode = node
+    node = node.next
   }
 
-  for (let i = 0; i < treeNode.list.length; i++)
-    if (treeNode.list[i] === index && i % 2 === 0) return false
-
-  treeNode.list.push(index, high)
+  if (!prevNode)
+    treeNode.list = {
+      index,
+      high,
+      next: node,
+    }
+  if (prevNode)
+    prevNode.next = {
+      index,
+      high,
+      next: prevNode.next,
+    }
   return true
@@ -23,11 +35,22 @@ }
 const removeInterval = (treeNode, index) => {
-  if (treeNode.list === void 0) return NOT_FOUND
+  let node = treeNode.list
 
-  for (let i = 0; i < treeNode.list.length; i++)
-    if (treeNode.list[i] === index && i % 2 === 0) {
-      treeNode.list.splice(i, 2)
-      break
+  if (node.index === index) {
+    if (node.next === null) return DELETE
+    treeNode.list = node.next
+    return KEEP
+  }
+
+  let prevNode = node
+  node = node.next
+
+  while (node !== null) {
+    if (node.index === index) {
+      prevNode.next = node.next
+      return KEEP
     }
 
-  return treeNode.list.length > 0 ? KEEP : DELETE
+    prevNode = node
+    node = node.next
+  }
 }
@@ -179,9 +202,3 @@
   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
-// }
+}
 
@@ -240,3 +257,3 @@ const fixInsert = (tree, z) => {
     // for our case so it's a solid O(1) alternative to
-    // the O(log n) searchNode()
+    // the O(log n) searchNode() in typical interval trees
     indexMap: {},
@@ -274,3 +291,7 @@ }
         right: NULL_NODE,
-        list: [index, high],
+        list: {
+          index,
+          high,
+          next: null,
+        },
       }
@@ -296,6 +317,6 @@
       const intervalResult = removeInterval(z, index)
-      if (intervalResult === NOT_FOUND) return
+      if (intervalResult === void 0) return
 
       if (intervalResult === KEEP) {
-        z.high = z.list[1]
+        z.high = z.list.high
         updateMax(z)
@@ -352,7 +373,7 @@ updateMaxUp(z)
         if (node.low <= high && node.high >= low) {
-          for (let i = 0, len = node.list.length; i < len; i++) {
-            const index = node.list[i++] // normally we'd include the high bound here, too, but since we
-            // don't need it in practice, it makes sense to just leave it out
+          let curr = node.list
 
-            if (node.list[i] >= low) callback(index, node.low)
+          while (curr !== null) {
+            if (curr.high >= low) callback(curr.index, node.low)
+            curr = curr.next
           }
@@ -366,6 +387,2 @@ }
     },
-
-    get root() {
-      return tree.root
-    },
   }
@@ -372,0 +389,0 @@ }

package.json

 {
   "name": "masonic",
-  "version": "2.1.4",
+  "version": "2.1.5",
   "homepage": "https://github.com/jaredLunde/masonic#readme",
@@ -94,5 +94,5 @@ "repository": "github:jaredLunde/masonic",
   "dependencies": {
-    "@essentials/memoize-one": "^1.0.1",
+    "@essentials/memoize-one": "^1.0.2",
     "@essentials/one-key-map": "^1.0.1",
-    "@react-hook/passive-layout-effect": "^1.0.2",
+    "@react-hook/passive-layout-effect": "^1.0.3",
     "@react-hook/window-scroll": "^1.0.6",
@@ -99,0 +99,0 @@ "@react-hook/window-size": "^1.0.10",

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

Lines of code

2546

increased by0.32%

Worsened metrics

Total package byte prevSize

114431

decreased by-0.53%

Dependency changes

• Updated@essentials/memoize-one@^1.0.2

• Updated@react-hook/passive-layout-effect@^1.0.3