inorder-tree-layout - npm Package Compare versions

Comparing version 0.0.2 to 0.0.3

inorder.js

@@ -6,3 +6,8 @@ "use strict"
 function rootInorder(n) {
-  return (bits.nextPow2(n+1)-1)>>>1
+  var ptree = (bits.nextPow2(n+1)>>>1) - 1
+  var f     = n - ptree
+  if(f >= ptree) {
+    return ptree
+  }
+  return (ptree>>>1)+f
 }
@@ -21,14 +26,26 @@ exports.root = rootInorder
 
-function leftMostAncestor(n, x) {
-  return x + 1 - (1<<heightInorder(n, x))
-}
-exports.lo = leftMostAncestor
-
-function rightMostAncestor(n, x) {
-  return Math.min(x + (1<<heightInorder(n,x)) - 1, n-1)
-}
-exports.hi = rightMostAncestor
-
+//This is really horrible because n is not necessarily a power of 2
+// If it was, we could just do:
+//
+//    hieght = bits.countTrailingZeros(~x)
+//
+// Instead, we need to do a more subtle case-by-case analysis of the node
+//  and its position in the tree
 function heightInorder(n, x) {
-  return bits.countTrailingZeros(~x)
+  var ptree = bits.nextPow2(n+1)>>>1
+  var f     = n - ptree + 1
+  var c     = f + bits.nextPow2(f) - 1
+  if(x < c) {
+    var h = bits.countTrailingZeros(~x)
+    if(x+1-(1<<h) > 2*f) {
+      h -= 1
+    }
+    return h
+  }
+  x -= f
+  var h = bits.countTrailingZeros(~x)
+  if(x === (1<<h)-1) {
+    return h+1
+  }
+  return h
 }
@@ -48,4 +65,18 @@ exports.height = heightInorder
 function parentInorder(n, x) {
-  var h = bits.countTrailingZeros(~x)
-  return (x & ~(1<<(h+1)) )^(1<<h)
+  var ptree = bits.nextPow2(n+1)>>>1
+  var f     = n - ptree + 1
+  var c     = f + bits.nextPow2(f) - 1
+  if(x < c) {
+    var h = bits.countTrailingZeros(~x)
+    var y = (x & ~(1<<(h+1)))^(1<<h)
+    if(y >= c) {
+      var e = bits.nextPow2(c+1) - c - 1
+      y -= e
+    }
+    return y
+  }
+  var y = x - f
+  var h = bits.countTrailingZeros(~y)
+  y = (y & ~(1<<(h+1)))^(1<<h)
+  return y + f
 }
@@ -55,3 +86,13 @@ exports.parent = parentInorder
 function leftInorder(n, x) {
-  return x-(1<<(bits.countTrailingZeros(~x)-1))
+  var ptree = bits.nextPow2(n+1)>>>1
+  var f     = n - ptree + 1
+  var c     = f + bits.nextPow2(f) - 1
+  if(x < c) {
+    var h = bits.countTrailingZeros(~x)
+    return x-(1<<(h-1))
+  } else if(x === c) {
+    return bits.nextPow2(f)-1
+  }
+  var h = bits.countTrailingZeros(~(x-f))
+  return x-(1<<(h-1))
 }
@@ -61,4 +102,14 @@ exports.left = leftInorder
 function rightInorder(n, x) {
-  return x+(1<<(bits.countTrailingZeros(~x)-1))
+  var ptree = bits.nextPow2(n+1)>>>1
+  var f     = n - ptree + 1
+  var c     = f + bits.nextPow2(f) - 1
+  if(x < c) {
+    var h = bits.countTrailingZeros(~x)
+    return x+(1<<(h-1))
+  }
+  var y = x - f
+  var h = bits.countTrailingZeros(~y)
+  y += (1<<(h-1))
+  return y + f
 }
 exports.right = rightInorder

package.json

 {
   "name": "inorder-tree-layout",
-  "version": "0.0.2",
+  "version": "0.0.3",
   "description": "Index calculations for inorder layout of balanced binary trees",
@@ -13,3 +13,4 @@ "main": "inorder.js",
   "devDependencies": {
-    "tap": "~0.4.1"
+    "tap": "~0.4.1",
+    "tree-layout-tester": "~0.0.1"
   },
@@ -16,0 +17,0 @@ "scripts": {

README.md

@@ -5,6 +5,39 @@ inorder-tree-layout
 
+Assumes that the tree is filled in level order, and laid out in memory via an inorder traversal.  For example:
+
+```
+The tree:
+
+          6
+        /   \
+       3     8
+      / \   / \
+     1   5 7   9
+    / \  |
+   0   2 4
+
+Maps to:
+
+[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
+```
+
 ## Install
 
     npm install inorder-tree-layout
+    
+## Example
 
+Given the tree from the intro, let's illustrate some queries:
+
+```javascript
+var layout = require("inorder-tree-layout")
+
+console.log(layout.left(10, 3))     //Prints:  1
+
+console.log(layout.parent(10, 7))   //Prints:  8
+
+console.log(layout.height(10, 9))   //Prints:  0
+
+```
+
 ## API
@@ -48,9 +81,4 @@
 
-### `layout.lo(n, x)`
-Returns the left-most ancestor of `x`
 
-### `layout.hi(n, x)`
-Returns the right-most ancestor of `x`
-
 # Credits
 (c) 2013 Mikola Lysenko. MIT License

test/test.js

 var layout = require("../inorder")
+  , layoutTester = require("tree-layout-tester")
+  , bits = require("bit-twiddle")
 
-
 require("tap").test("inorder-tree-layout", function(t) {
 
-  //Simple tree data structure
-  function T(v,l,r) {
-    return {
-        v: v
-      , left: l || null
-      , right: r || null
-      , h: Math.max(l ? l.h : -1, r ? r.h : -1) + 1
-      , n: (l ? l.n : 0) + (r ? r.n : 0) + 1
-    }
-  }
-  
-  //Do inorder traversal
-  function testTree(root) {
-    var n = root.n
-    t.equals(layout.root(n), root.v)
-    var ptr = layout.begin(n)
-    
-    function leftAncestor(x) {
-      if(x.left) {
-        return leftAncestor(x.left)
-      }
-      return x.v
-    }
-    
-    function rightAncestor(x) {
-      if(x.right) {
-        return rightAncestor(x.right)
-      }
-      return x.v
-    }
-    
-    function visit(node, parent) {
-      t.equals(layout.height(n, node.v), node.h)
-      if(parent) {
-        t.equals(layout.parent(n, node.v), parent.v)
-      }
-      if(node.left) {
-        t.equals(layout.left(n, node.v), node.left.v)
-        visit(node.left, node)
-      }
-      t.equals(ptr, node.v)
-      ptr = layout.next(n, ptr)
-      if(node.right) {
-        t.equals(layout.right(n, node.v), node.right.v)
-        visit(node.right, node)
-      }
-      t.equals(layout.lo(n, node.v), leftAncestor(node))
-      t.equals(layout.hi(n, node.v), rightAncestor(node))
-    }
-    
-    visit(root, null)
-    t.equals(layout.end(n), ptr)
-    
-    //Do a reverse traversal
-    function rvisit(node) {
-      if(node.right) {
-        rvisit(node.right)
-      }
-      ptr = layout.prev(n, ptr)
-      t.equals(ptr, node.v)
-      if(node.left) {
-        rvisit(node.left)
-      }
-    }
-    rvisit(root)
-    t.equals(layout.begin(n), ptr)
-  }
-  
+  var T = layoutTester.T
+    , testTree = layoutTester.bind({}, t, layout)
+
+  testTree(T(0))
+  testTree(T(1, T(0)))
+  testTree(T(1, T(0), T(2)))
+  testTree(T(2, T(1, T(0)), T(3)))
+  testTree(T(3, T(1, T(0), T(2)), T(4)))
+  testTree(T(3, T(1, T(0), T(2)), T(5, T(4))))
   testTree(T(3, T(1, T(0), T(2)), T(5, T(4), T(6))))
-  testTree(T(1, T(0), T(2)))
-  testTree(T(0))
-  testTree(T(1, T(0), null))
+  testTree(T(4, T(2, T(1, T(0)), T(3)), T(6, T(5), T(7))))
+  testTree(T(5, T(3, T(1, T(0), T(2)), T(4)), T(7, T(6), T(8))))
+  testTree(T(6, T(3, T(1, T(0), T(2)), T(5, T(4))), T(8, T(7), T(9))))
   
   t.end()
 })

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

5715

increased by11.14%

Lines of code

116

increased by1.75%

Number of lines in readme file

83

increased by50.91%

Worsened metrics

Dev dependency count

2

increased by100%

No dependency changes