#include <bitcoin/bitcoin.hpp>

// merkle.cpp
// antonopoulos - https://github.com/bitcoinbook/bitcoinbook/blob/develop/code/merkle.cpp
// g++ -g merkle.cpp -std=c++11 $(pkg-config --cflags --libs libbitcoin) && ./a.out

bc::hash_digest create_merkle(bc::hash_list& merkle)
{
    // Stop if hash list is empty.
    if (merkle.empty())
        return bc::null_hash;
    else if (merkle.size() == 1)
        return merkle[0];

    // While there is more than 1 hash in the list, keep looping...
    while (merkle.size() > 1)
    {
        // If number of hashes is odd, duplicate last hash in the list.
        if (merkle.size() % 2 != 0)
            merkle.push_back(merkle.back());
        // List size is now even.
        assert(merkle.size() % 2 == 0);

        // New hash list.
        bc::hash_list new_merkle;
        // Loop through hashes 2 at a time.
        for (auto it = merkle.begin(); it != merkle.end(); it += 2)
        {
            // Join both current hashes together (concatenate).
            bc::data_chunk concat_data(bc::hash_size * 2);
            auto concat = bc::serializer<
                decltype(concat_data.begin())>(concat_data.begin());
            concat.write_hash(*it);
            concat.write_hash(*(it + 1));
            // Hash both of the hashes.
            bc::hash_digest new_root = bc::bitcoin_hash(concat_data);
            // Add this to the new list.
            new_merkle.push_back(new_root);
        }
        // This is the new list.
        merkle = new_merkle;

        // DEBUG output -------------------------------------
        std::cout << "Current merkle hash list:" << std::endl;
        for (const auto& hash: merkle)
            std::cout << "  " << bc::encode_hash(hash) << std::endl;
        std::cout << std::endl;
        // --------------------------------------------------
    }
    // Finally we end up with a single item.
    return merkle[0];
}

int main()
{
    // Replace these hashes with ones from a block to reproduce the same merkle root.
    bc::hash_list tx_hashes{{
        bc::hash_literal("b5f60977102f95a9ed855b61acec86e2e434248b38c5f263ccf708a302832f3c"),
        bc::hash_literal("e6922d44c520c52dca2cd5300784af55944c11839684e5c1671d9b330f871f55"),
        bc::hash_literal("a72ef0e0240fb592dd1d6ec3d1ab24890def0870f5c44d478f1feb1f87701e43"),
        bc::hash_literal("51ef089bd2fc330cd02ee9d5a3cb5532ed48d8668ed78a92b84c8da97922975a"),
        bc::hash_literal("ae22ea6889a5712eb2e13736ce4586afd310295c6ddbbc2b56b1305441017a70"),
        bc::hash_literal("cfce9664889e17fa006cfa23dd82852a999f9a748478cf325e3791241dd27a50"),
        bc::hash_literal("4db4ac98aa68d75dc3602f8f3b06157ac93485268df220cc6dc4aa39f6f9d7a9"),
        bc::hash_literal("a0337aef8e3739e6b705c51202a9d58addc375e2830e3429727a461052279d46"),
        bc::hash_literal("0dc7b3bf9b1a98859d694146a0acd5a988d4184ab9c048ea91d8be7fd1cd84e6"),
        bc::hash_literal("72e15234eb42c9f4b650dec5727205dacbbcb039e8c22034b00bf805192abec7"),
        bc::hash_literal("dca4db368d5241219a0f5f8c744c42293b9bc4959b99e4ed43abc075c284b78c"),
        bc::hash_literal("a5e67793f9193a7b9192e4c3e7cd27268ef354b0513a9cd595c04778d3fa3eef"),
        bc::hash_literal("4d53b64a343589f9b76643c80eacdd632cc50fcec6ece4dd7d3c0c65dba1d0f9"),
        bc::hash_literal("3495a4fab0ff587f6050a22035e12253b250d088413dbd30b1cb44365b87bd86"),
    }};

    const bc::hash_digest merkle_root = create_merkle(tx_hashes);
    std::cout << "Result: " << bc::encode_hash(merkle_root) << std::endl;
	
    // std::cout << "----------------------------------------------------------------" << std::endl;
    // std::cout << "Test:   " << bc::encode_hash(  bc::hash_literal("b5f60977102f95a9ed855b61acec86e2e434248b38c5f263ccf708a302832f3c")) << std::endl;
    // std::cout << "Test 2: " << bc::encode_base16(bc::hash_literal("b5f60977102f95a9ed855b61acec86e2e434248b38c5f263ccf708a302832f3c")) << std::endl;
	
}