#ifndef DL_LIST_HEADER
#define DL_LIST_HEADER

////////////////////////////////////////////////////////////////////////////////
// COPYRIGHT IVAN NOVICK, OCT 2007, email: ivan at 0x4849 dot net
////////////////////////////////////////////////////////////////////////////////

#include <stdlib.h>
////////////////////////////////////////////////////////////////////////////////
// DATA TYPES

// doubly linked node
typedef struct dl_node
{
  struct dl_node* next;
  struct dl_node* prev;
  void* data;
} dl_node;

// a function that can be used to delete the data inside a node
// this will be used only during the dl_list_clear and dl_list_destroy functions
typedef void (*destroy_function)(void*);

// doubly linked list
typedef struct dl_list
{
  dl_node* head;
  dl_node* tail;
  destroy_function destroy;
} dl_list;
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// PUBLIC INTERFACE

// initialize a list structure
// x is an allocated list structure 
// d is called for each node during dl_list_clear and dl_list_destroy
// d should be able to delete the memory associated with the data of a node
// if d is 0 than no operation will occur for deleting node data 
// O(1)
void dl_list_init(dl_list* x, destroy_function d);

// call the destroy function for each node and deallocate the node
// reset the list head but not the destroy function pointer
// O(n)
void dl_list_clear(dl_list* x);

// call the destroy function for each node and deallocate the node
// reset the list head and the destroy function pointer
// O(n)
void dl_list_destroy(dl_list* x);

// return the number of nodes in the list x
// O(n)
int dl_list_size(dl_list* x);

// return 1 for empty list 0 for non-empty list
// O(1)
inline int dl_list_empty(dl_list* x); 

// add a new node to the front and return the node
// return 0 for bad allocation
// O(1)
dl_node* dl_list_push_front(dl_list* x);

// add a new node to the back and return the node
// return 0 for bad allocation
// O(1)
dl_node* dl_list_push_back(dl_list* x);

// remove the node from head and return it
// return 0 if there is no head
// O(1)
dl_node* dl_list_pop_front(dl_list* x);

// remove the node from back and return it
// return 0 if there is no tail
// O(1)
dl_node* dl_list_pop_back(dl_list* x);

// insert a node before n and return it
// if n is 0 than add to the head
// O(1)
dl_node* dl_list_insert_before(dl_list* x, dl_node* n);

// insert a node after n and return it
// if n is 0 than add to the tail
// O(1)
dl_node* dl_list_insert_after(dl_list* x, dl_node* n);

// remove the node n and return the removed node
// O(1)
void dl_list_remove_node(dl_list* x, dl_node* n);

// reverse the order of the list
// O(n)
void dl_list_reverse(dl_list* x);
////////////////////////////////////////////////////////////////////////////////


////////////////////////////////////////////////////////////////////////////////
// IMPLEMENTATION

void dl_list_init(dl_list* x, destroy_function d)
{
  x->head = 0;
  x->tail = 0;
  x->destroy = d;
}

void dl_list_clear(dl_list* x)
{
  dl_node* iter = x->head;

  while(iter)
  {
    dl_node* next = iter->next;
    if (x->destroy)
      x->destroy(iter->data);
    free(iter);
    iter = next;
  }
  x->head = 0;
  x->tail = 0;
}

void dl_list_destroy(dl_list* x)
{
  dl_list_clear(x);
  x->destroy = 0;
}

int dl_list_size(dl_list* x)
{
  int size = 0;
  dl_node* iter = x->head;
  while(iter)
  {
    ++size;
    iter = iter->next;
  }
  return size;
}

inline int dl_list_empty(dl_list* x) 
{
  return x->head ? 0 : 1;
}

dl_node* dl_list_push_front(dl_list* x)
{
  dl_node *alloc = malloc(sizeof(dl_node));
  if (!alloc)
  {
    return 0;
  }
  /* different for empty and non-empty list */
  if (x->head)
    x->head->prev = alloc;
  else
    x->tail = alloc;

  alloc->data = 0;
  alloc->next = x->head;
  alloc->prev = 0;
  x->head = alloc;
  return alloc;
}

dl_node* dl_list_push_back(dl_list* x)
{
  dl_node *alloc = malloc(sizeof(dl_node));
  if (!alloc)
  {
    return 0;
  }
  /* different for empty and non-empty list */
  if (x->head)
    x->tail->next = alloc;
  else
    x->head = alloc;

  alloc->data = 0;
  alloc->next = 0;
  alloc->prev = x->tail;
  x->tail = alloc;
  return alloc;
}

dl_node* dl_list_pop_front(dl_list* x)
{
  dl_node* old_head = x->head;

  if (!old_head)
    return 0;

  x->head = old_head->next;

  if (x->head)
    x->head->prev = 0;
  else
    x->tail = 0;

  return old_head; 
}

dl_node* dl_list_pop_back(dl_list* x)
{
  dl_node* old_tail = x->tail;

  if (!old_tail)
    return 0;

  x->tail = old_tail->prev;

  if (x->tail)
    x->tail->next = 0;
  else
    x->head = 0;

  return old_tail; 
}

dl_node* dl_list_insert_before(dl_list* x, dl_node* n)
{
  dl_node* allocated;

  if (!n || (n == x->head))
    return dl_list_push_front(x);

  allocated = malloc(sizeof(dl_node));
  if (!allocated)
  {
    return 0;
  } 
  allocated->data = 0;
  allocated->next = n;
  allocated->prev = n->prev;
  allocated->prev->next = allocated;
  allocated->next->prev = allocated;
  
  return allocated;
}

dl_node* dl_list_insert_after(dl_list* x, dl_node* n)
{
  dl_node* allocated;

  if (!n || (n == x->tail))
    return dl_list_push_back(x);

  allocated = malloc(sizeof(dl_node));
  if (!allocated)
  {
    return 0;
  } 
  allocated->data = 0;
  allocated->next = n->next;
  allocated->prev = n;
  allocated->prev->next = allocated;
  allocated->next->prev = allocated;
  
  return allocated;
}

void dl_list_remove_node(dl_list* x, dl_node* n)
{
  if (x->head == n)
    x->head = n->next;

  if (x->tail == n)
    x->tail = n->prev;

  if (n->prev)
    n->prev->next = n->next;

  if (n->next)
    n->next->prev = n->prev;
}

/* reverse a doubly-linked list */
void dl_list_reverse(dl_list* x)
{
  dl_node *iter, *tmp;
  iter = x->head;
  
  while(iter)
  {
    tmp = iter->next;
    iter->next = iter->prev;
    iter->prev = tmp;
    iter = tmp;
  }

  tmp = x->tail;
  x->tail = x->head;
  x->head = tmp;
}

#endif