#include <iostream>
#include <chrono>
#include <unordered_set>
#include <random>
#include <vector>
#include <iomanip>
#include "hash_wrappers.h"
#include "cpu_and_wall_time.h"
#include "cpu_bench.hpp"
#include <thread>

using namespace std;



mutex mtx;

//--------------Генерация множеств-------------------//

void lcg(vector<unsigned int>& r, int seed, int size, unsigned long a, unsigned long c, unsigned long m){
  if (size == 1){
    r.push_back((a*seed+c)%m);
    return;
  }
  for(int i = 0; i < size; ++i){
    r.push_back(0);
  }
  r[0] = seed;
  for(int i = 1; i < size; ++i){
    r[i] = uint32_t((a*r[i-1]+c)%m);
  }
  r.erase(r.begin());
}



void generate_v3_0(int seed, long sizeA, long sizeB, long sizeInter, vector<unsigned int> & a, vector<unsigned int>& b) {
//hardcoded consts for lcg generator
//a = 50001
//c = 49999
//m = 2500000000


lcg(a, seed, sizeA+1, 50001, 49999, 2500000000);
(sizeA!=sizeInter)?lcg(b, a[sizeA-sizeInter-1], sizeB+1, 50001, 49999, 2500000000):lcg(b, seed, sizeB+1, 50001, 49999, 2500000000);

std::shuffle(a.begin(), a.end(), std::default_random_engine(seed+1));
std::shuffle(b.begin(), b.end(), std::default_random_engine(seed+2));
}















//------------ Хешевое пересечение--------------//
class Hasher
{
public:
  uint32_t operator() (uint32_t const& key) const
  {
      hfl::FarmHash64Wrapper wrap;
      uint32_t hash = wrap(key);
      return hash;
  }
};

class HasherMUR
{
public:
  uint32_t operator() (uint32_t const& key) const
  {
      hfl::MurmurHash64AWrapper wrap;
      uint32_t hash = wrap(key);
      return hash;
  }
};

class HasherCITY
{
public:
  uint32_t operator() (uint32_t const& key) const
  {
      hfl::CityHash64Wrapper wrap;
      uint32_t hash = wrap(key);
      return hash;
  }
};

void unordered_intersectionSONS(unordered_set<uint32_t, Hasher> &A_hashed, vector<uint32_t> &B, vector<uint32_t> &C, vector<uint32_t>::iterator b_begin, vector<uint32_t>::iterator b_end){

    vector<uint32_t>::iterator bIt = b_begin;

  while(bIt != b_end){
    if(A_hashed.count(*bIt) >0){
      mtx.lock();
      C.push_back(*bIt);
      mtx.unlock();
    }
    ++bIt;
  }
}


void unordered_intersectionFATHER(unordered_set<uint32_t, Hasher> &A_hashed, vector<uint32_t> &B, vector<uint32_t> &C){
  vector<uint32_t>::iterator b_mid = B.begin() + B.size()/2;

  std::thread threadStart(unordered_intersectionSONS, ref(A_hashed), ref(B), ref(C), B.begin(), b_mid);
  std::thread threadEnd(unordered_intersectionSONS, ref(A_hashed), ref(B), ref(C), b_mid, B.end());
  threadStart.join();
  threadEnd.join();

}

void unordered_intersection(unordered_set<uint32_t, HasherCITY> &A_hashed, vector<uint32_t> &B, vector<uint32_t> &C){


  vector<uint32_t>::iterator bIt = B.begin();

  while(bIt != B.end()){

    //(A_hashed.find(*bIt) != A_hashed.end())?C.push_back(*bIt):void();


    if(A_hashed.count(*bIt) >0){
      C.push_back(*bIt);
    }

    ++bIt;
  }

}

void unordered_intersection(unordered_set<uint32_t, HasherMUR> &A_hashed, vector<uint32_t> &B, vector<uint32_t> &C){


  vector<uint32_t>::iterator bIt = B.begin();

  while(bIt != B.end()){

    //(A_hashed.find(*bIt) != A_hashed.end())?C.push_back(*bIt):void();


    if(A_hashed.count(*bIt) >0){
      C.push_back(*bIt);
    }

    ++bIt;
  }

}


int main(int argc, char* argv[]) {


  int A = 100000;
  int B = 100000;
  int inter = 10000;

  if (argc>1){
    A = stoi(argv[1]);
    B = stoi(argv[2]);
    inter = stoi(argv[3]);
  }

  vector<uint32_t> a;
  vector<uint32_t> b;
  vector<uint32_t> res;


  generate_v3_0(14, A, B, inter, a, b);
  cout << "generated\n";


  //cpu_times times_preprocess;
  //cpu_times times_done;

  //cpu_timer timer;
  auto start_wall = std::chrono::steady_clock::now();
  auto start_time = getCPUTime();

  unordered_set<uint32_t, HasherMUR> A_hashed(a.begin(), a.end());

  //times_preprocess = timer.elapsed();

  auto preprocess_time = getCPUTime();
  auto preprocess_wall = std::chrono::steady_clock::now();

  unordered_intersection(A_hashed, b, res);

  //times_done = timer.elapsed();



  auto end_time = getCPUTime();
  auto end_wall = std::chrono::steady_clock::now();

  auto elapsedTime = std::chrono::duration_cast<std::chrono::microseconds>(end_wall - start_wall);
  auto elapsedPreproc = std::chrono::duration_cast<std::chrono::microseconds>(preprocess_wall - start_wall);
  cout << "Intersection size: " << res.size() << endl; // ' ' << v_intersection.size() << endl;
  cout << "Union size: " << A + B - inter << endl;
  cout << "A: " << a.size() << " B: " << b.size() << endl;

  //std::cout << std::fixed << std::showpoint;
  //cout << "\nCPU time: " << setprecision(15) << end_time - start_time;
  //cout << "\nCPU preprocess time: " << setprecision(15) << preprocess_time - start_time<< endl;

  //cout << setprecision(15) << end_time << endl;
  //cout << setprecision(15) << start_time << endl;
  fprintf( stderr, "\nCPU time:%lf\n", (end_time - start_time) );
  fprintf( stderr, "CPU preprocess time:%lf\n", (preprocess_time - start_time) );
  fprintf( stderr, "\nWall time:%lf\n", elapsedTime.count()/1000000.0);
  fprintf( stderr, "Wall preprocess time:%lf\n", elapsedPreproc.count()/1000000.0);




  //cout << "\nWALL time: " << setprecision(15) << elapsedTime.count()/1000000 << endl;
  //cout << "\nWALL preprocess time: " << setprecision(15) << elapsedPreproc.count()/100000 << endl;

 fprintf( stderr, "%lf ", (end_time - start_time) );
 fprintf( stderr, "%lf ",  (preprocess_time - start_time));
 fprintf( stderr, "%lf ", elapsedTime.count()/1000000.0);
 fprintf( stderr, "%lf ",  elapsedPreproc.count()/1000000.0);

}