#include "doublylinkedlist.h"
#include <string.h>
#include <time.h>
#include <stdarg.h>
#include <stdlib.h>
#include <strings.h>

/**
 * This file contains the bodies of all functions used for doing stuff with our doubly-linked lists.
 * Yes, they should maybe be split up into separate files, but it's 3:40 AM, and we've been working on
 * this assignment since the day after it was assigned, so they won't be.
 * Lists in this library are treated similarly to strings in C, with a pointer to the first element in the
 * list being passed to functions.
 * @author Brian K. Smith and Erik D. Hanson
 * @version 1.0 of 2-18-2000
 */

//+---------------------------------------+
//| List input and output functions       |
//+---------------------------------------+

/**
 * Read a list from a stream written using the
 * write_list_to_file function, or any stream with newline separated values.
 * @param fp The file pointer from which to read the list.
 * @return A pointer to the first node in the list.
 */
struct dllnode *read_list_from_file(FILE *fp) 
{
  //Declare variables.
  char *data;
  struct dllnode *first_n;
  //Initialize data.
  first_n = make_new_node();
  first_n->next = NULL;
  first_n->prev = NULL;
  data = (char *) malloc(MAX_DATA_LENGTH);
  if(!data) {
    fprintf(stderr, "Error in read_list_from_file!\nFailed to allocate space for data.\n");
    exit(1);
  }//if
  //If the stream exists, try to read it.
  if(fp) {
    //If we have not reached the end of the file, build the first node in the list.
    if(fgets(data, MAX_DATA_LENGTH, fp)) {
      //Try to allocate space for the node contents.  Die screaming if we fail.
      first_n->data = (char *) malloc(MAX_DATA_LENGTH);
      if(!first_n->data) {
        fprintf(stderr, "Error in read_list_from_file!\nFailed to allocate space for data.\n");
        exit(1);
      }//if
      //Trim the trailing newline character given by fgets, if it exists.
      if (data[strlen(data)-1] == '\n') {
        data[strlen(data)-1] = '\0';
      }//if
      //Copy string into node.
      strcpy(first_n->data, data);
    }//if
    //If we have reached the end of the file, die screaming about the wicked empty file!
    else {
      fprintf(stderr, "Error in read_list_from_file!\nNo data in file.\n");
      exit(1);
    }//else
    //As long as we have not reached the end of the file, make more nodes for our happily growing list.
    while(fgets(data, MAX_DATA_LENGTH, fp)) {
      if (data[strlen(data)-1] == '\n') {
        data[strlen(data)-1] = '\0';
      }//if
      if(add_element_to_list(first_n, data)) {
        fprintf(stderr, "Error in read_list_from_file!\nAdd_element_to_list indicated failure.");
        exit(1);
      }//if
    }//while
    return first_n;
  }//if(fp)
  //If the file pointer was bad, complain about it.
  else {
    fprintf(stderr, "Error in read_list_from_file!\nNo file could be found.\n");
    exit(1);
  }//else
}//read_list_from_file

/**
 * Write a list to a stream, so that it can be read later by
 * the read_list_from_file function.
 * @param stream The stream to which to write the list.
 * @param first_n The first node in the list to write to the stream.
 * @return 0 if successful, 1 if not
 */
int write_list_to_file(FILE *stream, struct dllnode *first_n) 
{
  //Declare variables.
  struct dllnode *n;
  //Initialize variables.
  n = first_n;
  //Check to see if the stream exists.
  if(stream) {
    //Iterate through the list, writing each data element to the stream.
    while (has_next_element(n)) {
      fprintf(stream, "%s\n", n->data);
      n = get_next_element(n);
    }//while
    //Take care of the last node.
    fprintf(stream, "%s\n", n->data);
    return 0;
  }//if(stream)
  //If the stream does not exist, complain about it and return with an error.
  else {
    fprintf(stderr, "Error in write_list_to_file!\nThe stream to write to is null.\n");
    return 1;
  }//else
}//write_list_to_file

/**
 * Write the details of a list to a stream.
 * @param stream The stream to which to write the list.
 * @param first_n The first node in the list to write to the stream.
 * @return 0 if successful, 1 if not
 */
int write_list_details(FILE *stream, struct dllnode *first_n)
{
  //Declare variables.
  struct dllnode *n;
  //Initialize variables.
  n = first_n;
  //Check to see if stream exists.
  if(stream) {
    //Iterate through the list, writing details about each data element to the stream.
    while (has_next_element(n)) {
      fprintf(stream, "own address: %p, previous: %p, data: %s, next: %p\n", *n, n->prev, n->data, n->next);
      n = get_next_element(n);
    }//while
    //Take care of the last element.
    fprintf(stream, "own address: %p, previous: %p, data: %s, next: %p\n", *n, n->prev, n->data, n->next);
    return 0;
  }//if
  //If the stream does not exist, complain about it and return with an error.
  else {
    fprintf(stderr, "Error in write_list_details!\nThe stream to write to is null.\n");
    return 1;
  }//else
}//write_list_details


//+------------------------------------------------+
//| List manipulation functions                    |
//+------------------------------------------------+

/**
 * Add an element to the end of a list.
 * @param first_n The first node of the list.
 * @param element The string to add to the list.
 * @return 0 if successful, 1 if not
 */
int add_element_to_list(struct dllnode *first_n, char *element) 
{
  //Declare variables.
  struct dllnode *old_last;
  struct dllnode *new_last;
  //Initialise variables.
  new_last = make_new_node();
  new_last->next = NULL;
  old_last = get_last_node(first_n);
  new_last->data = (char *) malloc(MAX_DATA_LENGTH);
  //Check to see if memory was allocated correctly.
  if(!new_last->data) {
    fprintf(stderr, "Error in add_element_to_list!  Failed to allocate memory for list data.");
    return 1;
  }//if
  //Make everything point to the right place.
  strcpy(new_last->data, element);
  new_last->prev = old_last;
  old_last->next = new_last;
  return 0;
}//add_element_to_list

/**
 * Remove an element from a list.
 * @param first_n The list from which to remove node num.
 * @param num The node to remove from the list.
 * @return The first node in the new list which has n removed.
 */
struct dllnode *remove_element_from_list(struct dllnode *first_n, int num) 
{
  //Declare variables.
  struct dllnode *next;
  struct dllnode *previous;
  struct dllnode *n;
  //Initialize variables.
  n = list_element_at(first_n, num);
  //If there is an element in the list following the one we want to remove, do this.
  if (has_next_element(n)) {
    //Keep track of the next of the node to be removed.
    next = n->next;
    //If n is the first node in the list, change first_n so that it will be correct when we return it.
    if(n == first_n) {
      first_n = get_next_element(first_n);
    }//if
  }//if
  //If there is an element in the list prior to the one we want to remove, do this.
  if (has_previous_element(n)) {
    //Keep track of the previous of the node to be removed.
    previous = n->prev;
  }//if
  //If the node to be deleted was somewhere in the middle of the list.
  if (has_next_element(n) && has_previous_element(n)) {
    //Make it's previous and next look at each other.
    next->prev = previous;
    previous->next = next;
  }//if
  //If the node to be deleted is the first element in the list, make next's previous null.
  else if (has_next_element(n)){
    next->prev = NULL;
  }//else if
  //If the node to be deleted is the last element in the list, make previous's next null.
  else if (has_previous_element(n)) {
    previous->next = NULL;
  }//else if
  //Clean up after the node we are removing.
  free(n->data);
  memset(n, '\0', sizeof(struct dllnode));
  //Return.
  return first_n;
}//remove_element_from_list

/**
 * This variable arity function takes one or more lists as arguments
 * and concatenates the lists.  It returns the new list (which is the same
 * as the first list passed to the function.
 * @param one The first list to cat.
 * @param num The number of lists we will be concatenating.
 * @param ... Zero or more additional lists to concatenate.
 * @return The first list.
 */
struct dllnode *concatenate_lists(int num, struct dllnode *one, ...) {
  //Declare variables.
  va_list ap; //points to each unnamed arg in turn
  struct dllnode *current_first, *next_first, *current_last;
  //Initialize variables.
  current_first = one;
  //Because one gives no clues about whether or not there is another list following it,
  //we must explicitly give this function the number of things it should concatenate.
  //If there is more than one thing to concatenate, do the interesting things.
  if(num > 1) {
    //Set up the variable arity doohickey.
    va_start(ap, one);
    //As long as there are more lists to concatenate, try to do so.
    while(num > 1) {
      //Get the next first_node passed as an argument.
      next_first = va_arg(ap, struct dllnode *);
      //Set the last node for the list we are adding on to.
      current_last = get_last_node(current_first);
      //Make sure that we don't set up a list that eats its own tail.
      if(next_first != one) {
        //Set the next of the last node in the string we are adding on to.
        current_last->next = next_first;
      }//if
      //Continue our anti-snake stuff.
      else {
        current_last->next = NULL;
      }//else
      //Make the previous of the first node in the list we are adding on to the current one
      //point to the last node in the list we are adding on to.
      next_first->prev = current_last;
      //If we've somehow set up a loop in this step, kill it!
      if(next_first->prev == next_first->next) {
        next_first->next = NULL;
      }
      //Set up for the next iteration.
      current_first = next_first;
      num--;
    }//while
  }//if
  //Clean up the variable arity doohickey.
  va_end(ap);
  return one;
}//concatenate_lists

/**
 * Delete a list and free all memory associated with that list.
 * Clarification:  This function does not free the strings associated
 * with the node, as doing so was causing all sorts of problems, even
 * though we used strcpy everywhere relevant.
 * @param first_n The first node in the list to be deleted.
 * @return 0 if successful, 1 if not
 */
int delete_list(struct dllnode *first_n) {
  //Declare variables.
  struct dllnode *n;
  struct dllnode *temp;
  //Initialise variables.
  n = first_n;
  //Iterate through the nodes.
  while(has_next_element(n)) {
    //Keep track of the next so that we can get to it after we kill the current node.
    temp = n->next;
    //Smash!
    memset(n, '\0', sizeof(struct dllnode));
    //Set up for next iteration.
    n = temp;
  }//while
  //Take care of the final node.
  memset(n, '\0', sizeof(struct dllnode));
  return 0;
}//delete_list

/**
 * Get the last element in a doubly linked list.
 * @param first_n The first node in the list in question.
 * @return 0 if successful, 1 if not
 */
struct dllnode *get_last_node(struct dllnode *first_n) {
  //Declare variables.
  struct dllnode *n;
  //Initialize variables.
  n = first_n;
  //Keep getting the next node until you've got the last one.
  //Pretty simple.
  while(has_next_element(n)) {
    n = get_next_element(n);
  }//while
  return n;
}//get_last_node

/**
 * Get the next element in a doubly linked list.

 * With no information hiding in use, this function is pretty pointless.
 * @param n The element we are currently at.
 * @return The next element in the list.
 */
struct dllnode *get_next_element(struct dllnode *n) 
{
  return n->next;
}//get_next_element

/**
 * Get the previous element in a doubly linked list.
 * With no information hiding in use, this function is pretty pointless.
 * @param n The element we are currently at.
 * @return The previous element in the list.
 */
struct dllnode *get_prev_element(struct dllnode *n) 
{
  return n->prev;
}//get_prev_element

/**
 * Sort a list so that the data is arranged in ascending order.
 * (The first element is alphabetically before the second element, etc.)
 * For best results, the caller should try to call srand(int) with something useful
 * before calling this function.
 * @param first_n The first node in the list to be sorted.
 * @return The first node in the newly sorted list.
 */
struct dllnode *quicksort_list(struct dllnode *first_n) {
  //Declare variables.
  struct dllnode *smaller;
  struct dllnode *larger;
  struct dllnode *current;
  struct dllnode *old_second;
  int pivot_num, count, length, all_the_same_flag;
  char *pivot_string;
  //Initialise variables.
  all_the_same_flag = 1;
  pivot_string = (char *) malloc(MAX_DATA_LENGTH);
  //Make sure the malloc worked out.
  if(!pivot_string) {
    fprintf(stderr, "Error in quicksort_list!\nFailed to allocate data for the pivot_string.");
    exit(1);
  }//if
  length = list_length(first_n);
  larger = make_new_node();
  smaller = make_new_node();
  old_second = get_next_element(first_n);
  //If the list has only one element, return that element, because we are done recursing.
  if (length == 1) {
    return first_n;
  }
  //Assign the first element in the list to the current node.
  current = first_n;
  //Pick a pivot
  pivot_num = rand() % length;
  //Here the pivot string is assigned.
  strcpy(pivot_string, list_element_at(first_n, pivot_num)->data);
  //Split into 2 parts: a list that contains the nodes that have data that is smaller or equal to the pivot string and one that has data larger than the pivot string.
  //Step through each element in the list.
  for(count = 1; count <= length; count++) {
    //This decides if the current node has data that is earlier in the alphabet than pivot.
    if(strcmp(current->data, pivot_string) < 0) {
      all_the_same_flag = 0;
      //If larger has been started, add an elemnt to it. 
      if(larger->data != NULL) {
        if(add_element_to_list(larger, current->data)) {
          fprintf(stderr, "Error in quicksort_list!\nAdd_element_to_list indicated failure.");
          exit(1);
        }//if
      }//if larger list has been started
      //Otherwise, start it and put the current element in it.
      else {
        larger->data = (char *) malloc(MAX_DATA_LENGTH);
        strcpy(larger->data, current->data);
      }//else
    }//if larger
    //This decides if the current node has data that is later in the alphabet than pivot.
    if(strcmp(current->data, pivot_string) >= 0) {
      //Check to see if the data is not the same as the pivot.
      //(If all the data is the same as the pivot, we want to stop recursing.
      if(strcmp(current->data, pivot_string) != 0) {
        all_the_same_flag = 0;
      }//if
      //If smaller has been started, add the element to it.
      if(smaller->data != NULL) {
        if(add_element_to_list(smaller, current->data)) {
          fprintf(stderr, "Error in quicksort_list!\nAdd_element_to_list indicated failure.");
          exit(1);
        }//if
      }//if smaller has been started
      //Otherwise, create smaller and put the element in it.
      else {
        smaller->data = (char *) malloc(MAX_DATA_LENGTH);
        strcpy(smaller->data, current->data);
      }//else
    }//if smaller or equal
    //Set up for the next iteration through the loop. 
    current = get_next_element(current);
  }//for
  //Recurse on smaller and larger, if they exist, unless every element in this list is the same, in which
  //case it is sorted.
  if(all_the_same_flag) {
    return first_n;
  }//if
  if(smaller->data != NULL) {
    smaller = quicksort_list(smaller);
  }//if
  if(larger->data != NULL) {
    larger = quicksort_list(larger);
  }//if
  //Concatenate the lists
  //If both smaller and larger are populated, concatenate them!
  if((smaller->data != NULL) && (larger->data != NULL)) {
    first_n = concatenate_lists(2, larger, smaller);
  }//if
  //If larger is empty, make first_n equal smaller.
  else if((smaller->data != NULL) && (larger->data == NULL)) {
    first_n = smaller;
  }//else if
  //If smaller is empty, make first_n equal to larger.
  else if((smaller->data == NULL) && (larger->data != NULL)) {
    first_n = larger;
  }//else if
  //Delete the unused portions of the old list.
  delete_list(old_second);
  //Return the pointer to the first element of the sorted list.
  return first_n;
}//quicksort_list

/**
 * Allocate memory for a new dllnode.
 * This function is based off of Harbison & Steele's C: A Reference Manual 
 * Fourth Edition.  Page: 386.
 * @return A pointer to the new dllnode struct.
 */
struct dllnode *make_new_node() {
  struct dllnode *new_node = (struct dllnode *) malloc(sizeof(struct dllnode));
  if (new_node == NULL) {
    fprintf(stderr, "make_new_node: ran out of memory!!!!!\n");
    exit(1);
  }//if
  return new_node;
}//make_new_node


//+------------------------------------------+
//| List information functions               |
//+------------------------------------------+

/**
 * Get the list element at position.  This method is O(n), so don't use it
 * if you can help it.
 * @param first_n A pointer to the first node in the list in question.
 * @param position The position of the node we wish to access.
 * @return A pointer to the node at position.
 */
struct dllnode *list_element_at(struct dllnode *first_n, int position) {
  //Declare variables
  int count;
  struct dllnode *n;
  //Initialize variables.
  n = first_n;
  //Iterate until we get to the desired node.
  for(count = 0; count < position; count++) {
    n = get_next_element(n);
  }//for
  return n;
}//list_element_at

/**
 * Return an int which is the number of elements in a list.
 * This function is O(n), so don't use it if you can help it.
 * @param first_n The first node in the list to be counted.
 * @return The number of elements in the list.
 */
int list_length(struct dllnode *first_n) {
  //Declare variables.
  struct dllnode *n;
  int count;
  //Initalize variables.
  n = first_n;
  count = 1;
  //Iterate, and count how many times you do so.
  while(has_next_element(n)) {
    count++;
    n = get_next_element(n);
  }//while
  return count;
}//list_length

/**
 * Check to see if there is a next element in a doubly linked list.
 * @param n The element we are currently at.
 * @return 1 if there is a next element, 0 if not.
 */
int has_next_element(struct dllnode *n) 
{
  if(n->next != NULL) {
    return 1;
  }//if
  else {
    return 0;
  }//else
}//has_next_element

/**
 * Check to see if there is a previous element in a doubly linked list.
 * @param n The element we are currently at.
 * @return 1 if there is a previous element, 0 if not.
 */
int has_previous_element(struct dllnode *n) 
{
  if(n->prev != NULL) {
    return 1;
  }//if
  else {
    return 0;
  }//else
}//has_previous_element