#pragma once

#include <stdexcept>

namespace mtm {
    template<class T>
    class Node {
    public:
        Node(T value, Node* next) : next(next), value(value) {
        }

        Node(T value) : Node(value, nullptr) {
        }

        const Node* getNext() const {
            return next;
        }

        Node* getNext() {
            return next;
        }

        void setNext(Node* node) {
            this->next = node;
        }

        const T& getValue() const {
            return value;
        }

        T& getValue() {
            return value;
        }

    private:
        Node* next;
        T value;
    };

    template<typename T>
    class SortedList {
    public:
        SortedList() : listBegin(nullptr), listEnd(nullptr), listLength(0) {
        }

        SortedList(const SortedList& copy) : listBegin(nullptr),
                                             listEnd(nullptr), listLength(0) {
            try {
                for (const T& element: copy) {
                    this->insert(T(element));
                }
            }
            catch (...) {
                clear();
                throw;
            }
        }

        ~SortedList() {
            clear();
        }

        SortedList& operator=(const SortedList<T>& data) {
            if (this == &data) {
                return *this;
            }

            SortedList<T> temp(data);
            std::swap(listBegin, temp.listBegin);
            std::swap(listEnd, temp.listEnd);
            std::swap(listLength, temp.listLength);

            return *this;
        }

        class ConstIterator;

        ConstIterator begin() const {
            return ConstIterator(listBegin);
        }

        ConstIterator end() const {
            return ConstIterator(nullptr);
        }

        void insert(const T& newValue) {
            Node<T>* current = listBegin;

            // empty list
            if (current == nullptr) {
                listBegin = new Node<T>(T(newValue), nullptr);
                listLength++;
                listEnd = listBegin;
                return;
            }

            // biggest value yet
            if (newValue > current->getValue()) {
                listBegin = new Node<T>(T(newValue), current);
                listLength++;
                return;
            }

            // finding a place for the value
            while (current->getNext() != nullptr &&
                   !(newValue > current->getNext()->getValue())) {
                current = current->getNext();
            }

            // setting the value
            if (current->getNext() == nullptr) {
                Node<T>* newNode = new Node<T>(T(newValue), nullptr);
                current->setNext(newNode);
                listEnd = current->getNext();
            } else {
                Node<T>* newNode = new Node<T>(T(newValue), current->getNext());
                current->setNext(newNode);
            }
            listLength++;
        }

        void remove(const ConstIterator& location) {
            if (!(location != end()))
                return;

            if (location.current == listBegin) {
                Node<T>* node = listBegin;
                listBegin = listBegin->getNext();
                if (listBegin == nullptr) {
                    listEnd = nullptr;
                }
                delete node;
                listLength--;
                return;
            }
            Node<T>* prev = listBegin;
            while (prev != nullptr && prev->getNext() != location.current) {
                prev = prev->getNext();
            }
            if (prev == nullptr) {
                throw std::invalid_argument("Iterator not found in the list");
            }
            prev->setNext(location.current->getNext());
            if (location.current == listEnd) {
                listEnd = prev;
            }
            listLength--;
            delete location.current;
        }

        int length() const {
            return this->listLength;
        }

        template<class Predicate>
        SortedList filter(Predicate predicate) const {
            SortedList result;
            for (const T& val: *this) {
                if (predicate(val)) {
                    result.insert(val);
                }
            }
            return result;
        }

        template<class Operation>
        SortedList apply(Operation op) const {
            SortedList result;
            for (const T& val: *this) {
                result.insert(op(val));
            }
            return result;
        }

    private:
        Node<T> *listBegin, *listEnd;
        int listLength;

        void clear() {
            Node<T>* current = listBegin;
            while (current != nullptr) {
                Node<T>* del = current;
                current = current->getNext();
                delete del;
            }
        }
    };

    template<class T>
    class SortedList<T>::ConstIterator {
    public:
        ConstIterator(const ConstIterator& other) = default;

        ConstIterator& operator=(const ConstIterator&) = default;

        ~ConstIterator() = default;

        const T& operator*() const {
            if (current == nullptr)
                throw std::out_of_range("Out of list range.");
            return current->getValue();
        }

        ConstIterator& operator++() {
            if (current == nullptr)
                throw std::out_of_range("Out of list range.");
            current = current->getNext();
            return *this;
        }

        bool operator!=(const ConstIterator& iterator) const {
            return (iterator.current != current);
        }

    private:
        ConstIterator(Node<T>* node) : current(node) {
        }

        friend class SortedList<T>;

        Node<T>* current;
    };
}