/*****************************************************************************
 * File: ListSet.h
 *
 * An implementation of a multiset backed by a linked list.  Not very efficient,
 * but quite didactic!
 */

#ifndef ListSet_Included
#define ListSet_Included

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

template <typename T> class ListSet {
public:
	/* Create or destroy a ListSet. */
	ListSet();
	~ListSet();

	/* Append a new element. */
	void insert(const T& elem);

	/* Check whether an element exists. */
	bool contains(const T& elem) const;

	/* Mention that there's a const_iterator type, and that begin and
	 * end create them.
	 */
	class const_iterator;
	const_iterator begin() const;
	const_iterator end() const;

private:
	/* A cell in the linked list. */
	struct cellT {
		T data;
		cellT *next;
	};

	cellT* head;
	
	/* In order for const_iterator to access the cellT struct, it needs
	 * to be a friend.
	 */
	friend class const_iterator;
};

/* Actual declaration of the const_iterator type. */
template <typename T>
class ListSet<T>::const_iterator {
public:
	/* operator* is a pointer dereference.  It just returns the data in question. */
	const T& operator* () const {
		return curr->data;
	}

	/* The arrow operator returns the object that the arrow should really be applied
	 * to.  This "&**this" trick works by dereferencing the iterator to get the value
	 * being referenced, then taking its address.
	 */
	const T* operator-> () const {
		return &**this;
	}
	
	/* Comparison operators just compare the underlying pointers. */
	bool operator== (const const_iterator& other) const {
		return curr == other.curr;
	}
	bool operator!= (const const_iterator& other) const {
		return !(*this == other);
	}

	/* Increment operators - preincrement (below) and postincrement.
	 * The preincrement operator bumps the iterator forward by walking
	 * forward in the list, then returning a reference to the iterator
	 * itself.
	 */
	const_iterator& operator++ () {
		curr = curr->next;
		return *this;
	}
	
	/* The postincrement operator works by caching the value of the
	 * iterator, bumping it forward using preincrement, then returning
	 * the old value.
	 */
	const const_iterator operator++ (int dummy) {
		const_iterator result = *this; // Cache old value
		++*this;                       // Invoke preincrement
		return result;                 // Return old value
	}

private:
	cellT* curr;

	/* Necessary so begin() and end() can create iterators. */
	friend class ListSet<T>;
};

/* Constructor sets the ListSet's head pointer to NULL. */
template <typename T> ListSet<T>::ListSet() : head(NULL) {
	// Handled in initializer list
}

/* Traverses the list, deleting elements as they are encountered. */
template <typename T> ListSet<T>::~ListSet() {
	cellT* theList = head;
	while (theList != NULL) {
		cellT* next = theList->next;
		delete theList;
		theList = next;
	}
}

/* Prepends an element to the start of the list. */
template <typename T> void ListSet<T>::insert(const T &elem) {
	cellT* newCell = new cellT;
	newCell->data = elem;
	newCell->next = head;
	head = newCell;
}

/* Traverses the list checking whether an element exists. */
template <typename T> bool ListSet<T>::contains(const T& elem) const {
	for (cellT* theList = head; theList != NULL; theList = theList->next)
		if (theList->data == elem)
			return true;

	return false;
}

/* begin() and end() just synthesize iterators to the first element of the
 * list, and to NULL (the element one step past the end).
 */
template <typename T>
typename ListSet<T>::const_iterator ListSet<T>::begin() const {
	const_iterator result;
	result.curr = head;
	return result;
}
template <typename T>
typename ListSet<T>::const_iterator ListSet<T>::end() const {
	const_iterator result;
	result.curr = NULL;
	return result;
}

#endif