/************************************************\
* Filename:      queue.c                         *
* Author:        Sue Bogar                       *
* Date Written:  4/22/98                         *
* Section:       101                             *
* SSN:           123-45-6789                     *
* EMail:         bogar@cs.umbc.edu               *
*                                                *
* Description:  This file contains the functions *
* necessary to work with a queue.                *
* This set of functions provide the operations   *
* needed including adding an item to the queue,  *
* enqueue; deleting an item from the queue,      *
* dequeue; determining if the queue is empty and *
* the printing the items in the queue.           *
* Since the queue is being implemented as a      *
* linked list, some functions needed for a list  *
* have been added to this file, although they    *
* would normally be in a seperate header file,   *
* the one for linked lists.  Those functions     *
* are CreateNode and GetData.                    *
\************************************************/

#include <stdio.h>
#include <stdlib.h>

#include "queue.h"
#include "queens.h"

/******************
* Enqueue takes two pointers to NODEPTRs, and a
* NODEPTR as arguments.  The first argument will
* contain the address of head, the second argument
* will contain the address of tail, and the third
* argument is a pointer to the node to be inserted.  
* Enqueue will insert the item at the end of the 
* queue.  The address of head and tail are passed 
* into this function, because this function may
* need to change the address held in head, and 
* always changes the address held in tail.
******************/ 

void Enqueue (NODEPTR* headPtr, 
	      NODEPTR* tailPtr, NODEPTR temp)
{
  /* printf ("At start of enqueue: headptr %p, tailptr %p\n",
   *headPtr, *tailPtr); */
   if (IsEmpty (*headPtr))
   {
     /* printf ("   Adding to empty list\n"); */
      *headPtr = temp;
      *tailPtr = temp;
   }
   else
   {
     /* printf ("    Adding to end of list\n"); */
      (*tailPtr) -> next = temp;
      *tailPtr = temp;
   }
   /* printf ("At end of enqueue: headptr %p, tailptr %p\n",
    *headPtr, *tailPtr); */
   /* printf ("In Enqueue, the queue is:\n"); */
   /* PrintQueue (*headPtr); */
}


/******************
* Dequeue takes two pointers to NODEPTR as 
* its arguments.  The first argument will
* contain the address of head, the second 
* argument will contain the address of tail.
* This function removes an item from the 
* queue and returns the data value stored 
* there.  This function may alter the addresses 
* held in either head or tail.
******************/ 
BOARDPTR Dequeue (NODEPTR *headPtr, NODEPTR *tailPtr)
{
   BOARDPTR value;
   NODEPTR temp;

   if (IsEmpty (*headPtr))
   {
      printf ("Can't delete from an empty queue\n");
      return (NULL);
   }
   else
   {
      temp = *headPtr;
      value = (*headPtr) -> data;
      *headPtr = (*headPtr) -> next;
      
      if (*headPtr == NULL)
      {
	 *tailPtr = NULL;
      }
      free (temp);
      return (value);
   }      
}


/******************
 * PrintQueue takes a NODEPTR as an argument 
 * which is initially the head. The queue is 
 * traversed and the value of the data member 
 * of each item is printed. 
 ******************/ 
void PrintQueue (NODEPTR curr) 
{ 
  if (IsEmpty (curr)) 
    { 
      printf ("The queue is empty\n\n");
    }
  else 
    { 
      printf ("The queue contains :\n"); 
      /*Until the end of the list*/
      while (curr != NULL) 
	{ 
	  /* print the current data item */ 
	  PrintBoard(curr -> data);
	  /* move to the next node */ 
	  curr = curr -> next; 
	} 
      printf ("\n\n"); 
    } 
}