//
// queue.hpp
//
// Definition and implementation of a generic, array-based queue class.
//
// Because we're using templates, we need to define the methods in
// this file so that the compiler won't complain.
//
// Computer Science S-111, Harvard University
//

#ifndef QUEUE_HPP
#define QUEUE_HPP

#include <assert.h>
#include "../util/s111unx.hpp"


template <class elt>
class queue {
private:
    int front;
    int rear;
    int array_size;
    elt *data;

public:
    queue();
    queue(int max);
    ~queue();
    
    void set_max(int max);
    void reinit();

    bool insert(elt source);
    bool remove(elt& target);
    elt& peek();
    void traverse(void (*action)(int, elt));

    bool empty() { return (front == rear); }
    bool full()  { return (((rear+1) % array_size) == front); }
};


//
// Default constructor
//
template <class elt>
queue<elt>::queue()
{
    array_size = 0;
    front = 0;
    rear = 0;
    data = NULL;
}

//
// Constructor that takes the maximum number of items
//
template <class elt>
queue<elt>::queue(int max)
{
    data = NULL;
    set_max(max);
}

//
// Destructor
//
template <class elt>
queue<elt>::~queue()
{
    if (data != NULL)
	delete [] data;
}

//
// set_max - (re)initialize the queue to the specified maximum size
//
template <class elt>
void
queue<elt>::set_max(int max)
{
    assert(max > 0);

    if (data != NULL)
	delete [] data;

    //
    // We need one extra element because of our convention
    // that front is the index of the element ahead of the
    // item at the front.
    //
    array_size = max + 1;
    data = new elt[array_size];

    front = rear = 0;
}

//
// reinit - returns to an empty queue
//
template <class elt>
void
queue<elt>::reinit()
{
	front = rear = 0;
}

//
// insert - insert specified item (source) at the back of the queue, 
// returning false if queue is full.
//
template <class elt>
bool
queue<elt>::insert(elt source)
{
    if (full())
	return false;

    //
    // rear is the index of the item that's currently at the rear
    // of the queue.  Thus, we increment it (and do mod to handle
    // wrap-around) before using it as an index for the new item.
    //
    rear = (rear + 1) % array_size;
    data[rear] = source;

    return true;
}

//
// remove - removes item from the front of the queue into target,
// returning false if queue is empty.
//
template <class elt>
bool
queue<elt>::remove(elt& target)
{
    if (empty())
	return false;

    //
    // front is the index of the item that was removed last (one
    // place ahead of the item at the front).  Thus, we increment it
    // (and do mod to handle wrap-around) before using it as an index
    // for the item being removed.
    //
    front = (front + 1) % array_size;
    target = data[front];

    return true;
}

//
// peek - returns a reference to the front item without removing it
//
template <class elt>
elt&
queue<elt>::peek()
{
      assert (!empty());
      return data[(front+1) % array_size];
}

//
// traverse - traverses queue from front to back, applying
// specified function to each element in the queue.
//
template <class elt>
void
queue<elt>::traverse(void (*action)(int, elt))
{
    int pos;

    pos = front;
    while (pos != rear) {
	pos = (pos + 1) % array_size;
	(*action)(pos, data[pos]);
    }
}

#endif
