//
// qlink.hpp
//
// Definition and implementation of a generic, linked-list-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 QLINK_HPP
#define QLINK_HPP

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


// Class for nodes in the queue.
template <class elt>
class qnode {
public:
    elt data;
    qnode<elt> *next;
};

// Class for the queue itself.
template <class elt>
class queue {
private:
    qnode<elt> *front;
    qnode<elt> *rear;
    int num_items;
    int max_items;
    
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 == NULL); }
    bool full()  { return (num_items == max_items); }
};


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

    //
    // We don't enforce a max size unless the user specifies one.
    // Using a default value of -1 for max_items guarantees that 
    // full() will return false.
    //
    max_items = -1;
}

//
// Constructor that takes the maximum number of items
//
template <class elt>
queue<elt>::queue(int max)
{
    front = NULL;
    rear = NULL;
    num_items = 0;
    max_items = max;
}

//
// Destructor
//
template <class elt>
queue<elt>::~queue()
{
    reinit();
}

//
// set_max - reinitialize the queue and set a maximum size for it
//
template <class elt>
void
queue<elt>::set_max(int max)
{
    reinit();
    max_items = max;
}

//
// reinit - returns to an empty queue
//
template <class elt>
void
queue<elt>::reinit()
{
    elt junk;
    while (!empty()) 
	remove(junk);
}

//
// 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;
    
    qnode<elt> *n = new qnode<elt>;
    n->data = source;
    n->next = NULL;

    if (empty()) 
	front = rear = n;
    else {
	rear->next = n;
	rear = n;
    }
    num_items++;

    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;

    target = front->data;

    // Keep a pointer to the node so we can delete it below.
    qnode<elt>* temp = front;   

    if (front == rear)  // removing the last node
	front = rear = NULL;
    else 
	front = front->next;

    num_items--;
    delete temp;

    return true;
}

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

//
// 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))
{
    if (front == NULL)
	return;

    qnode<elt>* trav = front;
    int pos = 1;

    while (trav != NULL) {
	(*action)(pos, trav->data);
	trav = trav->next;
	pos++;
    } 
}

#endif
