#pragma implementation

#include "list.h"

template<class T>
list_node<T>::list_node():next((list_node<T>*)0),
   prev((list_node<T>*)0) {
};

template<class T>
list_node<T>::list_node(const T& e):next((list_node<T>*)0),
   prev((list_node<T>*)0),element(e) { };

template<class T>
list_iterator<T>::list_iterator(list_node<T>* n):node(n) {}

template<class T>
int list_iterator<T>::has_more_elements() {
  return node != (list_node<T>*)0;
};

template<class T>
T* list_iterator<T>::operator->() {
  return &(node->element);
};

template<class T>
T& list_iterator<T>::operator*() {
  return node->element;
};

template<class T>
T& list_iterator<T>::operator++() {
  node = node->next;
  return node->element;
};

template<class T>
T& list_iterator<T>::operator++(int) {
  T& remember = node->element;
  node = node->next;
  return remember;
};

template<class T>
T& list_iterator<T>::operator--() {
  node = node->prev;
  return node->element;
};

template<class T>
T& list_iterator<T>::operator--(int) {
  T& remember = node->element;
  node = node->prev;
  return remember;
};

template<class T>
list_node<T>* list_iterator<T>::getNode() {
  return node;
};

template<class T>
void list_iterator<T>::invalidate() {
  node = (list_node<T>*)0;
};

template<class T>
int list_iterator<T>::operator==(const list_iterator<T>& I) {
  return I.node == node;
};

template<class T>
int list_iterator<T>::operator!=(const list_iterator<T>& I) {
  return ! ((*this) == I);
};

template<class T>
T& list_iterator<T>::operator[](int n) {
  return (*this + n).node->element;
};

template<class T>
list_iterator<T>  list_iterator<T>::operator+(int n) {
  list_iterator<T> I;
  I.node = this->node;
  for(int i=0;i<n;i++) I++; 
  
  return I;   
};

template<class T>
list_iterator<T>  list_iterator<T>::operator-(int n) {
  list_iterator<T> I;
  I.node = this->node;
  for(int i=0;i<n;i++) I--;
  
  return I;
};


template<class T>
void list<T>::destroy(list_node<T>* from,list_node<T>* to) {

  if (from == (list_node<T>*)0 ||  to == (list_node<T>*)0) return;

  list_node<T>* ptr = from,
              *start = from->prev,
              *end = to->next;


  while(ptr != end) {
    from = ptr->next;
    delete ptr;
    size--;
    ptr = from;
  } 

 if(start==(list_node<T>*)0) _first = end;
 else start->next = end;

 if(end==(list_node<T>*)0) _last = start;
 else end->prev = start;
 
};

template<class T>
void list<T>::copy(list_node<T>* at,list_node<T>* at_next,list_node<T>* from,
                   list_node<T>* to,const list<T>) {
  list_node<T>* ptr = from;

  if (at == (list_node<T>*)0) { 
     at = new list_node<T>(ptr->element);
     size++;
     ptr = ptr->next;
     _first = at;
  } 

  while(ptr != to->next) {
     at->next = new list_node<T>(ptr->element);
     size++;
     at->next->prev = at; 
     ptr=ptr->next;
     at=at->next;
  }
 
  if (at_next==(list_node<T>*)0) _last = at; 
  else {
    at->next = at_next;
    at_next->prev = at;
  }
};

template<class T>
void list<T>:: insert_before(list_iterator<T> I,const T& element) {
  list_node<T>* node = I.getNode();

  if (_first == (list_node<T>*)0) {
     _first = new list_node<T>(element);
     size = 1;
     _last = _first;
     return;
  }

  if (node == (list_node<T>*)0) return;

  list_node<T>* before = node->prev;

  size ++;

  if (before == (list_node<T>*)0) {
    _first = new list_node<T>(element);
    _first->next = node;
    node->prev = _first;
    return;
  }

  before->next = new list_node<T>(element);
  before->next->next = node;
  before->next->prev = node->prev;
  node->prev = before->next;
};


template<class T>
void list<T>::insert_after(list_iterator<T> I,const T& element) {
  list_node<T> *node = I.getNode();

  if (_first == (list_node<T>*)0) {
     _first = new list_node<T>(element);
     size = 1;
     _last = _first;
     return;
  }

  if (node == (list_node<T>*)0) return;

  list_node<T>* after = node->next;

  size ++;

  if (after == (list_node<T>*)0) {
    _last = new list_node<T>(element);
    _last->prev = node;
    node->next = _last;
    return;
  }

  node->next = new list_node<T>(element);
  node->next->prev = node;		
  node->next->next = after;
  after->prev = node->next;
};

template<class T>
void list<T>::insert_before(list_iterator<T> I,const list<T>& L){
  copy(I.getNode()->prev,I.getNode(),L._first,L._last,L); 
};

template<class T>
void list<T>::insert_after(list_iterator<T> I,const list<T>& L){
  copy(I.getNode(),I.getNode()->next,L._first,L._last,L);
};

template<class T>
void list<T>::remove(list_iterator<T>& I) {
  list_node<T>* n = I.getNode();
  
  if (n==(list_node<T>*)0) return;

  list_node<T>* after  = n->next;
  list_node<T>* before = n->prev;

  if (before == (list_node<T>*)0) {
    _first = after;
  } else {
    before->next = after;
  }
 
  if (after == (list_node<T>*)0) {
    _last = before;
  } else {
    after->prev = before;
  }

  size--;

  delete n;

  I.invalidate();
};

template<class T>
list_iterator<T> list<T>::first() {
  list_iterator<T> I(_first);
  return I;
};

template<class T>
list_iterator<T> list<T>::last() {
  list_iterator<T> I(_last);

  return I;
};

template<class T>
int list<T>::length() const { return size; };

template<class T>
void list<T>::set_comparison(bool (*f)(const T&,const T&)) {
  less =  f;
};

template<class T>
list<T>::list(bool (*f)(const T&,const T&)):_first((list_node<T>*)0),
   _last((list_node<T>*)0),size(0),less(f) { };

template<class T>
list<T>::list(const list<T>& L):_first((list_node<T>*)0),
  _last((list_node<T>*)0),size(0) {
  copy(_first,_last,L._first,L._last,L);
};

template<class T>
list<T>::~list(){
  destroy(_first,_last);
};

template<class T>
list<T>& list<T>::operator=(const list<T>& L) {
  destroy(_first,_last);
  copy(_first,_last,L._first,L._last,L);
  return *this;
};

template<class T>
void list<T>::split(list<T>& smaller,list<T>& bigger, const T& v) {

  if (_first == (list_node<T>*)0) return;

  while(_first != (list_node<T>*)0) {
    if (less(*(first()),v)) {
       smaller.insert_after(smaller.last(),*(first()));
    } else {
       bigger.insert_after(bigger.last(),*(first()));
    }
    list_iterator<T> tmp = first();
    remove(tmp);  
  }
}

template<class T>
void list<T>::sort() {

  if (less==0) return;

  if (_first == _last) return;

  list<T> smaller(less);
  list<T> bigger(less);

  list_node<T>* first_node = _first;

  _first = _first->next;
  _first->prev = (list_node<T>*)0;

  size--;

  split(smaller,bigger,first_node->element);

  smaller.sort();
  bigger.sort();

  _first = smaller._first;
  _last  = bigger._last;
 
  if(smaller._last != (list_node<T>*)0) {  
    smaller._last->next = first_node;
    first_node->prev = smaller._last;
  } else {
    _first = first_node;
    first_node->prev = (list_node<T>*)0;
  }

  if(bigger._first != (list_node<T>*)0) {
    bigger._first->prev = first_node;
    first_node->next = bigger._first;
  } else {
    _last = first_node;
    first_node->next = (list_node<T>*)0;
  }
 
  size = bigger.size + smaller.size;
 
  // IMPORTANT, PREVENT DESTRUCTOR!!!   

  smaller._last = bigger._last = smaller._first = bigger._first 
     = (list_node<T>*)0;
}

#include "list_inst.h"