Visualization of Satoshi's BuildMerkleTree for issue #4926

merkl.py

'''Visualization of Satoshi's BuildMerkleTree for issue #4926.

Usage: merkle.py <num>
'''
from __future__ import print_function, division
import itertools

def build_merkle_tree(num):
    '''Build a Merkle tree according to Satoshi'''
    vtx = [('%2i'%(x+1)) for x in range(num)]
    vMerkleTree = [(None,None,False,x) for x in vtx]
    nSize = len(vtx)
    j = 0
    levels = 1
    symid = ord('A')
    while nSize > 1:
        i = 0
        while i < nSize:
            i2 = min(i+1, nSize-1)
            mucheck = False
            if i2 == (i+1) and (i2+1) == nSize:
                mucheck = True
            vMerkleTree.append((vMerkleTree[j+i], vMerkleTree[j+i2], mucheck, ' '+chr(symid)))
            symid += 1
            i += 2

        j += nSize
        nSize = (nSize + 1)//2
        levels += 1

    return (vMerkleTree, levels)

def colorize(text, color):
    return ('\x1b[0;%im' % ([30,90][color//8]+color%8)) + text + '\x1b[0m'

def visualize_node(node):
    return colorize(node[3], [15,9][node[2]])

def render_merkle_tree(vMerkleTree, levels):
    if not vMerkleTree:
        return
    nodes = [vMerkleTree[-1]]
    total_width = width = (1<<(levels-1)) * 3
    while nodes and nodes[0] is not None:
        distance = ' ' * (width-2)
        s1 = [' '] * total_width
        for x in range(len(nodes)//2):
            s1[x*width*2 + (width*2 + width)//4+1] = '/'
            s1[x*width*2 + (width*2 + width*3)//4+1] = '\\'
        s1 = ''.join(s1)
        s2 = ' ' * (width//2)
        s2 += distance.join([visualize_node(c) for c in nodes])
        print(colorize(s1, 8))
        print(s2)
        nodes = list(itertools.chain.from_iterable(child[0:2] for child in nodes))
        width //= 2

if __name__ == '__main__':
    import sys
    (vMerkleTree,levels) = build_merkle_tree(int(sys.argv[1]))
    render_merkle_tree(vMerkleTree, levels)
    print()