#include<iostream>
using namespace std;
#define tsize 10
#include<stdlib.h>
struct sc
{
    int data;
    struct sc *add;
};

class sepchain
{
        struct sc *head[10];
    public:
        sepchain();
        void insert();
        void del();
        void search();
        void display();
        int hash_fun(int);
};

sepchain::sepchain()
{
    int i;
    for(i=0;i<tsize;i++)
        head[i] = NULL;
}

int sepchain::hash_fun(int key)
{
    return key%tsize;
}

void sepchain::insert()
{
  int key,i;
  struct sc *ptr,*temp;
  cout << "\nEnter key to insert::\t";
  cin >> key;
  ptr = new (sc);
  ptr->data = key;
  ptr->add = NULL;
  i = hash_fun(key);
  if(head[i] == NULL)
  {
    head[i] = ptr;
    cout << "Successfully Key " << key << " Inserted..!!";
  }
  else
    {
      temp=head[i];
      if(temp->add == NULL)
      {
          temp->add = ptr;
          cout << "Successfully Key " << key << " Inserted..!!";
      }
      else
      {
          while(temp->add!=NULL)
            temp=temp->add;

          temp->add=ptr;
          cout << "Successfully Key " << key << " Inserted..!!";
      }
   }
}

void sepchain::search()
{
  int key,i,flag=0;
  struct sc *temp;
  cout << "\nEnter key to search::\t";
  cin >> key;
  i=hash_fun(key);
  if(head[i]==NULL)
  {
    cout << "\nUnsuccessful Search, No such element :-(";
  }
  else
    {
      temp=head[i];
      while(temp!=NULL)
      {
          if(temp->data==key)
          {
            cout <<"\nSuccessful Search, Key " << key << " found";
            flag++;
            break;
          }
          temp=temp->add;
      }
     if(flag==0)
      cout << "\nUnsuccessful Search, No such element :-(";
    }
}

void sepchain::del()
{
  int key,i,flag=-1;
  struct sc *temp,*prev;
  cout << "\nEnter key to delete::\t";
  cin >> key;
  i = hash_fun(key);
  if(head[i] == NULL)
  {
    cout << "\nSorry, No such element to delete";
  }
  else
    {
      temp=head[i];
      if(temp->add == NULL)
      {
          if(temp->data == key)
          {
            cout << "\nKey " << key << " is deleted";
            head[i] = NULL;
          }
          else
            cout << "\n Sorry, No such element to delete";
      }
      else
        {
            if(temp->add != NULL && temp->data == key)
            {
                head[i] = temp->add;
                cout << "\nKey " << key << " is deleted";
            }
            else
            {
                while(temp->add!=NULL)
                {
                    prev = temp;
                    temp = temp->add;
                    if(temp->data==key)
                    {
                        cout << "\nKey " << key << " is deleted";
                        prev->add = temp->add;
                        flag++;
                        break;
                    }
                }
                if(flag == -1)
                    cout << "\n Sorry, No such element to delete";
            }
        }
    }
}

void sepchain::display()
{
    int i;
    struct sc *temp;
    cout << "\nData in the Hash Table is :" << endl;
    for(i=0;i<10;i++)
    {
        temp = head[i];
        cout << "Head[" << i << "]\t";
        while(temp!=NULL)
        {
            cout <<"  -->  " << temp->data;
            temp=temp->add;
        }
        cout <<"  --> NULL" << endl;
    }
}

int main()
{
    int ch,i;
    sepchain sc;
    while(1)
    {
        cout << "\n\nSeparate Chaining::Operations";
        cout << "\n1.Insert\n2.Delete\n3.Search\n4.Display\n5.Exit" << endl;
        cout << "What's your choice::\t";
        cin >> ch;
        switch(ch)
        {
            case 1: sc.insert();
                    break;

            case 2: sc.del();
                    break;

            case 3: sc.search();
                    break;

            case 4: sc.display();
                    break;

            case 5: cout << "\nHappy Learning..!! Bye Bye...\n\n";
                    exit(0);

            default: cout << "\n Sorry, You have entered wrong choice..!! " << endl << "\nTry again..!! or Exit";
        }
    }
    return 0;
}
