#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>
#include <x86intrin.h>
#include <iterator>



std::vector<int> arr;
int n2,n1;

void reset(int n,int k){//Сбросить, всего элементв и пересекающихся
   n1=n-k;
   n2=n;
   arr.resize(n*2-k);
   for (int i=0;i<arr.size();i++)
      arr[i]=i;
   std::default_random_engine  g(_rdtsc());
   shuffle(arr.begin(),arr.end(),g);
}

void prn_a(){  //Начепятать в виде массивов
   printf("\n1: ");
   for (int i=0;i<n1;i++)
      printf("%2d ",arr[i]);
   printf("\n=: ");
   for (int i=n1;i<n2;i++)
      printf("%2d ",arr[i]);
   printf("\n2: ");
   for (int i=n2;i<arr.size();i++)
      printf("%2d ",arr[i]);

}

double test_1(int k=3){//Стандартный std::set
   uint64_t t=0;
   uint64_t t1,t2;
   std::set<int> c;
   std::set<int> a(arr.data()+0,arr.data()+n2),b(arr.data()+n1,arr.data()+arr.size());
   for (int o=0;o<k;o++){
      //printf("\n1: ");
      // for (auto i:a)
      //    printf("%2d ",i);
      //printf("\n2: ");
      //for (auto i:b)
      //   printf("%2d ",i);
      c.clear();
      t1=_rdtsc();
      set_intersection(a.begin(),a.end(), b.begin(),b.end(), std::inserter(c,c.begin()));
      t2=_rdtsc();
      if (o) t+=(t2-t1);
      if (c.size()!=n2-n1)
         printf("\nerr in &");

      // printf("\n&: ");
      // for (auto i:c)
      //   printf("%2d ",i);
      c.clear();
      t1=_rdtsc();
      set_union(a.begin(),a.end(), b.begin(),b.end(), std::inserter(c,c.begin()));
      t2=_rdtsc();
      if (o) t+=(t2-t1);
      if (c.size()!=arr.size())
         printf("\nerr in |");
      //printf("\n|: ");
      //for (auto i:c)
      //  printf("%2d ",i);

   }
   return double(t)/(k-1)*2.4e-6;
}
double test_3(int k=3){//Стандартный std::set
   uint64_t t=0;
   uint64_t t1,t2;
   std::set<int> c;
   std::set<int> a(arr.data()+0,arr.data()+n2),b(arr.data()+n1,arr.data()+arr.size());
   for (int o=0;o<k;o++){
      //printf("\n1: ");
      // for (auto i:a)
      //    printf("%2d ",i);
      //printf("\n2: ");
      //for (auto i:b)
      //   printf("%2d ",i);
      c.clear();
      t1=_rdtsc();
      {
         std::vector<int> d;
         set_intersection(a.begin(),a.end(), b.begin(),b.end(), std::back_inserter(d));
         c.insert(d.begin(),d.end());}
      t2=_rdtsc();
      if (o) t+=(t2-t1);
      if (c.size()!=n2-n1)
         printf("\nerr in &");

      // printf("\n&: ");
      // for (auto i:c)
      //   printf("%2d ",i);
      c.clear();
      t1=_rdtsc();
      {
         std::vector<int> d;
         set_union(a.begin(),a.end(), b.begin(),b.end(), std::back_inserter(d));
         c.insert(d.begin(),d.end());
      }
      t2=_rdtsc();
      if (o) t+=(t2-t1);
      if (c.size()!=arr.size())
         printf("\nerr in |");
      //printf("\n|: ");
      //for (auto i:c)
      //  printf("%2d ",i);

   }
   return double(t)/(k-1)*2.4e-6;
}


template<typename T>
struct my_tree{
   struct node{
      node *up;//Верхушка
      node *le,*ri;//Ветки
      T zn;
      static node* __(T* a,T* b){
         if (a==b)
            return nullptr;
         node* res=new node;
         T* m=a+(b-a)/2;
         res->zn=*m;
         res->le=__(a,m);
         res->ri=__(m+1,b);
         if (res->le)
            res->le->up=res;
         if (res->ri)
            res->ri->up=res;
         return res;
      }
      node* next(){
         node* h;
         if (ri) {
            h=ri;
            while (h->le) h=h->le;
            return h;
         }else if (up){
            h=up;
            while (h and h->up and h->zn<zn)
               h=h->up;
            return (h->zn<zn)?nullptr:h;
         }else return nullptr;
      }

      int size(){
         return 1+(le?le->size():0)+(ri?ri->size():0);
      }
      void prn(){
         if (le) {
            //            printf("(");
            le->prn();
            //            printf(")");
         }
         node* ne=next();
         printf("%d",zn);
         // if (ne)
         //    printf("->%d",ne->zn);
         printf(" ");
         if (ri){
            //            printf("{");
            ri->prn();
            //            printf("}");
         }
      }
   };
   node* core;

   my_tree():core(nullptr){}
   my_tree(T* i1,T* i2){
      add(i1,i2);
   }
   void add(T* i1,T* i2){ //Я отсортирую, и потому дерево будет сбалансированное
      core=nullptr;
      std::vector<T> arr(i1,i2);
      sort(arr.begin(),arr.end());
      core=node::__(&*arr.begin(),&*arr.end());
      core->up=nullptr;
   }
   node* begin(){
      node* h=core;
      while (h and h->le) h=h->le;
      return h;
   }
   node* end(){
      node* h=core;
      while (h and h->ri) h=h->ri;
      return h;
   }
   void clear(){
      core=nullptr;//Освобождение памяти не нужно
   }
   int size(){ //Это же лишь тест
      if (core)
         return core->size();
      else
         return 0;
   }
   void prn(){
      printf("\n[ ");
      if (core)
         core->prn();
      printf("]");
   }
   void _intersection( my_tree<T>& a, my_tree<T>& b){
      node *a1=a.begin();
      node *a2=b.begin();
      std::vector<T> c;
      while (a1 and a2){
         //++t;
         // printf("\n a1: %2d  a2: %2d",a1->zn,a2->zn);
         if (a1->zn<a2->zn)
            a1=a1->next();
         else if (a1->zn>a2->zn)
            a2=a2->next();
         else {
            c.push_back(a1->zn);
            //printf(" %d ",a1->zn);
            a1=a1->next();
            a2=a2->next();
         }

         // if (t>10)break;

      }
      //      printf("{");
      //      for (auto i:c)
      //         printf(" %d ",i);
      //      printf("}");
      core=node::__(&*c.begin(),&*c.end());
      core->up=nullptr;

   }
   void _union( my_tree<T>& a, my_tree<T>& b){
      node *a1=a.begin();
      node *a2=b.begin();
      std::vector<T> c;
      while (a1 and a2){
         //++t;
         // printf("\n a1: %2d  a2: %2d",a1->zn,a2->zn);
         if (a1->zn<a2->zn){
            c.push_back(a1->zn);
            a1=a1->next();}
         else if (a1->zn>a2->zn){
            c.push_back(a2->zn);
            a2=a2->next();}
         else {
            c.push_back(a2->zn);
            //printf(" %d ",a1->zn);
            a1=a1->next();
            a2=a2->next();
         }

         // if (t>10)break;

      }
      while (a1){
         c.push_back(a1->zn);
         a1=a1->next();
      }
      while (a2){
         c.push_back(a2->zn);
         a2=a2->next();
      }
      //      printf("{");
      //      for (auto i:c)
      //         printf(" %d ",i);
      //      printf("}");
      core=node::__(&*c.begin(),&*c.end());
      core->up=nullptr;

   }
};

double test_2(int k=3){
   uint64_t t=0;
   uint64_t t1,t2;
   //
   my_tree<int> c;
   my_tree<int> a(arr.data()+0,arr.data()+n2),b(arr.data()+n1,arr.data()+arr.size());
   //a.prn();
   //b.prn();
   for (int o=0;o<k;o++){
      //printf("\n1: ");
      // for (auto i:a)
      //    printf("%2d ",i);
      //printf("\n2: ");
      //for (auto i:b)
      //   printf("%2d ",i);
      c.clear();
      t1=_rdtsc();
      c._intersection(a,b);
      t2=_rdtsc();
      //c.prn();
      if (o) t+=(t2-t1);
      if (c.size()!=n2-n1)
         printf("\nerr in &");

      // printf("\n&: ");
      // for (auto i:c)
      //   printf("%2d ",i);
      c.clear();
      t1=_rdtsc();
      c._union(a,b);
      t2=_rdtsc();
      //c.prn();
      if (o) t+=(t2-t1);
      if (c.size()!=arr.size())
         printf("\nerr in |");
      //printf("\n|: ");
      //for (auto i:c)
      //  printf("%2d ",i);

   }
   return double(t)/(k-1)*2.4e-6;
}

void te(double (*fun)(int) ,int i){

   reset(2*i,i);
   double t=fun(2),s=1e3*t/i,s2=s/log(i)*4;
   printf("\n%7d : %-12.3f n: %-5.2f   nlog: %-5.2f", i,t,s,s2);
}

int main()
{
   reset(6,2);
   prn_a();
   test_2(2);

   printf("\n\n my_tree");
   for (int i: {10, 31, 100, 316, 1000, 3162, 10000, 31622, 100000/*, 316227*/})
      te(test_2,i);
   printf("\n\n std::set");
   for (int i: {10, 31, 100, 316, 1000, 3162, 10000, 31622, 100000/*, 316227*/})
      te(test_1,i);
   printf("\n\n std::set with vector");
   for (int i: {10, 31, 100, 316, 1000, 3162, 10000, 31622, 100000/*, 316227*/})
      te(test_3,i);


}