/**
 * Queue class from before modified to use a linked list instead
 * of a statically allocated array.  Use with example application
 * (flood fill) from before.
 */

using namespace std;

#include <cassert>
#include <cstdlib>

#include "queue.h"

/**
 * Constructs an empty queue.
 */

Queue::Queue()
{
  // initialize pointer to non-existant first element

  first = NULL;
}

/**
 * pre: none
 * post: returns true iff the queue is full.
 */

bool Queue::isFull() const
{
  // assume unlimited memory again

  return false;
}

/**
 * pre: none
 * post: returns true iff the queue is empty
 */

bool Queue::isEmpty() const
{
  // empty iff no first

  return (first == NULL);
}

/**
 * pre: this queue is not empty
 * post: the front element is removed from this queue and copied into the
 * parameter
 */

void Queue::dequeue(ItemType& dequeued)
{
  assert(!isEmpty());

  // get info out of first elt
  dequeued = first->info;

  // remember where old first was so we can delete it later
  Node* oldFirst = first;

  // set first to next node
  first = first->next;

  // remove old first to avoid memory leak
  delete oldFirst;
}

/**
 * pre: none
 * post: the queue is empty
 */

void Queue::makeEmpty()
{
  Node *curr = first;

  // run through all nodes, deleting each one

  while (curr != NULL)
    {
      Node *temp = curr->next;
      delete curr;
      curr = temp; // can't do standard curr = curr->next here since we deleted curr
    }

  first = NULL;
}

/**
 * pre: this queue is not full
 * post: item toAdd has been added to this queue
 */

void Queue::enqueue(const ItemType& toAdd)
{
  assert(!isFull());

  // make and initialize new node
  Node *newLast = new Node;
  newLast->info = toAdd;
  newLast->next = NULL;

  // special case for first add
  if (first == NULL)
    first = newLast;
  else
    {
      // find last node
      
      Node* last = first;
      while (last->next != NULL)
	last = last->next;

      // link last node to new node
      last->next = newLast;
    }
}