require "digest"    # for hash checksum digest function SHA256
require "pp"        # for pp => pretty printer

$depthLevel = 0

def calc_hash( first, second )
  b1 = [first].pack('H*')
  firstreverse = b1.reverse()
  b2 = [second].pack('H*')
  secondreverse = b2.reverse()
  sha = Digest::SHA256.new
  d1 = Digest::SHA256.digest(firstreverse+secondreverse)
  d2 = Digest::SHA256.digest(d1)
  d3 = d2.reverse.unpack('H*').join
  return d3
end

def compute_merkletree_hash( hashes )
  if hashes.empty?
    return "0"   ## return null hash (fix: what's the (proper) null hash?)
  elsif hashes.size == 1
    return hashes[0]
  else
    ## while there's more than one hash in the list, keep looping...
    while hashes.size > 1
      puts "Number of Branches at Depth #{$depthLevel} is #{hashes.size}"
      puts ""

      # if number of hashes is odd e.g. 3,5,7,etc., duplicate last hash in list
      if hashes.size % 2 != 0 then
        puts "Unbalanced Branch #{hashes.size} is self-hashed"
        hashes << hashes[-1] 
      end

      i = 1
      ## new hash list
      new_hashes = []
      ## loop through hashes two at a time
      hashes.each_slice(2) do |slice|
        ## join both hashes slice[0]+slice[1] together
        puts "Branch #{i} is #{slice[0]}"
        i += 1
        puts "Branch #{i} is #{slice[1]}"
        i += 1
        hash = calc_hash( slice[0], slice[1] )
        puts "Branch hash is #{hash}"
        puts ""
        new_hashes << hash
      end
      hashes = new_hashes
      puts "Completed Depth #{$depthLevel}"
      puts "#################################################################################"
      $depthLevel -= 1

      ## debug output
      #puts "current merkle hash list (#{hashes.size}):"
      #pp hashes
    end
    ### finally we end up with a single hash
    hashes[0]
   end
end # method compute_merkletree_hash


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

depthgauge = hashes.length
while( depthgauge > 0)
  $depthLevel = $depthLevel + 1
  depthgauge = depthgauge / 2
  depthgauge = depthgauge.floor
end
#depthLevel = depthLevel + 1

#print("depthLevel is: #{$depthLevel}")
hash = compute_merkletree_hash( hashes )

puts ""
puts "FINAL MERKLE ROOT AT DEPTH 0:"
puts ""
puts hash
puts ""