forward_list.h

Go to the documentation of this file.

 
#ifndef FORWARD_LIST_H
#define FORWARD_LIST_H
 
#include <cstddef>
#include <functional>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <limits>
#include <memory>
#include <ranges>
#include <utility>
 
namespace dsa
{
 
    template<typename T>
    class ForwardList;

    template<typename T>
    class ForwardList
    {
    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 ForwardList<T>;

            NodeBase* m_next{};
        };

        class Node : public NodeBase
        {
        public:

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

            Node(T&& value)
                : m_value{ std::move(value) }
            {}

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

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

            friend class ForwardList;
 
            T m_value{};
        };

        template<bool IF_CONST>
        class ForwardListIterator
        {
        public:

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

            using iterator_category = std::forward_iterator_tag;

            using difference_type = std::ptrdiff_t;

            using value_type = T;

            using size_type = std::size_t;

            using pointer = iterator_type*;

            using reference = iterator_type&;

            ForwardListIterator() noexcept = default;

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

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

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

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

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

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

            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 ForwardListIterator<true>()
            {
                return ForwardListIterator<true>(m_current_node);
            }
 
        private:

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

        using value_type = T;

        using allocator_type = std::allocator<value_type>;

        using size_type = std::size_t;

        using difference_type = std::ptrdiff_t;

        using pointer = value_type*;

        using const_pointer = const value_type*;

        using reference = value_type&;

        using const_reference = const value_type&;

        using const_iterator = ForwardListIterator<true>;

        using iterator = ForwardListIterator<false>;

        ForwardList();

        ForwardList(size_type count);

        ForwardList(size_type count, const T& value);

        template<typename InputIt>
            requires std::input_iterator<InputIt>
        ForwardList(InputIt first, InputIt last);

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

        ForwardList(const ForwardList<T>& other);

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

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

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

        ~ForwardList();

        void assign(size_type count, const_reference value);

        template<typename InputIt>
            requires std::input_iterator<InputIt>
        void assign(InputIt first, InputIt last);

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

        [[nodiscard]] constexpr auto get_allocator() const -> allocator_type;

        [[nodiscard]] auto front() -> reference;

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

        [[nodiscard]] auto before_begin() noexcept -> iterator;

        [[nodiscard]] auto before_begin() const noexcept -> const_iterator;

        [[nodiscard]] auto cbefore_begin() const noexcept -> const_iterator;

        [[nodiscard]] auto begin() noexcept -> iterator;

        [[nodiscard]] auto begin() const noexcept -> const_iterator;

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

        [[nodiscard]] auto end() noexcept -> iterator;

        [[nodiscard]] auto end() const noexcept -> const_iterator;

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

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

        [[nodiscard]] auto max_size() const noexcept -> size_type;

        void clear();

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

        auto insert_after(const const_iterator& pos, T&& value) -> iterator;

        auto insert_after(const const_iterator& pos, size_type count, const_reference value) -> iterator;

        template<typename InputIt>
            requires std::input_iterator<InputIt>
        auto insert_after(const const_iterator& pos, InputIt first, InputIt last) -> iterator;

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

        template<typename... Args>
        auto emplace_after(const_iterator pos, Args&&... args) -> iterator;

        auto erase_after(const const_iterator& pos) -> iterator;

        auto erase_after(const const_iterator& first, const const_iterator& last) -> iterator;

        void push_front(const_reference value);

        void push_front(T&& value);

        template<typename... Args>
        auto emplace_front(Args&&... args) -> reference;

        void pop_front();

        void resize(size_type count);

        void resize(size_type count, const_reference value);

        void swap(ForwardList<T>& other) noexcept(std::is_nothrow_swappable_v<T>);

        void merge(ForwardList<T>& other);

        void merge(ForwardList<T>&& other);

        template<typename Compare>
        void merge(ForwardList<T>& other, Compare comp);

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

        void splice_after(const const_iterator& pos, ForwardList<T>& other);

        void splice_after(const_iterator pos, ForwardList<T>&& other);

        void splice_after(const const_iterator& pos, ForwardList<T>& other, const const_iterator& iter);

        void splice_after(const_iterator pos, ForwardList<T>&& other, const_iterator iter);

        void splice_after(const const_iterator& pos, ForwardList<T>& other,
            const const_iterator& first, const const_iterator& last);

        void splice_after(const_iterator pos, ForwardList<T>&& other, const_iterator first, const_iterator last);

        auto remove(const_reference value) -> size_type;

        template<typename UnaryPred>
        auto remove_if(UnaryPred predicate) -> size_type;

        void reverse();

        auto unique() -> size_type;

        template<typename BinaryPred>
        auto unique(BinaryPred predicate) -> size_type;

        void sort();

        template<typename Compare>
        void sort(Compare comp);

        [[nodiscard]] auto size() const -> size_type
        {
            return m_size;
        }
 
    private:

        void init_node();

        [[nodiscard]] auto find_iter_before_last() -> iterator;

        auto erase_element_after(iterator pos) -> iterator;

        template<typename... Args>
        auto construct_node(NodeBase* next_ptr, Args&&... args) -> Node*;

        void destroy_node(NodeBase* node_to_destroy);

        [[nodiscard]] auto if_valid_iterator(const const_iterator& pos) -> bool;

        [[nodiscard]] auto distance(const_iterator first, const const_iterator& last) -> size_type;

         // transfers ownership of nodes, moving entire container is not necessary
         // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
        void transfer(const const_iterator& pos, ForwardList<T>&& other, const const_iterator& iter);

         // transfers ownership of nodes, moving entire container is not necessary
         // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
        void transfer(const const_iterator& pos, ForwardList<T>&& other,
            const const_iterator& first, const const_iterator& last);

        template<typename Compare>
        auto merge_sort(NodeBase* source, Compare comp) -> NodeBase*;

        template<typename Compare>
        auto merge(NodeBase* left, NodeBase* right, Compare comp) -> NodeBase*;
 
        NodeBase* m_head{};
        size_type m_size{};

        allocator_type m_allocator{};

        using node_allocator = typename std::allocator_traits<std::allocator<T>>::template rebind_alloc<Node>;

        using node_alloc_traits = std::allocator_traits<node_allocator>;

        node_allocator node_alloc{};
    };
 
    template<typename T>
    ForwardList<T>::ForwardList()
    {
        init_node();
    }
 
    template<typename T>
    ForwardList<T>::ForwardList(size_type count)
        : ForwardList(count, T{})
    {}
 
    template<typename T>
    ForwardList<T>::ForwardList(size_type count, const T& value)
    {
        init_node();
 
        for (size_type i = 0; i < count; i++)
        {
            push_front(value);
        }
    }
 
    template<typename T>
    template<typename InputIt>
        requires std::input_iterator<InputIt>
    ForwardList<T>::ForwardList(InputIt first, InputIt last)
    {
        init_node();
 
        assign(first, last);
    }
 
    template<typename T>
    ForwardList<T>::ForwardList(const std::initializer_list<T>& init_list)
    {
        init_node();
 
        auto iter = before_begin();
        for (const auto& item : init_list)
        {
            iter = insert_after(iter, item);
        }
    }
 
    template<typename T>
    ForwardList<T>::ForwardList(const ForwardList<T>& other)
    {
        init_node();
 
        auto iter = before_begin();
        for (const auto& item : other)
        {
            iter = insert_after(iter, item);
        }
    }
 
    template<typename T>
    auto ForwardList<T>::operator=(const ForwardList<T>& other) -> ForwardList<T>&
    {
        init_node();
 
        if (&other != this)
        {
            while (m_head->m_next)
            {
                pop_front();
            }
 
            auto iter = before_begin();
            for (const auto& item : other)
            {
                iter = insert_after(iter, item);
            }
        }
 
        return *this;
    }
 
    template<typename T>
    ForwardList<T>::ForwardList(ForwardList<T>&& other) noexcept
    {
        operator=(std::move(other));
    }
 
    template<typename T>
    auto ForwardList<T>::operator=(ForwardList<T>&& other) noexcept -> ForwardList<T>&
    {
        if (&other != this)
        {
            clear();
            init_node();
 
            m_head->m_next = other.m_head->m_next;
            m_size = other.m_size;
 
            other.m_head->m_next = nullptr;
            other.m_size = 0;
        }
 
        return *this;
    }
 
    template<typename T>
    ForwardList<T>::~ForwardList()
    {
        clear();
        delete m_head;
    }
 
    template<typename T>
    void ForwardList<T>::assign(size_type count, const_reference value)
    {
        while (m_head->m_next)
        {
            pop_front();
        }
 
        auto iter = before_begin();
        for (size_type i = 0; i < count; i++)
        {
            iter = insert_after(iter, value);
        }
    }
 
    template<typename T>
    template<typename InputIt>
        requires std::input_iterator<InputIt>
    void ForwardList<T>::assign(InputIt first, InputIt last)
    {
        clear();
 
        auto iter = before_begin();
        while (first != last)
        {
            iter = insert_after(iter, *first);
            first++;
        }
    }
 
    template<typename T>
    void ForwardList<T>::assign(const std::initializer_list<T>& init_list)
    {
        while (m_head->m_next)
        {
            pop_front();
        }
 
        auto iter = before_begin();
        for (const auto& item : init_list)
        {
            iter = insert_after(iter, item);
        }
    }
 
    template<typename T>
    [[nodiscard]] constexpr auto ForwardList<T>::get_allocator() const -> allocator_type
    {
        return m_allocator;
    }
 
    template<typename T>
    auto ForwardList<T>::front() -> typename ForwardList<T>::reference
    {
        return *begin();
    }
 
    template<typename T>
    auto ForwardList<T>::front() const -> typename ForwardList<T>::const_reference
    {
        return *cbegin();
    }
 
    template<typename T>
    auto ForwardList<T>::before_begin() noexcept -> typename ForwardList<T>::iterator
    {
        return iterator(m_head);
    }
 
    template<typename T>
    auto ForwardList<T>::before_begin() const noexcept -> typename ForwardList<T>::const_iterator
    {
        return const_iterator(m_head);
    }
 
    template<typename T>
    auto ForwardList<T>::cbefore_begin() const noexcept -> typename ForwardList<T>::const_iterator
    {
        return before_begin();
    }
 
    template<typename T>
    auto ForwardList<T>::begin() noexcept -> typename ForwardList<T>::iterator
    {
        return iterator(m_head->m_next);
    }
 
    template<typename T>
    auto ForwardList<T>::begin() const noexcept -> typename ForwardList<T>::const_iterator
    {
        return const_iterator(m_head->m_next);
    }
 
    template<typename T>
    auto ForwardList<T>::cbegin() const noexcept -> typename ForwardList<T>::const_iterator
    {
        return begin();
    }
 
    template<typename T>
    auto ForwardList<T>::end() noexcept -> typename ForwardList<T>::iterator
    {
        return iterator(nullptr);
    }
 
    template<typename T>
    auto ForwardList<T>::end() const noexcept -> typename ForwardList<T>::const_iterator
    {
        return const_iterator(nullptr);
    }
 
    template<typename T>
    auto ForwardList<T>::cend() const noexcept -> typename ForwardList<T>::const_iterator
    {
        return end();
    }
 
 
    template<typename T>
    auto ForwardList<T>::empty() const -> bool
    {
        return m_size == 0;
    }
 
    template<typename T>
    auto ForwardList<T>::max_size() const noexcept -> size_type
    {
        return std::numeric_limits<size_type>::max();
    }
 
    template<typename T>
    void ForwardList<T>::clear()
    {
        if (m_head)
        {
            NodeBase* temp{ m_head->m_next };
            while (temp)
            {
                m_head->m_next = temp->m_next;
                destroy_node(temp);
                temp = m_head->m_next;
            }
 
            m_size = 0;
            m_head->m_next = nullptr;
        }
    }
 
    template<typename T>
    auto ForwardList<T>::insert_after(const const_iterator& pos, const_reference value)
        -> typename ForwardList<T>::iterator
    {
        return insert_after(pos, 1, value);
    }
 
    template<typename T>
    auto ForwardList<T>::insert_after(const const_iterator& pos, T&& value)
        -> typename ForwardList<T>::iterator
    {
        if (!if_valid_iterator(pos))
        {
            return nullptr;
        }
 
        iterator iter{ pos.m_current_node };
        iter = emplace_after(iter, std::move(value));
 
        return iter;
    }
 
    template<typename T>
    auto ForwardList<T>::insert_after(const const_iterator& pos, size_type count, const_reference value)
        -> typename ForwardList<T>::iterator
    {
        if (!if_valid_iterator(pos))
        {
            return nullptr;
        }
 
        iterator iter{ pos.m_current_node };
        for (size_type i = 0; i < count; i++)
        {
            iter = emplace_after(iter, value);
        }
 
        return iter;
    }
 
    template<typename T>
    template<typename InputIt>
        requires std::input_iterator<InputIt>
    auto ForwardList<T>::insert_after(const const_iterator& pos, InputIt first, InputIt last)
        -> typename ForwardList<T>::iterator
    {
        if (!if_valid_iterator(pos))
        {
            return nullptr;
        }
 
        iterator iter{ pos.m_current_node };
        while (first != last)
        {
            iter = insert_after(iter, *first);
            first++;
        }
 
        return iter;
    }
 
    template<typename T>
    auto ForwardList<T>::insert_after(const const_iterator& pos, std::initializer_list<T> init_list)
        -> typename ForwardList<T>::iterator
    {
        if (!if_valid_iterator(pos))
        {
            return nullptr;
        }
 
        iterator iter{ pos.m_current_node };
        for (const auto val : init_list)
        {
            iter = emplace_after(iter, val);
        }
 
        return iter;
    }
 
    template<typename T>
    template<typename... Args>
    auto ForwardList<T>::emplace_after(const_iterator pos, Args&&... args) -> iterator
    {
        const iterator current{ pos.m_current_node };
 
        Node* newNode{ construct_node(current.m_current_node->m_next, std::forward<Args>(args)...) };
        current.m_current_node->m_next = newNode;
        ++m_size;
 
        return iterator(newNode);
    }
 
    template<typename T>
    auto ForwardList<T>::erase_after(const const_iterator& pos) -> typename ForwardList<T>::iterator
    {
        if (!if_valid_iterator(pos))
        {
            return nullptr;
        }
 
        iterator iter{ pos.m_current_node };
        iter = erase_element_after(iter);
 
        return iter;
    }
 
    template<typename T>
    auto ForwardList<T>::erase_after(const const_iterator& first,
        const const_iterator& last) -> typename ForwardList<T>::iterator
    {
        if (!if_valid_iterator(first) || !if_valid_iterator(last))
        {
            return nullptr;
        }
 
        const iterator iter(first.m_current_node);
        const size_type dist = distance(first, last);
        for (size_type i = 0; i < dist - 1; i++)
        {
            erase_element_after(iter);
        }
 
        return first.m_current_node->m_next;
    }
 
    template<typename T>
    void ForwardList<T>::push_front(const_reference value)
    {
        emplace_after(before_begin(), value);
    }
 
    template<typename T>
    void ForwardList<T>::push_front(T&& value)
    {
        emplace_after(before_begin(), std::move(value));
    }
 
    template<typename T>
    template<typename... Args>
    auto ForwardList<T>::emplace_front(Args&&... args) -> reference
    {
        emplace_after(before_begin(), std::forward<Args>(args)...);
        return front();
    }
 
    template<typename T>
    void ForwardList<T>::pop_front()
    {
        if (!m_head->m_next)
        {
            return;
        }
 
        NodeBase* temp{ m_head->m_next };
        if (m_size == 1)
        {
            m_head->m_next = nullptr;
        }
        else
        {
            m_head->m_next = temp->m_next;
        }
        destroy_node(temp);
 
        m_size--;
    }
 
    template<typename T>
    void ForwardList<T>::resize(size_type count)
    {
        resize(count, T{});
    }
 
    template<typename T>
    void ForwardList<T>::resize(size_type count, const_reference value)
    {
        init_node();
 
        if (count == m_size)
        {
            return;
        }
 
        if (m_size > count)
        {
            auto iter = begin();
            for (size_type i = 0; i < count - 1; i++)
            {
                ++iter;
            }
 
            while (m_size > count)
            {
                erase_after(iter);
            }
        }
 
        if (m_size < count)
        {
            auto iter = find_iter_before_last();
            if (iter != before_begin())
            {
                ++iter;
            }
 
            while (m_size < count)
            {
                iter = insert_after(iter, value);
            }
        }
    }
 
    template<typename T>
    void ForwardList<T>::swap(ForwardList<T>& other) noexcept(std::is_nothrow_swappable_v<T>)
    {
        std::swap(m_head->m_next, other.m_head->m_next);
        std::swap(m_size, other.m_size);
    }
 
    template<typename T>
    void ForwardList<T>::merge(ForwardList<T>& other)
    {
        merge(std::move(other));
    }
 
    template<typename T>
    void ForwardList<T>::merge(ForwardList<T>&& other)
    {
        merge(std::move(other), std::less<>());
    }
 
    template<typename T>
    template<typename Compare>
    void ForwardList<T>::merge(ForwardList<T>& other, Compare comp)
    {
        merge(std::move(other), comp);
    }
 
    template<typename T>
    template<typename Compare>
    // transfers ownership of nodes, moving entire container is not necessary
    // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
    void ForwardList<T>::merge(ForwardList<T>&& other, Compare comp)
    {
        if (&other == this)
        {
            return;
        }
 
        if (m_size != 0)
        {
            Node* temp_head{ construct_node(nullptr, T{}) };
            NodeBase* temp_tail{ temp_head };
 
            NodeBase* to_move{};
            NodeBase* to_return{};
 
            while (m_head->m_next && other.m_head->m_next)
            {
                Node* node_this = dynamic_cast<Node*>(m_head->m_next);
                Node* node_other = dynamic_cast<Node*>(other.m_head->m_next);
 
                if (node_this && node_other)
                {
                    if (comp(node_this->value(), node_other->value()))
                    {
                        to_move = m_head->m_next;
                        to_return = to_move->m_next;
                        temp_tail->m_next = to_move;
                        m_head->m_next = to_return;
                    }
                    else
                    {
                        to_move = other.m_head->m_next;
                        to_return = to_move->m_next;
                        temp_tail->m_next = to_move;
                        other.m_head->m_next = to_return;
                    }
 
                    temp_tail = temp_tail->m_next;
                }
            }
 
            if (m_head->m_next == nullptr)
            {
                temp_tail->m_next = other.m_head->m_next;
                other.m_head->m_next = nullptr;
            }
            else
            {
                temp_tail->m_next = m_head->m_next;
                m_head->m_next = nullptr;
            }
 
            m_head->m_next = temp_head->m_next;
            destroy_node(temp_head);
 
            m_size += other.m_size;
            other.m_size = 0;
        }
        else
        {
            swap(other);
        }
    }
 
    template<typename T>
    void ForwardList<T>::splice_after(const const_iterator& pos, ForwardList<T>& other)
    {
        transfer(pos, std::move(other), other.before_begin(), other.end());
    }
 
    template<typename T>
    void ForwardList<T>::splice_after(const_iterator pos, ForwardList<T>&& other)
    {
        transfer(pos, std::move(other), other.before_begin(), other.end());
    }
 
    template<typename T>
    void ForwardList<T>::splice_after(const const_iterator& pos, ForwardList<T>& other, const const_iterator& iter)
    {
        transfer(pos, std::move(other), iter);
    }
 
    template<typename T>
    void ForwardList<T>::splice_after(const_iterator pos, ForwardList<T>&& other, const_iterator iter)
    {
        transfer(pos, std::move(other), iter);
    }
 
    template<typename T>
    void ForwardList<T>::splice_after(const const_iterator& pos, ForwardList<T>& other,
        const const_iterator& first, const const_iterator& last)
    {
        transfer(pos, std::move(other), first, last);
    }
 
    template<typename T>
    void ForwardList<T>::splice_after(const_iterator pos, ForwardList<T>&& other, const_iterator first, const_iterator last)
    {
        transfer(pos, std::move(other), first, last);
    }
 
    template<typename T>
    auto ForwardList<T>::remove(const_reference value) -> size_type
    {
        return remove_if([value](T node_val) { return node_val == value; });
    }
 
    template<typename T>
    template<typename UnaryPred>
    auto ForwardList<T>::remove_if(UnaryPred predicate) -> size_type
    {
        NodeBase* temp{ m_head };
        NodeBase* next{};
 
        size_type removed_count{};
 
        while (temp)
        {
            next = temp->m_next;
 
            if (Node* node = dynamic_cast<Node*>(next))
            {
                if (predicate(node->value()))
                {
                    NodeBase* to_remove = temp->m_next;
                    temp->m_next = to_remove->m_next;
                    destroy_node(to_remove);
 
                    removed_count++;
                    m_size--;
                    continue;
                }
            }
 
            temp = temp->m_next;
        }
 
        return removed_count;
    }
 
    template<typename T>
    void ForwardList<T>::reverse()
    {
        NodeBase* temp{ m_head->m_next };
 
        auto iter = find_iter_before_last();
        NodeBase* last{ iter.m_current_node->m_next };
 
        m_head->m_next = last;
        last = temp;
 
        NodeBase* prev{};
        NodeBase* next{};
 
        for (size_type i = 0; i < m_size; i++)
        {
            next = temp->m_next;
            temp->m_next = prev;
 
            prev = temp;
            temp = next;
        }
 
        m_head->m_next = std::move(prev);
    }
 
    template<typename T>
    auto ForwardList<T>::unique() -> size_type
    {
        return unique(std::equal_to<>());
    }
 
    template<typename T>
    template<typename BinaryPred>
    auto ForwardList<T>::unique(BinaryPred predicate) -> size_type
    {
        NodeBase* temp{ m_head };
        NodeBase* prev{};
        NodeBase* next{};
 
        size_type removed_count{};
 
        while (temp)
        {
            prev = temp;
 
            while (prev)
            {
                next = prev->m_next;
 
                Node* node_next = dynamic_cast<Node*>(next);
                Node* node_temp = dynamic_cast<Node*>(temp);
                if (node_next && node_temp)
                {
                    if (predicate(node_next->value(), node_temp->value()))
                    {
                        NodeBase* to_remove = next;
                        prev->m_next = to_remove->m_next;
                        destroy_node(to_remove);
 
                        removed_count++;
                        m_size--;
                        continue;
                    }
                }
 
                prev = prev->m_next;
                temp = temp->m_next;
            }
        }
 
        return removed_count;
    }
 
    template<typename T>
    void ForwardList<T>::sort()
    {
        m_head->m_next = merge_sort(m_head->m_next, std::less<>());
    }
 
    template<typename T>
    template<typename Compare>
    void ForwardList<T>::sort(Compare comp)
    {
        m_head->m_next = merge_sort(m_head->m_next, comp);
    }

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

    template<typename T>
    [[nodiscard]] auto operator==(const ForwardList<T>& lhs, const ForwardList<T>& rhs)
        noexcept(noexcept(*lhs.begin() == *rhs.begin())) -> bool
    {
        if (lhs.size() != rhs.size())
        {
            return false;
        }
 
        auto lhs_iter = lhs.cbegin();
        auto rhs_iter = rhs.cbegin();
 
        while (lhs_iter != lhs.cend())
        {
            if (*lhs_iter != *rhs_iter)
            {
                return false;
            }
 
            lhs_iter++;
            rhs_iter++;
        }
 
        return true;
    }

    template<typename T>
    [[nodiscard]] auto operator<=>(const ForwardList<T>& lhs, const ForwardList<T>& rhs)
        noexcept(noexcept(*lhs.begin() == *rhs.begin())) -> std::compare_three_way_result_t<T>
    {
        auto lhs_iter = lhs.cbegin();
        auto rhs_iter = rhs.cbegin();
 
        while (lhs_iter != lhs.cend() && rhs_iter != rhs.cend())
        {
            auto cmp = *lhs_iter <=> *rhs_iter;
            if (cmp != 0)
            {
                return cmp;
            }
 
            lhs_iter++;
            rhs_iter++;
        }
 
        // first n elements are equal
        // check sizes
        return lhs.size() <=> rhs.size();
    }

    template<typename T>
    void swap(ForwardList<T>& lhs, ForwardList<T>& rhs) noexcept(noexcept(lhs.swap(rhs)))
    {
        lhs.swap(rhs);
    }

    template<typename T, typename U>
    auto erase(ForwardList<T>& container, const U& value) -> ForwardList<T>::size_type
    {
        return erase_if(container, [&value](U node_val) { return node_val == value; });
    }

    template<typename T, typename Pred>
    auto erase_if(ForwardList<T>& container, Pred pred) -> ForwardList<T>::size_type
    {
        return container.remove_if(pred);
    }
 
    // definitions of private methods
 
    template<typename T>
    void ForwardList<T>::init_node()
    {
        if (m_head == nullptr)
        {
            // NOLINTNEXTLINE(cppcoreguidelines-owning-memory)
            m_head = new NodeBase;
        }
    }
 
    template<typename T>
    auto ForwardList<T>::find_iter_before_last() -> iterator
    {
        NodeBase* temp{ m_head->m_next };
        while (temp && temp->m_next && temp->m_next->m_next)
        {
            temp = temp->m_next;
        }
 
        auto iter = iterator(temp);
        if (!iter.m_current_node)
        {
            iter = before_begin();
        }
 
        return iter;
    }
 
    template<typename T>
    auto ForwardList<T>::erase_element_after(iterator pos) -> iterator
    {
        NodeBase* temp{ pos.m_current_node };
        NodeBase* to_remove{ temp->m_next };
 
        temp->m_next = to_remove->m_next;
        destroy_node(to_remove);
 
        m_size--;
        return iterator(temp->m_next);
    }
 
    template<typename T>
    template<typename... Args>
    auto ForwardList<T>::construct_node(NodeBase* next_ptr, Args&&... args) -> Node*
    {
        Node* newNode{};
        try
        {
            newNode = node_alloc_traits::allocate(node_alloc, 1);
            node_alloc_traits::construct(node_alloc, newNode, std::forward<Args>(args)...);
            newNode->m_next = next_ptr;
        }
        catch (...)
        {
            node_alloc_traits::deallocate(node_alloc, newNode, 1);
            throw;
        }
 
        return newNode;
    }
 
    template<typename T>
    void ForwardList<T>::destroy_node(NodeBase* node_to_destroy)
    {
        if (Node* node_dyn = dynamic_cast<Node*>(node_to_destroy))
        {
            node_alloc_traits::destroy(node_alloc, node_dyn);
            node_alloc_traits::deallocate(node_alloc, node_dyn, 1);
        }
    }
 
    template<typename T>
    auto ForwardList<T>::if_valid_iterator(const const_iterator& pos) -> bool
    {
        bool valid_iterator{};
        for (auto it = cbefore_begin(); it != cend(); ++it)
        {
            if (it == pos)
            {
                valid_iterator = true;
                break;
            }
        }
        return valid_iterator;
    }
 
    template<typename T>
    auto ForwardList<T>::distance(const_iterator first, const const_iterator& last) -> size_type
    {
        size_type 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 ForwardList<T>::transfer(const const_iterator& pos, ForwardList<T>&& other, const const_iterator& iter)
    {
        if (&other != this && other.m_size > 0)
        {
            NodeBase* temp_prev{ pos.m_current_node };  // to append to
            NodeBase* temp_next{ iter.m_current_node }; // does not move
 
            NodeBase* to_move{ temp_next->m_next };
 
            temp_next->m_next = to_move->m_next;
            to_move->m_next = temp_prev->m_next;
            temp_prev->m_next = to_move;
 
            m_size += 1;
            other.m_size -= 1;
        }
    }
 
    template<typename T>
    // transfers ownership of nodes, moving entire container is not necessary
    // NOLINTNEXTLINE(cppcoreguidelines-rvalue-reference-param-not-moved)
    void ForwardList<T>::transfer(const const_iterator& pos, ForwardList<T>&& other,
        const const_iterator& first, const const_iterator& last)
    {
        if (&other != this && other.m_size > 0)
        {
            const size_type dist = distance(first, last) - 1;
 
            if (first == last || dist == 0)
            {
                return;
            }
 
            NodeBase* temp_prev{ pos.m_current_node };     // to append to
            NodeBase* temp_next{ first.m_current_node };   // does not move
 
            NodeBase* first_to_move{ temp_next->m_next };
            NodeBase* last_to_move{ temp_next };
            for (size_type i = 0; i < dist; i++)
            {
                last_to_move = last_to_move->m_next;
            }
 
            temp_next->m_next = last_to_move->m_next;
            last_to_move->m_next = temp_prev->m_next;
            temp_prev->m_next = first_to_move;
 
            m_size += dist;
            other.m_size -= dist;
        }
    }
 
    template<typename T>
    template<typename Compare>
    // Intentional recursive call for sorting nodes in top-down algorithm implementation
    // NOLINTNEXTLINE(misc-no-recursion)
    auto ForwardList<T>::merge_sort(NodeBase* source, Compare comp) -> NodeBase*
    {
        // Stop condition, one element list is already sorted
        if (source == nullptr || source->m_next == nullptr)
        {
            return source;
        }
 
        // Divide list into equal-sized sublists consisting of first and second half of the list
        NodeBase* left{ source };
        NodeBase* right{};
 
        // Use slow and fast pointer to find half of list
        NodeBase* slow{ source };
        NodeBase* fast{ source->m_next };
        while (fast && fast->m_next)
        {
            slow = slow->m_next;
            fast = fast->m_next->m_next;
        }
 
        // Split input list into two halfs
        right = slow->m_next;
        slow->m_next = nullptr;
 
        // Recursively sort both sub-lists
        left = merge_sort(left, comp);
        right = merge_sort(right, comp);
 
        // Merge sorted sublists
        NodeBase* result{ merge(left, right, comp) };
        return result;
    }
 
    template<typename T>
    template<typename Compare>
    // Intentional recursive call for merging nodes in top-down merge_sort algorithm implementation
    // NOLINTNEXTLINE(misc-no-recursion)
    auto ForwardList<T>::merge(NodeBase* left, NodeBase* right, Compare comp) -> NodeBase*
    {
        // Stop condition, empty element list is already sorted
        if (left == nullptr)
        {
            return right;
        }
        if (right == nullptr)
        {
            return left;
        }
 
        NodeBase* result{};
        Node* node_left = dynamic_cast<Node*>(left);
        Node* node_right = dynamic_cast<Node*>(right);
        if (node_left && node_right)
        {
            // Recursively merge nodes
            if (comp(node_left->m_value, node_right->m_value))
            {
                result = left;
                result->m_next = merge(left->m_next, right, comp);
            }
            else
            {
                result = right;
                result->m_next = merge(left, right->m_next, comp);
            }
        }
 
        return result;
    }
}
 
#endif // !FORWARD_LIST_H