/* Lecture code 13.1
 *
 * Implementation of a const_iterator class for a List.
 */
#include <iostream>
#include <cstdlib> // For NULL
#include <algorithm>
#include <iterator>
using namespace std;

template<typename ElemType> class List
{
private:
	/* We declare cellT up here so that it's visible to the const_iterator
	 * class down below.
	 */
	struct cellT
	{
		ElemType data;
		cellT *next;
	};
public:
	List();
	List(const List& other); // Copy constructor
	List& operator =(const List& other); // Assignment operator
	~List();

	void append(const ElemType& toAdd);

	/* Allow the const_iterator access to the cellT type. */
	friend class const_iterator;
	class const_iterator
	{
	public:
		/* Comparison operators just check the underlying pointers. */
		bool operator== (const const_iterator& other) const
		{
			return curr == other.curr;
		}
		bool operator!= (const const_iterator& other) const
		{
			return curr != other.curr;
		}
		/* 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.
		 */
		const ElemType& operator* () const
		{
			return curr->data;
		}
		/* Arrow operator.  Recall that the arrow operator returns the pointer
		 * that the actual arrow should be applied to.
		 */
		const ElemType* operator-> () const
		{
			return &curr->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.
		 */
		const_iterator& operator++ ()
		{
			curr = curr->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 const_iterator operator++ (int)
		{
			const_iterator result = *this;
			curr = curr->next;
			return result;
		}

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

		friend class List;
	};

	/* 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.
	 */
	const_iterator begin() const
	{
		const_iterator result;
		result.curr = head;
		return result;
	}

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

private:
	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;
}

template <typename T> void List<T>::copyOther(const List& other)
{
	head = tail = NULL;
	for(cellT *current = other.head; current != NULL; current = current->next)
		append(current->data);
}

const int NUM_INTS = 10;

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

	for(List<int>::const_iterator itr = myList.begin(); itr != myList.end(); ++itr)
		cout << *itr << endl;
	
	return 0;
}