#include<bits/stdc++.h>
#include<time.h>
#define hash_size 10000
#define null_value 99999

using namespace std;

typedef unsigned long long int lli;

///hash functions

lli djb2(string str)
{
    lli  x = 5381;
    int l = str.length();

    for (long long int i = 0; i < l; i++)
        x =x+ ((x * 33) + str[i]);

    return x;
}


   lli sdbm(string str)
   {
      lli hash = 0;

      for(int i = 0; i < str.length(); i++)
      {
         hash = str[i] + (hash << 6) + (hash << 16) - hash;
      }

      return hash;
   }

lli jenkins(string str)
{
    lli  x = 0;
    int l=str.length();
    for (int i = 0; i < l; i++)
    {
        x += str[i];
        x += (x << 10);
        x ^= (x >> 6);
    }

    x += (x << 3);
    x ^= (x >> 11);
    x += (x << 15);

    return x;
}

///random string generator
static const char alphanum[] ="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int stringLength = sizeof(alphanum) - 1;

char genRandom()  // Random string generator function.
{

    return alphanum[rand() % stringLength];
}

void random_generator(int ssize,int n,string *rstr)
{

 for(int i=0;i<n;i++)
 {
     string str="";
     for(int z=0; z < ssize; z++)
    {
        char x=genRandom();
        str.push_back((char)x);
    }
    rstr[i]=str;
 }

}


/// linearprobing probing

struct lnode
{
    string key;
    int value;

    lnode(string k, int v)
    {
        key=k;
        value=v;
    }
    lnode()
    {

    }

};


class linearprobing
{

    lnode *hashtable;
    int type,hsize,value,col;

public:

    linearprobing(int size,int htype)
    {
        hashtable=new lnode[size];
        type=htype;
        hsize=size;
        value=0;
        col=0;

        for(int i=0; i<hsize; i++)
        {
            hashtable[i]=lnode("EMPTY",-1);
        }
    }


    void insert (string key)
    {
        if(search(key)!=null_value)
            return;

        lli index;

        if(type==1)
            index=djb2(key);
        else if(type==2)
            index=sdbm(key);
        else
            index=jenkins(key);


        if(hashtable[index%hsize].value!= -1)
        {
            col++;
        }

        int i=0;
        while(i<hsize)
        {

           lli temp= (index+i) % hsize;

            if(hashtable[temp].key=="EMPTY")
            {
                value++;
                hashtable[temp]=lnode(key,value);
                return;
            }

            else
            {
                i++;
            }
        }

    }


    int search(string key)
    {
        lli index;
        int i=0;

        if(type==1)
            index=djb2(key);
        else if(type==2)
            index=sdbm(key);
        else
            index=jenkins(key);


        while(i<hsize)
        {
            lli temp= (index+i) % hsize;

            if(hashtable[temp].key=="EMPTY")
            {
                return null_value;
            }

            else if(hashtable[temp].key==key)
            {
                return temp;
            }

            else
            {
                i++;
            }
        }

        return null_value;

    }

    void deletekey (string key)
    {
        int temp=search(key);

        if(temp!=null_value)
        {
            hashtable[temp]=lnode("DELETED",-1);
        }

        else
        {
            cout<<"key not found"<<endl;
            return;
        }
    }


    int getcollision()
    {
        return col;
    }


    void print()
    {
        for(int i=0;i<hsize;i++)
        {
            cout<< hashtable[i].key<< " "<<hashtable[i].value <<endl;
        }
    }



};
//-------------------------------x----------------------------------------------
struct snode
{
    string key;
    int value;
    snode *next,*prev;


    snode(string k,int v)
    {
        key=k;
        value=v;

        next=0;
        prev=0;
    }

    snode()
    {
        next=0;
        prev=0;
    }


};


class spchainning
{

 snode **hashtable;
 int type,hsize,value,col;

 public:
     spchainning(int size,int htype)
     {
         hsize=size;
         type=htype;
         col=0;
         value=0;
         hashtable=new snode*[hsize];
         for(int i=0;i<hsize;i++)
            hashtable[i]=NULL;
     }


     void insert(string key)
     {

         lli index;

        if(type==1)
            index=djb2(key)%hsize;
        else if(type==2)
            index=sdbm(key)%hsize;
        else
            index=jenkins(key)%hsize;


       value++;
       snode *temp=new snode(key,value);


       if(hashtable[index]==NULL)
       {
           hashtable[index]=temp;
       }
       else
       {
           hashtable[index]->prev=temp;
           temp->next=hashtable[index];
           hashtable[index]=temp;
           col++;

       }



     }


     snode* search(string key)
     {

        lli index;

        if(type==1)
            index=djb2(key)%hsize;
        else if(type==2)
            index=sdbm(key)%hsize;
        else
            index=jenkins(key)%hsize;



        if(hashtable[index]==NULL)
        {
            return NULL;
        }
        else
        {

            snode *temp;
            temp=hashtable[index];

            while(temp)
            {
                if(temp->key==key)
                    return temp;
                else
                    temp=temp->next;

            }

        }

        return NULL;

     }


     void deletekey(string key)
     {

       snode *temp=search(key);

       if(temp==NULL)
       {
           printf("key not found");
           return;
       }


        lli index;
        if(type==1)
            index=djb2(key)%hsize;
        else if(type==2)
            index=sdbm(key)%hsize;
        else
            index=jenkins(key)%hsize;


        ///if node is the head in that index
        if(hashtable[index]==temp)
        {
            snode *temp2=temp->next;
            hashtable[index]=temp2;
            if(temp->next != NULL)
            {
                temp2->prev=NULL;

            }

            delete temp;

        }

        else
        {

         snode *prev=temp->prev;
         snode *next=temp->next;

         prev->next=next;
         if(next!= NULL)
         {
             next->prev=prev;
         }

         delete temp;


        }



     }


     int getcollision()
     {
         return col;
     }





};


int main()
{

    return 0;
}