/************************************
 * dllist.c                         *
 *                                  *
 * Andrew Vick                      *
 * PO Box 14-84                     *
 * The code for doubly linked lists *
 ************************************/

#include <strings.h>
#include <stdio.h>
#include "dllist.h"

/*Control whether the main is compiled or not*/
/*#define HAVEMAIN */
/*
Purpose: 
Preconditions: 
Postconditions: 
Problems: 
Parameters: 
Produces: 
*/

/*   
Purpose: Allocates a new node for the list.
Preconditions: Memory available for allocation.
Postconditions: Memory is allocated for a new list node.
Problems: Unknown behavior when data is null
Parameters: data - a pointer to a string, which will be copied into the data field of the new node.
Produces: A pointer to the newly created node, or NULL if it could not be created.
*/
dllist newDLListNode(char * data) {
  dllist newp = (dllist)malloc(sizeof(dllist));
  char * datap; /*= (char *)malloc(strlen(data)*sizeof(char))*/

  datap = strdup(data);

  if((newp==NULL) || (datap==NULL)) {
    free(newp);
    free(datap);
    return NULL;
  }
  newp->data = datap;
  newp->next = NULL;
  newp->prev = NULL;
  return newp;
}


/*removes the node from the list.  The node better not be still part of a 
  list.*/
/*
Purpose: Frees up the memory needed by a list node.
Preconditions: The node should be removed from any lists first.
Postconditions: The memory it occupied is available for reallocation.
Problems: None
Parameters: node - dllist structure.
Produces: Nothing
*/
void delete(dllist node) {
  free(node->data);
  free(node);
}


/*
Purpose: Inserts the new list after the existing one
Preconditions: node is not null.
Postconditions: new is joined onto the list.
Problems: none.
Parameters: node - the existing list.  Should not be null.
            new - the list to insert into the existing one.  
Produces: Nothing.
*/
void insertAfter(dllist node, dllist new){
  dllist oldnext; /*the next node, maybe null*/
  dllist oldprev; /*the previous node*/

  dllist newfront; /*the beginning of the new list*/
  dllist newback; /*the end of the new list*/

  if((new==NULL) || (node==NULL)) {
    /*Nothing to do*/
    return;
  }

  oldnext = node->next;
  oldprev = node;
  
  newfront = findEnd(new, 1);
  newback = findEnd(new, 0);

  newback->next = oldnext;
  newfront->prev = oldprev;
  
  if(oldnext!=NULL) {
    oldnext->prev = newback;
  }
  oldprev->next = newfront;
}


/*Attaches the new list in front of the existing one
Purpose: Attaches the new list before of the existing one.
Preconditions: node is not null
Postconditions: The list new is inserted before node.
Problems: None.
Parameters: node - the existing list. new - the list to insert.
Produces: Nothing.
*/
void insertBefore(dllist node, dllist new) {
  dllist oldnext=NULL; /*the next node*/
  dllist oldprev=NULL; /*the previous node, maybe null*/

  dllist newfront=NULL; /*the beginning of the new list*/
  dllist newback=NULL; /*the end of the new list*/

  if(new==NULL) {
    /*nothing to do*/
    return;
  }
  if(node==NULL) {
    return;
  }

  oldnext = node;
  oldprev = node->prev;
  
  newfront = findEnd(new, 1);
  newback = findEnd(new, 0);

  newback->next = oldnext;
  oldnext->prev = newback;

  newfront->prev = oldprev;
  if(oldprev!=NULL) {
    oldprev->next = newfront;
  }
}
  

/*
Purpose: Removes the node from the list.  Does not free up the memory.
Preconditions: node is not null
Postconditions: node is removed from the list but none of its information is 
                changed.
Problems: None.
Parameters: node - the node to remove.
Produces: The node that was passed to it.
*/
dllist takeOut(dllist node) {
  if(node->prev!=NULL) {
    node->prev->next = node->next;
  }
  if(node->next!=NULL) {
    node->next->prev = node->prev;
  }
  return node;
}


/*Creates a new list from a file and returns the first element.  If one of
  the elements of the file cannot be create (out of memory, for example)
  then what was done is returned.*/
/*File format: Each element will be on its own line, separated by a newline.
  A blank line will translate to a node with an empty data string.*/
/*
Purpose: Creates a new list from a file.
Preconditions: The file is already open with (at least) read permissions.
               The file has one list element on a line, blank lines are 
               permissible.
Postconditions: Each line of the file is its own element in a new list.  Blank
                lines become empty elements.
Problems: None.
Parameters: f - the file to read from
Produces: The first element of the list, with all the other elements attached.
*/
dllist readFromFile(FILE * f) {
  dllist ans;
  dllist current;
  dllist temp;
  char buf[256]; /*buffer for what we read*/

  /*Read the first element*/
  fgets(buf, 256, f);
  buf[strlen(buf)-1] = '\0';

  current = ans = newDLListNode(buf);
  if(current==NULL) {
    return ans; /*Nothing there*/
  }

  /*Read the rest of the elements*/
  while(fgets(buf, 256, f)!=NULL) {
    buf[strlen(buf)-1]='\0'; /*remove last \n*/
    temp = newDLListNode(buf);
    if(temp==NULL) {
      break;
    }
    insertAfter(current, temp);
    current = current->next;
  }
  return ans;
} /*readFromFile*/


/*Writes the list to a file, with each element on its own line.*/
/*
Purpose: Writes a list to a file.
Preconditions: f is opened with at least write permissions.
Postconditions: The list has been written to the file, with each element on
                its own line.
Problems: None.
Parameters: l - the list to write to file.  May be null.
            f - the file to write to
Produces: Nothing.
*/
void writeToFile(dllist l, FILE * f) {
  if(l == NULL) {
    return;
  } else {
    printf("Writing %s\n",l->data);
    fprintf(f,"%s\n",l->data);
    fflush(f);
    return writeToFile(l->next, f);
  }
} /*writeToFile*/


/*helper function to sort*/
/*
Purpose: Finds the elements in a list smaller than a particular value
Preconditions: None.
Postconditions: Nothing in the original list has changed.
Problems: None.
Parameters: l - The list of elements to compare.  May be null.
            acc - the accumulator of list elements that are smaller than data.
                  May be null.
            data - the data string to compare against.  May be null.
Produces: A list of elements smaller than data
*/
dllist findSmaller(dllist l, dllist acc, char * data) {
  if(l==NULL) {
    return NULL; /*base case*/
  }

  acc = findSmaller(l->next, acc, data);

  if(strcmp(l->data,data) < 0) {
    if(acc!=NULL) {
      insertBefore(acc,newDLListNode(l->data));
    } else {
      acc = newDLListNode(l->data);
    } /*if strcmp*/
  }

  return acc;
} /*findSmaller*/


/*helper function to sort*/
/*
Purpose: Finds the elements in a list smaller than a particular value
Preconditions: None.
Postconditions: Nothing in the original list has changed.
Problems: None.
Parameters: l - The list of elements to compare.  May be null.
            acc - the accumulator of list elements that are smaller than data.
                  May be null.
            data - the data string to compare against.  May be null. 
Produces: A list of elements smaller than data
*/
dllist findEqual(dllist l, dllist acc, char * data) {
  if(l==NULL) {
    return NULL; /*base case*/
  }

  acc = findEqual(l->next, acc, data);

  if(strcmp(l->data,data) == 0) {
    if(acc!=NULL) {
      insertBefore(acc,newDLListNode(l->data));
    } else {
      acc = newDLListNode(l->data);
    }
  } /*if strcmp*/

  return acc;
} /*findEqual*/


/*helper function to sort. l is the list to compare to, acc is the place to 
  stick matches*/
/*
Purpose: Finds the elements in a list smaller than a particular value
Preconditions: None.
Postconditions: Nothing in the original list has changed.
Problems: None.
Parameters: l - The list of elements to compare.  May be null.
            acc - the accumulator of list elements that are smaller than data.
                  May be null.
            data - the data string to compare against.  May be null.
Produces: A list of elements smaller than data
*/
dllist findLarger(dllist l, dllist acc, char * data) {
  if(l==NULL) {
    return NULL; /*base case*/
  }
  acc = findLarger(l->next, acc, data);

  if(strcmp(l->data,data) > 0) {
    if(acc!=NULL) {
      insertBefore(acc,newDLListNode(l->data));
    } else {
      acc = newDLListNode(l->data);
    }
  } /*if strcmp*/

  return acc;
} /*findLarger*/


/*Copies the list and quicksorts it.  Returns the first element of the new 
  list*/
/*   Quicksorts on lists (not arrays) */
/*
Purpose: Uses a quicksort algorithm to sort the list.
Preconditions: None.
Postconditions: The original list is not changed.
Problems: Does not bring about world peace.
Parameters: l - the list to sort.  May be null.
Produces: a sorted copy of l
*/
dllist sort(dllist l) {
  dllist pivot;
  dllist smaller;
  dllist equal;
  dllist larger;

  /*   Pick a pivot which we hope is in the middle */
  pivot = l;/*the first one*/

  /*   Base case: zero or one element in the list */
  if(l == NULL) {
    return l;
  }
  if(countElements(l) < 2) {
    return l;
  }

  /*   Split list into three - smaller, equal and larger than the pivot */
  smaller=findSmaller(l,NULL,pivot->data);
  equal = findEqual(l,NULL,pivot->data);
  larger =findLarger(l,NULL,pivot->data);

  /*   Recurse on smaller and larger */
  smaller = sort(findEnd(smaller,1));
  larger = sort(findEnd(larger,1));

  /*   Concatanate the lists */
  insertBefore(findEnd(equal,1),smaller);
  insertAfter(findEnd(equal,0),larger);

  return findEnd(equal,1); /*return the front of the list*/
} /*sort*/


/*Returns the end of the list.  The first node if lookforward is true, the last
  node otherwise*/
/*
Purpose: Finds the end of the list.
Preconditions: None.
Postconditions: l is not changed.
Problems: None.
Parameters: l - the list to find the end of
            lookforward - if this is true (nonzero), then the beginning of the
                          list is returned (l->prev->prev->...).  Else the end
                          of the list is returned (l->next->next->...)
Produces: The end element of the list.
*/
dllist findEnd(dllist l, int lookforward) {
  if(l==NULL) {
    return l;
  }
  if(lookforward) {
    if(l->prev == NULL) {
      return l;
    } else {
      return findEnd(l->prev,lookforward);
    }
  } else {
    if(l->next == NULL) {
      return l;
    } else {
      return findEnd(l->next,lookforward);
    }
  } /*else if lookforward*/
} /*findEnd*/


/*
Purpose: Helper function to countElements
Preconditions: None
Postconditions: l not altered.
Problems: None.
Parameters: l - the list to count.  May be null.
            acc - the number of elements already counted
Produces: The total number of elements in the list
*/
int count_hlpr(dllist l, int acc) {
  if(l == NULL) {
    return acc;
  } else {
    return count_hlpr(l->next,acc+1);
  }
} /*count_hlpr*/


/*Returns the number of elements in the list*/
/*
Purpose: Counts the number of elements in the list.
Preconditions: None.
Postconditions: l has not been changed.
Problems: None.
Parameters: l - the list to sort.  May be null.
Produces: The total number of elements in the list.
*/
int countElements(dllist l) {
  dllist tmp = findEnd(l,1);
  return count_hlpr(tmp, 0);
}


/*
Purpose: Prints out all the elements of the list.
Preconditions: None.
Postconditions: Each element of l has been printed to stdout, one element on a
                line.  When the printing is done, "Done printing" will be 
                printed.
Problems: None.
Parameters: l - the list to print
Produces: Nothing
*/
void printList(dllist l) {
  dllist node = findEnd(l,1);
  if(node==NULL) {
    printf("Empty list.\n");
  }
  while(node!=NULL) {
    printf("Node: \"%s\"\n",node->data);
    node = node->next;
  }
  printf("Done printing.\n");
} /*printList*/


#ifdef HAVEMAIN

/*
Purpose: The main function
Preconditions: none.
Postconditions: The program ends
Problems: None.
Parameters: None.
Produces: 0
*/
int main() {
  dllist list;
  dllist second;
  FILE * fp;
  printf("\n\n\n");
  fp = fopen("list.txt","r");
  list = readFromFile(fp);

/*   second = newDLListNode("Second one"); */
/*   insertAfter(second, newDLListNode("Second two")); */
/*   insertAfter(second->next, newDLListNode("Second three")); */

/*   printList(list); */
/*   printList(second); */

/*   insertBefore(list->next,second); */
  
  printList(list);
/*  exit(0);  */
  list = sort(list);

  printf("\nDone sorting.\n\nList length: %d\n", countElements(list));
  printList(list);

  close(fp);

  return 0;
}

#endif