// http://mschat.net/
// Queue.class.h
#ifndef __QUEUE_CLASS__
#define __QUEUE_CLASS__

#ifndef NULL
#define NULL ((void*)0)
#endif

// We can't use the data type supplied to us without any modification,
// so we simply make a structure containing the value and the next item (pointer).
template <class datatype>
struct QueueNode
{
  datatype value;
  QueueNode *next;
};

// The class definition of Queue
template <class datatype>
class Queue
{
  private:
    QueueNode<datatype> *top;
    QueueNode<datatype> *bottom;
    QueueNode<datatype> *current;
    int items;

  public:
    Queue();
    ~Queue();
    void add(datatype item);
    void push(datatype item);
    datatype remove();
    datatype pop();
    int length();
    void empty();
    void reset();
    datatype next();
    datatype front();
    datatype back();
};

#include "Queue.class.cpp"

#endif

// Queue.class.cpp
#ifndef __QUEUE_CLASS__
#include "Queue.class.h"
#endif

template <class datatype>
Queue<datatype>::Queue()
{
  // Top needs to point to NULL
  top = NULL;

  // Same goes for bottom...
  bottom = NULL;

  // No items, quite yet.
  items = 0;
}

template <class datatype>
Queue<datatype>::~Queue()
{
  empty();
}

template <class datatype>
void Queue<datatype>::add(datatype item)
{
  // add is an alias of push();
  push(item);
}

template <class datatype>
void Queue<datatype>::push(datatype item)
{
  // We can't use the item supplied exactly, so we need
  // a struct to hold the value and the next item (pointer)
  QueueNode<datatype> *dummy;
  dummy = new(QueueNode<datatype>);

  // Now set dummys value.
  dummy->value = item;

  if(top == NULL)
  {
    // Top now needs to point to dummy and bottom needs to point to top ;)
    top = dummy;
    bottom = top;
    reset();
  }

  // Now we need to link the last item to the next one.
  bottom->next = dummy;

  // Bottom now needs to go to dummy, since it is now the last one.
  bottom = dummy;

  // The very last item points to nothing, for now.
  bottom->next = NULL;

  // That's one more item!!!
  items++;
}

template <class datatype>
int Queue<datatype>::length()
{
  return items;
}

template <class datatype>
void Queue<datatype>::empty()
{
  // Get rid of everything! If anything, that is.
  if(items > 0)
  {
    delete[] top;
    delete[] bottom;

    // Now set them back to NULL
    top = NULL;
    bottom = NULL;
    reset();

    items = 0;
  }
}

template <class datatype>
datatype Queue<datatype>::remove()
{
  // remove is an alias of pop();
  return pop();
}

template <class datatype>
datatype Queue<datatype>::pop()
{
  // Can't remove anything if top is NULL, can we?
  if(top != NULL)
  {
    // The first item is what we want to remove.
    QueueNode<datatype> *dummy = top;

    // Now that dummy points to top, we can make top top's next...
    top = top->next;

    // 1 less item ;)
    items--;

    // No items..? We can't have bottom pointing there.
    if(items == 0)
      bottom = NULL;

    // We need to make a new variable to hold the previous top item, so we can return it.
    datatype value = dummy->value;
    delete(dummy);

    // Oh yeah, don't forget, we now have a new top!
    reset();

    return value;
  }
  else
    return false;
}

template <class datatype>
void Queue<datatype>::reset()
{
  // Reset current to the top.
  current = top;
}

template <class datatype>
datatype Queue<datatype>::next()
{
  // Current NULL? Nothing more!!!
  if(current == NULL)
    return false;

  // Save the current value, and more to the next item.
  datatype value = current->value;
  current = current->next;

  return value;
}

template <class datatype>
datatype Queue<datatype>::front()
{
  if(top == NULL)
    return false;

  return top->value;
}

template <class datatype>
datatype Queue<datatype>::back()
{
  if(bottom == NULL)
    return false;

  return bottom->value;
}