// linked list header
// doubley linked list class template

// functions tested so far:
//
// empty
// insert_tail
// remove_head 
// remove_tail
// count
// current
// next

#ifndef __LINKEDLIST_H
#define __LINKEDLIST_H

#include <stdlib.h>

// comments reflect pointer usage, but I am not actually using pointers
// DATA can be pretty much anything

template<class DATA>
class linked_list
{
public:
  linked_list();
  ~linked_list();
  int insert_before(DATA target);
    // insert before the current node
    // error to call with current = NULL
    // returns 0 on success
  int insert_after(DATA target);
    // insert after the current node
    // error to call with current = NULL
    // returns 0 on success
  int insert_head(DATA target);
    // insert at head
    // returns 0 on success
  int insert_tail(DATA target);
    // insert at tail
    // returns 0 on success
  DATA remove(void);
    // remove current node
    // returns NULL on failure, otherwise returns pointer to removed node
    // current becomes next node, NULL if deleting tail node
  DATA remove_head(void);
    // remove the head node
    // returns pointer to removed node, or NULL if list empty
    // if current = head, sets current to NULL
  DATA remove_tail(void);
    // remove the tail node
    // returns pointer to removed node, or NULL if list empty
    // if current = tail, sets curent to NULL
  DATA next(void);
    // go to the next node
    // returns pointer to the next node, or NULL if none
    // return value undefined if no next node
  DATA prev(void);
    // go to previous node
    // returns pointer to previous node, or NULL if none
    // return value undefined if no previous node
  int at_head(void);
    // returns nonzero if current node is first in list (head)
    // returns nonzero if list empty
  int at_tail(void);
    // returns nonzero if current node is last in list (tail)
    // returns nonzero if list empty
  int seek_head(void);
    // sets current node to head
    // returns nonzero if list empty
  int seek_tail(void);
    // sets current node to tail
    // returns nonzero if list empty
  DATA current(void);
    // returns pointer to current node, or NULL if none
  int empty(void);
    // returns 1 if list is empty, otherwise returns 0
  int node_count(void);
    // returns the number of nodes
  int operator +(DATA value);
    // same as insert_after
  DATA operator -(void);
    // same as remove
  DATA operator ++(void);
    // same as next
  DATA operator --(void);
    // same as prev
private:
  struct node
  // this is not a class because it has no member functions
  // list class does not delete client data element, so no const/dest needed
  {
    DATA data;
    node* prev;
    node* next;
  };
  node* head;
  node* tail;
  node* current_ptr;
};

// =====================================================================

// linked list template implementation


template<class DATA>
linked_list<DATA>::linked_list()
{
  head = new node;
  tail = new node;
  current_ptr = NULL;

  head->next = tail;
  head->prev = NULL;
  tail->prev = head;
  tail->next = NULL; 
}

// ---------------------------------------------------------------------

template<class DATA>
linked_list<DATA>::~linked_list()
{
  while (! empty())
  {
    remove_head();
  }
  delete head;
  delete tail;
}

// =====================================================================

template<class DATA>
int linked_list<DATA>::insert_before(DATA target)
    // insert before the current node
    // error to call with current = NULL
    // returns 0 on success
{
  node* temp;

  if (current_ptr == NULL)
  {
    return (1);
  }
  else
  {
    temp = new node;
    if (temp == NULL)
    {
      return (1);
    }
    else
    {
      temp->data = target;
      temp->next = current_ptr;
      temp->prev = current_ptr->prev;
      current_ptr->prev->next = temp;
      current_ptr->prev = temp;
      return (0);
    }
  }
}

// ---------------------------------------------------------------------

template<class DATA>
int linked_list<DATA>::insert_after(DATA target)
    // insert after the current node
    // error to call with current = NULL
    // returns 0 on success
{
  node* temp;

  if (current_ptr == NULL)
  {
    return (1);
  }
  else
  {
    temp = new node;
    if (temp == NULL)
    {
      return (1);
    }
    else
    {
      temp->data = target;
      temp->next = current_ptr->next;
      temp->prev = current_ptr;
      current_ptr->next->prev = temp;
      current_ptr->next = temp;
      return (0);
    }
  }
}

// ---------------------------------------------------------------------

template<class DATA>
int linked_list<DATA>::insert_head(DATA target)
    // insert at head
    // returns 0 on success
{
  node* temp;

  temp = new node;
  if (temp == NULL)
  {
    return (1);
  }
  else
  {
    temp->data = target;
    temp->next = head->next;
    temp->prev = head;
    head->next->prev = temp;
    head->next = temp;
  }
}

// ---------------------------------------------------------------------

template<class DATA>
int linked_list<DATA>::insert_tail(DATA target)
    // insert at tail
    // returns 0 on success
{
  node* temp;

  temp = new node;
  if (temp == NULL)
  {
    return (1);
  }
  else
  {
    temp->data = target;
    temp->next = tail;
    temp->prev = tail->prev;
    tail->prev->next = temp;
    tail->prev = temp;
  }
}

// ---------------------------------------------------------------------

template<class DATA>
DATA linked_list<DATA>::remove(void)
    // remove current node
    // returns NULL on failure, otherwise returns pointer to removed node
    // current becomes next node, NULL if deleting tail node
{
  node* temp;
  DATA removed;

  if (current_ptr == NULL)
  {
    return (NULL);
  }
  else
  {
    temp = current_ptr;
    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;
    current_ptr = temp->next;
    if (current_ptr == tail)
      current_ptr = NULL;
    removed = temp->data;
    delete temp;
    return (removed);
  }
}

// ---------------------------------------------------------------------

template<class DATA>
DATA linked_list<DATA>::remove_head(void)
    // remove the head node
    // returns pointer to removed node, or NULL if list empty
    // if current = head, sets current to NULL
{
  node* temp;
  DATA removed;

  if (empty())
  {
    return (NULL);
  }
  else
  {
    temp = head->next;
    head->next = temp->next;
    temp->next->prev = head;
    removed = temp->data;
    delete temp;
    return(removed);
  }
}

// ---------------------------------------------------------------------

template<class DATA>
DATA linked_list<DATA>::remove_tail(void)
    // remove the tail node
    // returns pointer to removed node, or NULL if list empty
    // if current = tail, sets curent to NULL
{
  node* temp;
  DATA removed;

  if (empty())
  {
    return (NULL);
  }
  else
  {
    temp = tail->prev;
    tail->prev = temp->prev;
    temp->prev->next = tail;
    removed = temp->data;
    delete temp;
    return(removed);
  }
}

// ---------------------------------------------------------------------

template<class DATA>
DATA linked_list<DATA>::next(void)
    // go to the next node
    // returns pointer to the next node, or NULL if none
{
  if ((current_ptr == NULL) || (current_ptr->next == tail))
  {
    current_ptr = NULL;
    return (NULL);
  }
  else
  {
    current_ptr = current_ptr->next;
    return (current_ptr->data);
  }
}


// ---------------------------------------------------------------------

template<class DATA>
int linked_list<DATA>::at_head(void)
{
  if (empty())
    return(1);
  else
    return(current_ptr == head->next);
}

// ---------------------------------------------------------------------

template<class DATA>
int linked_list<DATA>::at_tail(void)
{
  if (empty())
    return(1);
  else
    return(current_ptr == tail->prev || current_ptr == NULL);
}

// ---------------------------------------------------------------------

template<class DATA>
int linked_list<DATA>::seek_head(void)
{
  if (empty())
    return(1);
  else
  {
    current_ptr = head->next;
    return(0);
  }
}

// ---------------------------------------------------------------------

template<class DATA>
int linked_list<DATA>::seek_tail(void)
{
  if (empty())
    return(1);
  else
  {
    current_ptr = tail->prev;
    return(0);
  }
}

// ---------------------------------------------------------------------

template<class DATA>
DATA linked_list<DATA>::prev(void)
    // go to previous node
    // returns pointer to previous node, or NULL if none
{
  if ((current_ptr == NULL) || (current_ptr->prev == head))
  {
    current_ptr = NULL;
    return (NULL);
  }
  else
  {
    current_ptr = current_ptr->prev;
    return (current_ptr->data);
  }
}

// ---------------------------------------------------------------------

template<class DATA>
DATA linked_list<DATA>::current(void)
    // returns pointer to current node, or NULL if none
{
  if ((current_ptr == NULL) || (current_ptr == head) || (current_ptr == tail))
  // more checking than should be necessary, just in case
  {
    return (NULL);
  }
  else
  {
    return (current_ptr->data);
  }
}

// ---------------------------------------------------------------------

template<class DATA>
int linked_list<DATA>::node_count(void)
 // returns the number of nodes in teh list
{
  int count = 0;
  node* temp;

  temp = head->next;
  while (temp != tail)
  {
    temp = temp->next;
    count++;
  }
  return(count);
}

// ---------------------------------------------------------------------

template<class DATA>
int linked_list<DATA>::empty(void)
    // returns 1 if list is empty, otherwise returns 0
{
  if (head->next == tail)
  {
    return (1);
  }
  else
  {
    return (0);
  }
}


// =====================================================================

template<class DATA>
int linked_list<DATA>::operator +(DATA value)
    // same as insert_after
{
  return (insert_after(value));
}

// ---------------------------------------------------------------------

template<class DATA>
DATA linked_list<DATA>::operator -(void)
    // same as remove
{
  return (remove());
}

// ---------------------------------------------------------------------

template<class DATA>
DATA linked_list<DATA>::operator ++(void)
    // same as next
{
  return (next());
}

// ---------------------------------------------------------------------

template<class DATA>
DATA linked_list<DATA>::operator --(void)
    // same as prev
{
  return (prev());
}

#endif