/*
* File: list.h
* Purpose:  Just a small linked list class
*/
#ifndef LIST_H
#define LIST_H

class List {
private:
 class Node;

public:
 // Constructor and destructor
 List() {
   head = tail = 0x00;
 }


 ~List() {
   Node *cur;

   //start at the head
   cur = head;

   //kill all the things!
   while(cur) {
     cur = cur->next;
     delete head;
     head = cur;
   }
 }


 //high level operations
 void append(int data) {
   Node *node = createNode(data);

   //special case, empty list!
   if(isEmpty()) {
     head = tail = node;
     return;
   }

   tail->next = node;
   tail = node;
 }

 void prepend(int data) {
   Node *node = createNode(data);

   //special case, empty list!
   if(isEmpty()) {
     head = tail= node;
     return;
   }

   node->next = head;
   head=node;
 }


 bool isEmpty() {
   return !head;
 }


 //iterator
 class iterator {
 public:
   //dereference
   int operator*() {
     return node->data;
   }

   //comparison
   bool operator==(const iterator &rhs) {
     return node == rhs.node;
   }

   bool operator!=(const iterator &rhs) {
     return node != rhs.node;
   }

   //movement
   iterator &operator++() {
     if(node) node=node->next;
     return *this;
   }

   iterator operator++(int) {
     iterator itr(*this);

     if(node) node=node->next;
     return itr;
   }

   iterator &operator--() {
     node=l.findPrevious(node);
     return *this;
   }

   iterator operator--(int) {
     iterator itr(*this);

     node=l.findPrevious(node);

     return itr;
   }

 private:
   //current node
   Node *node;
   List &l;

   //private constructor
   iterator(Node *node, List &lst): l(lst) { this->node = node; }


   //we have but one friend
   friend class List;

 };

 //iterator creation
 iterator begin() {
   return iterator(head, *this);
 }


 iterator end() {
   return iterator(0x00, *this);
 }


 //iterator action
 void insertAfter(iterator &itr, int data) {
   //special case, insertion at the tail
   if(!itr.node || itr.node==tail) {
     append(data);
     return;
   }


   //insert after the iterator node
   Node *node = createNode(data);
   node->next = itr.node->next;
   itr.node->next = node;
 }



private:
 //inner type for storage of information
 class Node {
 public:
   int data;     //the payload
   Node *next;   //the link

   Node() { next=0x00; }
 };

 //private data elements
 Node *head;
 Node *tail;

 //private helpers
 Node * createNode(int data) {
   Node *node = new Node();
   node->data = data;
   return node;
 }


 Node * findPrevious(Node *node) {
   Node * cur = head;

   while(cur) {
     if(cur->next == node)
       return cur;
     cur = cur->next;
   }
 }
};

#endif