//Author: Jose M. Vidal
//
//A list class with iterators.
//It implements a small subset of the functionality found in
//the STL list container. 

#include<iostream>

using namespace std;

template<class T>
class List {
  
  class Node {
  public:
    T element;
    Node * next;
	Node * previous;
    Node() : next(0), previous(0) {};
    Node(const T & e, Node * n = 0, Node * p = 0): 
					element(e), next(n), previous(p){};
    ~Node(){}
  };
  
  Node * head;
  Node * tail;
public:
  class Iterator {
    Node * ihead;
	Node * itail;
    Node * current;
  public:
    Iterator() : ihead(0), current(0), itail(0) {};
    Iterator(Node * h, Node * t, Node * c) : ihead(h), current(c), itail(t) {};
    ~Iterator(){};
    Iterator & operator++() { 
		if (current != 0)
			current = current->next;
		return *this;};
    Iterator & operator++(int) {
		return operator++();};
	T & operator*() {
      return current->element;}
    bool operator!=(const Iterator & i) const{
      return current != i.current;}
    bool operator==(const Iterator & i) const{
      return current == i.current;}
	bool isNull() const{
		return current == 0;} //returns true if Iterator is not pointing to anyone
	Node * getCurrent() const {
		return current;}
	//operator- lets you substract these Iterators just like in the STL
	int operator-(const Iterator & i) const{ 
		int j = 0;
		Node * c = i.current;
		while (c != current && c != 0){
			c = c->next;
			j++;
		}
		return j;
	
	}
	//operator+ lets you add an int to an Iterator, the same as doing
	//  operator++ n times
	Iterator operator+(const int n){
		Node * c = current;
		for (int i=0; i<n && c != 0; i++)
			c = c->next;
		return Iterator(ihead, itail, c);
	}


	Iterator & operator--() { 
		if (current != 0)
			current = current->previous;
		else //we are one beyond, go to last
			current = itail;
		return *this;};
    Iterator & operator--(int) {
		return operator--();};

 
  };
  
  
  List() {
    head = new Node;
	tail = 0;};
  ~List() {
     MakeEmpty(); delete head;}
  bool IsEmpty(){return header->next == 0 };
  void MakeEmpty(){
    Node * nextNode;
    for (Node * c = head->next; c != 0; c = nextNode){
      nextNode = c->next;
      delete c;
    }
  };

 friend ostream & operator<<(ostream & os, const List<T> & l){
    Node * nextNode;
    for (Node * c = l.head->next; c != 0; c = nextNode){
      os << c->element << " ";
      nextNode = c->next;
    }
    return os;
  }
  Iterator begin() const{
    return Iterator(head, tail, head->next);
  };
  Iterator end() const{
    return Iterator(head, tail, 0);
  };

  //adds element at the front of the list
  void push_front(T x){
	Node * n= new Node(x,head->next, head);
	if (head->next != 0)
		head->next->previous = n;
	else //this is the first & last element (list is empty)
		tail = n;
    head->next = n;
  }

  //adds element to the back of the list
  void push_back(T x){
	Node * n;
	if (tail == 0){  //list is empty
		n = new Node(x, 0, head);
		tail = n;
		head->next = n;
	}
	else {
		n = new Node(x, 0, tail);
		tail->next = n;
		tail = n;
	}
  };

  //Insert element x right before the one pointed to by i.
  //  and return the position of the new element
  //If i points to 0 (one beyond end) then add it at the end.
  Iterator insert(const Iterator & i, const T & x){
	 if (i.isNull()){
		push_back(x);
		return Iterator(head, tail, tail);
	 }
	 Node * currentp = i.getCurrent();
	 Node * n = new Node(x, currentp, currentp->previous);
	 currentp->previous->next = n;
	 currentp->previous = n;
	 return Iterator(head, tail, n);
  }

  //Removes the element at position i and returns the position
  // of the next element
  //If i points to 0 then return iterator that points to 0 on this list.
  // and do not remove anything.
  Iterator erase(const Iterator & i){
	if (i.isNull())
		 return Iterator(head, tail, 0);
	Node * currentp = i.getCurrent();
	currentp->previous->next = currentp->next;
	if (currentp->next != 0)
		currentp->next->previous = currentp->previous;
	Node * newcur = currentp->next;
	delete currentp;
	return Iterator(head, tail, newcur);
  }

  //merges l into this list. It assumes that both lists are already
  // sorted using T::operator< 
  void merge(const List<T> & l){
    //cout << (*this) << "---" << l << endl;
	Iterator i = begin();
	Iterator j = l.begin();
	for(;i != end() && j != l.end();){
		if (*i < *j)
			++i;
		else {
			insert(i, *j);
			j++;
		}
	}
	for(;j!= l.end(); ++j)
		push_back(*j);
	//cout << "R:" << *this << endl;
  }

  //Sorts this list, using mergesort (and the merge we just defined above)
  // HINT: You will need to make copies of the list. Also, use the
  //  functions you have already defined.
  void sort(){
	if (head->next == 0) return; //list of 0 elements
	if (head->next->next == 0) return; //list of one element, already sorted
	int distance = end() - begin();
	Iterator mid = begin() + distance/2;

	List<T> firstHalf;
	Iterator i;
	for (i = begin(); i != mid; ++i)
		firstHalf.push_back(*i);

	List<T> secondHalf;
	for (;i!=end(); ++i)
		secondHalf.push_back(*i);
	
	firstHalf.sort();

	secondHalf.sort();
	firstHalf.merge(secondHalf);

	MakeEmpty(); //delete us;
	tail = 0; //we are empty now.
	for (i = firstHalf.begin(); i != firstHalf.end(); ++i)
		push_back(*i);

  }


};