//Doubly Linked List

#include <iostream.h>
#include <stdlib.h> //for exit(1)
#include <conio.h>
#define MAX 10


struct node{
       int data;
       struct node *lptr;
       struct node *rptr;
};

class dbllist{
    node *head;
    public:
    dbllist(){
       head=NULL;
    }
    void create(); //initial data assignmentvoid display(int); //process is display (assumed)int count(int);
    void insert();
    void del();
    void search();
    void reverse();
    void sort();
};


void dbllist :: create(){
     node *start=NULL,*newl=NULL,*end=NULL;
     int takedata;
     clrscr();
     cout<<"\n\t\t*****Create List*****\n";
     while(1){
    cout<<"\t\t-999 to Quit\n";
    cout<<"\t\tEnter data : ";
    cin>>takedata;
    if(takedata == -999)
       break;
    else{
          //create memory for new node
          newl = new node;
          if(newl == NULL){
         cout<<"\n\t\tNot Enough Memory";
         getch();
         exit(1);
          }
          newl->data = takedata;
          newl->lptr = NULL;
          newl->rptr = NULL;

          //check for first nodeif(start == NULL){
          start->rptr = newl;
          newl->lptr = start;
          start = newl;
          }
          else{
          end->rptr = newl;
          newl->lptr = end;
          }
          end = newl;
    }//end else
     }//end while

    head->rptr = start;
    start->lptr = head;
    head = start;
}

void dbllist :: display(int check){
     node *tmp=NULL;

     cout<<"\n\t\t*****Display*****\n";
     cout<<"\t\t";
   if(check==1){  //forward displayfor(tmp=head; tmp!=NULL; tmp=tmp->rptr){
     cout<<tmp->data;
     if(tmp->rptr != NULL)
        cout<<"-->";
     }//end for
   }
  else{   //Reverse displayfor( tmp=head; tmp->rptr!=NULL; tmp=tmp->rptr);//points to last nodewhile(tmp!=NULL)
     {
     cout<<tmp->data;
     if(tmp->lptr != NULL)
        cout<<"-->";
     tmp = tmp->lptr;
     }//end whiile
  }//end if
  getch();
}

int dbllist :: count(int check){
     node *tmp=NULL;
     int cnt;

     for(tmp=head,cnt=0 ; tmp!=NULL; tmp=tmp->rptr,cnt++);//do nothingif(check==1){
    cout<<"\n\t\t*****Status of List*****\n";
    cout<<"\t\tTotal Items : "<<cnt;
    getch();
    return(cnt);
     }
     elsereturn(cnt);  //To use count value in other functions
}


void dbllist :: insert(){
     node *newl=NULL,*tmp=NULL,*prev=NULL,*next=NULL;
     int choice,takedata,pos,i;
     while(1){
    clrscr();
    cout<<"\n\t\t*****Insertion*****\n";
    cout<<"\t\t1) Begining\n";
    cout<<"\t\t2) In Between\n";
    cout<<"\t\t3) End\n";
    cout<<"\t\t4) Return to Main Menu\n";
    cout<<"\t\tEnter your choice : ";
    cin>>choice;
    if(choice==1 || choice==2 || choice==3){
    //create memory for new node
      newl = new node;
      if(newl == NULL){
         cout<<"\n\t\tNot Enough Memory";
         getch();
         exit(1);
      }
      cout<<"\n\t\tEnter data : ";
      cin>>takedata;
      newl->data = takedata;
      newl->lptr = NULL;
      newl->rptr = NULL;
    }
    elsereturn;

    switch(choice){
         case 1 :   newl->rptr = head;
            head->lptr = newl;
            head = newl;
            break;

         case 2 :   cout<<"\n\t\tEnter Position : ";
            cin>>pos;
            if(pos <=1 || pos >= count(2)){
                cout<<"\n\t\tInvalid Position";
                getch();
                break;
            }
            else{
               //to points to previous node from where//to insertfor(i=1,prev=head; i < (pos-1); prev=prev->rptr,i++);

               next = prev->rptr;
               newl->rptr = next;
               next->lptr = newl;
               newl->lptr = prev;
               prev->rptr = newl;
               break;
            }
         case 3 :   //For pointing to last nodefor(tmp=head; tmp->rptr != NULL; tmp=tmp->rptr);

            tmp->rptr = newl;
            newl->lptr = tmp;
    }//end switch
     }//end while
}



void dbllist :: del(){
     node *delnode=NULL,*tmp=NULL,*prev=NULL,*next=NULL;
     int choice,deldata,pos,i;
     while(1){
    clrscr();
    cout<<"\n\t\t*****Deletion*****\n";
    cout<<"\t\t1) Begining\n";
    cout<<"\t\t2) In Between\n";
    cout<<"\t\t3) End\n";
    cout<<"\t\t4) Return to Main Menu\n";
    cout<<"\t\tEnter your choice : ";
    cin>>choice;
    switch(choice){
         case 1 :   delnode = head;
            head = head->rptr;
            head->lptr = NULL;
            break;

         case 2 :   cout<<"\n\t\tEnter Position : ";
            cin>>pos;
            if(pos <=1 || pos >= count(2)){
                cout<<"\n\t\tInvalid Position";
                getch();
                break;
            }
            else{
               //to points to previous node from where//to insertfor(i=1,prev=head; i < (pos-1); prev=prev->rptr,i++);

               next=prev->rptr->rptr;
               delnode = prev->rptr;
               prev->rptr = prev->rptr->rptr;
               next->lptr = prev;
               break;
            }
         case 3 :   //For pointing to last nodefor(tmp=head; tmp->rptr->rptr != NULL; tmp=tmp->rptr);
            delnode = tmp->rptr;
            tmp->rptr = NULL;
            break;
         case 4  :  return;
         default :   cout<<"\n\t\tInvalid Position";
             getch();
    }//end switch
    delete(delnode);
     }//end while
}



void dbllist :: search(){
     node *tmp=NULL;
     int item,n;
     cout<<"\n\t\t*****Search*****\n";
     cout<<"\t\tEnter data to be searched : ";
     cin>>item;
     for(tmp=head,n=1; tmp!=NULL; tmp=tmp->rptr,n++){
     if(tmp->data == item){
        cout<<"\n\t\tSearch is located at "<<n<<" location";
        getch();
        return;
     }
     }
     cout<<"\n\t\tSearch Not Found";
     getch();
}


void dbllist :: sort(){
     node *i,*j;
     int tmp;
     cout<<"\n\t\t*****Sort*****\n";
     for(i=head;i!=NULL;i=i->rptr){
       for(j=i;j!=NULL;j=j->rptr){
      if(i->data > j->data){
         tmp = i->data;
         i->data = j->data;
         j->data = tmp;
      }
       }
     }
     cout<<"\n\t\tAfter Sort...";
     cout<<"\n\n\t\t==List==";
     display(1);
}


void main()
{
   int choice;
   dbllist obj;
   while(1){
   clrscr();
   cout<<"\n\t\tDOUBLY LINK-LIST OPERATIONS\n\n";
   cout<<"\t\t1)  Create List\n";
   cout<<"\t\t2)  Display List\n";
   cout<<"\t\t3)  List Status\n";
   cout<<"\t\t4)  List Insertion\n";
   cout<<"\t\t5)  List Deletion\n";
   cout<<"\t\t6)  Search List\n";
   cout<<"\t\t7)  Display Reverse List\n";
   cout<<"\t\t8)  Sort List\n";
   cout<<"\t\t9)  Exit\n";
   cout<<"\t\tEnter your Choice :  ";
   cin>>choice;
   switch(choice){
     case 1 :  obj.create(); // 1 for A listbreak;
     case 2 :  obj.display(1);// 1 for A listbreak;
     case 3 :  choice = obj.count(1);
           //choice value is not used anywhere//it is just a placeholderbreak;
     case 4 :  obj.insert();
           break;
     case 5 :  obj.del();
           break;
     case 6 :  obj.search();
           break;
     case 7 :  obj.display(2);
           break;
     case 8 :  obj.sort();
           break;
     case 9 :  gotoout;
     default:  cout<<"\n\n\t\tInvalid Choice\n\n";
           getch();
           break;
   }
 }
 out:
}