BOOT_RINGS

#include <iostream>
#include <string>

template <typename T>
class SingleLinkedRing {
private:
    struct Node {
        T data;
        Node* next;

        Node(const T& value) : data(value), next(nullptr) {}
    };

    Node* head;

public:
    SingleLinkedRing() : head(nullptr) {}

    ~SingleLinkedRing() {
        clear();
    }

    // Метод добавления элемента в кольцо
    void add(const T& value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = newNode;
            head->next = head;
        } else {
            Node* temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            temp->next = newNode;
            newNode->next = head;
        }
    }

    // Печать кольца
    void print() const {
        if (!head) return;
        Node* temp = head;
        do {
            std::cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head);
        std::cout << std::endl;
    }

    // Подсчет количества вхождений заданного элемента
    int countOccurrences(const T& value) const {
        if (!head) return 0;
        int count = 0;
        Node* temp = head;
        do {
            if (temp->data == value) {
                count++;
            }
            temp = temp->next;
        } while (temp != head);
        return count;
    }

    // Поиск самого часто встречающегося элемента
    T findMostFrequent() const {
        if (!head) throw std::runtime_error("Ring is empty.");

        T mostFrequent = head->data;
        int maxCount = 0;

        Node* outer = head;
        do {
            int count = 0;
            Node* inner = head;
            do {
                if (inner->data == outer->data) {
                    count++;
                }
                inner = inner->next;
            } while (inner != head);

            if (count > maxCount) {
                maxCount = count;
                mostFrequent = outer->data;
            }
            outer = outer->next;
        } while (outer != head);

        return mostFrequent;
    }

    // Очистка кольца
    void clear() {
        if (!head) return;
        Node* temp = head;
        do {
            Node* nextNode = temp->next;
            delete temp;
            temp = nextNode;
        } while (temp != head);
        head = nullptr;
    }
};

// Функция для работы с кольцом целых чисел
void processIntegerRing() {
    SingleLinkedRing<int> intRing;
    intRing.add(1);
    intRing.add(2);
    intRing.add(3);
    intRing.add(1);
    intRing.add(2);

    std::cout << "Integer ring: ";
    intRing.print();

    int target = 2;
    std::cout << "Occurrences of " << target << ": " << intRing.countOccurrences(target) << std::endl;

    std::cout << "Most frequent integer: " << intRing.findMostFrequent() << std::endl;

    intRing.clear();
}

// Функция для работы с кольцом строк
void processStringRing() {
    SingleLinkedRing<std::string> stringRing;
    stringRing.add("apple");
    stringRing.add("banana");
    stringRing.add("apple");
    stringRing.add("cherry");
    stringRing.add("banana");

    std::cout << "String ring: ";
    stringRing.print();

    std::string target = "apple";
    std::cout << "Occurrences of \"" << target << "\": " << stringRing.countOccurrences(target) << std::endl;

    std::cout << "Most frequent string: " << stringRing.findMostFrequent() << std::endl;

    stringRing.clear();
}

int main() {
    std::cout << "integer ring:" << std::endl;
    processIntegerRing();

    std::cout << "\nstring ring:" << std::endl;
    processStringRing();

    return 0;
}