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


/* Library implementing double-linked lists.
 * Authors: Dmitry Krivin
 *          Oleksiy Andriychenko
 *          Prashant Paroda
 *          D. Hawando
 *
 * Dear Sam,
 *
 *   In order to get full credit for this assignment, 
 * we have implemented a lot of different and interesting
 * methods for operating the lists, including all the basic
 * methods (adding, deleting, displaying, length), 
 * iterating the list, sorting, searching and appending
 * the lists, and even duplicating lists. In addition, our quicksort
 * pics random pivot and takes a function for comparison as a 
 * parameter. Also, we have used wrapper structure to protect
 * users from directly messing up with implementation. 
 *
 * Have fun reading this. Hope you'll enjoy our program.
 * 
 * Sincerely,
 * 
 *    - Authors.
 */

typedef struct node {
  char cont[20];
  struct node *next;
  struct node *prev;
} Listnode;


typedef struct list {
  Listnode *head;
  Listnode *tail;
  Listnode *current;
} List;



/* Creates a new list and returns a pointer to the list wrapper. */
List *createlist()
{
 List *newlist = (List *)malloc(sizeof(List));
 if (newlist==NULL)
   {
       printf("Malloc failed. Sorry. Exiting...");
       exit(1);
   }
 newlist->head=NULL;
 newlist->current=NULL;
 newlist->tail=NULL;
 return newlist;
}



/* Adds an element to front of the list. 
   Works fine if list is empty.
*/
void addtofront (List *mylist, char *contents)
{
   Listnode *dima = (Listnode *)malloc(sizeof(Listnode));
   if (dima==NULL)
     {
       printf("Malloc failed. Sorry. Exiting...");
       exit(1);
     }
   strcpy(dima->cont, contents);


   if ((mylist->head) == NULL) /* empty list */
    {    
      dima->next=NULL;
      dima->prev=NULL;
      mylist->head=dima;
      mylist->tail=dima;
      mylist->current=dima;
    }
   else                       /* list is not empty */
     {
       dima->prev=NULL;
       dima->next=mylist->head;
       mylist->head->prev=dima;
       mylist->head=dima;
     }
}




/* Adds an element to the end of the list.
   Works fine if list is empty.
*/
void addtoend(List *mylist, char *contents)
{

  Listnode *dima = (Listnode *)malloc(sizeof(Listnode));
  if (dima==NULL)
    {
      printf("Malloc failed. Sorry. Exiting...");
      exit(1);
    }
  strcpy(dima->cont, contents);

  if ((mylist->head) == NULL) /* insert in empty */
    {    
      dima->next=NULL;
      dima->prev=NULL;
      mylist->head=dima;
      mylist->tail=dima;
      mylist->current=dima;
    }
  else 
    {
      dima->next=NULL;
      dima->prev=mylist->tail;
      mylist->tail->next=dima;
      mylist->tail=dima;

    }
}



/* Checks whether the list is empty. Returns 1 (true) if empty, 0 otherwise */
int isempty (List *mylist)
{
  if((mylist->head) == NULL) return 1;
  else return 0;
}



/* Returns the size of the list */
int length (List *mylist)
{
  Listnode *temp;
  int counter=0;

  temp=mylist->head;
  while(temp!=NULL)      /* step through the list until */
    {
      counter++;
      temp=temp->next;
    }
  
  return counter;
}




/* Deletes the head of the list. If list is empty, returns 0 (error),
   otherwise returns 1. If current points on head of the list,
   current is advanced.
*/
int deletehead (List *mylist)
{
  Listnode *headnode;
  Listnode *newhead;

  if (isempty(mylist)) return 0;
  else 
    {
      headnode=mylist->head;
      newhead=headnode->next;
      
      mylist->head=newhead;

      if (newhead==NULL)           /* delete from one-element list */
        {
          mylist->current=NULL;
          mylist->tail=NULL;
        }                     
      else
        {
          if (mylist->current==headnode)
            mylist->current=newhead;
          
          newhead->prev=NULL;
        }
      free(headnode);         
      return 1;
    }
}


/* Deletes the tail of the list. If list is empty, returns 0 (error),
   otherwise returns 1. If current points on tail of the list,
   current is changed to previous element.
*/
int deletetail (List *mylist)
{
  Listnode *tailnode;

  if (isempty(mylist)) return 0;
  else 
    {
      if (length(mylist)==1) deletehead(mylist);
      else
        {
         
          tailnode=mylist->tail;
          if (mylist->current==tailnode) mylist->current=tailnode->prev;
          (tailnode->prev)->next=NULL;
          mylist->tail=tailnode->prev;
          free(tailnode);
        }
      return 1;
    }
}




/* Moves the cursor to head of the list. If list is empty, current will 
   be NULL.
*/
void resettohead(List *mylist)
{
  mylist->current=mylist->head;
}

/* Moves the cursor to tail of the list. If list is empty, current will 
   be NULL.
*/
void resettotail(List *mylist)
{
  mylist->current=mylist->tail;
}



/* Places cursor at element with a given position. Valid values - from
   1 to length(mylist). Function returns 0 if position is out of range,
   or 1 for success
*/
int placecursor (List *mylist,int position)
{
  int i;

  if ((position<1) || (position > length(mylist)))
    return 0;
  else 
    {
      resettohead(mylist);
      for (i=1;i<position;i++)
          advance(mylist);
        
      return 1;
    }
}



/* Moves cursor one element back. Returns 0 if list is empty or
   cursor is on the head of the list. Otherwise returns 1.
 */
int retreat(List *mylist)
{
  if (isempty(mylist)) return 0;
  else
    {
      if (((mylist->current)->prev)==NULL) return 0;
      else
        {
          mylist->current=(mylist->current)->prev;
          return 1;
        }
    }
}


/* Advances. Returns 0 if list is empty or  cursor is on the tail of the 
   list. Otherwise returns 1.
 */
int advance(List *mylist)
{
  if (isempty(mylist)) return 0;
  else
    {
      if (((mylist->current)->next)==NULL) return 0;
      else
        {
          mylist->current=(mylist->current)->next;
          return 1;
        }
    }
}


/* Adds an element after the cursor. Works fine for empty lists. */
void addaftercursor(List *mylist, char *contents)
{
  
  Listnode *dima;


  if((mylist->head)==NULL)           /* Empty list */
     addtofront(mylist, contents);
     else
     {
       if ((mylist->current)==(mylist->tail)) 
         addtoend(mylist,contents);
       else
         {
           dima = (Listnode *)malloc(sizeof(Listnode));
           if (dima==NULL)
             {
               printf("Malloc failed. Sorry, sugarpies. Exiting...");
               exit(1);
             }
           strcpy(dima->cont, contents);            
           dima->next = (mylist->current)->next;    /* updating pointers.*/
           ((mylist->current)->next)->prev = dima;
           (mylist->current)->next = dima;
           dima->prev = mylist->current;
          
        }
     }
}

           
/* Deletes current element. Returns 1 for success, and 0 for error (list
   is empty). Cursor goes to next element, if it exists, or retreats one
   element back otherwise. If resulting list is empty, cursor is NULL.
*/
int deletecurrent (List *mylist)
{
  Listnode *oleksiy;
  if ((mylist->head)==NULL) return 0;
  else
    {
      if ((mylist->current)==(mylist->head))
        return(deletehead(mylist));
      else
        {
          if ((mylist->current)==(mylist->tail))
            return(deletetail(mylist));
          else
            {
              oleksiy=mylist->current;
              (oleksiy->prev)->next=oleksiy->next;
              (oleksiy->next)->prev=oleksiy->prev;
              mylist->current=oleksiy->next;      /* next element exits */

              free(oleksiy);
             
              return 1;
            }
        }
    }
}


/* Creates a copy of this list and returns a pointer to new list. */
List *duplicate(List *mylist)
{
  Listnode *oldcurrent;
  List *newlist=createlist();
  Listnode *dima;


  oldcurrent=mylist->current;           /* save current element */
  mylist->current=mylist->head->next;


  if ((mylist->head)!=NULL)
    {

      addtoend(newlist, mylist->head->cont); /* list is not empty. 
                                                create head. */

      while((mylist->current)!=NULL)   /* copy all the rest nodes */
        {
          dima=(Listnode *)malloc(sizeof(Listnode));
          if (dima==NULL)
            {
              printf("Malloc failed. Sorry, sugarpies. Exiting...");
              exit(1);
            }
      
          
          dima->prev=newlist->tail;  /* tail is poining on previous node */
          newlist->tail->next=dima;

          strcpy(dima->cont, mylist->current->cont);
          mylist->current=mylist->current->next;
          
          newlist->tail=dima;
        }
      
      dima->next=NULL; /* last to NULL */
      newlist->current=oldcurrent; /* set cursor */
    }
  mylist->current=oldcurrent;       /* restore cursor */
return newlist;
}
      
     

/* Useful function for destroying lists. Frees the memory occupied
   by List structure and each individual node.
*/
void destroylist(List *mylist)
{
  Listnode *dima,*oleksiy;
  
  dima=mylist->head;
  
  while(dima!=NULL)
    {
      /* not sure if free(ptr) changes ptr. probably not,
         but lets be on a safe side */

      oleksiy=dima->next;
      free(dima);
      dima=oleksiy;
    }

  free(mylist);
}
 
      
/* Returns the pointer to c_o_p_y of contents of current node. Copy is
   used since we don't want users to directly change contents.
*/
char *getcurrent(List *mylist)
{
  char *temp;

  if (mylist->current==NULL)
    return NULL;
  else
    {
      temp=(char*)malloc(20);
      strcpy(temp, mylist->current->cont);
      return temp;
    }
}


/* Changes the contents of current node in the list. Returns 1 for success,
   0 for failure (list is empty).
*/
int changecurrent(List *mylist, char *contents)
{
  if (mylist->current==NULL) return 0;  /* empty list */
  else
    {
      strcpy(mylist->current->cont, contents); /* all good */
      return 1;
    }
}

/* Writes list to a file (one entry per line). Returns 1 for success,
   or 0 if for some obscure reason the file cannot be created.
*/
int writetofile (List *mylist, char *filename)
{
  FILE *prashant;
  Listnode *temp;  /* pointer for browsing the list */

  temp = mylist->head;
  prashant = fopen(filename, "w");
  if (prashant == NULL)
    return 0;
  else 
    {
      
      while(temp!=NULL)
        {
          fprintf(prashant, "%s\n",temp->cont);
          temp=temp->next;
        }
      
      fclose(prashant);
      return 1;
    }
}
 
 
/* Writes list to screen (we hope it never fails.. joke) */
void writetoscreen (List *mylist)
{
  Listnode *temp;
  temp = mylist->head;

  while(temp!=NULL)
    {
      printf("%s\n",temp->cont);
      temp=temp->next;
    }
}


/* Reads a list from file. Precondition - file contains valid list. If
   the file cannot be opened, returns 0, otherwise returns 1
*/
List *readfromfile (char *filename)
{
  FILE *prashant;
  List *oleksiy;
  char samr[20];  /* sam - this is for you */
  

  prashant=fopen(filename,"r");

  oleksiy = createlist();

  if(prashant!=NULL)
    {
      fscanf(prashant,"%s",samr);
      while(!feof(prashant))
        {          
          addtoend(oleksiy,samr);
          fscanf(prashant,"%s",samr);
        }
    }
  return oleksiy;
}
        
         
/* Finds the element in the list. Only part of list from current to end
   is examined (including current element). If element is found - 
   sets current to this element and returns 1. If element is not 
   found - current is not changed, function returns 0
*/
int find(List *mylist, char *elem)
{
  Listnode *dima;

  if(isempty(mylist))
    return 0;


  /* Ok, list is not empty, so mylist->current is not NULL */
  dima=mylist->current->next;
  

  while(dima!=NULL)     /* lets go through the list until end is reached */
    {
      if(strcmp(elem,dima->cont)==0)
        {
          mylist->current=dima;
          return 1;
        }
      else dima=dima->next;
    }
  return 0;
}




/* Sorts a list using quicksort - O(n logn) on average, O(n^2) in worst case.
   In order to increase our grade, pivot is picked at random, and one of
   parameters - pointer to comparison function. Comparison function should
   return integer less than, equal to and greater than 0, depending on
   whether string 1 is less than, equal to or greater than 0.
*/ 
void quicksort(List *mylist, int (*compar)(char *,char *))
{
  int i;
  float j;
 

  List *lesslist, *greatlist, *equallist,*tmp;
  char pivot[20];


  if (mylist->head!=NULL)  /* if list is not empty. otherwise do nothing */
    {
 
      j=(float)(rand())/32768.1;
      i=(int)(j*length(mylist))+1;    /* picks a pivot */
      placecursor(mylist, i);
      strcpy(pivot,mylist->current->cont);
      
      lesslist=createlist();
      greatlist=createlist();
      equallist=createlist();
      tmp=createlist();
      
      resettohead(mylist);

      while(mylist->current!=NULL)
        {
          j = (*compar)(mylist->current->cont, pivot);
          if (j==0)
            addtoend(equallist, mylist->current->cont);
          else if(j<0)
            addtoend(lesslist, mylist->current->cont);
          else addtoend(greatlist, mylist->current->cont);
          
          mylist->current=mylist->current->next;
        }

      quicksort(lesslist,(int (*)(char*, char*))strcmp);
      quicksort(greatlist,(int (*)(char*, char*))strcmp);


     
      append(lesslist,equallist);
      append(lesslist,greatlist);

      
      tmp->head=mylist->head;
      tmp->tail=mylist->tail;
      destroylist(tmp);           /* deletes old list */

      mylist->head=lesslist->head; /* mylist now should refer */ 
      mylist->tail=lesslist->tail; /* to the new sorted list */
      mylist->current=mylist->head;

      free(lesslist);            /* deletes list structures */
      free(equallist);
      free(greatlist);

      

    }
}



/* Appends list 2 to end of list 1. Post: List 1 is now a joined list.
   List 2 is empty list (implementation choice).
*/
void append(List *list1, List *list2)
{
  if(isempty(list1))      /* works fine if both lists are empty */
    {
      list1->head=list2->head;
      list1->tail=list2->tail;
      list1->current=list2->current;

      list2->head=NULL;       /* make list2 empty */
      list2->tail=NULL;
      list2->current=NULL;
    }
  else if (!isempty(list2))  /* both lists are not empty */
    {
      list2->head->prev=list1->tail;  /* fix the pointers.*/
      list1->tail->next=list2->head;
      list1->tail=list2->tail;

      list2->head=NULL;       /* make list2 empty */
      list2->tail=NULL;
      list2->current=NULL;
      
    }
  /* second list is empty - > do nothing */
}