/**********************************************************************************
*  Queue.c
*  Implementation file for Queue ADT
***********************************************************************************/

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

/************** Private Structs: not exported *************************************/

typedef struct Node
{
   int data;
   struct Node* next;
} Node;

typedef struct QueueStruct
{
   Node* front;
   Node* back;
   int length;
} QueueStruct;


/************** Constructors-Destructors ******************************************/

/*
*  NewNode
*  Returns pointer to new Node struct. Initializes next field to NULL, and sets
*  data field to input parameter node_data. Private.
*/
Node*  NewNode(int node_data)
{
   Node* N = malloc(sizeof(Node));
   N->data = node_data;
   N->next = NULL;
   return(N);
}

/*
*  FreeNode
*  Frees heap memory pointed to by pNode. Private.
*/
void FreeNode(Node* N) { free(N); }

/*
*  NewQueue
*  Returns QueueHndl pointing to new QueueSturct which represents an empty Queue.
*  Initializes front and back fields to NULL, sets length field to 0.  Exported.
*/
QueueHndl NewQueue(void)
{
   QueueHndl Q;
   Q = (QueueStruct*) malloc(sizeof(QueueStruct));
   Q->front = Q->back = NULL;
   Q->length = 0;
   return(Q);
}

/*
*  FreeQueue
*  Frees all heap memory associated with the QueueHndl *Qp, including all memory
*  in existing Nodes.  Sets *Qp to NULL.  Exported.
*/
void FreeQueue(QueueHndl* Qptr)
{
   if(Qptr==NULL || *Qptr==NULL) { return; }
   while( !isEmpty(*Qptr) ) { Dequeue(*Qptr); }
   free(*Qptr);
   *Qptr = NULL;
}



/***************** Access functions ***********************************************/

/*
*  getFront
*  Returns the value at the front of Q.
*  Pre: !isEmpty(Q)
*/
int getFront(QueueHndl Q)
{
   if( Q==NULL )
   {
      printf("Queue Error: calling getFront() on NULL QueueHndl\n");
      exit(1);
   }
   if( isEmpty(Q) )
   {
      printf("Queue Error: calling getFront() on an empty Queue\n");
      exit(1);
   }
   return(Q->front->data);
}

/*
*  getLength
*  Returns the length of Q
*/
int getLength(QueueHndl Q) 
{
   if( Q==NULL )
   {
      printf("Queue Error: calling getLength() on NULL QueueHndl\n");
      exit(1);
   } 
   return(Q->length); 
}

/*
*  isEmpty
*  Returns True if Q is empty, otherwise returns false
*/
boolean isEmpty(QueueHndl Q) 
{
   if( Q==NULL )
   {
      printf("Queue Error: calling isEmpty() on NULL QueueHndl\n");
      exit(1);
   }
   return(Q->length==0); 
}



/**************** Manipulation procedures ****************************************/

/*
*  Enqueue
*  Places new data element at the end of Q
*  Post: !isEmpty(Q)
*/
void Enqueue(QueueHndl Q, int data)
{
   Node* N = NewNode(data);

   if( Q==NULL )
   {
      printf("Queue Error: calling Enqueue() on NULL QueueHndl\n");
      exit(1);
   }
   if( isEmpty(Q) ) { Q->front = Q->back = N; }
   else { Q->back->next = N; Q->back = N; }
   Q->length++;
}

/*
*  Dequeue
*  Deletes element at front of Q
*  Pre: !isEmpty(Q)
*/
void Dequeue(QueueHndl Q)
{
   Node* N = NULL;

   if( Q==NULL )
   {
      printf("Queue Error: calling Dequeue() on NULL QueueHndl\n");
      exit(1);
   }
   if( isEmpty(Q) )
   {
      printf("Queue Error: calling Dequeue on an empty Queue\n");
      exit(1);
   }
   N = Q->front;
   if( getLength(Q)>1 ) { Q->front = Q->front->next; }
   else { Q->front = Q->back = NULL; }
   Q->length--;
   FreeNode(N);
}


/*************** Other Functions *************************************************/

/*
*  printQueue
*  Prints data elements in Q on a single line to stdout.
*/
void printQueue(QueueHndl Q)
{
   Node* N = NULL;

   if( Q==NULL )
   {
      printf("Queue Error: calling printQueue() on NULL QueueHndl\n");
      exit(1);
   }
   for(N = Q->front; N != NULL; N = N->next)
   {
      printf("%d ", N->data);
   }
   printf("\n");
}

/*
*  equals  
*  returns true if A is identical to B, false otherwise
*/
boolean equals(QueueHndl A, QueueHndl B)
{
   boolean flag = true;
   Node* N = A->front;
   Node* M = B->front;

   if( A==NULL || B==NULL )
   {
      printf("Queue Error: calling equals() on NULL QueueHndl\n");
      exit(1);
   }
   if( A->length != B->length ) { return false; }
   while( flag && N!=NULL)
   {
      flag = (N->data==M->data);
      N = N->next;
      M = M->next;
   }
   return flag;
}