This is imperative style pseudo-code, written loosely on Java syntax. It uses mutable data-structures, and is a rough translation of the Haskell snippet (purely functional & hence immutable) provided at - https://gist.github.com/stoichammer/7735abcddec08614a0b46335fe94a65f
class MerkleNode {
String node;
String leftChild;
String rightChild;
MerkleNode(String n, String l, String r) {
//initialize
}
}
class HashCompute {
HashMap < Int, MerkleNode > prevNodeStateAtTreeHeight;
ArrayList < MerkleNode > subTreeToCommit;
}
public HashCompute pushHash(HashCompute hcompute, String nhash, String left, String right, Int ht, Int ind, Bool final)
{
MerkleNode prev = hcompute.prevNodeStateAtTreeHeight.get(ind);
if (prev.node != null) {
hcompute.subTreeToCommit.add(prev, left, right);
hcompute.subTreeToCommit.add(nhash, prev.leftChild, prev.rightChild);
hcompute.prevNodeStateAtTreeHeight.put(ind, null);
pushHash(hcompute, (hashPair pv nhash), prev, nhash, ht, (ind + 1), final);
} else {
hcompute.prevNodeStateAtTreeHeight.put(ind, MerkleNode(nhash, left, right));
if ht == ind {
hcompute.subTreeToCommit.add(nhash, left, right);
return hcompute;
}
else {
if (final == True) {
hcompute.subTreeToCommit.add(nhash, left, right);
pushHash(hcompute, (hashPair nhash nhash), nhash, nhash, ht, (ind + 1), final);
} else {
return hcompute;
}
}
}
}
** Note: **
Make sure the calling function recursively invokes pushHash
and when it returns a non-empty subTreeToCommit
, commit it to graph DB and subsequent calls to pushHash
are done with an empty subTreeToCommit