/*
 *
 * Minimal Queue Implementation
 *
 * Author: Gamblers doth Idyl blog
 *
 * From my blog posts about brushing up on some old techniques
 * This is not intended to be a full implementation, just an example to 
 * demonstrate some basic principles.
 *
 *
 *
 *
 * Changes and Additions
 *
 * 0.21 Apr 29 2008
 * Refactoring to hide QueueItem
 * 
 * 0.2 Apr 28 2008
 * Addition of an "STL style" iterator
 *
 * 0.1 Apr 26 2008
 *
 *
 *
 * Do with this code what you like.
 * I place this in the public domain. No warranty expressed or implied.
 * 
 *
 */


#ifndef _QUEUE_H_
#define _QUEUE_H_

#include <cassert>



template <class T>
struct Queue {
	
	Queue() {
		num_items = 0;
		head = tail = NULL;
	}
	
	~Queue() {
		
		// delete all items in the queue - just pop them all off
		T tmp; while (pop(tmp));
	}
	
	void push(const T item) {
		
		QueueItem* new_item = new QueueItem(item);
		
		if (num_items > 0) 
			new_item->next = head;
		else
			tail = head;
		
		head = new_item;
		num_items++;
	}
	
	bool pop(T& item) {
		
		bool res = false;
		
		if (!is_empty()) {
			
			// return the data at the head of the queue
			item = head->data;
			
			// now make the 2nd in the queue the first
			QueueItem* tmp = head;
			head = head->next;
			delete tmp;
			
			num_items--;
			
			res = true;
		}
		
		return res;
	}
	
	void push_back(const T item) {
		
		QueueItem* new_item = new QueueItem(item);
		
		if (is_empty()) {
			head = tail = new_item;
		} else {
			tail->next = new_item;
			tail = new_item;
		}
		num_items++;
	}
	
	bool is_empty() {
		return (num_items == 0);
	}
	
	unsigned long size() {
		return num_items;
	}
	
	const T peek() {
		
		assert(head);
		return head->data;
	}
	

	private:
	
	struct QueueItem {
		
		QueueItem(T data_) {
			data = data_;
			next = NULL;
		}
		
		T data;
		QueueItem* next;
	};

	QueueItem *head, *tail;
	unsigned long num_items;
	
	public:
	
	struct iterator
	{
		iterator(QueueItem* head) { pointer = head; }
		
		bool operator==(const iterator& rhs) {
			return (pointer == rhs.pointer);
		}
		
		bool operator!=(const iterator& rhs) {
			return (pointer != rhs.pointer);
		}
		
		void operator++(int) {
			if (pointer)
				pointer = pointer->next;
		}
		
		T operator*() {
			
			if (pointer)
				return pointer->data;
			else 
				return T();
		}
		
		private:
		
		QueueItem* pointer;
	};

	iterator begin() { return iterator(head); }
	iterator end() { return iterator(NULL); }
	
	
};



#endif