/**********************************************************************************
*  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 Node* NodeRef;

typedef struct Queue{
   NodeRef front;
   NodeRef back;
   int length;
} Queue;


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

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

/*
*  freeNode
*  Frees heap memory pointed to by pN. Private.
*/
void freeNode(NodeRef* pN){
   if( pN!=NULL && *pN!=NULL ){
      free(*pN);
      *pN = NULL;
   }
}


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

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



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

/*
*  getFront
*  Returns the value at the front of Q.
*  Pre: !isEmpty(Q)
*/
int getFront(QueueRef Q){
   if( Q==NULL ){
      printf("Queue Error: calling getFront() on NULL QueueRef\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(QueueRef Q){
   if( Q==NULL ){
      printf("Queue Error: calling getLength() on NULL QueueRef\n");
      exit(1);
   }
   return(Q->length);
}

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



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

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

   if( Q==NULL ){
      printf("Queue Error: calling Enqueue() on NULL QueueRef\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(QueueRef Q){
   NodeRef N = NULL;

   if( Q==NULL ){
      printf("Queue Error: calling Dequeue() on NULL QueueRef\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(QueueRef Q){
   Node* N = NULL;

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

/*
*  equals
*  returns 1 if A is identical to B, 0 otherwise
*/
int equals(QueueRef A, QueueRef B){
   int flag = 1;
   Node* N = NULL;
   Node* M = NULL;

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