import hashlib
import codecs
from binascii import hexlify

Level = 0
DepthLevel = 0

# Recursive hash
def merkle(hashList, ):
    global DepthLevel
    #print("DepthLevel: ",DepthLevel)
    DepthLevel -= 1 #0 offset is root

    global Level
    Level = Level + 1
    if len(hashList) == 1:
        print()
        print("FINAL MERKLE ROOT AT DEPTH 0: \n")
        return hashList[0]
    newHashList = []
    #print("Number of Branches in Level", Level, "is", len(hashList))
    print("Number of Branches at Depth", DepthLevel, "is", len(hashList))
    print()
    
    # Process pairs. For odd length, last item is hashed with itself
    for i in range(0, len(hashList)-1, 2):
        print("Branch",i+1, "is", hashList[i])
        print("Branch",i+2, "is", hashList[i+1])
        print("Branch hash is", hash2(hashList[i], hashList[i+1]))
        print()
        newHashList.append(hash2(hashList[i], hashList[i+1]))
    if len(hashList) % 2 == 1: # odd, hash last item twice
        print("Branch", len(hashList), "is", hashList[len(hashList)-1])
        print("Unbalanced Branch",len(hashList),"is self-hashed to yield:", hash2(hashList[-1], hashList[-1]))
        newHashList.append(hash2(hashList[-1], hashList[-1]))
    print("Completed Depth", DepthLevel)
    print("#################################################################################")
    return merkle(newHashList)

def hash2(first, second):
    # Reverse inputs before and after hashing due to big-endian / little-endian nonsense
     firstreverse = codecs.decode(first,'hex')[::-1]
     secondreverse = codecs.decode(second, 'hex')[::-1]
     h = hashlib.sha256(hashlib.sha256(firstreverse+secondreverse).digest()).digest()
     return codecs.encode(h[::-1],'hex')

txHashes2 = [
    "b5f60977102f95a9ed855b61acec86e2e434248b38c5f263ccf708a302832f3c",
    "e6922d44c520c52dca2cd5300784af55944c11839684e5c1671d9b330f871f55",
    "a72ef0e0240fb592dd1d6ec3d1ab24890def0870f5c44d478f1feb1f87701e43",
    "51ef089bd2fc330cd02ee9d5a3cb5532ed48d8668ed78a92b84c8da97922975a",
    "ae22ea6889a5712eb2e13736ce4586afd310295c6ddbbc2b56b1305441017a70",
    "cfce9664889e17fa006cfa23dd82852a999f9a748478cf325e3791241dd27a50",
    "4db4ac98aa68d75dc3602f8f3b06157ac93485268df220cc6dc4aa39f6f9d7a9",
    "a0337aef8e3739e6b705c51202a9d58addc375e2830e3429727a461052279d46",
    "0dc7b3bf9b1a98859d694146a0acd5a988d4184ab9c048ea91d8be7fd1cd84e6",
    "72e15234eb42c9f4b650dec5727205dacbbcb039e8c22034b00bf805192abec7",
    "dca4db368d5241219a0f5f8c744c42293b9bc4959b99e4ed43abc075c284b78c",
    "a5e67793f9193a7b9192e4c3e7cd27268ef354b0513a9cd595c04778d3fa3eef",
    "4d53b64a343589f9b76643c80eacdd632cc50fcec6ece4dd7d3c0c65dba1d0f9",
    "3495a4fab0ff587f6050a22035e12253b250d088413dbd30b1cb44365b87bd86"
]

depthgauge = len(txHashes2)
DepthLevel = 0
#print(f"length of list is: {depthgauge}")
while( depthgauge > 0 ):
    DepthLevel += 1
    depthgauge = depthgauge / 2
    #print("after division: ",depthgauge)
    depthgauge = int(depthgauge)
    #print("after int: ",depthgauge)
DepthLevel += 1
#print(f"DepthLevel: {DepthLevel}")

print(merkle(txHashes2).decode())
print()