#ifndef __CPP_QUEUE_H
#define __CPP_QUEUE_H

#ifdef __cplusplus

#include <ubixos/types.h>
#include <lib/Pair.h>
#include <lib/Alloc.h>

template <class T> class Queue
{
    public:

	class Pair<int, T>;
    
	Queue();
	~Queue();

	void insert(const int, const T &);
	void insert(Pair<int,T> & a) { insert(a.first(), a.second()); }; 
	const Pair<int,T> find(const int) const;
	const T remove(const int);
	const T remove();
	const T top();
	const Pair<int,T> pop();
	void empty();
	int size();

	

    private:
	class Node 
	{
	    public:
		Node() : index(-1), prev(NULL), next(NULL), data() {};

		int    index;
		Node * prev;
		Node * next;
		T      data;
	};

	Node * first;
	Node * last;
	int sz;

	Alloc allocator;

};

template <class T> Queue<T>::Queue() : first(NULL), last(NULL), sz(0)
  { allocator.setSize(sizeof(Node)); };
template <class T> Queue<T>::~Queue() { while(first != NULL) this->pop(); };

template <class T>
void Queue<T>::insert(const int a, const T & b) 
{ 
    Node * temp = (Node *) allocator.allocate();
    temp->index = a;
    temp->data = b;
    
    temp->next = first;

    if (NULL == last)
	this->last = temp;
    else
	this->first->prev = temp;

    this->first = temp;

    sz++;

}

template <class T>
const Pair<int,T> Queue<T>::find(const int a) const {

    T item = T();
    bool found = false;
    Node * temp = first;

    while ((NULL != temp) && !found)
    {
	if (a == temp->index)
	{
	    item = temp->data;
	    found = true;
	}
	
	temp = temp->next;
    }

    if (found)
	return Pair<int,T>(a,item);
    else
	return Pair<int,T>(-1,item);
}

template <class T>
const T Queue<T>::remove(const int a) {
    
    T item = T();
    bool found = false;
    Node * temp = first;

    while ((NULL != temp) && !found)
    {
	if (a == temp->index)
	{
	    item = temp->data;
	    found = true;

	    if (NULL != temp->prev)
		temp->prev->next = temp->next;
	    if (NULL != temp->next)
		temp->next->prev = temp->prev;
	    if (temp == first)
		first = temp->next;
	    if (temp == last)
		last = temp->prev;

	    allocator.deallocate(temp);
	    temp = NULL;
	    
	    sz--;
	}
	
	temp = temp->next;
    }

    return item;
}

template <class T>
const T Queue<T>::remove() 
{
    T item = T();
    Node * temp;

    if (NULL != last)
    {
	item = last->data;

	if (NULL != last->prev)
	{
	    last->prev->next = NULL;
	    temp = last;
	    last = last->prev;
	    
	    delete temp;
	}
	else
	{
	    temp = last;
	    first = last = NULL;
	    delete temp;
	}
	sz--;
    }

    return item;
}

template <class T>
const T Queue<T>::top()
{
    T item = T();
    if (NULL != last)
    {
	item = last->data;
    }
    return item;
}

template <class T>
const Pair<int,T> Queue<T>::pop()
{
    T item = T();
    int index;
    bool found = false;
    Node * temp;
    
    if (NULL != first)
    {
	item = first->data;
	index = first->index;
	found = true;

	if (NULL != first->next)
	{
	    temp = first;
	    first = first->next;
	    first->prev = NULL;

	    delete temp;
	}
	else
	{
	    temp = last;
	    first = last = NULL;
	    delete temp;
	}
	sz--;
    }
    
     
    if (found)
	return Pair<int, T>(index, item);
    else
	return Pair<int, T>(-1, item);
}
	    

template <class T>
void Queue<T>::empty() { while (last != NULL) pop(); }

template <class T>
int Queue<T>::size() { return sz; }
#endif

#endif // __QUEUE_H