#include <iostream>
#include <chrono>
#include "Key.h"
#include <unordered_map>
#include <vector>
//#include <utility>

using namespace std;

namespace std
{
  template<>
  struct hash<Key>{
    size_t operator()(const Key & k) const
    {
      size_t b{16777619};
      for(int i = 0; i < C; i++)
	{
	  b =2166136261 *b^(k.digit[i]);
	}
      return b;
    }
  };
}

int
main(int argc, char* argv[])
{
	unsigned char buffer[C+1];     // temporary string buffer
	Key encrypted;                 // the encrypted password
	Key zero = {{0}};              // the all zero key
	Key T[N];                      // the table T



	if (argc != 2)
	{
		cout << "Usage:" << endl << argv[0] << " password < rand8.txt" << endl;

		return 1;
	}

	encrypted = KEYinit((unsigned char *) argv[1]);

	// read in table T
	for (int i{0}; i < N; ++i)
	{
		scanf("%s", buffer);
		T[i] = KEYinit(buffer);
	}

	auto begin = chrono::high_resolution_clock::now();

	Key half_it{{0}};   // Create a Key iterator with value 0
	half_it++; // add 1 to the iterator
	for (int i = 0; i <= N/2; ++i) {  // for (Amount of bits of the password /2)
		half_it = half_it + half_it;
	}

	unordered_map<Key, vector<Key>> table;  // Create the map to save "low" values inside

	Key low{{0}};
	do {
		table[encrypted - KEYsubsetsum(low, T)].push_back(low);  // put low in the table
		++low;
	} while(low <= half_it);

	Key high{{0}};  // Kind of a Key iterator for the high part
	do {
		unordered_map<Key, vector<Key>>::iterator it = table.find(KEYsubsetsum(high, T));  // Create a iterator, pointing to the position of higherhalf
		if (it != table.end()) {  // If the iterator is in the end there wasn't a match and it's not a password.
			for (Key candidate : it->second) { //If we are here we have found some password(s). So lets output all the passwords in the vector
				cout << high + candidate << endl;
			}
		}
		high = high + half_it;
	} while (high != zero);


	auto end = chrono::high_resolution_clock::now();
	cout << "Decryption took "
	     << std::chrono::duration_cast<chrono::seconds>(end - begin).count()
	     << " seconds." << endl;

	return 0;
}