#ifndef SL_LIST_HEADER
#define SL_LIST_HEADER

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

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

// singlely linked node
typedef struct sl_node
{
  struct sl_node* next;
  void* data;
} sl_node;

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

// singlely linked list
typedef struct sl_list
{
  sl_node* head;
  destroy_function destroy;
} sl_list;
////////////////////////////////////////////////////////////////////////////////

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

// initialize a list structure
// x is an allocated list structure 
// d is called for each node during sl_list_clear and sl_list_destroy
// d should be able to delete the memory associated with the data of a node
// if d is null than no operation will occur for deleting node data 
// O(1)
void sl_list_init(sl_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 sl_list_clear(sl_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 sl_list_destroy(sl_list* x);

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

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

// add a new node to the front and return the node
// return 0 for bad allocation
// O(1)
sl_node* sl_list_push_front(sl_list* x);

// remove the node from head and return it
// return 0 if there is no head
// O(1)
sl_node* sl_list_pop_front(sl_list* x);

// insert a node after n and return it
// if n is NULL than add to the head
// O(1)
sl_node* sl_list_insert_after(sl_list* x, sl_node* n);

// remove the node after n and return the removed node
// 0 is returned if there is no node to remove
// if n is null, remove from head
// O(1)
sl_node* sl_list_remove_after(sl_list* x, sl_node* n);

// reverse the order of the list
// O(n)
void sl_list_reverse(sl_list* x);
////////////////////////////////////////////////////////////////////////////////


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

void sl_list_init(sl_list* x, destroy_function d)
{
  x->head = 0;
  x->destroy = d;
}

void sl_list_clear(sl_list* x)
{
  sl_node* iter = x->head;

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

void sl_list_destroy(sl_list* x)
{
  sl_list_clear(x);
  x->destroy = 0;
}

int sl_list_size(sl_list* x)
{
  int size = 0;
  sl_node* iter = x->head;
  while(iter)
  {
    ++size;
    iter = iter->next;
  }
  return size;
}

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

sl_node* sl_list_push_front(sl_list* x)
{
  sl_node *alloc = malloc(sizeof(sl_node));
  if (!alloc)
  {
    return 0;
  }
  alloc->data = 0;
  alloc->next = x->head;
  x->head = alloc;
  return alloc;
}

sl_node* sl_list_pop_front(sl_list* x)
{
  sl_node* old_head;

  old_head = x->head;

  if (!old_head)
    return 0;

  x->head = old_head->next;

  return old_head; 
}

sl_node* sl_list_insert_after(sl_list* x, sl_node* n)
{
  sl_node *allocated, *nxt;

  if (!n)
    return sl_list_push_front(x);

  allocated = malloc(sizeof(sl_node));
  if (!allocated)
  {
    return 0;
  } 
  allocated->data = 0;

  nxt = n->next;
  n->next = allocated;
  allocated->next = nxt;

  return allocated;
}

sl_node* sl_list_remove_after(sl_list* x, sl_node* n)
{
  sl_node *nxt, *removed;

  if (!n)
    return sl_list_pop_front(x);

  removed = n->next;
  if (!removed)
    return 0;

  n->next = removed->next;
  return removed;
}

void sl_list_reverse(sl_list* x)
{
  sl_node *iter, *next, *prev;
  
  iter = x->head;
  prev = 0;

  while(iter)
  {
    next = iter->next;
    iter->next = prev;
    prev = iter;
    iter = next;
  }

  x->head = prev;
}

#endif