// Arup Guha
// 6/26/07
// Example of how to implement a queue with a linked list.

/*** Added code on 10/11/2023 for COP 3502 Exam 1 Thursday Part A Question 4 ***/
#include <stdio.h>
#include <stdlib.h>

#define EMPTY -1

// Stores one node of the linked list.
struct node {
    int data;
    struct node* next;
};

// Stores our queue.
struct queue {
    struct node* front;
    struct node* back;
};

void init(struct queue* qPtr);
int enqueue(struct queue* qPtr, int val);
int dequeue(struct queue* qPtr);
int empty(struct queue* qPtr);
void simulate(struct queue* qPtr);

int main() {

    struct queue mine;
    init(&mine);
    enqueue(&mine, 3);
    enqueue(&mine, 7);
    enqueue(&mine, 2);
    enqueue(&mine, 5);
    enqueue(&mine, 4);
    enqueue(&mine, 13);
    simulate(&mine);
    return 0;
}

/*** Solution to question 4...Here I print out the iteration as well for debugging and verification purposes. ***/
void simulate(struct queue* qPtr) {

    // Start our counter.
    int cnt = 1;

    // Keep going until queue is empty.
    while (!empty(qPtr)) {

        // Get the next item.
        int cur = dequeue(qPtr);

        // Here we print.
        if (cnt%cur == 0)
            printf("itr:%d num:%d\n", cnt, cur);

        // Here we put it in the back of the queue.
        else
            enqueue(qPtr, cur);

        // Increment...
        cnt++;
    }
}

// Pre-condition: qPtr points to a valid struct queue.
// Post-condition: The struct that qPtr points to will be set up to represent an
//                 empty queue.
void init(struct queue* qPtr) {

     // Just set both pointers to NULL!
     qPtr->front = NULL;
     qPtr->back = NULL;
}

// Pre-condition: qPtr points to a valid struct queue and val is the value to
//                enqueue into the queue pointed to by qPtr.
// Post-condition: If the operation is successful, 1 will be returned, otherwise
//                 no change will be made to the queue and 0 will be returned.
int enqueue(struct queue* qPtr, int val) {

    struct node* temp;

    // Allocate space for a new node to add into the queue.
    temp = (struct node*)malloc(sizeof(struct node));

    // This case checks to make sure our space got allocated.
    if (temp != NULL) {

        // Set up our node to enqueue into the back of the queue.
        temp->data = val;
        temp->next = NULL;

        // If the queue is NOT empty, we must set the old "last" node to point
        // to this newly created node.
        if (qPtr->back != NULL)
            qPtr->back->next = temp;

        // Now, we must reset the back of the queue to our newly created node.
        qPtr->back = temp;

        // If the queue was previously empty we must ALSO set the front of the
        // queue.
        if (qPtr->front == NULL)
            qPtr->front = temp;

        // Signifies a successful operation.
        return 1;
    }

    // No change to the queue was made because we couldn't find space for our
    // new enqueue.
    else
        return 0;
}

// Pre-condition: qPtr points to a valid struct queue.
// Post-condition: If the queue pointed to by qPtr is non-empty, then the value
//                 at the front of the queue is deleted from the queue and
//                 returned. Otherwise, -1 is returned to signify that the queue
//                 was already empty when the dequeue was attempted.
int dequeue(struct queue* qPtr) {

    struct node* tmp;
    int retval;

    // Check the empty case.
    if (qPtr->front == NULL)
        return EMPTY;

    // Store the front value to return.
    retval = qPtr->front->data;

    // Set up a temporary pointer to use to free the memory for this node.
    tmp = qPtr->front;

    // Make front point to the next node in the queue.
    qPtr->front = qPtr->front->next;

    // If deleting this node makes the queue empty, we have to change the back
    // pointer also!
    if (qPtr->front == NULL)
        qPtr->back = NULL;

    // Free our memory.
    free(tmp);

    // Return the value that just got dequeued.
    return retval;
}

// Pre-condition: qPtr points to a valid struct queue.
// Post-condition: returns true iff the queue pointed to by pPtr is empty.
int empty(struct queue* qPtr) {
    return qPtr->front == NULL;
}