#include <iostream>
using namespace std;

struct Node 
{
    int data;
    Node* next;
    
    Node(int value) : data(value), next(nullptr) {}
};

class CircularLinkedList 
{
private:
    Node* head_node;

public:
    CircularLinkedList() : head_node(nullptr) {}

    //insert a node at the end of the list
    void insertAtEnd(int value) 
    {
        Node* newNode = new Node(value);
        
        if (!head_node) 
        {
            head_node = newNode;
            head_node->next = head_node;
        } 
        else
        {
            Node* temp = head_node;
            while (temp->next != head_node) 
            {
                temp = temp->next;
            }
            temp->next = newNode;
            newNode->next = head_node;
        }
    }

    //insert a node at the beginning of the list
    void insertAtBeginning(int value) 
    {
        Node* newNode = new Node(value);
        
        if (!head_node) 
        {
            head_node = newNode;
            head_node->next = head_node;
        } 
        else 
        {
            Node* temp = head_node;
            
            while (temp->next != head_node)
            {
                temp = temp->next;
            }
            
            newNode->next = head_node;
            temp->next = newNode;
            head_node = newNode;
        }
    }

    //delete a node from the end of the list
    void deleteFromEnd()
    {
        if (!head_node) 
            return;
        
        if (head_node->next == head_node) 
        {
            delete head_node;
            head_node = nullptr;
        } 
        else 
        {
            Node* temp = head_node;
            Node* prev = nullptr;
            
            while (temp->next != head_node)
            {
                prev = temp;
                temp = temp->next;
            }
            
            prev->next = head_node;
            delete(temp);
        }
    }

    //delete a node from the beginning of the list
    void deleteFromBeginning() 
    {
        if (!head_node) 
        return;
        
        if (head_node->next == head_node) 
        {
            delete(head_node);
            head_node = nullptr;
        } 
        else 
        {
            Node* temp = head_node;
            Node* tail = head_node;
            
            while (tail->next != head_node)
            {
                tail = tail->next;
            }
            
            head_node = head_node->next;
            tail->next = head_node;
            delete(temp);
        }
    }

    //traverse and print the list
    void traverse() 
    {
        if (!head_node) 
        {
            cout << "List is empty." << endl;
            return;
        }
        
        Node* temp = head_node;
        
        do
        {
            cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head_node);
        
        cout << endl;
    }

    //find and print the middle node
    void findTheMiddle()
    {
        if (!head_node) 
        return;

        Node* slow = head_node;
        Node* fast = head_node;

        while (fast->next != head_node && fast->next->next != head_node)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        cout << "Middle node data: " << slow->data << endl;
    }

    //insert a node at a given index
    void insertAtIndex(int index, int value) 
    {
        if (index == 0) 
        {
            insertAtBeginning(value);
            return;
        }

        Node* newNode = new Node(value);
        Node* temp = head_node;
        
        for (int i = 0; i < index - 1 && temp->next != head_node; i++) 
        {
            temp = temp->next;
        }
        
        newNode->next = temp->next;
        temp->next = newNode;
    }

    //delete a node from a given index
    void deleteFromIndex(int index) 
    {
        if (index == 0) 
        {
            deleteFromBeginning();
            return;
        }

        Node* temp = head_node;
        Node* prev = nullptr;
        for (int i = 0; i < index && temp->next != head_node; i++)
        {
            prev = temp;
            temp = temp->next;
        }

        if (prev != nullptr) 
        {
            prev->next = temp->next;
            delete(temp);
        }
    }

    //reverse the circular linked list
    void reverse()
    {
        if (!head_node) 
            return;

        Node* prev = nullptr;
        Node* current = head_node;
        Node* next = nullptr;
        Node* tail = head_node;

        while (tail->next != head_node) 
        {
            tail = tail->next;
        }

        do 
        {
            next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        } while (current != head_node);

        tail->next = prev;
        head_node->next = prev;
        head_node = prev;
    }
};

int main() 
{
    CircularLinkedList circular_linked_list;

    circular_linked_list.insertAtEnd(11);
    circular_linked_list.insertAtEnd(221);
    circular_linked_list.insertAtEnd(34);
    circular_linked_list.insertAtBeginning(0);
    circular_linked_list.traverse();

    circular_linked_list.deleteFromEnd();
    circular_linked_list.traverse();

    circular_linked_list.findTheMiddle();

    circular_linked_list.insertAtIndex(1, 5);
    circular_linked_list.traverse();

    circular_linked_list.deleteFromIndex(2);
    circular_linked_list.traverse();

    circular_linked_list.reverse();
    circular_linked_list.traverse();

    return 0;
}