/* liststuff.c
 * Authors: Pete Broadwell
 *          Josh Vickery
 * this file contains various operations one may perform upon linked lists
 */

#include "ll_defs.h"

/* create a list. returns a pointer to the list, takes an existing node */
llist *create_l(node *nnode) {
  llist *new_list;
  /* allocate memory for the list */
  new_list=(llist *) malloc(sizeof(llist));

  if (new_list == NULL) {
    printf("Cannot allocate memory for new list!\n");
    exit(1);
  }
 
  /* set the values of the list */ 
  new_list->first=(node *)nnode;
  new_list->current=(node *)nnode;
  new_list->last=(node *)nnode;
  
  return(new_list);
}

/* add a node to the end of a list.
 * takes pointers to the list and the node to be added,
 * returns the new and improved list
 */
llist *add_to_end(llist *clist, node *cnode) {

  if (clist == NULL)
    return (llist *)create_l(cnode);
  else {
    cnode->previous=(node *)clist->last;
    clist->last->next=(node *)cnode;
    clist->last=(node *)cnode;
    return(clist);
  }
}

/* add a node to the front of a list
 * takes pointers to the list and the node to be added,
 * returns the new and imrpoved list
 */

llist *add_to_front(llist *clist, node *cnode) {
  
  if (clist == NULL)
    return (llist *)create_l(cnode);
  else {
      cnode->next=(node *)clist->first;
      clist->first->previous=(node *)cnode;
      clist->first=(node *)cnode;
      return(clist);
  }
}

/* advance the cursor of a list, takes a pointer to a list, and updates the 
 * cursor, returns the cursor pointer
 */

node *advance_cursor(llist *clist) {

  if (clist->current==clist->last){
    printf("Cannot advance past last element. Nothing changed.\n");
    return clist->current;    
  }
  clist->current=(node *)clist->current->next;
  return clist->current;
}

/* backup the cursor of a list, takes a pointer to a list, and updates the 
 * cursor, returns the cursor pointer
 */

node *backup_cursor(llist *clist) {
 
  if (clist->current==clist->first){
    printf("Cannot backup past first element. Nothing changed.\n");
    return clist->current;
  }
  clist->current=(node *)clist->current->previous;
  return clist->current;
}
/* move the cursor to the front of the list
 * takes a pointer to the list, returns the new position of the cursor
 */

node *tofront(llist *clist) {

  clist->current=(node *)clist->first;
  return clist->current;
}

/*move the cursor to the end of the list
 * takes a pointer to the list, returns the new position of the cursor
 */

node *toend(llist *clist) {

  clist->current=(node *)clist->last;
  return clist->current;
}

/* deletes the current node in a list, free up the memory used by it 
 * updates current to be NULL
 * This function is called from the interactive loop of fun_with_lists,
 * where it is immediately followed by a tofront() function call,
 * which resets the current pointer to the first element of the list
 */

llist *delete_element(llist *clist) {

  /* case for an empty list */
  if (clist==NULL)
    printf("List is empty. Nothing done.\n"); 

  /* case for a one-element list */
  else if (clist->first==clist->last){
    clist->first=NULL;
    clist->last=NULL;
    free(clist->current);
    clist->current=NULL;
  }
  else if (clist->current==clist->first){
    clist->first=clist->first->next;
    clist->first->previous=NULL;
    free(clist->current);
    clist->current=NULL;
  }
  else if (clist->current==clist->last){
    clist->last=clist->last->previous;
    clist->last->next=NULL;
    free(clist->current);
    clist->current=NULL;
  }
  else {
    clist->current->previous->next=(node *)clist->current->next;
    clist->current->next->previous=(node *)clist->current->previous;
    free(clist->current);
    clist->current=NULL;
  }
  return clist;
}

/* This function deletes a list, it deletes every element in a list, and
 * then frees the pointer to the list
 */

delete_l(llist *clist) {
 if (clist != NULL){
   clist->current=(node *)tofront(clist);
   if (clist->first==clist->last){
      clist = (llist *)delete_element(clist);
   }
   else {
      clist = (llist *)delete_element(clist);
      do {
	if (clist->first==clist->last){
	    clist = (llist *)delete_element(clist);
	}
	else {
	   clist->current=(node *)tofront(clist);
	   clist = (llist *)delete_element(clist);
        }
      }
      while(clist->first!=clist->last);
   }
  free(clist);
 }   
	
}

/* counts the number of nodes on a list. It is important to know this
 * number, especially when breaking up the list during quicksort (otherwise,
 * nodes can get left out of the quicksort
 */
int count_nodes(llist *clist) {
  int count=0;

/* moves forward from the first element of the list until it hits the last
 * one, incrementing its counter as it goes.
 * When it hits the end, it resets the cursor to the first element of the
 * list. Takes a pointer to the list, returns the size of list (an integer).
 */
  if(clist==NULL)
    return count;
  else {
    count++;
    clist->current=(node *)tofront(clist);
    while (clist->current != clist->last){
      count++;
      clist->current=(node *)advance_cursor(clist); 
    }
    clist->current=(node *)tofront(clist);
    return count;
  }
}

/* concatenates 2 lists, returns a new list, and frees up the memory that
 * the other two lists where using.  If a list is null, returns the other
 * list, if both lists are null, return null.  Frees up unused memory
 * Called in quicksort.
 */

llist *conclists(llist *list1, llist *list2) {
  llist *nlist;
  
   if( (list1 == NULL) && (list2 == NULL) )
     return NULL;
   
   else if (list1 == NULL)
     return list2;
   
   else if (list2 == NULL)
     return list1;
   
   else {
     
     list1->current=tofront(list1);
     
     nlist = (llist *)create_l((node *)list1->first);
     
     if(list1->current != list1->last) {
       
       do {
  	   list1->current=(node *)advance_cursor(list1); 
	   nlist = (llist *)add_to_end(nlist, list1->current);
       }
       while (list1->current != list1->last);
     }
     list2->current=(node *)tofront(list2);	
     nlist = (llist *)add_to_end(nlist, list2->first);
     
     if(list2->current != list2->last) {
       
       do {		
	 list2->current=(node *)advance_cursor(list2);
	 nlist = (llist *)add_to_end(nlist, list2->current);
       }
       while(list2->current != list2->last);
     }
 
     nlist->current = (node *)tofront(nlist);
     
     return nlist;
     delete_l(list1);
     delete_l(list2);
   }
}