#include <bitcoin/bitcoin.hpp>
// NOTES
// /usr/local/include/bitcoin/bitcoin/math/hash.hpp|51 col 34|
//   typedef std::vector<hash_digest> hash_list;
// bitcoin/math/hash.hpp|43 col 31|
//   typedef byte_array<hash_size> hash_digest;
// bitcoin/utility/data.hpp|36 col 7|
//   using byte_array = std::array<uint8_t, Size>;

bc::hash_digest create_merkle(bc::hash_list& merkle, int &DepthLevel)
{
	// 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 left in the list, keep on keepin' on...
	while (merkle.size() > 1)
	{
		bool uneven = false;
		std::cout << "Number of Branches at Depth " << DepthLevel << " is " << merkle.size() << std::endl;
		std::cout << std::endl;
		// If number of hashes is odd, balance the tree by duplicating the last hash in the list.
		uneven = (merkle.size() % 2 != 0);
		if (merkle.size() % 2 != 0)
			merkle.push_back(merkle.back());
		// List size is now even.  Let's make sure...
		assert(merkle.size() % 2 == 0);


		// New hash list.
		bc::hash_list new_merkle;
		// Loop through hashes 2 at a time.
		int counter = 1;
		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));
			std::cout << "Branch " << counter++ << " is " << bc::encode_hash(*it) << std::endl;
			std::cout << "Branch " << counter++ << " is " << bc::encode_hash(*(it+1)) << std::endl;
			// Hash both of the hashes.
			bc::hash_digest new_root = bc::bitcoin_hash(concat_data);
			std::cout << "Branch hash is " << bc::encode_hash(new_root)  << std::endl;
			// Add this to the new list.
			std::cout << std::endl;
			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_base16(hash) << std::endl;
		//std::cout << std::endl;
		// --------------------------------------------------
		std::cout << "Completed Depth " << DepthLevel << std::endl;
		DepthLevel--;
		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"),
	}};

	u_long size = tx_hashes.size();
	std::cout << "Size: " << size << std::endl;
	int DepthLevel = 0;

	while ( size > 0 )
	{
		DepthLevel++;
		size /= 2;
	}
	std::cout << "Size: " << size << std::endl;

	const bc::hash_digest merkle_root = create_merkle(tx_hashes, DepthLevel);

	std::cout << std::endl;
	std::cout << "FINAL MERKLE ROOT AT DEPTH " << DepthLevel << ": " << std::endl;
	std::cout << std::endl;
	std::cout << "Result: " << bc::encode_hash(merkle_root) << std::endl;
	//std::cout << "Result: " << bc::encode_base16(merkle_root) << std::endl;  //Antonopolous original code

	return 0;
}