BSTList.h

Go to the documentation of this file.

#pragma once
 
#include "RE/M/MemoryManager.h"
 
namespace RE
{
    template <class T>
    class BSTListNode
    {
    public:
        using value_type = T;
 
        template <class... Args>
        inline BSTListNode(Args&&... a_args) :
            item(std::forward<Args>(a_args)...)
        {}
 
        // members
        BSTListNode<T>* next;  // 00
        BSTListNode<T>* prev;  // 08
        value_type      item;  // 10
    };
 
    template <class T>
    class BSTListHeapAllocator
    {
    public:
        [[nodiscard]] inline BSTListNode<T>* allocate()
        {
            return malloc<BSTListNode<T>>();
        }
 
        inline void deallocate(BSTListNode<T>* a_node)
        {
            free(a_node);
        }
    };
 
    template <class T, class Allocator = BSTListHeapAllocator<T>>
    class BSTList
    {
    public:
        using value_type = T;
        using allocator_type = Allocator;
        using reference = T&;
        using const_reference = const T&;
 
        struct const_iterator
        {
        public:
            using value_type = T;
            using const_pointer = const T*;
            using iterator_category = std::bidirectional_iterator_tag;
 
            friend BSTList<T, Allocator>;
 
            const_iterator(BSTListNode<T>* a_node) noexcept :
                _cur(a_node)
            {}
 
            constexpr const_iterator(const const_iterator& a_rhs) noexcept :
                _cur(a_rhs._cur)
            {}
 
            constexpr const_iterator(const const_iterator&& a_rhs) noexcept :
                _cur(a_rhs._cur)
            {
                a_rhs._cur = nullptr;
            }
 
            constexpr const_iterator& operator=(const const_iterator& a_rhs) noexcept
            {
                if (this != std::addressof(a_rhs)) {
                    _cur = a_rhs._cur;
                }
                return *this;
            }
 
            constexpr const_iterator& operator=(const_iterator&& a_rhs) noexcept
            {
                if (this != std::addressof(a_rhs)) {
                    _cur = std::move(a_rhs._cur);
                    a_rhs._cur = nullptr;
                }
                return *this;
            }
 
            [[nodiscard]] constexpr const_reference operator*() const noexcept { return _cur->item; }
            [[nodiscard]] constexpr const_pointer   operator->() const noexcept { return std::addressof(_cur->item); }
 
            [[nodiscard]] constexpr bool operator==(const const_iterator& a_rhs) const noexcept { return _cur == a_rhs._cur; }
            [[nodiscard]] constexpr bool operator!=(const const_iterator& a_rhs) const noexcept { return !(*this == a_rhs); }
 
            // prefix
            constexpr const_iterator& operator++() noexcept
            {
                assert(_cur);
                _cur = _cur->next;
                return *this;
            }
 
            // postfix
            [[nodiscard]] constexpr const_iterator operator++(int) noexcept
            {
                const_iterator tmp(*this);
                ++(*this);
                return tmp;
            }
 
            // prefix
            constexpr const_iterator& operator--() noexcept
            {
                assert(_cur);
                _cur = _cur->prev;
                return *this;
            }
 
            // postfix
            [[nodiscard]] constexpr const_iterator operator--(int) noexcept
            {
                const_iterator tmp(*this);
                --(*this);
                return tmp;
            }
 
        protected:
            stl::observer<BSTListNode<T>*> _cur;
        };
 
        struct iterator : public const_iterator
        {
        public:
            using pointer = T*;
 
            using const_iterator::const_iterator;
 
            [[nodiscard]] constexpr reference operator*() const noexcept { return const_iterator::_cur->item; }
            [[nodiscard]] constexpr pointer   operator->() const noexcept { return std::addressof(const_iterator::_cur->item); }
 
            // prefix
            constexpr iterator& operator++() noexcept
            {
                const_iterator::operator++();
                return *this;
            }
 
            // postfix
            [[nodiscard]] constexpr iterator operator++(int) noexcept
            {
                iterator        tmp(*this);
                const_iterator::operator++();
                return tmp;
            }
 
            // prefix
            constexpr iterator& operator--() noexcept
            {
                const_iterator::operator--();
                return *this;
            }
 
            // postfix
            [[nodiscard]] constexpr iterator operator--(int) noexcept
            {
                iterator        tmp(*this);
                const_iterator::operator--();
                return tmp;
            }
        };
 
        constexpr BSTList() :
            _sentinel(nullptr)
        {}
 
        BSTList(const BSTList&) = delete;
        BSTList(BSTList&&) = delete;
 
        inline ~BSTList()
        {
            clear();
            if (_sentinel) {
                destroy_list();
            }
        }
 
        BSTList& operator=(const BSTList&) = delete;
        BSTList& operator=(BSTList&&) = delete;
 
        inline reference front()
        {
            return _sentinel->next->item;
        }
 
        inline const_reference front() const
        {
            return _sentinel->next->item;
        }
 
        inline reference back()
        {
            return _sentinel->prev->item;
        }
 
        inline const_reference back() const
        {
            return _sentinel->prev->item;
        }
 
        inline iterator begin()
        {
            return iterator(_sentinel ? _sentinel->next : nullptr);
        }
 
        inline const_iterator begin() const
        {
            return const_iterator(_sentinel ? _sentinel->next : nullptr);
        }
 
        inline const_iterator cbegin() const
        {
            return const_iterator(_sentinel ? _sentinel->next : nullptr);
        }
 
        inline iterator end()
        {
            return iterator(_sentinel);
        }
 
        inline const_iterator end() const
        {
            return const_iterator(_sentinel);
        }
 
        inline const_iterator cend() const
        {
            return const_iterator(_sentinel);
        }
 
        constexpr bool empty() const
        {
            return !_sentinel || _sentinel->next == _sentinel;
        }
 
        inline void clear()
        {
            if (!_sentinel) {
                return;
            }
 
            for (auto node = _sentinel->next; node != _sentinel; node = node->next) {
                std::destroy_at(node);
                allocator_type{}.deallocate(node);
            }
 
            destroy_list();
        }
 
        template <class... Args>
        inline iterator emplace(const_iterator a_pos, Args&&... a_args)
        {
            emplace_impl(a_pos, std::forward<Args>(a_args)...);
            return a_pos._cur->prev;
        }
 
        inline iterator erase(const_iterator a_pos)
        {
            const auto node = a_pos._cur;
            const auto next = node->next;
            node->prev->next = next;
            next->prev = node->prev;
 
            node->prev = nullptr;
            node->next = nullptr;
            allocator_type{}.deallocate(node);
 
            return iterator(next);
        }
 
        inline void push_back(const T& a_value)
        {
            emplace_back(a_value);
        }
 
        inline void push_back(T&& a_value)
        {
            emplace_back(std::move(a_value));
        }
 
        template <class... Args>
        inline reference emplace_back(Args&&... a_args)
        {
            emplace_back_impl(std::forward<Args>(a_args)...);
            return back();
        }
 
        inline void push_front(const T& a_value)
        {
            emplace_front(a_value);
        }
 
        inline void push_front(T&& a_value)
        {
            emplace_front(std::move(a_value));
        }
 
        template <class... Args>
        inline reference emplace_front(Args&&... a_args)
        {
            emplace_front_impl(std::forward<Args>(a_args)...);
            return front();
        }
 
    private:
        template <class... Args>
        inline void emplace_impl(const_iterator a_pos, Args&&... a_args)
        {
            const auto node = allocator_type{}.allocate();
            if (!node) {
                return;
            }
 
            std::construct_at(node, std::forward<Args>(a_args)...);
            node->next = a_pos._cur;
            node->prev = a_pos._cur->prev;
            a_pos._cur->prev->next = node;
            a_pos._cur->prev = node;
        }
 
        template <class... Args>
        inline void emplace_back_impl(Args&&... a_args)
        {
            if (!_sentinel) {
                create_list();
            }
 
            const auto node = allocator_type{}.allocate();
            if (!node) {
                return;
            }
 
            std::construct_at(node, std::forward<Args>(a_args)...);
            node->next = _sentinel;
            node->prev = _sentinel->prev;
            _sentinel->prev->next = node;
            _sentinel->prev = node;
        }
 
        template <class... Args>
        inline void emplace_front_impl(Args&&... a_args)
        {
            if (!_sentinel) {
                create_list();
            }
 
            const auto node = allocator_type{}.allocate();
            if (!node) {
                return;
            }
 
            std::construct_at(node, std::forward<Args>(a_args)...);
            node->prev = _sentinel;
            node->next = _sentinel->next;
            _sentinel->next->prev = node;
            _sentinel->next = node;
        }
 
        inline bool create_list()
        {
            _sentinel = allocator_type{}.allocate();
            if (_sentinel) {
                _sentinel->next = _sentinel;
                _sentinel->prev = _sentinel;
            }
            return _sentinel;
        }
 
        inline void destroy_list()
        {
            allocator_type{}.deallocate(_sentinel);
            _sentinel = nullptr;
        }
 
        // members
        BSTListNode<T>* _sentinel;  // 0
    };
}