#include <iostream>
#include "cpu_bench.hpp"
#include "stdc++.h"
#include "set_generator.hpp"


using namespace std;
void split(vector<unsigned int>& s, vector<vector<unsigned int>>& sub, int n){
  vector<unsigned int>::iterator splitter = s.begin();
  while(s.end() >= splitter + n){
      sub.push_back(vector<unsigned int>(splitter ,splitter + n));
      splitter += n;
  }
  if(s.end() - splitter > 0){
    sub.push_back(vector<unsigned int>(splitter, s.end()));
  }

}


void preprocessHash64(vector<unsigned int>::iterator s, vector<unsigned int>::iterator e, vector<vector<unsigned int>>& h_m, bitset<64>& bit){


  unordered_map<unsigned int, unsigned int> h;
  vector<unsigned int>::const_iterator i = s;
  int buf_h;


  while(i < e){
    buf_h = *i%64;
    bit[buf_h] = true;
    h[*i] = buf_h;
    h_m[buf_h].push_back(*i);
    ++i;
  }


}

void preprocessor64(vector<unsigned int>& s){
  sort(s.begin(), s.end());


}

void IntersectSmall64(bitset<64>& bA, vector<vector<unsigned int>>&v_mA, bitset<64>& bB, vector<vector<unsigned int>>&v_mB, vector<unsigned int>& res){
  bitset<64> bAnd = bA&bB;

for(int i = bAnd._Find_first(); i < bAnd.size(); i = bAnd._Find_next(i)){
    set_intersection(v_mA[i].begin(), v_mA[i].end(), v_mB[i].begin(), v_mB[i].end(), back_inserter(res));
}


}

void dk_intersection64(vector<unsigned int>& sA, vector<unsigned int>& sB,  vector<unsigned int>& result){
  int p,q;
  p = 0;
  q = 0;
  vector<vector<unsigned int>> h_rA;
  vector<vector<unsigned int>> h_rB;
  for (int i = 0; i < 64; ++i){
    h_rA.push_back(vector<unsigned int>());
    h_rB.push_back(vector<unsigned int>());
  }
  int leftoutA;
  int leftoutB;


  bitset<64> bit_A;
  bitset<64> bit_B;

  while(p < sA.size() && q < sB.size()){
      leftoutA = std::min(8, int(sA.size()-p));
      leftoutB = std::min(8, int(sB.size()-q));
      if (sA[p] > sB[q+leftoutB-1]){

        q += leftoutB;


      }
      else if(sA[p+leftoutA-1] < sB[q]){
        p += leftoutA;

      }
      else{

        preprocessHash64(sA.begin() + p, sA.begin()+p+leftoutA, h_rA, bit_A);
        preprocessHash64(sB.begin() + q, sB.begin()+q+leftoutB, h_rB, bit_B);
        IntersectSmall64(bit_A, h_rA, bit_B, h_rB, result);

        for(int i = 0; i <h_rA.size(); ++i){
          vector<unsigned int>().swap(h_rA[i]);
          vector<unsigned int>().swap(h_rB[i]);
        }
        bit_A.reset();
        bit_B.reset();


        if (sA[p+leftoutA-1] < sB[q+leftoutB-1]){
          p += leftoutA;

        }
        else{
          q += leftoutB;
        }
      }
  }


}


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";

  vector<vector<unsigned int>> subsetsA;
  vector<vector<unsigned int>> subsetsB;

  vector<bitset<64>> bitmasksA;
  vector<bitset<64>> bitmasksB;


  vector<vector<vector<unsigned int>>> h_rA;
  vector<vector<vector<unsigned int>>> h_rB;



  auto start_time = getCPUTime();

  preprocessor64(a);
  preprocessor64(b);

  dk_intersection64(a, b, res);


  auto end_time = getCPUTime();

  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;

  fprintf( stderr, "\nCPU time:%lf\n", (end_time - start_time) );
  fprintf( stderr, "%lf ", (end_time - start_time) )
}