#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 100

typedef struct {
    int data[SIZE];
    int front;
    int rear;
} CircularQueue;

void init_circular_queue(CircularQueue *q){
    q->front = -1;
    q->rear = -1;
}


// Circular Queue functions
int emptyq(CircularQueue *q) {
    return q->front == -1;
}

int fullq(CircularQueue *q) {
    return (q->rear + 1) % SIZE == q->front;
}

void addq(CircularQueue *q, int val) {
    if(fullq(q)) {
        printf("Queue is full!");
        exit(1);
    } else {
        if(emptyq(q))
            q->front = 0;
        q->rear = (q->rear + 1) % SIZE;
        q->data[q->rear] = val;
    }
}

int deleteq(CircularQueue *q) {
    if(emptyq(q)) {
        printf("Queue is empty!");
        exit(1);
    } else {
        int deletedValue = q->data[q->front];
        if(q->front == q->rear) {              // queue is empty
            q->front = -1;                     // set front and rear to -1 to symbolize empty state of CircularQueue
            q->rear = -1;
        } else {
            q->front = ++(q->front) % SIZE;    // use % SIZE to prevent overflow and memory waste
        }
        return deletedValue;
    }
}

void printq(CircularQueue *q) {
    if(emptyq(q)) {
        printf("Queue is empty!");
        exit(2);
    }
    int it;
    for(it = q->front; it != q->rear + 1; it = (++it) % SIZE) {
        printf("%d ", q->data[it]);
    }
}


// Questions
void random_number_generator(CircularQueue* q, int range, int offset, int len) {
    srand(time(NULL));          // use srand(time(NULL)) to set seed of random number generator as current time
    int i;
    for(i = 0; i < len; i++)
        addq(q, rand() % range + offset);  // generate random number
}

void print_queue(CircularQueue* ele_q, int ElementsInOneLine) {
    CircularQueue temp_q;
    init_circular_queue(&temp_q);
    int ElementsInCurrentLine = 0;

    while(!emptyq(ele_q)) {
        int deleted_value = deleteq(ele_q); addq(&temp_q, deleted_value);
        printf("%d ", deleted_value);
        if(++ElementsInCurrentLine >= ElementsInOneLine) {
            printf("\n");
            ElementsInCurrentLine = 0;
        }
    }
    while(!emptyq(&temp_q)) {
        int deleted_value = deleteq(&temp_q);
        addq(ele_q, deleted_value);
    }
    printf("\n");
}

void restore(CircularQueue *ele_q, CircularQueue *deleted_ele_q) {
    CircularQueue temp_q;
    init_circular_queue(&temp_q);

    while(!emptyq(ele_q)) {           // temp_q = ele_q
        addq(&temp_q, deleteq(ele_q));
    }
    while(!emptyq(deleted_ele_q)) {   // ele_q = deleted_q
        addq(ele_q, deleteq(deleted_ele_q));
    }
    while(!emptyq(&temp_q)) {         // ele_q = deleted_q + temp_q
        addq(ele_q, deleteq(&temp_q));
    }
}

void reverseQueue(CircularQueue *q) {
    // base case
    if (emptyq(q))
        return;
    // store front(first element) of queue, and remove front
    int fr = deleteq(q);
 
    // asking recursion to reverse the leftover queue
    reverseQueue(q);
 
    // placing first element at its correct position
    addq(q, fr);
}

int getElement(CircularQueue *ele_q, int fromFront, int n) {    // 1 is fromFront, 0 is fromBack
    CircularQueue temp_q;
    init_circular_queue(&temp_q);
    int i, deleted_value;
    
    if(fromFront == 1) {
        for(i = 0; i < n; i++) {
            deleted_value = deleteq(ele_q);
            addq(&temp_q, deleted_value);
        }
        restore(ele_q, &temp_q);
    } else {
        reverseQueue(ele_q);
        for(i = 0; i < n; i++) {
            deleted_value = deleteq(ele_q);
            addq(&temp_q, deleted_value);
        }
        restore(ele_q, &temp_q);
        reverseQueue(ele_q);
    }
    return deleted_value;
}


int main() {
    CircularQueue q;
    init_circular_queue(&q);

    // p1
    random_number_generator(&q, 100, 1, 21);  // Use rand()%100+1 to get 21 random numbers
    print_queue(&q, 7);     // 7 numbers in one line

    // p2
    int w = getElement(&q, 1, 11);
    printf("%d \n", w);

    return 0;
}