#ifndef QUEUE_H
#define QUEUE_H

#include <iostream>

const int null = 0;

template <typename DataType>
class Queue
{
  private:

	/// For each element stored in the queue, a Node is created to keep pointers to
	/// the next element. Note Node is for Queue class use exclusively (private)
	struct Node
	{
		/// A copy of the original element to be stored in the queue
		DataType data;
		/// A pointer to the next node in the queue
		Node* next;

	  public:
		/// Conversion constructor
		explicit Node(const DataType& data) : data(data), next(null) { }
	};

  private:
	/// A pointer to the first node in the queue. Null if queue is empty
	Node* head;
	/// A pointer to the last node in the queue. Null if queue is empty
	Node* tail;
	/// The count of elements currently stored in the queue
	size_t size;

  public:
	/// Default constructor
	Queue() : head(null), tail(null), size(0) { }
	/// Destructor: when the queue is destroyed, all its values are deleted also
	~Queue()
	{
		clear();
	}
	/// Returns true if queue is empty
	inline bool empty() const { return head == null; }
	/// Adds a copy of the given element into the queue
	/// @return true on success, false if not enough memory
	bool add(const DataType& data)
	{
		Node* node = new Node(data);
		if ( ! node ) return false;

		if ( empty() )
			tail = head = node;
		else
			tail = tail->next = node;

		return ++size;
	}
	/// Remove all elements from the queue
	void clear()
	{
		for ( Node* node = head; head; node = head)
		{
			head = head->next;
			delete node;
		}

		tail = null;
		size = 0;
	}
	/// Prints all elements of the queue to the given output stream
	/// @param output File or stream to print
	/// @param separator Each element will be separated from another with this text
	std::ostream& print(std::ostream& output, const char* separator = " ") const
	{
		for ( Node* node = head; node; node = node->next)
			output << node->data << separator;
		return output;
	}

  public:
	/// Allows traversing the queue or pointing to a specific value in the queue
	class ConstIterator
	{
	  private:
		/// An iterator mimics a pointer to this element which is stored in the queue
		const Node* node;

	  public:
		/// Default constructor and conversion constructor
		explicit ConstIterator(const Node* node = null) : node(node) { }
		/// Returns true if this iterator points to the same element than other iterator
		inline bool operator!=(const ConstIterator& other) const { return node != other.node; }
		/// Get read-only access to the pointed element in array
		inline const DataType& operator*() const { return node->data; }
		/// Pre-increment operator: ++itr
		const ConstIterator& operator++()
		{
			node = node->next;
			return *this;
		}
		/// Post-increment operator: itr++
		ConstIterator operator++(int)
		{
			ConstIterator previous(node);
			node = node->next;
			return previous;
		}
	};

	/// Returns an iterator to the first element in the queue
	inline ConstIterator begin() const { return ConstIterator(head); }
	/// Returns an iterator to an invalid position in the queue
	inline ConstIterator end() const { return ConstIterator(); }

  private:
	Queue(const Queue& other);
	const Queue& operator=(const Queue& other);
};

/// Allows std::cout << myqueue1 << myqueue2 << ... ;
template <typename DataType>
std::ostream& operator<<(std::ostream& output, const Queue<DataType>& queue)
{
	return queue.print(output);
}

#endif // QUEUE_H