list.h

Go to the documentation of this file.

 
#ifndef LIST_H
#define LIST_H
 
#include <cstddef>
#include <cstdint>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <limits>
#include <memory>
#include <ranges>
 
namespace dsa
{
 
    template<typename T>
    class List;
 
    template<typename T>
    auto operator+(const List<T>& list1, const List<T>& list2) -> List<T>;

    template<typename T>
    class List
    {
    public:

        class NodeBase
        {
        public:

            NodeBase() = default;

            NodeBase(const NodeBase& other) = default;

            auto operator=(const NodeBase& other) -> NodeBase & = default;

            NodeBase(NodeBase&& other) = default;

            auto operator=(NodeBase&& other) -> NodeBase & = default;

            virtual ~NodeBase() = default;
 
        private:
 
            friend class List<T>;

            std::unique_ptr<NodeBase> m_next{};

            NodeBase* m_prev{};
        };

        class Node : public NodeBase
        {
        public:

            Node(T value)
                : m_value{ value }
            {
            }

            auto value() -> T&
            {
                return m_value;
            }

            [[nodiscard]] auto value() const -> T
            {
                return m_value;
            }
 
        private:

            friend class List;
 
            T m_value{};
        };

        template<bool IF_CONST>
        class ListIterator
        {
        public:

            using iterator_type = std::conditional_t<IF_CONST, const T, T>;

            using iterator_category = std::bidirectional_iterator_tag;

            using difference_type = std::ptrdiff_t;

            using value_type = T;

            using pointer = iterator_type*;

            using reference = iterator_type&;

            ListIterator() noexcept = default;

            ListIterator(NodeBase* node) noexcept
                : m_current_node{ node }
            {
            }

            auto operator=(NodeBase* node) -> ListIterator&
            {
                this->m_current_node = node;
                return *this;
            }

            auto operator++() -> ListIterator&
            {
                if (m_current_node)
                {
                    m_current_node = m_current_node->m_next.get();
                }
 
                return *this;
            }

            auto operator++(int) -> ListIterator
            {
                const ListIterator iterator = *this;
                ++(*this);
                return iterator;
            }

            auto operator--() -> ListIterator&
            {
                if (m_current_node)
                {
                    m_current_node = m_current_node->m_prev;
                }
 
                return *this;
            }

            auto operator--(int) -> ListIterator
            {
                const ListIterator iterator = *this;
                --(*this);
                return iterator;
            }

            auto operator==(const ListIterator& other) const -> bool
            {
                return m_current_node == other.m_current_node;
            }

            auto operator!=(const ListIterator& other) const -> bool
            {
                return !operator==(other);
            }

            auto operator[](size_t index) -> ListIterator
            {
                NodeBase* temp{ m_current_node };
 
                for (size_t i = 0; i < index; i++)
                {
                    if (temp->m_next)
                    {
                        temp = temp->m_next.get();
                    }
                    else
                    {
                        return nullptr;
                    }
                }
 
                return temp;
            }

            auto operator*() const -> reference
            {
                if (Node* node = dynamic_cast<Node*>(m_current_node))
                {
                    return node->value();
                }
                throw std::runtime_error("Invalid iterator dereference");
            }

            auto operator->() -> pointer
            {
                if (Node* node = dynamic_cast<Node*>(m_current_node))
                {
                    return &node->value();
                }
                throw std::runtime_error("Invalid iterator pointer");
            }

            operator ListIterator<true>()
            {
                return ListIterator<true>(m_current_node);
            }
 
        private:

            friend class List;
 
            NodeBase* m_current_node{};
        };

        using value_type = T;

        using pointer = T*;

        using const_pointer = const T*;

        using reference = T&;

        using const_reference = const T&;

        using const_iterator = ListIterator<true>;

        using iterator = ListIterator<false>;

        List();

        List(size_t count);

        List(size_t count, const T& value);

        List(const std::initializer_list<T>& init_list);

        List(const List<T>& other);

        auto operator=(const List<T>& other) -> List&;

        List(List<T>&& other) noexcept;

        auto operator=(List<T>&& other) noexcept -> List&;

        ~List();

        void assign(size_t count, const_reference value);

        void assign(const std::initializer_list<T>& init_list);

        auto front() -> reference;

        [[nodiscard]] auto front() const -> const_reference;

        auto back() -> reference;

        [[nodiscard]] auto back() const -> const_reference;

        auto begin() -> iterator;

        auto begin() const -> const_iterator;

        [[nodiscard]] auto cbegin() const -> const_iterator;

        auto end() -> iterator;

        auto end() const -> const_iterator;

        [[nodiscard]] auto cend() const -> const_iterator;

        [[nodiscard]] auto empty() const -> bool;

        [[nodiscard]] auto size() const -> size_t;

        [[nodiscard]] auto max_size() const -> size_t;

        void clear();

        auto insert(const const_iterator& pos, const_reference value) -> iterator;

        auto insert(const const_iterator& pos, size_t count, const_reference value) -> iterator;

        auto insert(const const_iterator& pos, std::initializer_list<T> init_list) -> iterator;

        auto erase(iterator pos) -> iterator;

        auto erase(const_iterator pos) -> iterator;

        auto erase(iterator first, iterator last) -> iterator;

        auto erase(const_iterator first, const_iterator last) -> iterator;

        void push_back(T value);

        void pop_back();

        void push_front(T value);

        void pop_front();

        void resize(size_t count);

        void resize(size_t count, const_reference value);

        void swap(List<T>& other) noexcept;

        void merge(List<T>& other);

         // transfers ownership of nodes, moving entire container is not necessary
         // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
        void merge(List<T>&& other);

        void splice(const const_iterator& pos, List<T>& other);

        void splice(const_iterator pos, List<T>&& other);

        void splice(const const_iterator& pos, List<T>& other, const const_iterator& iter);

        void splice(const_iterator pos, List<T>&& other, const_iterator iter);

        void splice(const const_iterator& pos, List<T>& other, const const_iterator& first, const const_iterator& last);

        void splice(const_iterator pos, List<T>&& other, const_iterator first, const_iterator last);

        void remove(const_reference value);

        void reverse();

        void unique();

        auto operator+=(const List<T>& other) -> List<T>&
        {
            for (auto it = other.cbegin(); it != other.cend(); ++it)
            {
                push_back(*it);
            }
 
            return *this;
        }

        auto operator+=(const std::initializer_list<T> init_list) -> List<T>&
        {
            for (const auto& item : init_list)
            {
                push_back(item);
            }
 
            return *this;
        }

        [[nodiscard]] auto get(size_t index) const -> Node*;

        auto set(size_t index, T value) -> bool;
 
    private:

        friend auto operator+<>(const List<T>& list1, const List<T>& list2)->List<T>;

        void init_node()
        {
            if (m_head == nullptr)
            {
                m_head = std::make_unique<NodeBase>();
                m_tail = m_head.get();
            }
        }

        auto erase_element(iterator pos) -> iterator
        {
 
            if (pos == begin())
            {
                pop_front();
                return iterator(begin());
            }
 
            if (pos == (--end()))
            {
                pop_back();
                return iterator(end());
            }
 
            NodeBase* temp{ pos.m_current_node->m_prev };
            NodeBase* to_remove{ temp->m_next.get() };
 
            temp->m_next = std::move(to_remove->m_next);
            temp->m_next->m_prev = temp;
 
            m_size--;
            return iterator(temp->m_next.get());
        }

        auto insert_element_before(iterator pos, const_reference value) -> iterator
        {
            if (pos == begin())
            {
                push_front(value);
                return begin();
            }
 
            if (pos == end())
            {
                push_back(value);
                return end().m_current_node->m_prev;
            }
 
            NodeBase* temp{ pos.m_current_node->m_prev };
 
            auto newNode = std::make_unique<Node>(value);
            newNode->m_next = std::move(temp->m_next);
            newNode->m_prev = temp;
 
            temp->m_next = std::move(newNode);
            temp->m_next->m_next->m_prev = temp->m_next.get();
 
            m_size++;
            return iterator(temp->m_next.get());
        }

        auto if_valid_iterator(const_iterator pos) -> bool
        {
            bool valid_iterator{};
 
            if (pos == cbegin() || pos == cend())
            {
                return true;
            }
 
            for (auto it = cbegin(); it != cend(); ++it)
            {
                if (it == pos)
                {
                    valid_iterator = true;
                    break;
                }
            }
            return valid_iterator;
        }

        auto distance(const_iterator first, const const_iterator& last) -> size_t;

         // transfers ownership of nodes, moving entire container is not necessary
         // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
        void transfer(const_iterator pos, List<T>&& other, const_iterator first, const const_iterator& last);
 
        std::unique_ptr<NodeBase> m_head{};
        NodeBase* m_tail{};
        size_t m_size{};
    };
 
    template<typename T>
    List<T>::List()
    {
        init_node();
    }
 
    template<typename T>
    List<T>::List(size_t count)
        : List(count, T{})
    {
    }
 
    template<typename T>
    List<T>::List(size_t count, const T& value)
    {
        init_node();
 
        for (size_t i = 0; i < count; i++)
        {
            push_front(value);
        }
    }
 
    template<typename T>
    List<T>::List(const std::initializer_list<T>& init_list)
    {
        for (const auto& item : init_list)
        {
            push_back(item);
        }
    }
 
    template<typename T>
    List<T>::List(const List<T>& other)
    {
        for (size_t i = 0; i < other.size(); i++)
        {
            push_back(other.get(i)->value());
        }
    }
 
    template<typename T>
    auto List<T>::operator=(const List<T>& other) -> List<T>&
    {
        if (&other != this)
        {
            while (m_head->m_next)
            {
                pop_front();
            }
 
            for (size_t i = 0; i < other.size(); i++)
            {
                push_back(other.get(i)->value());
            }
        }
 
        return *this;
    }
 
    template<typename T>
    List<T>::List(List<T>&& other) noexcept
    {
        operator=(std::move(other));
    }
 
    template<typename T>
    auto List<T>::operator=(List<T>&& other) noexcept -> List<T>&
    {
        if (&other != this)
        {
            clear();
 
            m_head = std::move(other.m_head);
            m_tail = std::move(other.m_tail);
            m_size = other.m_size;
 
            other.m_head = nullptr;
            other.m_tail = nullptr;
            other.m_size = 0;
        }
 
        return *this;
    }
 
    template<typename T>
    List<T>::~List()
    {
        clear();
    }
 
    template<typename T>
    void List<T>::assign(size_t count, const_reference value)
    {
        clear();
 
        for (size_t i = 0; i < count; i++)
        {
            push_back(value);
        }
    }
 
    template<typename T>
    void List<T>::assign(const std::initializer_list<T>& init_list)
    {
        clear();
 
        for (const auto& item : init_list)
        {
            push_back(item);
        }
    }
 
    template<typename T>
    auto List<T>::front() -> typename List<T>::reference
    {
        return *begin();
    }
 
    template<typename T>
    auto List<T>::front() const -> typename List<T>::const_reference
    {
        return *cbegin();
    }
 
    template<typename T>
    auto List<T>::back() -> typename List<T>::reference
    {
        return *(--end());
    }
 
    template<typename T>
    auto List<T>::back() const -> typename List<T>::const_reference
    {
        return *(--cend());
    }
 
    template<typename T>
    auto List<T>::begin() -> typename List<T>::iterator
    {
        return iterator(m_head.get());
    }
 
    template<typename T>
    auto List<T>::begin() const -> typename List<T>::const_iterator
    {
        return const_iterator(m_head.get());
    }
 
    template<typename T>
    auto List<T>::cbegin() const -> typename List<T>::const_iterator
    {
        return begin();
    }
 
    template<typename T>
    auto List<T>::end() -> typename List<T>::iterator
    {
        return iterator(m_tail);
    }
 
    template<typename T>
    auto List<T>::end() const -> typename List<T>::const_iterator
    {
        return const_iterator(m_tail);
    }
 
    template<typename T>
    auto List<T>::cend() const -> typename List<T>::const_iterator
    {
        return end();
    }
 
    template<typename T>
    auto List<T>::empty() const -> bool
    {
        return m_size == 0;
    }
 
    template<typename T>
    auto List<T>::size() const -> size_t
    {
        return m_size;
    }
 
    template<typename T>
    auto List<T>::max_size() const -> size_t
    {
        return std::numeric_limits<size_t>::max();
    }
 
    template<typename T>
    void List<T>::clear()
    {
        if (m_head && m_head->m_next)
        {
            while (m_head->m_next)
            {
                m_head = std::move(m_head->m_next);
            }
 
            m_size = 0;
            m_tail->m_prev = nullptr;
        }
    }
 
    template<typename T>
    auto List<T>::insert(const const_iterator& pos, const_reference value) -> typename List<T>::iterator
    {
        return insert(pos, 1, value);
    }
 
    template<typename T>
    auto List<T>::insert(const const_iterator& pos, size_t count, const_reference value) -> typename List<T>::iterator
    {
        iterator iter{ pos.m_current_node };
 
        if (!if_valid_iterator(pos))
        {
            return nullptr;
        }
 
        for (size_t i = 0; i < count; i++)
        {
            iter = insert_element_before(iter, value);
        }
 
        return iter;
    }
 
    template<typename T>
    auto List<T>::insert(const const_iterator& pos, std::initializer_list<T> init_list) -> typename List<T>::iterator
    {
        iterator iter(pos.m_current_node);
 
        if (!if_valid_iterator(pos))
        {
            return nullptr;
        }
 
        for (const auto& val : init_list)
        {
            iter = insert_element_before(iter, val);
            ++iter;
        }
 
        return iter;
    }
 
    template<typename T>
    auto List<T>::erase(iterator pos) -> typename List<T>::iterator
    {
        if (!if_valid_iterator(pos))
        {
            return nullptr;
        }
 
        return erase_element(pos);
    }
 
    template<typename T>
    auto List<T>::erase(iterator first, iterator last) -> typename List<T>::iterator
    {
        if (!if_valid_iterator(first) || !if_valid_iterator(last))
        {
            return nullptr;
        }
 
        const size_t dist = distance(first, last);
        if (dist == 0)
        {
            return last;
        }
 
        iterator iter(first.m_current_node);
        for (size_t i = 0; i < dist; i++)
        {
            iter = erase_element(iter);
        }
 
        return iter;
    }
 
    template<typename T>
    void List<T>::push_front(T value)
    {
        init_node();
 
        auto newNode = std::make_unique<Node>(value);
        if (!m_head->m_next)
        {
            newNode->m_next = std::move(m_head);
            m_head = std::move(newNode);
            m_tail->m_prev = m_head.get();
        }
        else
        {
            m_head->m_prev = newNode.get();
            newNode->m_next = std::move(m_head);
            m_head = std::move(newNode);
        }
 
        m_size++;
    }
 
    template<typename T>
    void List<T>::pop_front()
    {
        if (m_size == 0)
        {
            return;
        }
 
        if (m_size == 1)
        {
            m_head = std::move(m_head->m_next);
            m_tail->m_prev = nullptr;
        }
        else
        {
            m_head = std::move(m_head->m_next);
            m_head->m_prev = nullptr;
        }
 
        m_size--;
    }
 
    template<typename T>
    void List<T>::push_back(T value)
    {
        init_node();
 
        auto newNode = std::make_unique<Node>(value);
 
        if (!m_head->m_next) // only sentinel exists
        {
            newNode->m_next = std::move(m_head);
            m_head = std::move(newNode);
            m_tail->m_prev = m_head.get();
        }
        else
        {
            newNode->m_prev = m_tail->m_prev;
            newNode->m_next = std::move(m_tail->m_prev->m_next);
            m_tail->m_prev = newNode.get();
            m_tail->m_prev->m_prev->m_next = std::move(newNode);
        }
 
        m_size++;
    }
 
    template<typename T>
    void List<T>::pop_back()
    {
        if (m_size == 0)
        {
            return;
        }
 
        if (m_size == 1)
        {
            m_head = std::move(m_head->m_next);
            m_tail->m_prev = nullptr;
        }
        else
        {
            NodeBase* temp{ m_tail->m_prev->m_prev };
            m_tail->m_prev->m_prev->m_next = std::move(m_tail->m_prev->m_next);
            m_tail->m_prev = temp;
        }
 
        m_size--;
    }
 
    template<typename T>
    void List<T>::resize(size_t count)
    {
        resize(count, T{});
    }
 
    template<typename T>
    void List<T>::resize(size_t count, const_reference value)
    {
        if (count == m_size)
        {
            return;
        }
 
        if (m_size > count)
        {
            // container is reduced to its count elements
            while (m_size > count)
            {
                pop_back();
            }
        }
 
        if (m_size < count)
        {
            // additional copies of value are appended
            while (m_size < count)
            {
                push_back(value);
            }
        }
    }
 
    template<typename T>
    void List<T>::swap(List<T>& other) noexcept
    {
        std::swap(m_head, other.m_head);
        std::swap(m_tail, other.m_tail);
        std::swap(m_size, other.m_size);
    }
 
    template<typename T>
    void List<T>::merge(List<T>& other)
    {
        merge(std::move(other));
    }
 
    template<typename T>
    // transfers ownership of nodes, moving entire container is not necessary
    // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
    void List<T>::merge(List<T>&& other)
    {
        if (&other != this)
        {
            if (m_size != 0)
            {
                auto temp_head = std::make_unique<Node>(0);
                NodeBase* temp_tail = temp_head.get();
 
                std::unique_ptr<NodeBase> to_move{};
                std::unique_ptr<NodeBase> to_return{};
 
                std::unique_ptr<NodeBase> sentinel_this{ std::move(m_tail->m_prev->m_next) };
                const std::unique_ptr<NodeBase> sentinel_other{ std::move(other.m_tail->m_prev->m_next) };
 
                while (m_head && other.m_head)
                {
                    Node* node_this = dynamic_cast<Node*>(m_head.get());
                    Node* node_other = dynamic_cast<Node*>(other.m_head.get());
 
                    if (node_this && node_other)
                    {
                        if (node_this->value() <= node_other->value())
                        {
                            to_move = std::move(m_head);
                            to_move->m_prev = temp_tail;
 
                            to_return = std::move(to_move->m_next);
                            temp_tail->m_next = std::move(to_move);
                            m_head = std::move(to_return);
                        }
                        else
                        {
                            to_move = std::move(other.m_head);
                            to_move->m_prev = temp_tail;
 
                            to_return = std::move(to_move->m_next);
                            temp_tail->m_next = std::move(to_move);
                            other.m_head = std::move(to_return);
                        }
 
                        temp_tail = temp_tail->m_next.get();
                    }
                }
 
                NodeBase* last{};
                if (m_head == nullptr) // other.m_head attached at the end
                {
                    last = sentinel_other->m_prev;
                    other.m_head->m_prev = temp_tail;
                    temp_tail->m_next = std::move(other.m_head);
                }
                else // this.m_head attached at the end
                {
                    last = sentinel_this->m_prev;
                    m_head->m_prev = temp_tail;
                    temp_tail->m_next = std::move(m_head);
                }
                last->m_next = std::move(sentinel_this);
                last->m_next->m_prev = last;
 
                m_head = std::move(temp_head->m_next);
                m_head->m_prev = nullptr;
 
                m_size += other.m_size;
                other.m_size = 0;
            }
            else
            {
                swap(other);
            }
        }
    }
 
    template<typename T>
    auto List<T>::distance(const_iterator first, const const_iterator& last) -> size_t
    {
        size_t dist{};
        while (first != last)
        {
            ++first;
            ++dist;
        }
 
        return dist;
    }
 
    template<typename T>
    // transfers ownership of nodes, moving entire container is not necessary
    // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
    void List<T>::transfer(const_iterator pos, List<T>&& other, const_iterator first, const const_iterator& last)
    {
        if (&other != this && other.m_size > 0)
        {
            const size_t dist = distance(first, last);
            if (dist == 0)
            {
                return;
            }
 
            NodeBase* temp_prev{ pos.m_current_node->m_prev }; // to append to
            NodeBase* last_to_move{ last.m_current_node->m_prev };
 
            // select fragment from other
 
            std::unique_ptr<NodeBase> fragment{};
            std::unique_ptr<NodeBase> fragment_end{ std::move(last_to_move->m_next) };
            if (first == other.begin())
            {
                fragment = std::move(other.m_head);
                other.m_head = std::move(fragment_end);
                other.m_head->m_prev = nullptr;
            }
            else
            {
                fragment = std::move(first.m_current_node->m_prev->m_next);
                fragment->m_prev->m_next = std::move(fragment_end);
                fragment->m_prev->m_next->m_prev = first.m_current_node->m_prev;
                fragment->m_prev = nullptr;
            }
 
            // insert fragment into this
 
            if (pos == begin())
            {
                last_to_move->m_next = std::move(m_head);
                last_to_move->m_next->m_prev = last_to_move;
                m_head = std::move(fragment);
            }
            else
            {
                last_to_move->m_next = std::move(temp_prev->m_next);
                last_to_move->m_next->m_prev = last_to_move;
                temp_prev->m_next = std::move(fragment);
                temp_prev->m_next->m_prev = temp_prev;
            }
 
            m_size += dist;
            other.m_size -= dist;
        }
    }
 
    template<typename T>
    void List<T>::splice(const const_iterator& pos, List<T>& other)
    {
        transfer(pos, std::move(other), other.begin(), other.end());
    }
 
    template<typename T>
    void List<T>::splice(const_iterator pos, List<T>&& other)
    {
        transfer(pos, std::move(other), other.begin(), other.end());
    }
 
    template<typename T>
    void List<T>::splice(const const_iterator& pos, List<T>& other, const const_iterator& iter)
    {
        transfer(pos, std::move(other), iter, iter.m_current_node->m_next.get());
    }
 
    template<typename T>
    void List<T>::splice(const_iterator pos, List<T>&& other, const_iterator iter)
    {
        transfer(pos, std::move(other), iter, iter.m_current_node->m_next.get());
    }
 
    template<typename T>
    void List<T>::splice(const const_iterator& pos, List<T>& other,
        const const_iterator& first, const const_iterator& last)
    {
        transfer(pos, std::move(other), first, last);
    }
 
    template<typename T>
    void List<T>::splice(const_iterator pos, List<T>&& other, const_iterator first, const_iterator last)
    {
        transfer(pos, std::move(other), first, last);
    }
 
    template<typename T>
    void List<T>::remove(const_reference value)
    {
        NodeBase* temp{ m_head.get() };
        NodeBase* next{};
 
        while (temp->m_next.get())
        {
            next = temp->m_next.get();
 
            if (Node* node = dynamic_cast<Node*>(m_head.get()))
            {
                if (node->value() == value)
                {
                    pop_front();
                    temp = m_head.get();
                    continue;
                }
            }
 
            if (next && next != m_tail && next->m_next != nullptr)
            {
                Node* node = dynamic_cast<Node*>(next);
                if (node->value() == value)
                {
                    erase(ListIterator<false>(node));
                    continue;
                }
            }
 
            temp = temp->m_next.get();
        }
    }
 
    template<typename T>
    void List<T>::reverse()
    {
        if (m_head->m_next == nullptr)
        {
            return;
        }
 
        NodeBase* new_back{ m_head.get() };
        std::unique_ptr<NodeBase> sentinel = std::move(m_tail->m_prev->m_next);
 
        std::unique_ptr<NodeBase> temp = std::move(m_head);
        std::unique_ptr<NodeBase> prev{};
 
        for (size_t i = 0; i < m_size; i++)
        {
            std::unique_ptr<NodeBase> next = std::move(temp->m_next);
            temp->m_next = std::move(prev);
            temp->m_prev = next.get();
 
            prev = std::move(temp);
            temp = std::move(next);
        }
 
        m_head = std::move(prev);
        m_tail->m_prev = new_back;
        m_tail->m_prev->m_next = std::move(sentinel);
    }
 
    template<typename T>
    void List<T>::unique()
    {
        NodeBase* temp{ m_head.get() };
        NodeBase* prev{};
        NodeBase* next{};
        while (temp)
        {
            prev = temp;
 
            while (prev)
            {
                next = prev->m_next.get();
 
                Node* node_next = dynamic_cast<Node*>(next);
                Node* node_temp = dynamic_cast<Node*>(temp);
                if (node_next && node_temp)
                {
                    if (node_next->value() == node_temp->value())
                    {
                        NodeBase* to_remove = next;
 
                        if (to_remove->m_next)
                        {
                            to_remove->m_next->m_prev = prev;
                        }
                        else // temp was last node
                        {
                            m_tail = prev;
                        }
 
                        prev->m_next = std::move(to_remove->m_next);
 
                        m_size--;
                        continue;
                    }
                }
 
                prev = prev->m_next.get();
                temp = temp->m_next.get();
            }
        }
    }
 
    template<typename T>
    auto List<T>::get(size_t index) const -> typename List<T>::Node*
    {
        if (index >= m_size)
        {
            return nullptr;
        }
 
        NodeBase* temp{};
 
        // select list end to look for selected index
        enum Mode : std::uint8_t { FRONT, BACK, AUTO };
        constexpr Mode mode = Mode::AUTO;
 
 
        if constexpr (mode == FRONT)
        {
            // count nodes from front
            temp = m_head.get();
            for (size_t i = 0; i < index; i++)
            {
                temp = temp->m_next.get();
            }
        }
        else if constexpr (mode == BACK)
        {
            // count nodes from back
            temp = m_tail->m_prev;
            for (size_t i = m_size - 1; i > index; i--)
            {
                temp = temp->m_prev;
            }
        }
        else // mode == AUTO
        {
            // optimize counting nodes from front or back
            if (index < m_size / 2)
            {
                temp = m_head.get();
                for (size_t i = 0; i < index; i++)
                {
                    temp = temp->m_next.get();
                }
            }
            else
            {
                temp = m_tail->m_prev;
                for (size_t i = m_size - 1; i > index; i--)
                {
                    temp = temp->m_prev;
                }
            }
        }
 
        return dynamic_cast<Node*>(temp);
    }
 
    template<typename T>
    auto List<T>::set(size_t index, T value) -> bool
    {
        Node* temp = get(index);
        if (temp)
        {
            temp->m_value = value;
            return true;
        }
 
        return false;
    }

    template<typename T>
    auto operator+(const List<T>& list1, const List<T>& list2) -> List<T>
    {
        List<T> temp(list1);
 
        for (auto iter = list2.cbegin(); iter != list2.cend(); ++iter)
        {
            T value = *iter;
            temp.push_back(value);
        }
 
        return temp;
    }

    template<typename T>
    auto operator<<(std::ostream& out, const List<T>& list) -> std::ostream&
    {
        if (list.empty())
        {
            return out;
        }
 
        for (auto iter = list.cbegin(); iter != list.cend(); ++iter)
        {
            T value = *iter;
            out << value << ' ';
        }
 
        return out;
    }

    template<typename T>
    auto operator==(const List<T>& list1, const List<T>& list2) -> bool
    {
        if (list1.size() != list2.size())
        {
            return false;
        }
 
        auto list1_iter = list1.cbegin();
        auto list2_iter = list2.cbegin();
 
        while (list1_iter != list1.cend())
        {
            if (*list1_iter != *list2_iter)
            {
                return false;
            }
 
            list1_iter++;
            list2_iter++;
        }
 
        return true;
    }

    template<typename T>
    auto operator!=(const List<T>& list1, const List<T>& list2) -> bool
    {
        return !(operator==(list1, list2));
    }

    template<typename T>
    auto operator<(const List<T>& list1, const List<T>& list2) -> bool
    {
        auto list1_iter = list1.cbegin();
        auto list2_iter = list2.cbegin();
 
        while (list1_iter != list1.cend() && list2_iter != list2.cend())
        {
            if (*list1_iter > *list2_iter)
            {
                return false;
            }
            if (*list1_iter < *list2_iter)
            {
                return true;
            }
 
            list1_iter++;
            list2_iter++;
        }
 
        // first n elements are equal
        // check sizes
        return list1.size() < list2.size();
    }

    template<typename T>
    auto operator>(const List<T>& list1, const List<T>& list2) -> bool
    {
        return operator<(list2, list1);
    }

    template<typename T>
    auto operator<=(const List<T>& list1, const List<T>& list2) -> bool
    {
        return !(operator>(list1, list2));
    }

    template<typename T>
    auto operator>=(const List<T>& list1, const List<T>& list2) -> bool
    {
        return !(operator<(list1, list2));
    }
}
 
#endif // !LIST_H