/* Lecture code 11.1
 *
 * List template class with iterator support.  There are some minor
 * changes to the lecture code in this version, as an astute student
 * pointed out that the forward declaration of cellT accidentally
 * made the cellT struct public.  This has been corrected in this
 * version.
 */

#include <iostream>
#include <cstdlib> // For NULL
#include <algorithm>
#include <iterator>
using namespace std;

template<typename ElemType> class List
{
private:
	/* Forward-declare cellT in the private section so that
	 * class clients can't access it.
	 */
	struct cellT;
public:
	List();
	List(const List& other); // Copy constructor
	List& operator =(const List& other); // Assignment operator
	~List();

	void append(const ElemType& toAdd);

	/* A class representing a linked list iterator.  The standard
	 * pointer operations translate into list movement.
	 */
	friend class iterator; // Necessary so that iterator can use cellT.
	class iterator
	{
	public:
		/* Comparison operators to allow for iterator comparison. */
		bool operator != (const iterator &other) const
		{
			return other.current != current;
		}
		bool operator == (const iterator &other) const
		{
			return other.current == current;
		}

		/* Pointer dereference operator.  The return type is a reference
		 * to an ElemType, so that we can write code of the form
		 * *itr = 137 and have it compile correctly.  Note that the
		 * member function itself is const because this operation
		 * doesn't change the iterator itself.
		 */
		ElemType& operator *() const
		{
			return current->data;
		}

		/* Two versions of operator ++.  The first version is the
		 * prefix operator ++ (e.g. ++itr), which updates the
		 * iterator and returns a reference to it.
		 */
		iterator& operator ++()
		{
			current = current->next;
			return *this;
		}

		/* Second version of operator ++.  This second version
		 * is the postfix operator ++ (e.g. itr++), which
		 * caches the value of the iterator, moves the pointer
		 * forward, and returns the old value.
		 */
		const iterator operator ++(int dummy) // dummy is always 0.
		{
			iterator oldValue = *this;
			current = current->next;
			return oldValue;
		}

		/* Because the List should be able to read and write our data
		 * members, we mark the List as a friend.
		 */
		friend class List;
	private:
		cellT* current;
	};


	/* Begin returns an iterator that is pointing to the start
	 * of the list.  Note that we can access data members directly
	 * because List is a friend of iterator.
	 */
	iterator begin()
	{
		iterator result;
		result.current = head;
		return result;
	}

	/* End returns an iterator that points to NULL, the value one
	 * past the end of the list.
	 */
	iterator end()
	{
		iterator result;
		result.current = NULL;
		return result;
	}

private:
	struct cellT
	{
		ElemType data;
		cellT *next;
	};
	cellT *head;
	cellT *tail;

	void clear();
	void copyOther(const List& other);

};

/* Constructor just zeros out the list. */
template <typename T> List<T>::List()
{
	head = NULL;
	tail = NULL;
}

/* Copy constructor invokes copyOther. */
template <typename T> List<T>::List(const List& other)
{
	copyOther(other);
}

/* Assignment operator checks for self-assignment, then clears and calls copyOther. */
template <typename T> List<T>& List<T>::operator =(const List& other)
{
	if(this != &other)
	{
		clear();
		copyOther(other);
	}
	return *this;
}

/* Destructor just calls clear. */
template <typename T> List<T>::~List()
{
	clear();
}

/* Clear iterates over the list and deletes it. */
template <typename T> void List<T>::clear()
{
	while(head)
	{
		cellT *next = head->next;
		delete head;
		head = next;
	}
	head = tail = NULL;
}

/* Append adds the element and moves the tail. */
template <typename T> void List<T>::append(const T& toAdd)
{
	/* If list is empty, create it! */
	if(head == NULL)
	{
		/* Set the head to the a new cell containing the element. */
		head = new cellT;
		head->data = toAdd;
		head->next = NULL;

		/* The last element is now the head. */
		tail = head;
		return;
	}

	/* Otherwise, chain something onto the tail and move the tail forward. */
	tail->next = new cellT;
	tail = tail->next;

	tail->data = toAdd;
	tail->next = NULL;
}

/* copyOther copies other data by using the iterator interface to
 * traverse the other container, calling append as needed.
 */
template <typename T> void List<T>::copyOther(const List& other)
{
	head = tail = NULL;
	for(iterator itr = other.begin(); itr != other.end(); ++itr)
		append(*itr);
}

const int NUM_INTS = 10;

int main()
{
	List<int> myList;
	for(int i = 0; i < NUM_INTS; ++i)
		myList.append(i);

	/* How to print elements? */
	for(List<int>::iterator itr = myList.begin(); itr != myList.end(); ++itr)
		cout << *itr << endl;

	return 0;
}