//
//
//	simplified list class
//
//	Described in Chapter 9 of
//	Data Structures in C++ using the STL
//	Published by Addison-Wesley, 1997
//	Written by Tim Budd, budd@cs.orst.edu
//	Oregon State University
//
//

template <class T> class listIterator {
	typedef listIterator<T> iterator;
public:
		// constructor
	listIterator (list<T> * tl, link<T> * cl)
		: theList(tl), currentLink(cl) { }

		// iterator protocol
	T & operator * () 
		{ return currentLink->value; }
	void operator = (iterator & rhs) 
		{ theList = rhs.theList; currentLink = rhs.currentLink; }
	bool operator == (const iterator rhs) const
		{ return currentLink == rhs.currentLink; }
	iterator & operator ++ (int)
		{ currentLink = currentLink->nextLink; return * this; }
	iterator operator ++ ();
	iterator & operator -- (int)
		{ currentLink = currentLink->prevLink; return * this; }
	iterator operator -- ();

protected:
	list <T> * theList;
	link <T> * currentLink;
	friend class list<T>;
};

template <class T>
class list {
public:
		// type definitions
	typedef T value_type;
	typedef listIterator<T> iterator;

		// constructor and destructor
	list () : firstLink(0), lastLink(0) { }
	list (list<T> & x) : firstLink(0), lastLink(0) { }
	~ list ();

		// operations
	bool empty () { return firstLink == 0; }
	int size();
	T & back () { return lastLink->value; }
	T & front () { return firstLink->value; }
	void push_front(T &);
	void push_back(T &);
	void pop_front ();
	void pop_back ();
	iterator begin () { return iterator (this, firstLink); }
	iterator end () { return iterator (this, 0); }
	void sort ();
	void insert (iterator &, T &);
	void erase (iterator & itr) { erase (itr, itr); }
	void erase (iterator &, iterator &);

protected:
	link <T> * firstLink;
	link <T> * lastLink;
};

template <class T> class link {
private:
	link (T & v) : value(v), nextLink(0), prevLink(0) { }
	T value;
	link<T> * nextLink;
	link<T> * prevLink;
		// allow lists to see element values
	friend class list<T>;
	friend class listIterator<T>;
};

template <class T> int list<T>::size ()
	// count number of elements in collection
{
	int counter = 0;
	for (link<T> * ptr = firstLink; ptr != 0; ptr = ptr->nextLink)
		counter++;
	return counter;
}

template <class T> void list<T>::push_front (T & newValue)
	// add a new value to the front of a list
{
	link<T> * newLink = new link<T> (newValue);
	if (empty()) 
		firstLink = lastLink = newLink;
	else {
		firstLink->prevLink = newLink;
		newLink->nextLink = firstLink;
		firstLink = newLink;
		}
}

template <class T> void list<T>::pop_front()
	// remove first element from linked list
{
	link <T> * save = firstLink;
	firstLink = firstLink->nextLink;
	if (firstLink != 0)
		firstLink->prevLink = 0;
	else
		lastLink = 0;
	delete save;
}

template <class T> list<T>::~list ()
	// remove each element from the list
{
	link <T> * first = firstlink;
	while (first != 0) {
		link <T> * next  = first->nextLink;
		delete first;
		first = next;
		}
}


template <class T> listIterator<T> listIterator<T>::operator ++ ()
	// postfix form of increment
{
		// clone, then increment, return clone
	listIterator<T> clone (theList, currentLink);
	currentLink = currentLink->nextLink;
	return clone;
}

template <class T> void list<T>::insert (listIterator<T> & itr, T & value)
	// insert a new element into the middle of a linked list
{
	link<T> * newLink = new link(value);
	link<T> * current = itr->currentLink;

	newLink->nextLink = current;
	newLink->prevLink = current->prevLink;
	current->prevLink = newLink;
	current = newLink->prevLink;
	if (current != 0)
		current->nextLink = newLink;
}

template <class T> 
void list<T>::erase (listIterator<T> & start, listIterator<T> & stop)
	// remove values from the range of elements
{
	link<T> * first = start.currentLink;
	link<T> * prev = first->prevLink;
	link<T> * last = stop.currentLink;
	if (prev == 0) { 	// removing initial portion of list
		firstLink = last;
		if (last == 0)
			lastLink = 0;
		else
			last->prevLink = 0;
		}
	else {
		prev->nextLink = last;
		if (last == 0)
			lastLink = prev;
		else
			last->prevLink = prev;
		
		}
		// now delete the values
	while (start != stop) {
		listIterator<T> next = start;
		++next;
		delete start.currentLink;
		start = next;
		}
}