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


struct node{
       int data;
       struct node *next;
};

class sngllist{
    node *A,*B,*MRG;
    int cnt;
    public:
    sngllist(){
       cnt=0;
       A=NULL;
       B=NULL;
       MRG=NULL;
    }
    //ALL THE OPERATIONS ARE PERFORMED ON NODE A//Except Merge, union, intersection.void create(int); //initial data assignmentvoid display(int); //process is display (assumed)int count(int);
    void insert();
    void del();
    void search();
    void copy();
    void reverse();
    void sort();
    void merge();
    void unionList();
    void intersectionList();
};


void sngllist :: create(int check){
     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->next = NULL;
          cnt++;

          //check for first nodeif(start == NULL)
          start = newl;
          else
          end->next = newl;
          end = newl;
          end->next = NULL;
    }//end else
     }//end while//check to create which listif(check==1){
    A->next = start;
    A = start;
     }
     if(check==2){
    B->next = start;
    B = start;
     }
     if(check==3){
    MRG->next = start;
    MRG = start;
     }
}

void sngllist :: display(int check){
     node *tmp;

     //check to print which listif(check==1)
     tmp=A;
     if(check==2)
     tmp=B;
     if(check==3)
     tmp=MRG;

     cout<<"\n\t\t*****Display*****\n";
     cout<<"\t\t";
     for( ; tmp!=NULL; tmp=tmp->next){
     cout<<tmp->data;
     if(tmp->next != NULL)
        cout<<"-->";
     }//end for
     getch();
}

int sngllist :: count(int check){
     node *tmp;
     int cnt;

     for(tmp=A,cnt=0 ; tmp!=NULL; tmp=tmp->next,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 sngllist :: insert(){
     node *newl=NULL,*tmp=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->next = NULL;
    }
    elsereturn;

    switch(choice){
         case 1 :   newl->next = A;
            A = 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,tmp=A; i < (pos-1); tmp=tmp->next,i++);

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

            tmp->next = newl;
    }//end switch
     }//end while
}



void sngllist :: del(){
     node *delnode=NULL,*tmp=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->next = A;
            delnode = A;
            A = A->next;
            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,tmp=A; i < (pos-1); tmp=tmp->next,i++);

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


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


void sngllist :: copy(){
     node *tmp=NULL,*newl=NULL,*end=NULL;
     B=NULL;
     cout<<"\n\t\t*****Copy*****\n";
     for(tmp=A; tmp!=NULL; tmp=tmp->next){
     //create memory
     newl = new node;
     newl->data = tmp->data;
     newl->next = NULL;
     if(B == NULL){
        B->next = newl;
        B = newl;
     }
     else
         end->next=newl;
     end=newl;
     }
     cout<<"\n\t\tAfter Copy...";
     cout<<"\n\n\t\t==List A==";
     display(1);  //List A
     cout<<"\n\n\t\t==List B==";
     display(2); //List B
}

void sngllist :: reverse(){
    //Reversing Logic without using another list
    node *prev=NULL,*curr=A,*succ=A->next;
    while(succ!=NULL){
       curr->next = prev;
       prev = curr;
       curr = succ;
       succ = succ->next;
    }
    curr->next = prev;
    prev = curr;

    A = prev->next;
    A = prev;
    display(1);
}


void sngllist :: sort(){
     node *i,*j;
     int tmp;
     cout<<"\n\t\t*****Sort*****\n";
     for(i=A;i!=NULL;i=i->next){
       for(j=i;j!=NULL;j=j->next){
      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); //List B
}

void sngllist :: merge(){
     node *i,*newl=NULL,*end=NULL;
     MRG=NULL;

     create(1); //Create List A
     create(2); //Create List B

     cout<<"\n\t\t*****Merge*****\n";
     //Merging A to listfor(i=A;i!=NULL;i=i->next){
     //create memory
     newl = new node;
     newl->data = i->data;
     newl->next = NULL;
     if(MRG == NULL){
        MRG->next = newl;
        MRG = newl;
     }
     else
         end->next=newl;
     end=newl;
     }

     //Merging B to listfor(i=B;i!=NULL;i=i->next){
     //create memory
     newl = new node;
     newl->data = i->data;
     newl->next = NULL;
     end->next=newl;
     end=newl;
      }

     cout<<"\n\t\tAfter Merge...";
     cout<<"\n\n\t\t==List==";
     display(3); //List MRG
}


void sngllist :: unionList(){
     node *i,*j,*newl=NULL,*end=NULL;
     MRG=NULL;
     int flag=0;

     create(1); //Create List A
     create(2); //Create List B

     cout<<"\n\t\t*****Union of List*****\n";
     //Union A to listfor(i=A;i!=NULL;i=i->next){
         if(MRG == NULL){
           newl = new node;
           newl->data = i->data;
           newl->next = NULL;
           MRG->next = newl;
           MRG = newl;
           end->next=newl;
           end=newl;
           continue;
         }
    for(j=MRG;j!=NULL;j=j->next){
      if(i->data != j->data)
          flag=1;
     }

     if(flag==1){
          flag=0;
         //create memory
         newl = new node;
         newl->data = i->data;
         newl->next = NULL;
         end->next=newl;
         end=newl;
      }//end if
     }//end for//Union B to listfor(i=B;i!=NULL;i=i->next){
    for(j=MRG;j!=NULL;j=j->next){
      if(i->data != j->data)
          flag=1;
     }
     if(flag==1){
          flag=0;
         //create memory
         newl = new node;
         newl->data = i->data;
         newl->next = NULL;
         end->next=newl;
         end=newl;
      }//end if
     }//end for

     cout<<"\n\t\tAfter Union...";
     cout<<"\n\n\t\t==List==";
     display(3); //List MRG
}

void sngllist :: intersectionList(){
     node *i,*j,*newl=NULL,*end=NULL;
     MRG=NULL;
     int flag=0;

     create(1); //Create List A
     create(2); //Create List B

     cout<<"\n\t\t*****Intersection of List*****\n";
     //Intersection  to listfor(i=A;i!=NULL;i=i->next){
    for(j=B;j!=NULL;j=j->next){
      if(i->data == j->data)
          flag=1;
     }

     if(flag==1){
          flag=0;
         if(MRG == NULL){
           newl = new node;
           newl->data = i->data;
           newl->next = NULL;
           MRG->next = newl;
           MRG = newl;
           end->next=newl;
           end=newl;
           continue;
         }
         //create memory
         newl = new node;
         newl->data = i->data;
         newl->next = NULL;
         end->next=newl;
         end=newl;
      }//end if
     }//end for

     cout<<"\n\t\tAfter Intersection...";
     cout<<"\n\n\t\t==List==";
     display(3); //List MRG
}


void main()
{
   int choice;
   sngllist obj;
   while(1){
   clrscr();
   cout<<"\n\t\tSINGLY 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)  Copy List\n";
   cout<<"\t\t8)  Reverse List\n";
   cout<<"\t\t9)  Sort List\n";
   cout<<"\t\t10) Merge List\n";
   cout<<"\t\t11) Union of List\n";
   cout<<"\t\t12) Intersection of List\n";
   cout<<"\t\t13) Exit\n";
   cout<<"\t\tEnter your Choice :  ";
   cin>>choice;
   switch(choice){
     case 1 :  obj.create(1); // 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.copy();
           break;
     case 8 :  obj.reverse();
           break;
     case 9 :  obj.sort();
           break;
     case 10 :  obj.merge();
           break;
     case 11 :  obj.unionList();
           break;
     case 12 :  obj.intersectionList();
           break;
     case 13 :  gotoout;
     default:  cout<<"\n\n\t\tInvalid Choice\n\n";
           getch();
           break;
   }
 }
 out:
}