#include <stdlib.h>
#include <string>
#include <iostream>

using namespace std;

class nodes { //objet node
public :
    nodes() {
        next = NULL;
    }
    int element; //element dans la node
    nodes* next; //prochain element
}*front = NULL, *rear=NULL, *n, *temp, *temp1; //initialisation des variables

class circularqueue { //objet de la queue circulaire
public :
    //Fonctions des queues circulaire
    void InsertQueue(); 
    void Delete();
    void SearchQueue();
    void DisplayQueue();
};

//Fonction delete des queues circulaires
void circularqueue::Delete() {
    int x; // element à enlever
    temp = front; // temp devient la position de front
    if (front == NULL) { //Si pas de front (empty)
        cout << "The queue is empty" << endl;
    }
    else {
        if (front == rear) {//si positon de front est la meme que rear (un seul element)
            x = front->element; //x devient la valeur de front
            delete(temp); //enleve l'élément qui est à la position de temp(front)
            front = NULL; //Remet front à null
            rear = NULL;// remet rear à null
        }
        else {
            x = temp->element; //x devient la valeur de front (temp == front)
            front = front->next; //front devient le prochain élément
            rear->next = front; //la position de rear devient la position du prochain de front (rear devient l'ancien front)
            delete(temp); //eneleve l'élement temporaire
        }
        cout << "Element " << x << " has been deleted" << endl;
    }
}
void circularqueue::InsertQueue() {
    n = new nodes[sizeof(nodes)]; //crée un nouvel objet node
    cout << "Enter the element you wish to insert: ";
    cin >> n->element; //entrer l'élément de la nouvelle node
    if (front == NULL) { //si front est null
        front = n; //emplacement de front est maintenant la valeur entrée
    } else
    {
        rear->next = n; //position de rear devient le prochain
    }
    rear = n; //l'emplacement rear devient la valeur entrée
    rear->next = front; //position rear devient le prochain
}

void circularqueue::SearchQueue(){
    int search; // Valeur a chercher dans la queue
    int n = 0; //Compteur

    temp = front; // Valeur temporaire est à front;
    temp1 = NULL; // Autre valeur temp. est nulle

    if (front == NULL) { //Si front na pas d'élément
        cout << "The queue is empty..." << endl;
    }
    else {
        cout << "Enter the element you are searching for: ";
        cin >> search; //Enter l'élément à trouver

        while (temp != temp1) { //Fait pendant que la valeur temp != front
            if (search == temp->element) { //si le search est egal à l'élément de la node
                n++; //ajoute au compteur
                temp = temp->next; //change la valeur du front pour la prochaine valeur
                temp1 = front; //Deuxieme temporaire devient la valeur front
            }
        }
        cout << "The element " << search << " is in the queue " << n << " times." << endl;
    }
    return ;
}

void circularqueue::DisplayQueue() {
    temp = front; //temp devient la position de front
    temp1 = NULL; //deuxieme temp  est NULL
    if (front == NULL) { //si la front est vide
        cout << " The queue is empty..." << endl;
    }
    else { //si c'est pas vide
        cout << "The elements in the queue are: ";
        while (temp != temp1) { //pendant que temp n'est pas temp1 (le tour de la queue n'est pas complétée)
            cout << temp->element << " ";
            temp = temp->next; //temp devient la prochaine position
            temp1 = front; //temp 1 devient le front
        }
    }
 }
void OptionList() {
    cout << "1: Insert in the queue." << endl;
    cout << "2: Delete from the queue." << endl;
    cout << "3: Search the queue." << endl;
    cout << "4: Display the queue." << endl;
}
int main() {
    int opt; //option choisie
    bool whileTrue = true; //bool qui est toujours true pour options

    circularqueue Queue; //crée une nouvel object de circular queue
    
    //choisir un option
    while (whileTrue) {

        OptionList();

        cout << "Enter your desired option: ";
        cin >> opt;

        switch (opt) {
        case 1: Queue.InsertQueue();
            break;
        case 2: Queue.Delete();
            break;
        case 3:Queue.SearchQueue();
            break;
        case 4: Queue.DisplayQueue();
            break;
        }

    }
}