Imperative style pseudo-code for the Transpose Merkle Tree construction.

imperative pseudo-code.md

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