/**
 * dll.c
 *   A simple implementation of lists.
 */

// +---------+--------------------------------------------------------
// | Headers |
// +---------+

#include <stdio.h>
#include <stdlib.h>
#include <string.h>		// For strcmp

#include "dll.h"


// +-------+----------------------------------------------------------
// | Types |
// +-------+

/**
 * One node in a doubly linked list.
 */
struct dnode 
  {
    char *data;         // The data stored in the node.
    struct dnode *prev; // The previous node.  NULL for the head.
    struct dnode *next; // The next node.  NULL for the tail.
  };


/**
 * The "wrapper" that lets us keep track of both ends of the list.
 */
struct dll
  {
    struct dnode *head;         // The front of the list.  NULL when empty.
    struct dnode *tail;         // The back of the list.  NULL when empty.
    struct dnode *cursor;       // The cursor.  NULL when empty.
  };


// +--------------------+---------------------------------------------
// | Exported Variables |
// +--------------------+

/**
 * A description of the error that most recently occured.
 */
char *dll_error = "unknown error";


// +---------+--------------------------------------------------------
// | Helpers |
// +---------+

/**
 * error (err)
 *   Set the error and return 0.
 */
static int 
error (char *err)
{
  dll_error = err;
  return 0;
} // error


// +----------------------------+-------------------------------------
// | Constructors & Destructors |
// +----------------------------+

struct dll *
dll_new ()
{
  struct dll *lst = malloc (sizeof (struct dll));
  if (lst == NULL)
    return NULL;
  lst->head = NULL;
  lst->tail = NULL;
  lst->cursor = NULL;
  return lst;
} // dll_new

void
dll_free (struct dll* lst)
{
  // Free all of the cons cells.
  dll_clear (lst);
  // Reset values (not necessary, but safer).
  lst->cursor = NULL;
  lst->head = NULL;
  lst->tail = NULL;
  // Free the surrounding struct
  free (lst);
} // dll_free

void
dll_clear (struct dll *lst)
{
  lst->head = NULL;
  lst->tail = NULL;
} // dll_clear


// +-----------+------------------------------------------------------
// | Observers |
// +-----------+

char *
dll_get (struct dll *lst)
{
  // Note: If the preconditions are not met, this behaves badly.
  return lst->cursor->data;
} // dll_get

int
dll_is_empty (struct dll *lst)
{
  return lst->head == NULL;
} // dll_is_empty

int
dll_at_head (struct dll *lst)
{
  return lst->cursor == lst->head;
} // dll_at_head

int
dll_at_tail (struct dll *lst)
{
  return lst->cursor == lst->tail;
} // dll_at_tail

void
dll_print (struct dll *lst, FILE *fp)
{
  // Special case: Empty list
  if (lst->head == NULL)
    {
      fprintf (fp, "{}");
    }
  
  // Normal case
  else
    {
      struct dnode *current = lst->head;
      // Print the first element
      fprintf (fp, "{");
      fprintf (fp, "\"%s\"", current->data);
      // Print the remaining elements
      while ((current = current->next) != NULL)
        fprintf (fp, ",\"%s\"", current->data);
      // End the list
      fprintf (fp, "}");
    } // normal case
} // dll_print


// +---------------+--------------------------------------------------
// | List Mutators |
// +---------------+

int 
dll_insert_after (struct dll *lst, char *str)
{
  
  return error ("unimplemented");       // STUB
} // dl_insert_after

int 
dll_insert_before (struct dll *lst, char *str)
{
  return error ("unimplemented");       // STUB
} // dl_insert_before

int 
dll_append (struct dll *lst, char *str)
{
  // Build a node to hold the string.
  struct dnode *newtail = malloc (sizeof (struct dnode));
  if (newtail == NULL)
    return error ("could not allocate space for a new node");
  newtail->next = NULL;
  newtail->prev = lst->tail;
  newtail->data = str;

  // Special case: List is currently empty
  if (lst->head == NULL)
    {
      lst->head = newtail;
      lst->tail = newtail;
    }

  // Normal case: List is nonempty.  Update the tail.
  else
    {
      lst->tail->next = newtail;
      lst->tail = newtail;
    }

  // And we're done
  return 1;
} // dll_append

int 
dll_prepend (struct dll *lst, char *str)
{
  // Build a node to hold the string.
  struct dnode *newhead = malloc (sizeof (struct dnode));
  if (newhead == NULL)
    return error ("could not allocate space for a new node");
  newhead->next = lst->head;
  newhead->prev = NULL;
  newhead->data = str;
  // Insert it at the head
  lst->head = newhead;
  // And we're done
  return 1;
} // dll_prepend

int 
dll_delete (struct dll *lst)
{
  if (lst->cursor == NULL)
    return error ("no cursor");

  // Fix pointers in previous node, if applicable
  if (lst->cursor->prev != NULL)
    lst->cursor->prev->next = lst->cursor->next;
  else
    lst->head = lst->cursor->next;

  // Fix pointers in next node, if applicable
  if (lst->cursor->next != NULL)
    lst->cursor->next->prev = lst->cursor->prev;
  else
    lst->tail = lst->cursor;

  // Move to the next element
  if (lst->cursor->next != NULL)
    lst->cursor = lst->cursor->next;
  else
    lst->cursor = lst->cursor->prev;

  // And we're done
  return 1;
} // dll_delete


// +-----------------+------------------------------------------------
// | Cursor Mutators |
// +-----------------+

int 
dll_to_head (struct dll *lst)
{
  lst->cursor = lst->head;
  return 1;
} // dll_to_head

int 
dll_to_tail (struct dll *lst)
{
  lst->cursor = lst->tail;
  return 1;
} // dll_to_tail

int
dll_advance (struct dll *lst)
{
  lst->cursor = lst->cursor->next;
  return 1;
} // dll_advance

int
dll_retreat (struct dll *lst)
{
  lst->cursor = lst->cursor->prev;
  return 1;
} // dll_retreat


// +---------------+--------------------------------------------------
// | Miscellaneous |
// +---------------+

int
dll_check (struct dll *lst, char *strings[], int size)
{
  char err[] = "mismatch at position XXXXXXX";
  struct dnode *current;
  int i;

  // Look at each pair of elements
  for (i = 0,        current=lst->head; 
       (i < size) && (current != NULL);
       i++,          current=current->next)
    {
      // If the pair of elements don't match, give up
      if (strcmp (current->data, strings[i]) != 0)
        {
          sprintf (err, "mismatch at position %d", i);
          return error (err);
        }
    } // for

  // Are we at the end of the list?  If not, the sizes don't match
  if (current != NULL)
    return error ("list is longer than array");

  // Are we at the end of the array?  If not, the sizes don't match.
  if (i != size)
    return error ("array is longer than list");

  // Those seem to be the only kinds of mismatch possible
  return 1;
} // dll_check