@chainsafe/persistent-merkle-tree - npm Package Compare versions

Comparing version 0.1.3 to 0.2.0

CHANGELOG.md

@@ -0,1 +1,11 @@
+## 0.2.0 (2020-07-27)
+
+## Features
+
+* Add iterateNodestDepth ([24ca18](https://github.com/persistent-merkle-tree/commit/24ca18))
+
+## BREAKING CHANGES
+
+* Rearrange params, depth first where appropriate ([24ca18](https://github.com/persistent-merkle-tree/commit/24ca18))
+
 ## 0.1.3 (2020-06-07)
@@ -2,0 +12,0 @@

lib/gindex.d.ts

 export declare type Gindex = bigint;
 export declare type GindexBitstring = string;
 export declare function bitIndexBigInt(v: bigint): number;
-export declare function toGindex(index: bigint, depth: number): Gindex;
-export declare function toGindexBitstring(index: bigint, depth: number): GindexBitstring;
+export declare function toGindex(depth: number, index: bigint): Gindex;
+export declare function toGindexBitstring(depth: number, index: bigint): GindexBitstring;
 export declare function countToDepth(count: bigint): number;
@@ -10,7 +10,7 @@ /**
  */
-export declare function iterateAtDepth(startIndex: bigint, count: bigint, depth: number): Iterable<Gindex>;
-export interface GindexIterator extends Iterable<number> {
+export declare function iterateAtDepth(depth: number, startIndex: bigint, count: bigint): Iterable<Gindex>;
+export declare type Bit = 0 | 1;
+export interface GindexIterator extends Iterable<Bit> {
     remainingBitLength(): number;
-    totalBitLength(): number;
 }
-export declare function gindexIterator(gindex: Gindex): GindexIterator;
+export declare function gindexIterator(gindex: Gindex | GindexBitstring): GindexIterator;

lib/gindex.js

@@ -7,3 +7,3 @@ "use strict";
 exports.bitIndexBigInt = bitIndexBigInt;
-function toGindex(index, depth) {
+function toGindex(depth, index) {
     const anchor = BigInt(1) << BigInt(depth);
@@ -16,3 +16,3 @@ if (index >= anchor) {
 exports.toGindex = toGindex;
-function toGindexBitstring(index, depth) {
+function toGindexBitstring(depth, index) {
     const str = index ? index.toString(2) : '';
@@ -39,3 +39,3 @@ if (str.length > depth) {
  */
-function iterateAtDepth(startIndex, count, depth) {
+function iterateAtDepth(depth, startIndex, count) {
     const anchor = BigInt(1) << BigInt(depth);
@@ -45,3 +45,3 @@ if (startIndex + count >= anchor) {
     }
-    let i = toGindex(startIndex, depth);
+    let i = toGindex(depth, startIndex);
     const last = i + count;
@@ -68,6 +68,15 @@ return {
 function gindexIterator(gindex) {
-    if (gindex < 1) {
-        throw new Error(ERR_INVALID_GINDEX);
+    let bitstring;
+    if (typeof gindex === "string") {
+        if (!gindex.length) {
+            throw new Error(ERR_INVALID_GINDEX);
+        }
+        bitstring = gindex;
     }
-    const bitstring = gindex.toString(2);
+    else {
+        if (gindex < 1) {
+            throw new Error(ERR_INVALID_GINDEX);
+        }
+        bitstring = gindex.toString(2);
+    }
     let i = 1;
@@ -86,5 +95,2 @@ const next = () => {
         },
-        totalBitLength() {
-            return bitstring.length;
-        },
         remainingBitLength() {
@@ -91,0 +97,0 @@ return bitstring.length - i;

lib/tree.d.ts

@@ -20,2 +20,9 @@ import { Gindex } from "./gindex";
     getSingleProof(index: Gindex): Uint8Array[];
+    /**
+     * Fast read-only iteration
+     * In-order traversal of nodes at `depth`
+     * starting from the `startIndex`-indexed node
+     * iterating through `count` nodes
+     */
+    iterateNodesAtDepth(depth: number, startIndex: number, count: number): IterableIterator<Node>;
 }

lib/tree.js

@@ -6,3 +6,5 @@ "use strict";
 const zeroNode_1 = require("./zeroNode");
-const ERR_INVALID_TREE = "Invalid tree";
+const ERR_INVALID_TREE = "Invalid tree operation";
+const ERR_PARAM_LT_ZERO = "Param must be >= 0";
+const ERR_COUNT_GT_DEPTH = "Count extends beyond depth limit";
 class Tree {
@@ -110,3 +112,79 @@ constructor(node, hook) {
     }
+    /**
+     * Fast read-only iteration
+     * In-order traversal of nodes at `depth`
+     * starting from the `startIndex`-indexed node
+     * iterating through `count` nodes
+     */
+    *iterateNodesAtDepth(depth, startIndex, count) {
+        // Strategy:
+        // First nagivate to the starting Gindex node,
+        // At each level record the tuple (current node, the navigation direction) in a list (Left=0, Right=1)
+        // Once we reach the starting Gindex node, the list will be length == depth
+        // Begin emitting nodes: Outer loop:
+        //   Yield the current node
+        //   Inner loop
+        //     pop off the end of the list
+        //     If its (N, Left) (we've nav'd the left subtree, but not the right subtree)
+        //       push (N, Right) and set set node as the n.right
+        //       push (N, Left) and set node as n.left until list length == depth
+        //   Inner loop until the list length == depth
+        // Outer loop until the list is empty or the yield count == count
+        if (startIndex < 0 || count < 0 || depth < 0) {
+            throw new Error(ERR_PARAM_LT_ZERO);
+        }
+        if ((BigInt(1) << BigInt(depth)) < startIndex + count) {
+            throw new Error(ERR_COUNT_GT_DEPTH);
+        }
+        if (count === 0) {
+            return;
+        }
+        if (depth === 0) {
+            yield this.rootNode;
+            return;
+        }
+        let node = this.rootNode;
+        let currCount = 0;
+        const startGindex = gindex_1.toGindexBitstring(depth, BigInt(startIndex));
+        const nav = [];
+        for (const i of gindex_1.gindexIterator(startGindex)) {
+            nav.push([node, i]);
+            if (i) {
+                if (node.isLeaf())
+                    throw new Error(ERR_INVALID_TREE);
+                node = node.right;
+            }
+            else {
+                if (node.isLeaf())
+                    throw new Error(ERR_INVALID_TREE);
+                node = node.left;
+            }
+        }
+        while (nav.length && currCount < count) {
+            yield node;
+            currCount++;
+            if (currCount === count) {
+                return;
+            }
+            do {
+                const [parentNode, direction,] = nav.pop();
+                // if direction was left
+                if (!direction) {
+                    // now navigate right
+                    nav.push([parentNode, 1]);
+                    if (parentNode.isLeaf())
+                        throw new Error(ERR_INVALID_TREE);
+                    node = parentNode.right;
+                    // and then left as far as possible
+                    while (nav.length !== depth) {
+                        nav.push([node, 0]);
+                        if (node.isLeaf())
+                            throw new Error(ERR_INVALID_TREE);
+                        node = node.left;
+                    }
+                }
+            } while (nav.length && nav.length !== depth);
+        }
+    }
 }
 exports.Tree = Tree;

package.json

 {
   "name": "@chainsafe/persistent-merkle-tree",
-  "version": "0.1.3",
+  "version": "0.2.0",
   "description": "Merkle tree implemented as a persistent datastructure",
@@ -5,0 +5,0 @@ "main": "lib/index.js",

README.md

 # Persistent Merkle Tree
 
+![ES Version](https://img.shields.io/badge/ES-2020-yellow)
+![Node Version](https://img.shields.io/badge/node-12.x-green)
+
 A binary merkle tree implemented as a [persistent data structure](https://en.wikipedia.org/wiki/Persistent_data_structure).
@@ -4,0 +7,0 @@

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

34884

increased by12.68%

Lines of code

555

increased by19.61%

Number of lines in readme file

104

increased by2.97%

No dependency changes