#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_SINGLE_LIST
#define CA_UWATERLOO_ALUMNI_DWHARDER_SINGLE_LIST

#include "Single_node.h"
#include "Exception.h"
#include <iostream>

// Author:  Douglas Wilhelm Harder
// Copyright (c) 2011 by Douglas Wilhelm Harder.  All rights reserved.

namespace Data_structures {
	template <typename Type>
	class Single_list {
		private:
			Single_node<Type> *list_head;
			Single_node<Type> *list_tail;
			Single_node<Type> *head() const;
			Single_node<Type> *tail() const;
	
		public:
			class iterator;
	
			Single_list();
			~Single_list();
	
			// Mutators
	
			void push_front( const Type & );
			void push_back( const Type & );
			void pop_front();
	
			class iterator {
				private:
					iterator( Single_node<Type> * );
					Single_node<Type> *current;
				public:
					Type &operator*();
					iterator operator++();
					iterator operator++( int );
					bool operator==( iterator const & ) const;
					bool operator!=( iterator const & ) const;
	
				friend class Single_list;
			};
	
			iterator find( Type const & ) const;
			iterator begin() const;
			iterator end() const;
	
		// Friends
	
		template <typename T>
		friend std::ostream &operator<<( std::ostream &, const Single_list<T> & );
	};
	
	template <typename Type>
	Single_list<Type>::Single_list():
	list_head(0),
	list_tail(0) {
		// Empty constructor
	}
	
	template <typename Type>
	Single_list<Type>::~Single_list() {
		while ( head() != 0 ) {
			pop_front();
		}
	}
	
	template <typename Type>
	Single_node<Type> *Single_list<Type>::head() const {
		return list_head;
	}
	
	template <typename Type>
	typename Single_list<Type>::iterator Single_list<Type>::begin() const {
		return iterator( head() );
	}
	
	template <typename Type>
	typename Single_list<Type>::iterator Single_list<Type>::end() const {
		return iterator( 0 );
	}
	
	template <typename Type>
	Single_node<Type> *Single_list<Type>::tail() const {
		return list_tail;
	}
	
	template <typename Type>
	typename Single_list<Type>::iterator Single_list<Type>::find( const Type &obj ) const {
		for ( Single_node<Type> *ptr = list_head; ptr != 0; ptr = ptr->next() ) {
			if ( ptr->retrieve() == obj ) {
				return iterator( ptr );
			}
		}
	
		return iterator( 0 );
	}
	
	template <typename Type>
	void Single_list<Type>::push_front( const Type &obj ) {
		if ( head() == 0 ) {
			list_head = new Single_node<Type>( obj );
			list_tail = list_head;
		} else {
			list_head = new Single_node<Type>( obj, list_head );
		}
	}
	
	template <typename Type>
	void Single_list<Type>::push_back( const Type &obj ) {
		if ( head() == 0 ) {
			list_head = new Single_node<Type>( obj );
			list_tail = list_head;
		} else {
			list_tail->next_node = new Single_node<Type>( obj, 0 );
			list_tail = list_tail->next();
		}
	}
	
	template <typename Type>
	void Single_list<Type>::pop_front() {
		if ( head() == 0 ) {
			throw underflow();
		}
	
		if ( head()->next() == 0 ) {
			delete list_head;
			list_head = 0;
			list_tail = 0;
		} else {
			Single_node<Type> *tmp = list_head;
			list_head = list_head->next();
			delete tmp;
		}
	}
	
	template <typename Type>
	Single_list<Type>::iterator::iterator( Single_node<Type> *ptr ):
	current( ptr ) {
		// empty constructor
	}
	 
	template <typename Type>
	Type &Single_list<Type>::iterator::operator*() {
		return current->element;
	}
	
	template <typename Type>
	typename Single_list<Type>::iterator Single_list<Type>::iterator::operator++() {
		if ( current != 0 ) {
			current = current->next();
		}
	
		return iterator( current );
	}
	
	template <typename Type>
	typename Single_list<Type>::iterator Single_list<Type>::iterator::operator++( int ) {
		Single_node<Type> *previous = current;
	
		if ( current != 0 ) {
			current = current->next();
		}
	
		return iterator( previous );
	}
	
	template <typename Type>
	bool Single_list<Type>::iterator::operator==( Single_list<Type>::iterator const &itr ) const {
		return current == itr.current;
	}
	
	template <typename Type>
	bool Single_list<Type>::iterator::operator!=( Single_list<Type>::iterator const &itr ) const {
		return current != itr.current;
	}
	
	template <typename T>
	std::ostream &operator<<( std::ostream &out, const Single_list<T> &list ) {
		for ( Single_node<T> *ptr = list.head(); ptr != 0; ptr = ptr->next() ) {
			out << " -> " << ptr->retrieve();
		}
	
		out << " -> 0";
	
		return out;
	}
	
}

#endif