/*
 * Linked list class implementation
 */

#ifndef __LINKED_LIST__
#define __LINKED_LIST__

extern "C++" {

template <class __tp>
struct linked_list_node {
  linked_list_node<__tp>* next;
  linked_list_node<__tp>* prev;
  __tp data;
};

template <class __type> class List
{
  typedef linked_list_node<__type> node;
  typedef linked_list_node<__type>* nodeptr;
  typedef List<__type> self;

  node sentinel;    
  nodeptr current;  // iterator position
  int n;            // number of nodes in the list (except for sentinel)

public:
  List () : current(0), n(0) {
    sentinel.next = sentinel.prev = &sentinel;
  }

  int size () {
    return n;
  }
  bool empty () {
    return n==0;
  }
  bool begin () {
    return current->prev==&sentinel;
  }
  bool end () {
    return current->next==&sentinel;
  }
  
  __type& operator* () {
    return current->data;
  }  

  List& operator++ () {
    nodeptr __temp = current->next;
    if(__temp!=&sentinel)
      current = __temp;
    return *this;
  }
  List& operator-- () {
    nodeptr __temp = current->prev;
    if(__temp!=&sentinel)
      current = __temp;
    return *this;
  }

  List& rewind () {
    current = sentinel.next;
    return *this;
  }
  List& to_back () {
    current = sentinel.prev;
    return *this;
  }
  List& push_front (const __type& item) {
    nodeptr __temp = new node;
    __temp->data = item;
    __temp->prev = &sentinel;
    __temp->next = sentinel.next;
    sentinel.next->prev = __temp;
    sentinel.next = __temp;
    n++;
    return *this;
  }
  List& push_back (const __type& item) {
    nodeptr __temp = new node;
    __temp->data = item;
    __temp->prev = sentinel.prev;
    __temp->next = &sentinel;
    sentinel.prev->next = __temp;
    sentinel.prev = __temp;
    n++;
    return *this;
  }
  List& insert (const __type& item) {
    nodeptr __temp = new node;
    __temp->data = item;
    __temp->prev = current->prev;
    __temp->next = current;
    current->prev->next = __temp;
    current->prev = __temp;
    current = __temp;
    n++;
    return *this;
  }
  List& pop_front () {
    if(!empty()) {
      nodeptr __head = sentinel.next;
      sentinel.next = __head->next;
      __head->next->prev = &sentinel;
      if(current==__head)
        current==__head->next;
      delete __head;
      n--;
    }
    return *this;
  }
  List& pop_back () {
    if(!empty()) {
      nodeptr __back = sentinel.prev;
      sentinel.prev = __back->prev;
      __back->prev->next = &sentinel;
      if(current==__back)
        current==__back->prev;
      delete __back;
      n--;
    }
    return *this;
  }
  List& remove () {
    if(!empty()) {
      current->prev->next = current->next;
      current->next->prev = current->prev;
      delete current;
      current = current->next;
      n--;
    }
    return *this;
  }

  List& erase () {
    nodeptr __temp = sentinel.next;
    nodeptr __temp2;
    while(__temp!=&sentinel) {
      __temp2 = __temp->next;
      delete __temp;
      __temp = __temp2;
    }
    n = 0;
    sentinel.prev = sentinel.next = &sentinel;
    current = 0;
    return *this;
  }

  __type* array() {
    __type* newarray = new __type[size()];
    __type* p = newarray;
    rewind();
    for(int i=size(); i; i--) {
      *p = current->data;
      p++;
      current = current->next;
    }
    return newarray;
  }
  
  List& operator += (const List& L) 
  {
    nodeptr __src = L.sentinel.next;
    nodeptr __temp = sentinel.prev;
    nodeptr __temp2;
    for(int i=L.n; i; i--) {
      __temp->next = new node;
      __temp2 = __temp->next;
      __temp2->data = __src->data;
      __temp2->prev = __temp;
      __temp = __temp2;
      __src = __src->next;
    }
    __temp->next = &sentinel;
    sentinel.prev = __temp;
    n += L.n;
  }

  List(const List& L) : current(0), n(0)
  {
    nodeptr __src = L.sentinel.next;
    nodeptr __temp = &sentinel;
    nodeptr __temp2;
    for(int i=L.n; i; i--) {
      __temp->next = new node;
      __temp2 = __temp->next;
      __temp2->data = __src->data;
      __temp2->prev = __temp;
      __temp = __temp2;
      __src = __src->next;
    }
    __temp->next = &sentinel;
    sentinel.prev = __temp;
    n = L.n;
  }

  ~List() {
    erase();
  }
  
};

} // extern "C++"

#endif
