//Dumea Eduard Constantin, Grupa 134

#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;
	double aux=v[val];
	
    while ((aux - int(aux)) != 0)
    {
        aux *= 10;
        if (aux > size)
        {
            aux -= size;
        }
    }
    poz = (((unsigned int)a1 + (unsigned int)b1*(unsigned int)aux ) % (unsigned int)mod1) % (unsigned int)size;
    return poz;
}

unsigned int Hash_Double::functia2(unsigned int val)
{
    int poz;
	double aux=v[val];
	
    while ((aux - int(aux)) != 0)
    {
        aux *= 10;
        if (aux > size)
        {
            aux -= size;
        }
    }
    poz = (((unsigned int)a2 + (unsigned int)b2*(unsigned int)aux ) % (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;
	float aux=v[val];
	
    while ((aux - int(aux)) != 0)
    {
        aux *= 10;
        if (aux > size)
        {
            aux -= size;
        }
    }
    poz = (((unsigned int)a1 + (unsigned int)b1*(unsigned int)aux ) % (unsigned int)mod1) % (unsigned int)size;
    return poz;
}

unsigned int Hash_Float::functia2(unsigned int val)
{
    int poz;
	float aux=v[val];
	
    while ((aux - int(aux)) != 0)
    {
        aux *= 10;
        if (aux > size)
        {
            aux -= size;
        }
    }
    poz = (((unsigned int)a2 + (unsigned int)b2*(unsigned int)aux ) % (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=1;
	
	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;
}