#include <iostream>
#include <unordered_map>
#include <time.h>
#include <wchar.h>
#include <chrono>
#include <thread>
#include <vector>
#include <array>
#include <stdlib.h>
#include <string.h>


using namespace std;

namespace me{

   using tint = unsigned long;//ideone жалуется на tint
   using nint = long long;

   template <typename K,typename T,typename _hash= std::hash<K>>
   struct unordered_map{
      tint *data;//Вся информация

      struct key{
         K first;
         T second;
         tint next;
      };
      key *pi;//Полезная информация
      tint clv=0;// количество

      tint buck;
      tint size;

      void resize(tint n){
         size=n;
         data=(decltype(data))realloc(data,n);
         pi=(key*)(nint((void*)data)+sizeof(tint)*buck)-1;

      }

      unordered_map(int a):buck(a),data(nullptr){
         //  data=malloc();
         resize(sizeof(tint)*buck+buck*sizeof(key)/2);
         for (tint i=0;i<buck;i++)
            ((tint*)data)[i]=0;
      }
      unordered_map():unordered_map(4){}



      tint hash(K& a)const{
         // return 0;
         return _hash()(a)%buck;
      }
      void insert(std::pair<K,T> a){

         if (size<sizeof(tint)*buck+sizeof(key)*(5+clv))
            resize(size*2);
         tint y=hash(a.first);
         //  wprintf(L"insert pair %f [hash=%d] %d ------------\n",*(float*)a.first.p,y,a.second);
         //   prn();
         tint* w=&data[y];
         //  wprintf(L"]]");
         //   wprintf(L":%d:",*w);
         while (*w){
            //pi[w]
            w=&pi[*w].next;
            //   wprintf(L":%d:",*w);
         }
         //    wprintf(L"[[===========\n");



         clv++;
         key* me=&pi[clv];
         me->first=a.first;
         me->second=a.second;
         me->next=0;
         *w=clv;

      }

      key* find(K a){
         tint y=hash(a);
         tint* w=&data[y];
         while (*w){
            //pi[w]
            if (pi[*w].first==a){
               return &pi[*w];
            }
            w=&pi[*w].next;
         }
         return nullptr;
      }


      ~unordered_map(){
         free(data);
      }




   };

   inline nint rdtsc()
   {
      static tint lo, hi;
      asm volatile("rdtsc\n"
                   : "=a"(lo), "=d"(hi));
      return ((nint)hi << 32) | lo;
   }

}

double hz;

void test(me::tint N,me::tint seed){

   wprintf(L"\n\n     N: %d    seed: %d\n",N,seed);
   using namespace me;
   tint c1,c2;
   nint t1,t2;
   struct mm{  //Какая-то временная структура
      int n;//а тут их количество
      float* p;//Вот тут лежат флоаты
      size_t operator()(const mm& a) const{
         size_t t=1231231;

         for (int i=0;i<a.n;i++)
            t^=std::hash<float>()(a.p[i])<<i;
         return t;
      };
      bool operator ==(const mm& a)const {
         if (a.n!=n)return false;
         for (int i=0;i<n;i++)
            if (a.p[i]!=p[i])
               return false;
         return true;

      }
   };



   std::vector<std::array<float,8>> ms{N};
   srand(seed);
   for (int i=0;i<N;i++){
      ms[i][0]=rand()%(N/2);
      for (int t=1;t<ms[i].size();t++)
         ms[i][t]=0;
   }

   std::vector<mm> arr{N};

   for (int i=0;i<N;i++){
      arr[i].n=8;
      arr[i].p=(decltype(arr[i].p))(&ms[i]);
   }


   double e1,m1,e2,m2;

   std::vector<tint> ind(N);//Здесь индексы
   std::vector<float> ver(sizeof(float)*8*N);//Здесь вершины
   int j;//Количество добавленных

   auto std=[&]
   {
      j=0;
      c1=clock();t1=rdtsc();
      std::unordered_map<mm,tint,mm> kk(N);
      for (int i=0;i<N;i++)
      {

         auto r=kk.find(arr[i]);
         if (r==kk.cend()){//Если такого ещё нет
            memcpy(&ver[j*8],arr[i].p,sizeof(float)*8);
            ind[i]=j;
            kk.insert({arr[i],j});
            j++;
         }
         else
         {
            ind[i]=r->second;//kk[aa[i]];  }
         }

      }
      c2=clock();t2=rdtsc();
      wprintf(L"N: %d    j: %d\n",N,j);
      wprintf(L"std | %d ms [%.2f] :  %lldk\n",c2-c1,(t2-t1)/hz,t2-t1);
      m1=c2-c1;
      e1=t2-t1;
   };




   auto me=[&]
   {
      j=0;
      c1=clock();t1=rdtsc();
      me::unordered_map<mm,tint,mm> kk(N);
      for (int i=0;i<N;i++)
      {

         // kk.prn();
         auto r=kk.find(arr[i]);
         if (r==nullptr){//Если такого ещё нет
            memcpy(&ver[j*8],arr[i].p,sizeof(float)*8);
            ind[i]=j;
            kk.insert({arr[i],j});
            j++;
         }
         else
         {
            ind[i]=r->second;//kk[aa[i]];  }
         }
         // wprintf(L"\n");
      }
      c2=clock();t2=rdtsc();
      wprintf(L"N: %d    j: %d\n ",N,j);
      wprintf(L"me | %d ms [%.2f] :  %lldk\n",c2-c1,(t2-t1)/hz,t2-t1);
      m2=c2-c1;
      e2=t2-t1;
   };


   std();
   me();
   wprintf(L"                                       %.2f%%  %.2f%%\n",100.0*m1/m2,100.0*e1/e2);
   me();
   std();
   wprintf(L"                                       %.2f%%  %.2f%%\n",100.0*m1/m2,100.0*e1/e2);


}

int main()
{
   using namespace me;

   tint c1=clock();
   nint t1=me::rdtsc();
   std::this_thread::sleep_for(std::chrono::milliseconds(100));
   tint c2=clock();
   nint t2=me::rdtsc();
   hz=double(t2-t1)/(c2-c1);
   wprintf(L"khz: %.2f\n",hz);

   test(1000000,123);
   test(1000,52);
   test(10,76);


}