#include <iostream>
#include <stdexcept>
#include <functional>
#include <fstream>
#include <sstream>
#include <string>
#include <iomanip>

using namespace std;

// Манипулятор для вывода в научном формате
template <typename T>
ostream& scientific_format(ostream& os, const T& value) {
    os << std::scientific << value;
    return os;
}

// Манипулятор для вывода в 8-ричной системе счисления
template <typename T>
ostream& octal_format(ostream& os, const T& value) {
    os << std::oct << value;
    return os;
}

template<class T>
class Element {
protected:
    Element* next;
    T info;

public:
    Element() : next(nullptr), info(T()) {}
    Element(const T& data) : next(nullptr), info(data) {}
    Element(Element* Next, const T& data) : next(Next), info(data) {}
    Element(const Element& el) : next(el.next), info(el.info) {}

    template<class T1>
    friend ostream& operator<<(ostream& s, const Element<T1>& el);

    const T& getInfo() const {
        return info;
    }

    T& getInfo() {
        return info;
    }

    Element* getNext() const {
        return next;
    }

    void setNext(Element* nextElement) {
        next = nextElement;
    }

    virtual ~Element() {}

    template<class T1> friend class LinkedList;
    template<class T1> friend class DoublyLinkedStack;
    template<class T1> friend ostream& operator<<(ostream& s, const Element<T1>& el);
};

template<class T1>
ostream& operator<<(ostream& s, const Element<T1>& el) {
    s << el.info;
    return s;
}

template<class T>
class LinkedList {
protected:
    Element<T>* head;
    Element<T>* tail;
    int count;

public:
    LinkedList() : head(nullptr), tail(nullptr), count(0) {}

    virtual Element<T>* pop() = 0;
    virtual Element<T>* push(const T& value) = 0;

    bool isEmpty() { return count == 0; }
    //getter
    Element<T>* getHead() const { return head; }

    virtual ~LinkedList() {
        cout << "\nBase class destructor\n";
        Element<T>* current = head;
        while (current != nullptr) {
            Element<T>* nextElement = current->getNext();
            delete current;
            current = nextElement;
        }
        head = tail = nullptr;
        count = 0;
    }
};

template<class T>
class SinglyLinkedListStack : public LinkedList<T> {
public:
    SinglyLinkedListStack() : LinkedList<T>() {}

    virtual Element<T>* push(const T& value) override {
        Element<T>* newElement = new Element<T>(value);
        if (this->head == nullptr) {
            this->head = this->tail = newElement;
        }
        else {
            this->tail->setNext(newElement);
            this->tail = newElement;
        }
        this->count++;
        return newElement;
    }

    virtual Element<T>* pop() override {
        if (this->tail == nullptr)
            return nullptr;

        Element<T>* res = this->tail;

        if (this->head == this->tail) {
            this->head = this->tail = nullptr;
        }
        else {
            /*Element<T>* current = this->head;
            while (current->getNext() != this->tail) {
                current = current->getNext();
            }
            this->tail = current;
            current->setNext(nullptr);*/
            this->head = this->head->getNext();
        }

        this->count--;
        return res;
    }

    virtual ~SinglyLinkedListStack() { cout << "\nSinglyLinkedListStack class destructor\n"; }
};

template<class T>
class SinglyLinkedListQueue : public LinkedList<T> {
public:
    SinglyLinkedListQueue() : LinkedList<T>() {}

    virtual Element<T>* push(const T& value) override {
        Element<T>* newElement = new Element<T>(value);
        if (this->head == nullptr) {
            this->head = this->tail = newElement;
        }
        else {
            this->tail->setNext(newElement);
            this->tail = newElement;
        }
        this->count++;
        return newElement;
    }

    virtual Element<T>* pop() override {
        if (this->head == nullptr)
            return nullptr;

        Element<T>* res = this->head;

        if (this->head == this->tail) {
            this->head = this->tail = nullptr;
        }
        else {
            this->head = this->head->getNext();
        }

        this->count--;
        return res;
    }

    virtual ~SinglyLinkedListQueue() { cout << "\nSinglyLinkedListQueue class destructor\n"; }
};

template<class T>
class StackQueue : protected SinglyLinkedListStack<T>, protected SinglyLinkedListQueue<T> {
public:
    StackQueue() : SinglyLinkedListStack<T>(), SinglyLinkedListQueue<T>() {}

    Element<T>* push_back(const T& value) { return SinglyLinkedListQueue<T>::push(value); }
    Element<T>* push_front(const T& value) { return SinglyLinkedListStack<T>::push(value); }
    Element<T>* pop_back() { return SinglyLinkedListStack<T>::pop(); }
    Element<T>* pop_front() { return SinglyLinkedListQueue<T>::pop(); }

    using LinkedList<T>::isEmpty;
};

template<class T>
class DoublyLinkedElement : public Element<T> {
protected:
    DoublyLinkedElement* prev;

public:
    DoublyLinkedElement() : Element<T>(), prev(nullptr) {}
    DoublyLinkedElement(const T& data) : Element<T>(data), prev(nullptr) {}
    DoublyLinkedElement(DoublyLinkedElement* Next, DoublyLinkedElement* Prev, const T& data)
        : Element<T>(Next, data), prev(Prev) {}

    DoublyLinkedElement* getPrev() const {
        return prev;
    }

    void setPrev(DoublyLinkedElement* prevElement) {
        prev = prevElement;
    }
};

template<class T>
class DoublyLinkedStack : public SinglyLinkedListStack<T> {
public:
    DoublyLinkedStack() : SinglyLinkedListStack<T>() {}

    using LinkedList::head;

    virtual Element<T>* push(const T& value) override {
        DoublyLinkedElement<T>* newElement = new DoublyLinkedElement<T>(value);
        if (this->head == nullptr) {
            this->head = this->tail = newElement;
        }
        else {
            static_cast<DoublyLinkedElement<T>*>(this->tail)->setNext(newElement);
            newElement->setPrev(static_cast<DoublyLinkedElement<T>*>(this->tail));
            this->tail = newElement;
        }
        this->count++;
        return newElement;
    }

    virtual Element<T>* pop() override {
        if (this->tail == nullptr)
            return nullptr;

        //DoublyLinkedElement<T>* res = static_cast<DoublyLinkedElement<T>*>(this->tail);
        // Преобразование указателя на базовый класс в указатель на производный класс
        DoublyLinkedElement<T>* res = dynamic_cast<DoublyLinkedElement<T>*>(this->tail);

        if (this->head == this->tail) {
            this->head = this->tail = nullptr;
        }
        else {
            this->tail = res->getPrev();
            if (this->tail) {
                this->tail->setNext(nullptr);
            }
        }

        this->count--;
        return res;
    }

    // Insert a new element at the specified index
    void insert(int index, const T& value) {
        if (index < 0 || index > this->count) {
            throw out_of_range("Index out of range");
        }

        if (index == this->count) {
            push(value);
            return;
        }

        DoublyLinkedElement<T>* newElement = new DoublyLinkedElement<T>(value);
        if (index == 0) {
            newElement->setNext(static_cast<DoublyLinkedElement<T>*>(this->head));
            static_cast<DoublyLinkedElement<T>*>(this->head)->setPrev(newElement);
            this->head = newElement;
        }
        else {
            DoublyLinkedElement<T>* current = static_cast<DoublyLinkedElement<T>*>(this->head);
            for (int i = 0; i < index - 1; ++i) {
                current = static_cast<DoublyLinkedElement<T>*>(current->getNext());
            }
            newElement->setNext(current->getNext());
            newElement->setPrev(current);
            if (current->getNext() != nullptr) {
                static_cast<DoublyLinkedElement<T>*>(current->getNext())->setPrev(newElement);
            }
            current->setNext(newElement);
        }

        this->count++;
    }

    // Remove the element at the specified index
    void remove(int index) {
        if (index < 0 || index >= this->count) {
            throw out_of_range("Index out of range");
        }

        DoublyLinkedElement<T>* toDelete = static_cast<DoublyLinkedElement<T>*>(this->head);
        if (index == 0) {
            this->head = toDelete->getNext();
            if (this->head != nullptr) {
                static_cast<DoublyLinkedElement<T>*>(this->head)->setPrev(nullptr);
            }
        }
        else {
            for (int i = 0; i < index; ++i) {
                toDelete = static_cast<DoublyLinkedElement<T>*>(toDelete->getNext());
            }
            DoublyLinkedElement<T>* prevElement = toDelete->getPrev();
            DoublyLinkedElement<T>* nextElement = static_cast<DoublyLinkedElement<T>*>(toDelete->getNext());
            if (prevElement != nullptr) {
                prevElement->setNext(nextElement);
            }
            if (nextElement != nullptr) {
                nextElement->setPrev(prevElement);
            }
        }

        if (toDelete == this->tail) {
            this->tail = toDelete->getPrev();
        }

        delete toDelete;
        this->count--;
    }

    // Iterative version of find
    Element<T>* find(const T& value) const {
        //DoublyLinkedElement<T>* current = static_cast<DoublyLinkedElement<T>*>(this->head);
        Element<T>* current = this->head;
        while (current != nullptr) {
            if (current->getInfo() == value) {
                return current;
            }
            current = current->getNext(); //static_cast<DoublyLinkedElement<T>*>(current->getNext());
        }
        return nullptr;
    }

    // Recursive version of find
    Element<T>* find_recursive(const T& value, DoublyLinkedElement<T>* current) const {
        if (current == nullptr) {
            return nullptr;
        }
        if (current->getInfo() == value) {
            return current;
        }
        return find_recursive(value, static_cast<DoublyLinkedElement<T>*>(current->getNext()));
    }

    // Iterative version of filter
    void filter(function<bool(const T&)> condition) const {
        //DoublyLinkedElement<T>* current = static_cast<DoublyLinkedElement<T>*>(this->head);
        Element<T>* current = this->head;
        while (current != nullptr) {
            if (condition(current->getInfo())) {
                cout << current->getInfo() << " ";
            }
            current = current->getNext();  //static_cast<DoublyLinkedElement<T>*>(current->getNext());
        }
        cout << endl;
    }

    // Recursive version of filter
    void filter_recursive(function<bool(const T&)> condition, DoublyLinkedElement<T>* current) const {
        if (current == nullptr) {
            return;
        }
        if (condition(current->getInfo())) {
            cout << current->getInfo() << " ";
        }
        filter_recursive(condition, static_cast<DoublyLinkedElement<T>*>(current->getNext()));
    }

    // Overloading the output stream operator
    friend ostream& operator<<(ostream& os, const DoublyLinkedStack& stack) {
        DoublyLinkedElement<T>* current = static_cast<DoublyLinkedElement<T>*>(stack.head);
        while (current != nullptr) {
            os << current->getInfo() << " ";
            current = static_cast<DoublyLinkedElement<T>*>(current->getNext());
        }
        return os;
    }
    
    // Overloading the subscript operator
    T& operator[](int index) {
        if (index < 0 || index >= this->count) {
            throw out_of_range("Index out of range");
        }

        DoublyLinkedElement<T>* current = static_cast<DoublyLinkedElement<T>*>(this->head);
        for (int i = 0; i < index; ++i) {
            current = static_cast<DoublyLinkedElement<T>*>(current->getNext());
        }

        return current->info;
    }
};

class State {
protected:
    string name;
    string capital;
    string language;
    long population;
    double area;

public:


    State() : name(""), capital(""), language(""), population(0), area(0.0) {}
    State(string n, string c, string l, long p, double a)
        : name(n), capital(c), language(l), population(p), area(a) {}

    friend ostream& operator<<(ostream& os, const State& state) {
        os << "State: " << state.name << ", Capital: " << state.capital
            << ", Language: " << state.language << ", Population: " << state.population
            << ", Area: " << state.area;
        return os;
    }

    bool operator==(const State& other) const {
        return name == other.name;
    }
    // geters
    string getName() const { return name; }
    double getArea() const { return area; }
    long getPopulation() const { return population; }
    string getCapital() const { return capital; }
    string getLanguage() const { return language; }

};


class StateList : public DoublyLinkedStack<State> {
protected:
    SinglyLinkedListQueue<State> stateList;

public:
    // Добавление нового государства в начало списка
    //void addState(const State& state) {
    //    stateList.push(state);
    //}
    virtual Element<State>* push(const State& state) override {
        stateList.push(state);
        return stateList.getHead();
    }
    friend ostream& operator<<(ostream& os, const StateList& stateList) {
        Element<State>* current = stateList.stateList.getHead();
        while (current != nullptr) {
            //os << current->getInfo() << endl;
            // Выводим элемент в научном виде и в 8-ричной системе счисления
            os << scientific << current->getInfo() << " " << oct << current->getInfo() << endl;
            current = current->getNext();
        }
        return os;
    }

    // Удаление государства из начала списка
    virtual Element<State>* pop() override {
        try {
            return new Element<State>(removeState());
        }
        catch (const logic_error& e) {
            cout << e.what() << endl;
            return nullptr;
        }
    }
    State removeState() {
        Element<State>* element = stateList.pop();
        if (element) {
            State state = element->getInfo();
            delete element;
            return state;
        }
        throw logic_error("State list is empty");
    }
    // Поиск государства по названию
    State* findStateByName(const string& name) {
        Element<State>* current = stateList.getHead();
        while (current != nullptr) {
            if (current->getInfo().getName() == name) {
                return &(current->getInfo());
            }
            current = current->getNext();
        }
        return nullptr;
    }

    // Фильтрация государств по площади
    void printStatesByArea(double minArea, double maxArea) {
        Element<State>* current = stateList.getHead();
        while (current != nullptr) {
            const State& state = current->getInfo();
            if (state.getArea() >= minArea && state.getArea() <= maxArea) {
                cout << state << endl;
            }
            current = current->getNext();
        }
    }

    // Универсальная фильтрация государств по произвольному условию
    void printStatesByCondition(function<bool(const State&)> condition) {
        Element<State>* current = stateList.getHead();
        while (current != nullptr) {
            const State& state = current->getInfo();
            if (condition(state)) {
                cout << state << endl;
            }
            current = current->getNext();
        }
    }

    // Сохранение списка состояний в файл
    void save(const string& filename) const {
        ofstream outputFile(filename);
        if (!outputFile.is_open()) {
            throw runtime_error("Unable to open file for writing");
        }

        Element<State>* current = stateList.getHead();
        while (current != nullptr) {
            outputFile << current->getInfo().getName() << ","
                << current->getInfo().getCapital() << ","
                << current->getInfo().getLanguage() << ","
                << current->getInfo().getPopulation() << ","
                << current->getInfo().getArea() << endl;
            current = current->getNext();
        }

        outputFile.close();
    }

    // Загрузка списка состояний из файла
    void load(const string& filename) {
        ifstream file(filename);
        if (file.is_open()) {
            // Очищаем текущий список состояний перед загрузкой новых данных
            while (!stateList.isEmpty()) {
                stateList.pop();
            }

            string line;
            while (getline(file, line)) {
                stringstream ss(line);
                string name, capital, language;
                long population;
                double area;
                getline(ss, name, ',');
                getline(ss, capital, ',');
                getline(ss, language, ',');
                ss >> population;
                ss.ignore(1); // Ignore the comma
                ss >> area;
                State state(name, capital, language, population, area);
                stateList.push(state);
            }
            file.close();
        }
        else {
            cout << "Unable to open file for loading" << endl;
        }
    }
};



int main() {
    DoublyLinkedStack<int> stack;

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);

    cout << "Stack after pushing 1, 2, 3, 4: " << stack << endl;

    stack.insert(2, 99);
    cout << "Stack after inserting 99 at index 2: " << stack << endl;

    stack.remove(1);
    cout << "Stack after removing element at index 1: " << stack << endl;

    Element<int>* found = stack.find(99);
    if (found) {
        cout << "Found element with value 99: " << found->getInfo() << endl;
    }
    else {
        cout << "Element with value 99 not found" << endl;
    }

    found = stack.find_recursive(3, static_cast<DoublyLinkedElement<int>*>(stack.head));
    if (found) {
        cout << "Found element with value 3 using recursive find: " << found->getInfo() << endl;
    }
    else {
        cout << "Element with value 3 not found using recursive find" << endl;
    }

    cout << "Filtering elements greater than 2: ";
    stack.filter([](const int& value) { return value > 2; });

    cout << "Filtering elements greater than 2 using recursive filter: ";
    stack.filter_recursive([](const int& value) { return value > 2; }, static_cast<DoublyLinkedElement<int>*>(stack.head));
    cout << endl;

    cout << "Element at index 1: " << stack[1] << endl;

    while (!stack.isEmpty()) {
        Element<int>* elem = stack.pop();
        if (elem) {
            cout << elem->getInfo() << " ";
            delete elem;
        }
    }
    cout << endl;


    StateList* states = new StateList();
 
    //for 6.2
    states->push(State("USA", "Washington D.C.", "English", 328000000, 9833510));
    states->push(State("India", "New Delhi", "Hindi", 1380000000, 3287263));

    // Сохраняем список состояний в файл
    states->save("states.txt");

    // Загружаем список состояний из файла
    StateList loadedStates;
    loadedStates.load("states.txt");

    cout << "List of states:" << endl;
    //cout << states->findStateByName("USA") << endl;
    cout << loadedStates << endl;

    cout << "States with area between 9800500 and 9987263:" << endl;
    states->printStatesByArea(9800500, 9987263);

    cout << "States with population greater than 1 billion:" << endl;
    states->printStatesByCondition([](const State& state) 
        {
        return state.getPopulation() > 1000000000;
        });

    State* foundState = states->findStateByName("USA");
    if (foundState) {
        cout << "Found state: " << *foundState << endl;
    }
    else {
        cout << "State not found" << endl;
    }

    try {
        State removedState = states->removeState();
        cout << "Removed state: " << removedState << endl;
    }
    catch (const out_of_range& e) {
        cout << e.what() << endl;
    }

    cout << "States after removal:" << endl;
    states->printStatesByArea(0, 10000000);

    // Освобождение памяти, выделенной для объекта StateList
    delete states;

    return 0;
}