/*
 * list.c
 * A package for managing doubly-linked lists.
 */
#include "list.h"
#include <stdlib.h>

/* Prototypes of static functions: */
static void list_delete_element (List *p_list, Element *p_elem);

/* ------------------------------------------------------------------------
 * Function: list_init
 */
List *list_init ()
{
  List    *p_list;

  /* Allocate a new List object. */
  p_list = (List *) malloc (sizeof(List));

  /* Set its fields to indicate and empty list. */
  p_list->p_head = NULL;
  p_list->p_tail = NULL;
  p_list->size = 0;

  return (p_list);
}

/* ------------------------------------------------------------------------
 * Function: list_prepend
 */
void list_prepend (List *p_list, double x)
{
  Element *p_elem;

  /* Sanity check: */
  if (p_list == NULL)
    exit(-1);

  /* Allocate a new Element object and set its fields. */
  p_elem = (Element *) malloc (sizeof(Element));

  p_elem->value = x;
  p_elem->p_prev = NULL;
  p_elem->p_next = NULL;

  /* Set the element as the new list head. */
  if (p_list->p_head != NULL)
  {
    /* The new element should be placed before the current list head. */
    p_list->p_head->p_prev = p_elem;
    p_elem->p_next = p_list->p_head;

    /* Set the new element as the new list head. */
    p_list->p_head = p_elem;
  }
  else
  {
    /* The list is empty - the new element should be both its head and
       its tail. */
    p_list->p_head = p_elem;
    p_list->p_tail = p_elem;
  }

  /* Increment the list size. */
  p_list->size++;

  return;
}

/* ------------------------------------------------------------------------
 * Function: list_append
 */
void list_append (List *p_list, double x)
{
  Element *p_elem;

  /* Sanity check: */
  if (p_list == NULL)
    exit(-1);

  /* Allocate a new Element object and set its fields. */
  p_elem = (Element *) malloc (sizeof(Element));

  p_elem->value = x;
  p_elem->p_prev = NULL;
  p_elem->p_next = NULL;

  /* Set the element as the new list tail. */
  if (p_list->p_tail != NULL)
  {
    /* The new element should be placed after the current list tail. */
    p_list->p_tail->p_next = p_elem;
    p_elem->p_prev = p_list->p_tail;

    /* Set the new element as the new list tail. */
    p_list->p_tail = p_elem;
  }
  else
  {
    /* The list is empty - the new element should be both its head and
       its tail. */
    p_list->p_head = p_elem;
    p_list->p_tail = p_elem;
  }

  /* Increment the list size. */
  p_list->size++;

  return;
}

/* ------------------------------------------------------------------------
 * Function: list_find
 */
const Element *list_find (const List *p_list, double x)
{
  Element *p_elem;

  /* Sanity check: */
  if (p_list == NULL)
    exit(-1);

  /* Go over the list. */
  p_elem = p_list->p_head;
  while (p_elem != NULL)
  {
    /* Check if the current element contains the requested value. */
    if (p_elem->value == x)
      return (p_elem);

    /* Proceed to the next element. */
    p_elem = p_elem->p_next;
  }

  /* If we reached here, the value is not found in the list. */
  return (NULL);
}

/* ------------------------------------------------------------------------
 * Function: list_delete
 */
int list_delete (List *p_list, double x)
{
  Element *p_elem;

  /* Sanity check: */
  if (p_list == NULL)
    exit(-1);

  /* Find the element containing x in the list. */
  p_elem = (Element *) list_find (p_list, x);

  if (p_elem == NULL)
    /* The value x is not found in the list: */
    return (0);

  /* Delete p_elem from the list. */
  list_delete_element (p_list, p_elem);

  return (1);
}

/* ------------------------------------------------------------------------
 * Function: list_pop_first
 */
double list_pop_first (List *p_list)
{
  double  x;

  /* Sanity checks: */
  if (p_list == NULL || p_list->size == 0)
    exit(-1);

  /* Keep the value of the list head. */
  x = p_list->p_head->value;

  /* Delete the list head, and return the value it stored. */
  list_delete_element (p_list, p_list->p_head);
  return (x);
}

/* ------------------------------------------------------------------------
 * Function: list_pop_last
 */
double list_pop_last (List *p_list)
{
  double  x;

  /* Sanity checks: */
  if (p_list == NULL || p_list->size == 0)
    exit(-1);

  /* Keep the value of the list tail. */
  x = p_list->p_tail->value;

  /* Delete the list tail, and return the value it stored. */
  list_delete_element (p_list, p_list->p_tail);
  return (x);
}

/* ------------------------------------------------------------------------
 * Function: list_reset
 */
void list_reset (List *p_list)
{
  Element *p_elem;

  /* Sanity check: */
  if (p_list == NULL)
    exit(-1);

  while (p_list->p_head != NULL)
  {
    /* Keep track of the current list head. */
    p_elem = p_list->p_head;

    /* Make the second element the new list head. */
    p_list->p_head = p_list->p_head->p_next;

    /* Free memory. */
    free (p_elem);
  }

  /* Reset the rest of the fields. */
  p_list->p_tail = NULL;
  p_list->size = 0;

  return;
}

/* ------------------------------------------------------------------------
 * Function: list_delete_element
 * Purpose:  Delete the given element from the list.
 * Input:    p_list - The list.
 *           p_elem - The element to be deleted.
 * Returns:  Nothing.
 */
static void list_delete_element (List *p_list, Element *p_elem)
{
  /* Link the previous element and the next element of p_elem so none of
     them will keep pointing to p_elem. */
  if (p_elem->p_prev != NULL)
  {
    /* Make the previous element point to the next element (skip p_elem). */
    p_elem->p_prev->p_next = p_elem->p_next;
  }
  else
  {
    /* p_elem is the current list head - assign the next element as the
       new head. */
    p_list->p_head = p_elem->p_next;
  }

  if (p_elem->p_next != NULL)
  {
    /* Make the previous element point to the next element (skip p_elem). */
    p_elem->p_next->p_prev = p_elem->p_prev;
  }
  else
  {
    /* p_elem is the current list tail - assign the previous element as the
       new tail. */
    p_list->p_tail = p_elem->p_prev;
  }

  /* Free p_elem itself. */
  free (p_elem);

  /* Update the list size. */
  p_list->size--;

  return;
}