#include<iostream>
#include<fstream>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <vector>
  
using namespace std;
  
// Hash-ul de Baza
class Basic_Hash
{
protected:
    unsigned int *hash1, *hash2;
    unsigned int size;
    unsigned int mod1, mod2;
    unsigned int a1, a2, b1, b2;
  
public:
         
    Basic_Hash(unsigned int n);
    virtual ~Basic_Hash();
     
    void Initializare();
    void generare_parametri();
     
    virtual void Rezolvare()=0;
    virtual unsigned int functia1(unsigned int &)=0;
    virtual unsigned int functia2(unsigned int &)=0;
    virtual bool comparare(unsigned int, unsigned int)=0;
     
    bool operator += (unsigned int);
    void operator -= (unsigned int);
    bool operator == (unsigned int);
 
  
};
 
Basic_Hash::Basic_Hash(unsigned int n) 
{
    size=n;
     
    hash1 = new unsigned int[size];
    hash2 = new unsigned int[size];
}
 
Basic_Hash::~Basic_Hash()
{
    delete[] hash1;
    delete[] hash2;
}
 
void Basic_Hash::generare_parametri()
{
    unsigned int pr[]={999983,999979,899981,900007,800011};
    a1 = rand() % size;
    b2 = rand() % size;
    a2 = rand() % size;
    b1 = rand() % size;
    mod1 = pr[rand () % 5];
    mod2 = pr[rand () % 5];
}
 
bool Basic_Hash::operator+=(unsigned int val)
{
    unsigned int nr=0, poz1, poz2, aux;
      
    poz1 = functia1(val);
    poz2 = functia2(val);
      
    if( (comparare(hash1[poz1],val)) || ( comparare(hash2[poz2],val)) )
        return true;
      
    if(hash1[poz1]==0)
    {
        hash1[poz1]=val;
        return true;
    }
    else
        if(hash2[poz2]==0)
        {
            hash2[poz2]=val;
            return true;
        }
        else
        {
            aux = val;
            val = hash1[poz1];
            hash1[poz1] = aux;
        }
      
    while(nr<30)
    {
        nr++;
          
        poz2 = functia2(val);
          
        if(hash2[poz2]==0)
        {
            hash2[poz2]=val;
            return true;
        }
        else
        {
            poz1 = functia1(hash2[poz2]);
            aux=hash2[poz2];
            hash2[poz2]=val;
            val=hash1[poz1];
            hash1[poz1]=aux;
        }
    }
      
    return false;
}
 
void Basic_Hash::operator-=(unsigned int val)
{
    unsigned int poz1, poz2;
      
    poz1 = functia1(val);
    poz2 = functia2(val);
      
    if( comparare(hash1[poz1],val))
        hash1[poz1]=0;
          
    else
        if( comparare(hash2[poz2],val))
            hash2[poz2] = 0;
}
 
bool Basic_Hash::operator==(unsigned int val)
{
    unsigned int poz1, poz2;
     
    poz1 = functia1(val);
    poz2 = functia2(val);
      
    if( comparare( hash1[poz1], val ) || comparare( hash2[poz2], val ))
        return 1;
    else
        return 0;
}
     
void Basic_Hash::Initializare()
{
    fill(hash1,hash1+size,0);
    fill(hash2,hash2+size,0);
    generare_parametri();
}
  
 
 
// Cuckoo Hash pentru Stringuri
  
class Hash_String:public Basic_Hash
{
     
    string *v;
  
public:
  
    Hash_String(unsigned int size):Basic_Hash(size)
    {
        v=new string[size+1];
    }
    ~Hash_String(){delete[] v;}
     
    void Rezolvare();
    unsigned int functia1(unsigned int &);
    unsigned int functia2(unsigned int &);
    bool comparare(unsigned int, unsigned int);
     
};
 
void Hash_String::Rezolvare()
{
    unsigned int n, op, i, ok=0;
  
      
      
    while(ok==0)
    {
        Initializare();
          
        ifstream f("hashuri.in");
        ofstream g("hashuri.out");
          
        f>>n;
          
        ok=1;
      
        for(i=1; i <= n && ok; i++)
        {
            f>>op>>v[i];
          
            if(op==1)
                ok = *this += i;
            else
                if(op==2)
                    *this -= i;
            else
                g<<(*this==i)<<"\n";
             
             
        }
          
        f.close();
        g.close();
          
    }
}
 
unsigned int Hash_String::functia1(unsigned int &val)
{
    unsigned int aux = 0;
    for (unsigned int i =0;i<v[val].size();i++)
        aux = (aux+a1 + b1*v[val][i])%size;
    return aux;
}
 
unsigned int Hash_String::functia2(unsigned int &val)
{
    unsigned int aux = 0;
    for (unsigned int i =0;i<v[val].size();i++)
        aux = (aux+a2 + b2*v[val][i])%size;
    return aux;
}
 
bool Hash_String::comparare(unsigned int x, unsigned int y)
{
    if(v[x]==v[y])
        return 1;
    else
        return 0;
}
  
 
//Cuckoo Hash pt Int
class Hash_Int:public Basic_Hash
{
   
    int *v;
  
public:
  
    Hash_Int(unsigned int size):Basic_Hash(size)
    {
        v=new int[size+1];
    }
    ~Hash_Int(){ delete[] v;}
    void Rezolvare();
    unsigned int functia1(unsigned int &);
    unsigned int functia2(unsigned int &);
    bool comparare(unsigned int, unsigned int);
     
};
 
void Hash_Int::Rezolvare()
{
    unsigned int n, op, i, ok=0;
  
      
      
    while(ok==0)
    {
        Initializare();
          
        ifstream f("hashuri.in");
        ofstream g("hashuri.out");
          
        f>>n;
         
         
          
        ok=1;
      
        for(i=1; i <= n && ok; i++)
        {
            f>>op>>v[i];
          
            if(op==1)
                ok = *this += i;
            else
                if(op==2)
                    *this -= i;
            else
                g<<(*this==i)<<"\n";
        }
          
        f.close();
        g.close();
          
    }
}
 
unsigned int Hash_Int::functia1(unsigned int &val)
{
    unsigned int poz;
     
    poz=((a1 + b1*v[val] ) % mod1) % size;
    return poz;
}
 
unsigned int Hash_Int::functia2(unsigned int &val)
{
    unsigned int poz;
    poz=((a2 + b2*v[val] ) % mod2) % size;
    return poz;
}
 
bool Hash_Int::comparare(unsigned int x, unsigned int y)
{
    if(v[x]==v[y])
        return 1;
    else
        return 0;
}
 
//Cuckoo Hash pt Double
class Hash_Double:public Basic_Hash
{
   
    double *v;
  
public:
  
    Hash_Double(unsigned int size):Basic_Hash(size)
    {
        v=new double[size+1];
    }
    ~Hash_Double(){ delete[] v;}
    void Rezolvare();
    unsigned int functia1(unsigned int &);
    unsigned int functia2(unsigned int &);
    bool comparare(unsigned int, unsigned int);
     
};
 
void Hash_Double::Rezolvare()
{
    unsigned int n, op, i, ok=0;
  
      
      
    while(ok==0)
    {
        Initializare();
          
        ifstream f("hashuri.in");
        ofstream g("hashuri.out");
          
        f>>n;
         
         
          
        ok=1;
      
        for(i=1; i <= n && ok; i++)
        {
            f>>op>>v[i];
          
            if(op==1)
                ok = *this += i;
            else
                if(op==2)
                    *this -= i;
            else
                g<<(*this==i)<<"\n";
        }
          
        f.close();
        g.close();
          
    }
}
 
unsigned int Hash_Double::functia1(unsigned int &val)
{
    unsigned int poz;
     
    while ((v[val]- int(v[val])) != 0)
    {
        v[val] *= 10;
        if (v[val] > size)
        {
            v[val] -= size;
        }
    }
    poz = (((unsigned int)a1 + (unsigned int)b1*(unsigned int)v[val] ) % (unsigned int)mod1) % (unsigned int)size;
    return poz;
}
 
unsigned int Hash_Double::functia2(unsigned int &val)
{
    int poz;
     
    while ((v[val] - int(v[val])) != 0)
    {
        v[val] *= 10;
        if (v[val] > size)
        {
            v[val] -= size;
        }
    }
    poz = (((unsigned int)a2 + (unsigned int)b2*(unsigned int)v[val] ) % (unsigned int)mod2) % (unsigned int)size;
    return poz;
}
 
bool Hash_Double::comparare(unsigned int x, unsigned int y)
{
    if(v[x]==v[y])
        return 1;
    else
        return 0;
}
 
//Cuckoo Hash pt Float
class Hash_Float:public Basic_Hash
{
   
    float *v;
  
public:
  
    Hash_Float(unsigned int size):Basic_Hash(size)
    {
        v=new float[size+1];
    }
    ~Hash_Float(){ delete[] v;}
    void Rezolvare();
    unsigned int functia1(unsigned int &);
    unsigned int functia2(unsigned int &);
    bool comparare(unsigned int, unsigned int);
     
};
 
void Hash_Float::Rezolvare()
{
    unsigned int n, op, i, ok=0;
  
      
      
    while(ok==0)
    {
        Initializare();
          
        ifstream f("hashuri.in");
        ofstream g("hashuri.out");
          
        f>>n;
         
         
          
        ok=1;
      
        for(i=1; i <= n && ok; i++)
        {
            f>>op>>v[i];
          
            if(op==1)
                ok = *this += i;
            else
                if(op==2)
                    *this -= i;
            else
                g<<(*this==i)<<"\n";
        }
          
        f.close();
        g.close();
          
    }
}
 
 
unsigned int Hash_Float::functia1(unsigned int &val)
{
    unsigned int poz;
     
    while ((v[val] - int(v[val])) != 0)
    {
        v[val] *= 10;
        if (v[val] > size)
        {
            v[val] -= size;
        }
    }
    poz = (((unsigned int)a1 + (unsigned int)b1*(unsigned int)v[val] ) % (unsigned int)mod1) % (unsigned int)size;
    return poz;
}
 
unsigned int Hash_Float::functia2(unsigned int &val)
{
    int poz;
     
    while ((v[val] - int(v[val])) != 0)
    {
        v[val] *= 10;
        if (v[val] > size)
        {
            v[val] -= size;
        }
    }
    poz = (((unsigned int)a2 + (unsigned int)b2*(unsigned int)v[val] ) % (unsigned int)mod2) % (unsigned int)size;
    return poz;
}
 
bool Hash_Float::comparare(unsigned int x, unsigned int y)
{
    if(v[x]==v[y])
        return 1;
    else
        return 0;
}
 
 
// Cuckoo Hash pentru Unsigned int
class Hash_UnInt:public Basic_Hash
{
   
    unsigned int *v;
  
public:
  
    Hash_UnInt(unsigned int size):Basic_Hash(size)
    {
        v=new unsigned int[size+1];
    }
    ~Hash_UnInt(){ delete[] v;}
    void Rezolvare();
    unsigned int functia1(unsigned int &);
    unsigned int functia2(unsigned int &);
    bool comparare(unsigned int, unsigned int);
     
};
 
void Hash_UnInt::Rezolvare()
{
    unsigned int n, op, i, ok=0;
  
      
      
    while(ok==0)
    {
        Initializare();
          
        ifstream f("hashuri.in");
        ofstream g("hashuri.out");
          
        f>>n;
         
         
          
        ok=1;
      
        for(i=1; i <= n && ok; i++)
        {
            f>>op>>v[i];
          
            if(op==1)
                ok = *this += i;
            else
                if(op==2)
                    *this -= i;
            else
                g<<(*this==i)<<"\n";
        }
          
        f.close();
        g.close();
          
    }
}
 
unsigned int Hash_UnInt::functia1(unsigned int &val)
{
    unsigned int poz;
     
    poz=((a1 + b1*v[val] ) % mod1) % size;
    return poz;
}
 
unsigned int Hash_UnInt::functia2(unsigned int &val)
{
    unsigned int poz;
    poz=((a2 + b2*v[val] ) % mod2) % size;
    return poz;
}
 
bool Hash_UnInt::comparare(unsigned int x, unsigned int y)
{
    if(v[x]==v[y])
        return 1;
    else
        return 0;
}
 
 
int main()
{
    short x=2;
     
    srand(time(NULL));
      
    Basic_Hash *h;
      
    //cout<<"Alegeti tipul de date:\n1. unsigned int\n2. int\n3. float\n4. double\n5.string\n";
    //cin>>x;
    while(x<1||x>5)
    {
        cout<<"introduceti o valoare intre 1 si 5: ";
        cin>>x;
    }
    if(x==1)
        h = new Hash_UnInt(1000000);
    else
        if(x==2)
            h = new Hash_Int(1000000);
        else
            if(x==3)
                h = new Hash_Float(1000000);
            else
                if(x==4)
                    h = new Hash_Double(1000000);
                else
                    h = new Hash_String(1000000);
             
   
       
    h->Rezolvare ();
  
    return 0;
}