// Programmer:  Aaron Shbeeb
// File:  Queue_2.h
// Created:  07-27-03
// Updated:  08-13-03

#ifndef MYQUEUE_2_H
#define MYQUEUE_2_H

#include "../Queue/Queue.h"
#include "../Keywords.h"
#include "../Macros.h"

namespace ShbeebLib
{

#define CURR 0

template <typename T>
class Queue_Node
{
public:
	T data;
	Queue_Node<T>* next;
};

template <typename T>
concrete_class Queue_2
{
public:
	//Basic Operations
	procedure Enqueue(consumes T& item);
	procedure Dequeue(produces T& item);
	function  int  Length();
	function  T&   operator[](preserves int dummy);

	//Constructor/Destructor
	Queue_2();
	~Queue_2();

	//Standard Operations
	procedure Clear();
	procedure operator&=(alters Queue_2<T>& q);

protected:
	Queue_Node<T>* first;
	Queue_Node<T>* last;
	int len;

	procedure Initialize();
	procedure Finalize();
};

//Basic Operations
template <typename T>
procedure_body Queue_2<T>::
Enqueue(consumes T& item)
{
	Queue_Node<T>* tmp;

	tmp = new Queue_Node<T>;
	Swap(tmp->data, item);
	tmp->next = 0;	//next is always null

	if(last == 0)	//there's currently nothing in the queue
	{
		last = tmp;
		first = tmp;
	}else{	//this is a non-empty queue
		last->next = tmp;
		last = tmp;
	}

	len++;
}

template <typename T>
procedure_body Queue_2<T>::
Dequeue(produces T& item)
{
	Queue_Node<T>* tmp;
	Swap(item, first->data);

	tmp = first;
	first = first->next;

	if(len == 1)
	{
		first = last = 0;
	}

	len--;
	delete tmp;
}

template <typename T>
function_body int Queue_2<T>::
Length()
{
	return len;
}

template <typename T>
function_body T& Queue_2<T>::
operator[](preserves int current)
{
	return first->data;
}

//Constructor/Destructor
template <typename T>
Queue_2<T>::
Queue_2()
{
	Initialize();
}

template <typename T>
Queue_2<T>::
~Queue_2()
{
	Finalize();
}

//Standard Operations
template <typename T>
procedure_body Queue_2<T>::
Clear()
{
	Finalize();
	Initialize();
}

template <typename T>
procedure_body Queue_2<T>::
operator&=(alters Queue_2<T>& q)
{
	first = (Queue_Node<T>*)((unsigned int)first ^ (unsigned int)q.first);
	q.first = (Queue_Node<T>*)((unsigned int)q.first ^ (unsigned int)first);
	first = (Queue_Node<T>*)((unsigned int)first ^ (unsigned int)q.first);

	last = (Queue_Node<T>*)((unsigned int)last ^ (unsigned int)q.last);
	q.last = (Queue_Node<T>*)((unsigned int)q.last ^ (unsigned int)last);
	last = (Queue_Node<T>*)((unsigned int)last ^ (unsigned int)q.last);

	swap(len,q.len);
}

//Protected Operations
template <typename T>
procedure_body Queue_2<T>::
Initialize()
{
	first = last = 0;
	len = 0;
}

template <typename T>
procedure_body Queue_2<T>::
Finalize()
{
	while(first)
	{
		Queue_Node<T>* tmp;

		tmp = first;
		first = first->next;

		delete tmp;
	}
}

}//end namespace ShbeebLib

#endif