#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct emp_s{
   int id;
   char name[20];
   struct emp_s *pNext;
}emp_t;

emp_t *pHead = NULL;
int totalNodes = 0;

emp_t* fillData(void);
void addAtFront(void);
void display(void);
void addAtEnd(void);
void delete(int);
void insert(void);
emp_t* linearSearch(int );
emp_t* findMiddle(emp_t*, emp_t*);
void printMiddle(void);
emp_t* binarySearch(int id);
void selectionSort(void);
void bubbleSort(void);
void reverseList(void);
int main()
{
    int choice;
    int id;
    emp_t* pTemp;

    while(1)
    {
        printf("Add at front: 1\n");
        printf("Add at end: 2\n");
        printf("display: 3\n");
        printf("delete: 4\n");
        printf("insert : 5\n");
        printf("linear serch : 6\n");
        printf("binary Search : 7\n");
        printf("selection sort : 8\n");
        printf("bubble sort : 9\n");
        printf("print middle : 10\n");
        printf("Reverse list: 11\n");

        printf("Enter your choice\n");
        scanf("%d", &choice);

        switch(choice)
        {
           case 1: 
                addAtFront();
                totalNodes++;
                break;

            case 2:
                addAtEnd();
                totalNodes++;
                break;

            case 3:
                display();
                break;
            
            case 4:
                printf("Enter id of employee to delete\n");
                scanf("%d", &id);
                delete(id);
                totalNodes--;
                break;

            case 5:
                insert();
                totalNodes++;
                break;

            case 6:
                printf("Enter ID for serch\n");
                scanf("%d", &id);
                pTemp = linearSearch(id);
                if(pTemp != NULL)
                {
                   printf("Employee ID: %d\n", pTemp->id);
                   printf("Employee Name: %s\n", pTemp->name);
                }
                else
                   printf("there is no node with the passed ID\n");

                break;

            case 7:
               // pTemp = findMiddle();
                printf("Enter ID for serch\n");
                scanf("%d", &id);
                pTemp = binarySearch(id);
                if(pTemp != NULL)
                {
                   printf("Employee ID: %d\n", pTemp->id);
                   printf("Employee Name: %s\n", pTemp->name);
                }
                else
                   printf("there is no Linked list\n");
                break;

            case 8:
                selectionSort();
                break;

            case 9:
                bubbleSort();
                break;

            case 10:
                printMiddle();
                break;

            case 11:
                reverseList();
                break;

            default:
                exit(0);
         }
     }
     return 0;
}

emp_t* fillData(void)
{
    emp_t *new;
    new = malloc(sizeof(emp_t));
    
    printf("Enter ID of employee\n");
    scanf("%d", &new->id);

    printf("Enter name of employee\n");
    scanf("%s", new->name);

    new->pNext = NULL;

    return new;
}


void addAtFront(void)
{
  emp_t *new;
   
  new = fillData();
  
  if(pHead == NULL)
  {
    pHead = new;
    pHead->pNext = NULL;
  }
  else
  {
    new->pNext = pHead;
    pHead = new;
  }
}
   
        

void display(void)
{
    emp_t *pTemp;
    
    pTemp = pHead;
    while(pTemp != NULL)
    {
       printf("Employee ID: %d\n", pTemp->id);
       printf("Employee Name: %s\n", pTemp->name);
       pTemp = pTemp->pNext;
    }
}

   
void addAtEnd(void)
{
   
  emp_t *new;
  emp_t *pTemp;
   
  new = fillData();

  if(pHead == NULL)
  {
    pHead = new;
    pHead->pNext = NULL;
  }
  else
  {
    pTemp = pHead;
    while(pTemp->pNext != NULL)
     pTemp = pTemp->pNext;
    pTemp->pNext = new;
  }
}
 

void delete(int id)
{
    emp_t *old;
    emp_t *pTemp;

    if(pHead == NULL)
    {
      printf("List is NULL\n");
      return;
    }

    pTemp = pHead;
    while(pTemp != NULL)
    {
       if(pTemp->id == id)
       {
          if(pTemp == pHead)
          {
             pHead = pHead->pNext;
             free(pTemp);
             return;
          }
          else
          {
             old->pNext = pTemp->pNext;
             free(pTemp);
             return;
          }
       }
       else
       {
         old = pTemp;
         pTemp = pTemp->pNext;
       }
    }

}


void insert(void)
{
  emp_t *new;
  emp_t *pTemp;
  emp_t *current;
 
  
  new = fillData();
  pTemp = pHead; 
     
  if(pHead == NULL || pHead->id > new->id)
  {
     new->pNext = pHead;
     pHead = new;
  }
  else
  {
     current = pHead;
     while(current->pNext != NULL && current->pNext->id < new->id)
     {
        current = current->pNext; 

     }
     new->pNext = current->pNext; 
     current->pNext = new;
  }

}

emp_t* linearSearch(int id)
{
    emp_t* pTemp = pHead;

    while(pTemp != NULL)
    {
       if(pTemp->id == id)
         return pTemp;
       else
         pTemp = pTemp->pNext;
    }
    return NULL;
}

emp_t* findMiddle(emp_t *startNode, emp_t *endNode)
{
   int i;
   emp_t *pTemp = startNode;
   emp_t *pMiddle = NULL;
   
   for(i = 1; pTemp != endNode; pTemp = pTemp->pNext, i++)
   {
      if(i == 1)
        pMiddle = pTemp;
      else if(i%2 == 1)
        pMiddle = pMiddle->pNext;
   }
   return pMiddle;
}


emp_t* binarySearch(int id)
{
   emp_t *pMiddle = NULL;
   emp_t *startNode = pHead; 
   emp_t *endNode = NULL;
  
   do{
        pMiddle = findMiddle(startNode,endNode);
        if(pMiddle == NULL)
        {
           return NULL;
        }
        else if(pMiddle->id == id)
        {
           return pMiddle;
           break;
        }
        else if(pMiddle->id < id)
        {
          startNode = pMiddle->pNext;
        }
        else
        {
          endNode = pMiddle;
        }
     }while(endNode == NULL || endNode != pMiddle->pNext);
   return NULL;
}
         
void selectionSort(void)
{
   emp_t *p, *q;
   int i, j; 
   int tempId;
   char tempName[20];
   p = pHead;
   for(i = 0; i < totalNodes - 1; i++)
   {
      q = p->pNext;
      for(j = 1; j < totalNodes -1; j++)
      {
         if(p->id > q->id)
         {
            tempId = p->id;
            strcpy(tempName, p->name);
            p->id = q->id;
            strcpy(p->name, q->name);
            q->id = tempId;
            strcpy(q->name, tempName);
         }
         q = q->pNext;
      }
      p = p->pNext;
    }
}

void bubbleSort(void)
{
   emp_t *p, *q;
   int i, j, k; 
   int tempId;
   char tempName[20];
   k = totalNodes;

   for(i = 0; i < totalNodes -1; i++, k--)
   {
     p = pHead;
     q = p->pNext;
     for(j = 1; j < k; j++)
     {
         if(p->id > q->id)
         {
            tempId = p->id;
            strcpy(tempName, p->name);
            p->id = q->id;
            strcpy(p->name, q->name);
            q->id = tempId;
            strcpy(q->name, tempName);
         }
         p = p->pNext;
         q = q->pNext;
      }
   }
}

void printMiddle(void)
{
  emp_t* pTemp = NULL;
  emp_t* pMiddle = pHead;
  int count = 0;

  pTemp = pHead;
  while(pTemp != NULL)
  {
    if(count & 1)
      pMiddle = pMiddle->pNext;
    count++;
    pTemp = pTemp->pNext;
  }
  if(pMiddle != NULL)
  {
    printf("Id of Middle :%d\n", pMiddle->id);
    printf("Name of Middle :%s\n", pMiddle->name);
  } 

}
  
void reverseList(void)
{
  emp_t *current;
  emp_t *next;
  emp_t *prev;

  current = pHead;
  while(current != NULL)
  {
    //store next
     next = current->pNext;
    //reverse current pointer
     current->pNext = prev;
    //move both pointers
     prev = current;
     current = next;
  }
  pHead = prev;
}