/*
 * 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