rb_tree.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_CONTAINER_RB_TREE_HPP__
#define NEFORCE_CORE_CONTAINER_RB_TREE_HPP__

 
#include "NeForce/core/algorithm/compare.hpp"
#include "NeForce/core/interface/icollector.hpp"
#include "NeForce/core/interface/iiterator.hpp"
#include "NeForce/core/memory/construct.hpp"
#include "NeForce/core/memory/standard_allocator.hpp"
#include "NeForce/core/utility/compressed_pair.hpp"
#include "NeForce/core/utility/pair.hpp"
NEFORCE_BEGIN_NAMESPACE__


NEFORCE_INLINE17 constexpr bool RB_TREE_RED = false;

NEFORCE_INLINE17 constexpr bool RB_TREE_BLACK = true;
 

struct rb_tree_node_base {
    using color_type = bool;             
    using base_ptr = rb_tree_node_base*; 
 
    color_type color_ = RB_TREE_RED; 
    base_ptr parent_ = nullptr;      
    base_ptr left_ = nullptr;        
    base_ptr right_ = nullptr;       

    static base_ptr minimum(base_ptr root) noexcept {
        if (root == nullptr) {
            return nullptr;
        }
        while (root->left_ != nullptr) {
            root = root->left_;
        }
        return root;
    }

    static base_ptr maximum(base_ptr root) noexcept {
        if (root == nullptr) {
            return nullptr;
        }
        while (root->right_ != nullptr) {
            root = root->right_;
        }
        return root;
    }
};
 

NEFORCE_ALWAYS_INLINE_INLINE void rb_tree_rotate_left(rb_tree_node_base* axis, rb_tree_node_base*& root) noexcept {
    rb_tree_node_base* y = axis->right_;
    axis->right_ = y->left_;
    if (y->left_ != nullptr) {
        y->left_->parent_ = axis;
    }
 
    y->parent_ = axis->parent_;
 
    if (axis == root) {
        root = y;
    } else if (axis == axis->parent_->left_) {
        axis->parent_->left_ = y;
    } else {
        axis->parent_->right_ = y;
    }
 
    y->left_ = axis;
    axis->parent_ = y;
}

NEFORCE_ALWAYS_INLINE_INLINE void rb_tree_rotate_right(rb_tree_node_base* axis, rb_tree_node_base*& root) noexcept {
    rb_tree_node_base* y = axis->left_;
    axis->left_ = y->right_;
    if (y->right_ != nullptr) {
        y->right_->parent_ = axis;
    }
    y->parent_ = axis->parent_;
 
    if (axis == root) {
        root = y;
    } else if (axis == axis->parent_->right_) {
        axis->parent_->right_ = y;
    } else {
        axis->parent_->left_ = y;
    }
 
    y->right_ = axis;
    axis->parent_ = y;
}

NEFORCE_ALWAYS_INLINE_INLINE void rb_tree_insert_rebalance(rb_tree_node_base* insert,
                                                           rb_tree_node_base*& root) noexcept {
    insert->color_ = RB_TREE_RED;
 
    while (insert != root && insert->parent_->color_ == RB_TREE_RED) {
        if (insert->parent_ == insert->parent_->parent_->left_) {
            rb_tree_node_base* y = insert->parent_->parent_->right_;
 
            if (y != nullptr && y->color_ == RB_TREE_RED) {
                insert->parent_->color_ = RB_TREE_BLACK;
                y->color_ = RB_TREE_BLACK;
                insert->parent_->parent_->color_ = RB_TREE_RED;
                insert = insert->parent_->parent_;
            } else {
                if (insert == insert->parent_->right_) {
                    insert = insert->parent_;
                    _NEFORCE rb_tree_rotate_left(insert, root);
                }
                insert->parent_->color_ = RB_TREE_BLACK;
                insert->parent_->parent_->color_ = RB_TREE_RED;
                _NEFORCE rb_tree_rotate_right(insert->parent_->parent_, root);
            }
        } else {
            rb_tree_node_base* y = insert->parent_->parent_->left_;
            if (y != nullptr && y->color_ == RB_TREE_RED) {
                insert->parent_->color_ = RB_TREE_BLACK;
                y->color_ = RB_TREE_BLACK;
                insert->parent_->parent_->color_ = RB_TREE_RED;
                insert = insert->parent_->parent_;
            } else {
                if (insert == insert->parent_->left_) {
                    insert = insert->parent_;
                    _NEFORCE rb_tree_rotate_right(insert, root);
                }
                insert->parent_->color_ = RB_TREE_BLACK;
                insert->parent_->parent_->color_ = RB_TREE_RED;
                _NEFORCE rb_tree_rotate_left(insert->parent_->parent_, root);
            }
        }
    }
    root->color_ = RB_TREE_BLACK;
}

NEFORCE_ALWAYS_INLINE_INLINE rb_tree_node_base* rb_tree_erase_rebalance(rb_tree_node_base* erase,
                                                                        rb_tree_node_base*& root,
                                                                        rb_tree_node_base*& leftmost,
                                                                        rb_tree_node_base*& rightmost) noexcept {
    rb_tree_node_base* y = erase;
    rb_tree_node_base* x = nullptr;
    rb_tree_node_base* x_parent = nullptr;
 
    if (y->left_ == nullptr) {
        x = y->right_;
    } else {
        if (y->right_ == nullptr) {
            x = y->left_;
        } else {
            y = y->right_;
            while (y->left_ != nullptr) {
                y = y->left_;
            }
            x = y->right_;
        }
    }
 
    if (y != erase) {
        erase->left_->parent_ = y;
        y->left_ = erase->left_;
 
        if (y != erase->right_) {
            x_parent = y->parent_;
            if (x != nullptr) {
                x->parent_ = y->parent_;
            }
 
            y->parent_->left_ = x;
            y->right_ = erase->right_;
            erase->right_->parent_ = y;
        } else {
            x_parent = y;
        }
 
        if (root == erase) {
            root = y;
        } else if (erase->parent_->left_ == erase) {
            erase->parent_->left_ = y;
        } else {
            erase->parent_->right_ = y;
        }
 
        y->parent_ = erase->parent_;
        _NEFORCE swap(y->color_, erase->color_);
        y = erase;
    } else {
        x_parent = y->parent_;
        if (x != nullptr) {
            x->parent_ = y->parent_;
        }
 
        if (root == erase) {
            root = x;
        } else {
            if (erase->parent_->left_ == erase) {
                erase->parent_->left_ = x;
            } else {
                erase->parent_->right_ = x;
            }
        }
 
        if (leftmost == erase) {
            if (erase->right_ == nullptr) {
                leftmost = erase->parent_;
            } else {
                leftmost = rb_tree_node_base::minimum(x);
            }
        }
 
        if (rightmost == erase) {
            if (erase->left_ == nullptr) {
                rightmost = erase->parent_;
            } else {
                rightmost = rb_tree_node_base::maximum(x);
            }
        }
    }
 
    if (y->color_ != RB_TREE_RED) {
        while (x != root && (x == nullptr || x->color_ == RB_TREE_BLACK)) {
            if (x == x_parent->left_) {
                rb_tree_node_base* w = x_parent->right_;
                NEFORCE_DEBUG_VERIFY(w != nullptr, "RB-tree structure corrupted: right sibling is null");
                if (w == nullptr) {
                    x = x_parent;
                    x_parent = x_parent->parent_;
                    continue;
                }
 
                if (w->color_ == RB_TREE_RED) {
                    w->color_ = RB_TREE_BLACK;
                    x_parent->color_ = RB_TREE_RED;
                    _NEFORCE rb_tree_rotate_left(x_parent, root);
                    w = x_parent->right_;
                }
 
                if ((w->left_ == nullptr || w->left_->color_ == RB_TREE_BLACK) &&
                    (w->right_ == nullptr || w->right_->color_ == RB_TREE_BLACK)) {
                    w->color_ = RB_TREE_RED;
                    x = x_parent;
                    x_parent = x_parent->parent_;
                } else {
                    if (w->right_ == nullptr || w->right_->color_ == RB_TREE_BLACK) {
                        if (w->left_ != nullptr) {
                            w->left_->color_ = RB_TREE_BLACK;
                        }
                        w->color_ = RB_TREE_RED;
                        _NEFORCE rb_tree_rotate_right(w, root);
                        w = x_parent->right_;
                    }
                    w->color_ = x_parent->color_;
                    x_parent->color_ = RB_TREE_BLACK;
                    if (w->right_ != nullptr) {
                        w->right_->color_ = RB_TREE_BLACK;
                    }
                    _NEFORCE rb_tree_rotate_left(x_parent, root);
                    break;
                }
            } else {
                rb_tree_node_base* w = x_parent->left_;
                NEFORCE_DEBUG_VERIFY(w != nullptr, "RB-tree structure corrupted: left sibling is null");
                if (w == nullptr) {
                    x = x_parent;
                    x_parent = x_parent->parent_;
                    continue;
                }
 
                if (w->color_ == RB_TREE_RED) {
                    w->color_ = RB_TREE_BLACK;
                    x_parent->color_ = RB_TREE_RED;
                    _NEFORCE rb_tree_rotate_right(x_parent, root);
                    w = x_parent->left_;
                }
 
                if ((w->right_ == nullptr || w->right_->color_ == RB_TREE_BLACK) &&
                    (w->left_ == nullptr || w->left_->color_ == RB_TREE_BLACK)) {
                    w->color_ = RB_TREE_RED;
                    x = x_parent;
                    x_parent = x_parent->parent_;
                } else {
                    if (w->left_ == nullptr || w->left_->color_ == RB_TREE_BLACK) {
                        if (w->right_ != nullptr) {
                            w->right_->color_ = RB_TREE_BLACK;
                        }
 
                        w->color_ = RB_TREE_RED;
                        _NEFORCE rb_tree_rotate_left(w, root);
                        w = x_parent->left_;
                    }
                    w->color_ = x_parent->color_;
                    x_parent->color_ = RB_TREE_BLACK;
                    if (w->left_ != nullptr) {
                        w->left_->color_ = RB_TREE_BLACK;
                    }
 
                    _NEFORCE rb_tree_rotate_right(x_parent, root);
                    break;
                }
            }
        }
 
        if (x != nullptr) {
            x->color_ = RB_TREE_BLACK;
        }
    }
    return y;
}
 

template <typename T>
struct rb_tree_node : rb_tree_node_base {
    T data; 

    rb_tree_node() noexcept(is_nothrow_default_constructible_v<T>) :
    data() {}
};
 

struct rb_tree_base_iterator {
public:
    using iterator_category = bidirectional_iterator_tag; 
 
protected:
    using base_ptr = rb_tree_node_base::base_ptr; 
 
    base_ptr node_ = nullptr; 

    void increment() noexcept {
        if (node_->right_ != nullptr) {
            node_ = node_->right_;
            while (node_->left_ != nullptr) {
                node_ = node_->left_;
            }
        } else {
            base_ptr y = node_->parent_;
            while (node_ == y->right_) {
                node_ = y;
                y = y->parent_;
            }
            if (node_->right_ != y) {
                node_ = y;
            }
        }
    }

    void decrement() noexcept {
        if (node_->color_ == RB_TREE_RED && node_->parent_ != nullptr && node_->parent_->parent_ == node_) {
            node_ = node_->right_;
        } else if (node_->left_ != nullptr) {
            base_ptr y = node_->left_;
            while (y->right_ != nullptr) {
                y = y->right_;
            }
            node_ = y;
        } else {
            base_ptr y = node_->parent_;
            if (y == nullptr) {
                return;
            }
            while (node_ == y->left_) {
                node_ = y;
                y = y->parent_;
            }
            node_ = y;
        }
    }
};
 

template <bool IsConst, typename RbTree>
struct rb_tree_iterator : rb_tree_base_iterator, iiterator<rb_tree_iterator<IsConst, RbTree>> {
public:
    using container_type = RbTree;                                      
    using value_type = typename container_type::value_type;             
    using size_type = typename container_type::size_type;               
    using difference_type = typename container_type::difference_type;   
    using iterator_category = rb_tree_base_iterator::iterator_category; 
    using reference = conditional_t<IsConst, typename container_type::const_reference,
                                    typename container_type::reference>; 
    using pointer = conditional_t<IsConst, typename container_type::const_pointer,
                                  typename container_type::pointer>; 
 
private:
    using base_type = rb_tree_base_iterator;    
    using node_type = rb_tree_node<value_type>; 
    using link_type = node_type*;               
 
    const container_type* container_ = nullptr; 
 
    template <typename, typename, typename, typename, typename>
    friend class rb_tree;
 
public:
    rb_tree_iterator() noexcept = default;
    ~rb_tree_iterator() = default;
 
    rb_tree_iterator(const rb_tree_iterator&) noexcept = default;
    rb_tree_iterator& operator=(const rb_tree_iterator&) noexcept = default;
    rb_tree_iterator(rb_tree_iterator&&) noexcept = default;
    rb_tree_iterator& operator=(rb_tree_iterator&&) noexcept = default;

    rb_tree_iterator(node_type* ptr, const container_type* tree) noexcept :
    container_(tree) {
        node_ = ptr;
    }

    NEFORCE_NODISCARD reference dereference() const noexcept {
        NEFORCE_DEBUG_VERIFY(node_ && container_, "Attempting to dereference on a null pointer");
        link_type link = link_type(node_);
        NEFORCE_DEBUG_VERIFY(node_ != container_->header_ && node_->parent_ != nullptr,
                             "Attempting to dereference out of boundary");
        return link->data;
    }

    NEFORCE_CONSTEXPR20 void increment() noexcept {
        NEFORCE_DEBUG_VERIFY(node_ && container_, "Attempting to increment a null pointer");
        NEFORCE_DEBUG_VERIFY(link_type(node_) != container_->header_, "Attempting to increment out of boundary");
        base_type::increment();
    }

    NEFORCE_CONSTEXPR20 void decrement() noexcept {
        NEFORCE_DEBUG_VERIFY(node_ && container_, "Attempting to decrement a null pointer");
        NEFORCE_DEBUG_VERIFY(!container_->empty() || node_ != container_->header_,
                             "Attempting to decrement on empty container");
        base_type::decrement();
    }

    NEFORCE_NODISCARD bool equal_to(const rb_tree_iterator& rhs) const noexcept {
        NEFORCE_DEBUG_VERIFY(container_ == rhs.container_, "Attempting to equal to a different container");
        return node_ == rhs.node_;
    }

    NEFORCE_NODISCARD pointer base() const noexcept { return node_; }

    NEFORCE_NODISCARD const container_type* container() const noexcept { return container_; }
};
 

template <typename Key, typename Value, typename KeyOfValue, typename Compare,
          typename Alloc = allocator<rb_tree_node<Value>>>
class rb_tree : icollector<rb_tree<Key, Value, KeyOfValue, Compare, Alloc>> {
    static_assert(is_allocator_v<Alloc>, "Alloc type is not a standard allocator type.");
    static_assert(is_same_v<rb_tree_node<Value>, typename Alloc::value_type>, "allocator type mismatch.");
    static_assert(is_object_v<Value>, "list only contains object types.");
 
public:
    using key_type = Key;    
    using color_type = bool; 
 
    using value_type = Value;                                                 
    using pointer = Value*;                                                   
    using reference = Value&;                                                 
    using const_pointer = const Value*;                                       
    using const_reference = const Value&;                                     
    using size_type = size_t;                                                 
    using difference_type = ptrdiff_t;                                        
    using iterator = rb_tree_iterator<false, rb_tree>;                        
    using const_iterator = rb_tree_iterator<true, rb_tree>;                   
    using reverse_iterator = _NEFORCE reverse_iterator<iterator>;             
    using const_reverse_iterator = _NEFORCE reverse_iterator<const_iterator>; 
    using allocator_type = Alloc;                                             
 
private:
    using base_node = rb_tree_node_base;   
    using link_node = rb_tree_node<Value>; 
    using base_ptr = base_node*;           
    using link_type = link_node*;          
 
    link_type header_ = nullptr;                                                    
    Compare key_compare_{};                                                         
    KeyOfValue extracter_{};                                                        
    compressed_pair<allocator_type, size_t> size_pair_{default_construct_tag{}, 0}; 
 
    template <bool, typename>
    friend struct rb_tree_iterator;
 
private:
    struct node_guard {
    private:
        rb_tree* tree_;
        link_type node_;
        bool released_ = false;
 
    public:
        node_guard(rb_tree* t, link_type n) noexcept :
        tree_(t),
        node_(n) {}
 
        ~node_guard() {
            if (!released_) {
                tree_->destroy_node(node_);
            }
        }
 
        link_type release() noexcept {
            released_ = true;
            return node_;
        }
    };

    link_type& root() const noexcept { return reinterpret_cast<link_type&>(header_->parent_); }

    link_type& leftmost() const noexcept { return reinterpret_cast<link_type&>(header_->left_); }

    link_type& rightmost() const noexcept { return reinterpret_cast<link_type&>(header_->right_); }

    static link_type& left(link_type ptr) noexcept { return reinterpret_cast<link_type&>(ptr->left_); }

    static link_type& right(link_type ptr) noexcept { return reinterpret_cast<link_type&>(ptr->right_); }

    static link_type& parent(link_type ptr) noexcept { return reinterpret_cast<link_type&>(ptr->parent_); }

    static const Key& key(link_type ptr) noexcept { return KeyOfValue()(ptr->data); }

    static const Key& key(base_ptr ptr) noexcept { return rb_tree::key(reinterpret_cast<link_type>(ptr)); }

    static link_type minimum(link_type ptr) noexcept { return static_cast<link_type>(base_node::minimum(ptr)); }

    static link_type maximum(link_type ptr) noexcept { return static_cast<link_type>(base_node::maximum(ptr)); }

    template <typename... Args>
    link_type create_node(Args&&... args) {
        link_type tmp = size_pair_.get_base().allocate();
        try {
            _NEFORCE construct(&tmp->data, _NEFORCE forward<Args>(args)...);
        } catch (...) {
            rb_tree::destroy_node(tmp);
            throw;
        }
        return tmp;
    }

    link_type copy_node(link_type ptr) {
        link_type tmp = rb_tree::create_node(ptr->data);
        tmp->color_ = ptr->color_;
        tmp->left_ = nullptr;
        tmp->right_ = nullptr;
        return tmp;
    }

    void destroy_node(link_type ptr) noexcept(is_nothrow_destructible_v<link_node>) {
        if (ptr == nullptr) {
            return;
        }
        _NEFORCE destroy(&ptr->data);
        size_pair_.get_base().deallocate(ptr);
    }

    iterator insert_into(base_ptr child, base_ptr parent, link_type ptr) {
        auto x = static_cast<link_type>(child);
        auto y = static_cast<link_type>(parent);
        if (y == header_ || x != nullptr || key_compare_(rb_tree::key(ptr), rb_tree::key(y))) {
            rb_tree::left(y) = ptr;
            if (y == header_) {
                root() = ptr;
                leftmost() = ptr;
                rightmost() = ptr;
            } else if (y == leftmost()) {
                leftmost() = ptr;
            }
        } else {
            rb_tree::right(y) = ptr;
            if (y == rightmost()) {
                rightmost() = ptr;
            }
        }
        rb_tree::parent(ptr) = y;
        rb_tree::left(ptr) = nullptr;
        rb_tree::right(ptr) = nullptr;
        _NEFORCE rb_tree_insert_rebalance(ptr, header_->parent_);
        ++size_pair_.value;
        return iterator(ptr, this);
    }

    link_type copy_under(link_type src_root, link_type parent) {
        link_type top = rb_tree::copy_node(src_root);
        top->parent_ = parent;
        try {
            if (src_root->right_ != nullptr) {
                top->right_ = rb_tree::copy_under(rb_tree::right(src_root), top);
            }
            parent = top;
            src_root = rb_tree::left(src_root);
            while (src_root != nullptr) {
                link_type y = rb_tree::copy_node(src_root);
                parent->left_ = y;
                y->parent_ = parent;
                if (src_root->right_ != nullptr) {
                    y->right_ = rb_tree::copy_under(rb_tree::right(src_root), y);
                }
                parent = y;
                src_root = rb_tree::left(src_root);
            }
        } catch (...) {
            rb_tree::erase_under(top);
            throw;
        }
        return top;
    }

    void erase_under(link_type root) noexcept(is_nothrow_destructible_v<link_node>) {
        if (root == nullptr) {
            return;
        }
        rb_tree::erase_under(rb_tree::right(root));
        rb_tree::erase_under(rb_tree::left(root));
        rb_tree::destroy_node(root);
    }

    void header_init() {
        header_ = size_pair_.get_base().allocate(1);
        header_->color_ = RB_TREE_RED;
        root() = nullptr;
        leftmost() = header_;
        rightmost() = header_;
    }

    void copy_from(const rb_tree& other) {
        if (other.root() == nullptr) {
            root() = nullptr;
            leftmost() = header_;
            rightmost() = header_;
        } else {
            try {
                root() = rb_tree::copy_under(other.root(), header_);
            } catch (...) {
                size_pair_.get_base().deallocate(header_);
                header_ = nullptr;
                throw;
            }
            leftmost() = rb_tree::minimum(root());
            rightmost() = rb_tree::maximum(root());
        }
        size_pair_.value = other.size_pair_.value;
    }

    pair<iterator, bool> insert_unique(link_type node) {
        link_type y = header_;
        link_type x = root();
        bool comp = true;
        while (x != nullptr) {
            y = x;
            comp = key_compare_(rb_tree::key(node), rb_tree::key(x));
            x = comp ? rb_tree::left(x) : rb_tree::right(x);
        }
 
        iterator j(y, this);
        if (comp) {
            if (j == begin()) {
                return pair<iterator, bool>(rb_tree::insert_into(x, y, node), true);
            }
            --j;
        }
 
        if (key_compare_(rb_tree::key(link_type(j.node_)), rb_tree::key(node))) {
            return pair<iterator, bool>(rb_tree::insert_into(x, y, node), true);
        }
        rb_tree::destroy_node(node);
        return pair<iterator, bool>(j, false);
    }

    iterator insert_equal(link_type node) {
        link_type y = header_;
        link_type x = root();
        while (x != nullptr) {
            y = x;
            x = key_compare_(rb_tree::key(node), rb_tree::key(x)) ? rb_tree::left(x) : rb_tree::right(x);
        }
        return rb_tree::insert_into(x, y, node);
    }
 
public:
    rb_tree() { header_init(); }

    explicit rb_tree(const Compare& comp) :
    key_compare_(comp) {
        header_init();
    }

    rb_tree(const rb_tree& other) :
    key_compare_(other.key_compare_),
    extracter_(other.extracter_),
    size_pair_(other.size_pair_) {
        header_init();
        rb_tree::copy_from(other);
    }

    rb_tree& operator=(const rb_tree& other) {
        if (_NEFORCE addressof(other) == this) {
            return *this;
        }
        rb_tree tmp(other);
        rb_tree::swap(tmp);
        return *this;
    }

    rb_tree(rb_tree&& other) noexcept(is_nothrow_move_constructible_v<Compare> &&
                                      is_nothrow_move_constructible_v<KeyOfValue> &&
                                      is_nothrow_move_constructible_v<allocator_type>) :
    header_(_NEFORCE move(other.header_)),
    key_compare_(_NEFORCE move(other.key_compare_)),
    extracter_(_NEFORCE move(other.extracter_)),
    size_pair_(_NEFORCE move(other.size_pair_)) {
        other.header_ = nullptr;
        other.size_pair_.value = 0;
    }

    rb_tree& operator=(rb_tree&& other) noexcept(is_nothrow_move_constructible_v<rb_tree>) {
        if (_NEFORCE addressof(other) == this) {
            return *this;
        }
        rb_tree tmp(_NEFORCE move(other));
        rb_tree::swap(tmp);
        return *this;
    }

    ~rb_tree() {
        clear();
        if (header_) {
            size_pair_.get_base().deallocate(header_);
        }
    }

    NEFORCE_NODISCARD iterator begin() noexcept { return {leftmost(), this}; }

    NEFORCE_NODISCARD iterator end() noexcept { return {header_, this}; }

    NEFORCE_NODISCARD const_iterator begin() const noexcept { return cbegin(); }

    NEFORCE_NODISCARD const_iterator end() const noexcept { return cend(); }

    NEFORCE_NODISCARD const_iterator cbegin() const noexcept { return {leftmost(), this}; }

    NEFORCE_NODISCARD const_iterator cend() const noexcept { return {header_, this}; }

    NEFORCE_NODISCARD reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }

    NEFORCE_NODISCARD reverse_iterator rend() noexcept { return reverse_iterator(begin()); }

    NEFORCE_NODISCARD const_reverse_iterator rbegin() const noexcept { return crbegin(); }

    NEFORCE_NODISCARD const_reverse_iterator rend() const noexcept { return crend(); }

    NEFORCE_NODISCARD const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(cend()); }

    NEFORCE_NODISCARD const_reverse_iterator crend() const noexcept { return const_reverse_iterator(cbegin()); }

    NEFORCE_NODISCARD size_type size() const noexcept { return size_pair_.value; }

    NEFORCE_NODISCARD size_type max_size() const noexcept { return static_cast<size_type>(-1); }

    NEFORCE_NODISCARD bool empty() const noexcept { return size_pair_.value == 0; }

    NEFORCE_NODISCARD Compare key_compare() const noexcept(is_nothrow_copy_constructible_v<Compare>) {
        return key_compare_;
    }

    template <typename... Args>
    pair<iterator, bool> emplace_unique(Args&&... args) {
        const link_type tmp = rb_tree::create_node(_NEFORCE forward<Args>(args)...);
        return rb_tree::insert_unique(tmp);
    }

    pair<iterator, bool> insert_unique(const value_type& value) { return rb_tree::emplace_unique(value); }

    pair<iterator, bool> insert_unique(value_type&& value) { return rb_tree::emplace_unique(_NEFORCE move(value)); }

    template <typename... Args>
    iterator emplace_unique_hint(iterator position, Args&&... args) {
        link_type tmp = rb_tree::create_node(_NEFORCE forward<Args>(args)...);
        node_guard guard(this, tmp);
 
        if (position.node_ == header_->left_) {
            if (size() > 0 && key_compare_(rb_tree::key(tmp), rb_tree::key(position.node_))) {
                guard.release();
                return rb_tree::insert_into(position.node_, position.node_, tmp);
            }
            guard.release();
            return rb_tree::insert_unique(tmp).first;
        }
 
        if (position.node_ == header_) {
            if (key_compare_(rb_tree::key(rightmost()), rb_tree::key(tmp))) {
                guard.release();
                return rb_tree::insert_into(nullptr, rightmost(), tmp);
            }
            guard.release();
            return rb_tree::insert_unique(tmp).first;
        }
 
        iterator before = position;
        --before;
 
        if (key_compare_(rb_tree::key(before.node_), rb_tree::key(tmp)) &&
            key_compare_(rb_tree::key(tmp), rb_tree::key(position.node_))) {
            if (rb_tree::right(link_type(before.node_)) == nullptr) {
                guard.release();
                return rb_tree::insert_into(nullptr, before.node_, tmp);
            }
            if (rb_tree::left(link_type(position.node_)) == nullptr) {
                guard.release();
                return rb_tree::insert_into(position.node_, position.node_, tmp);
            }
        }
 
        guard.release();
        return rb_tree::insert_unique(tmp).first;
    }

    iterator insert_unique(iterator position, const value_type& value) {
        return rb_tree::emplace_unique_hint(position, value);
    }

    iterator insert_unique(iterator position, value_type&& value) {
        return rb_tree::emplace_unique_hint(position, _NEFORCE move(value));
    }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    void insert_unique(Iterator first, Iterator last) {
        for (; first != last; ++first) {
            rb_tree::insert_unique(*first);
        }
    }

    template <typename... Args>
    iterator emplace_equal(Args&&... args) {
        const link_type tmp = rb_tree::create_node(_NEFORCE forward<Args>(args)...);
        return rb_tree::insert_equal(tmp);
    }

    iterator insert_equal(const value_type& value) { return rb_tree::emplace_equal(value); }

    iterator insert_equal(value_type&& value) { return rb_tree::emplace_equal(_NEFORCE move(value)); }

    template <typename... Args>
    iterator emplace_equal_hint(iterator position, Args&&... args) {
        link_type tmp = rb_tree::create_node(_NEFORCE forward<Args>(args)...);
        node_guard guard(this, tmp);
 
        if (position.node_ == header_->left_) {
            if (size() > 0 && key_compare_(rb_tree::key(tmp), rb_tree::key(position.node_))) {
                guard.release();
                return rb_tree::insert_into(position.node_, position.node_, tmp);
            }
            guard.release();
            return rb_tree::insert_equal(tmp);
        }
 
        if (position.node_ == header_) {
            if (!key_compare_(rb_tree::key(tmp), rb_tree::key(rightmost()))) {
                guard.release();
                return rb_tree::insert_into(nullptr, rightmost(), tmp);
            }
            guard.release();
            return rb_tree::insert_equal(tmp);
        }
 
        iterator before = position;
        --before;
 
        if (!key_compare_(rb_tree::key(tmp), rb_tree::key(before.node_)) &&
            !key_compare_(rb_tree::key(position.node_), rb_tree::key(tmp))) {
            if (rb_tree::right(link_type(before.node_)) == nullptr) {
                guard.release();
                return rb_tree::insert_into(nullptr, before.node_, tmp);
            }
            guard.release();
            return rb_tree::insert_into(position.node_, position.node_, tmp);
        }
 
        guard.release();
        return rb_tree::insert_equal(tmp);
    }

    iterator insert_equal(iterator position, const value_type& value) {
        return rb_tree::emplace_equal_hint(position, value);
    }

    iterator insert_equal(iterator position, value_type&& value) {
        return rb_tree::emplace_equal_hint(position, _NEFORCE move(value));
    }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    void insert_equal(Iterator first, Iterator last) {
        for (; first != last; ++first) {
            rb_tree::insert_equal(*first);
        }
    }

    size_type erase(const key_type& key) noexcept(is_nothrow_destructible_v<link_node>) {
        pair<iterator, iterator> p = rb_tree::equal_range(key);
        const size_type n = _NEFORCE distance(p.first, p.second);
        rb_tree::erase(p.first, p.second);
        return n;
    }

    void erase(iterator position) noexcept(is_nothrow_destructible_v<link_node>) {
        auto y = reinterpret_cast<link_type>(
                _NEFORCE rb_tree_erase_rebalance(position.node_, header_->parent_, header_->left_, header_->right_));
        rb_tree::destroy_node(y);
        --size_pair_.value;
    }

    void erase(iterator first, iterator last) noexcept(is_nothrow_destructible_v<link_node>) {
        if (first == begin() && last == end()) {
            clear();
        } else {
            while (first != last) {
                rb_tree::erase(first++);
            }
        }
    }

    void clear() noexcept(is_nothrow_destructible_v<link_node>) {
        if (header_ == nullptr) {
            return;
        }
        if (size_pair_.value == 0) {
            return;
        }
        rb_tree::erase_under(root());
        leftmost() = header_;
        root() = nullptr;
        rightmost() = header_;
        size_pair_.value = 0;
    }

    NEFORCE_NODISCARD iterator find(const key_type& key) {
        link_type y = header_;
        link_type x = root();
 
        while (x != nullptr) {
            if (!key_compare_(rb_tree::key(x), key)) {
                y = x;
                x = rb_tree::left(x);
            } else {
                x = rb_tree::right(x);
            }
        }
 
        iterator j(y, this);
        if (j == end()) {
            return end();
        }
        return key_compare_(key, rb_tree::key(y)) ? end() : j;
    }

    NEFORCE_NODISCARD const_iterator find(const key_type& key) const {
        link_type y = header_;
        link_type x = root();
 
        while (x != nullptr) {
            if (!key_compare_(rb_tree::key(x), key)) {
                y = x;
                x = rb_tree::left(x);
            } else {
                x = rb_tree::right(x);
            }
        }
 
        const_iterator j(y, this);
        if (j == cend()) {
            return cend();
        }
        return key_compare_(key, rb_tree::key(y)) ? cend() : j;
    }

    NEFORCE_NODISCARD size_type count(const key_type& key) const {
        pair<const_iterator, const_iterator> p = rb_tree::equal_range(key);
        const size_type n = _NEFORCE distance(p.first, p.second);
        return n;
    }

    NEFORCE_NODISCARD iterator lower_bound(const key_type& key) {
        link_type y = header_;
        link_type x = root();
 
        while (x != nullptr) {
            if (!key_compare_(rb_tree::key(x), key)) {
                y = x;
                x = rb_tree::left(x);
            } else {
                x = rb_tree::right(x);
            }
        }
 
        return iterator(y, this);
    }

    NEFORCE_NODISCARD const_iterator lower_bound(const key_type& key) const {
        link_type y = header_;
        link_type x = root();
 
        while (x != nullptr) {
            if (!key_compare_(rb_tree::key(x), key)) {
                y = x;
                x = rb_tree::left(x);
            } else {
                x = rb_tree::right(x);
            }
        }
 
        return const_iterator(y, this);
    }

    NEFORCE_NODISCARD iterator upper_bound(const key_type& key) {
        link_type y = header_;
        link_type x = root();
 
        while (x != nullptr) {
            if (key_compare_(key, rb_tree::key(x))) {
                y = x;
                x = rb_tree::left(x);
            } else {
                x = rb_tree::right(x);
            }
        }
 
        return iterator(y, this);
    }

    NEFORCE_NODISCARD const_iterator upper_bound(const key_type& key) const {
        link_type y = header_;
        link_type x = root();
 
        while (x != nullptr) {
            if (key_compare_(key, rb_tree::key(x))) {
                y = x;
                x = rb_tree::left(x);
            } else {
                x = rb_tree::right(x);
            }
        }
 
        return const_iterator(y, this);
    }

    NEFORCE_NODISCARD pair<iterator, iterator> equal_range(const key_type& key) {
        return pair<iterator, iterator>(rb_tree::lower_bound(key), rb_tree::upper_bound(key));
    }

    NEFORCE_NODISCARD pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
        return pair<const_iterator, const_iterator>(rb_tree::lower_bound(key), rb_tree::upper_bound(key));
    }

    void swap(rb_tree& other) noexcept(is_nothrow_swappable_v<Compare> && is_nothrow_swappable_v<KeyOfValue> &&
                                       is_nothrow_swappable_v<allocator_type>) {
        _NEFORCE swap(header_, other.header_);
        _NEFORCE swap(size_pair_, other.size_pair_);
        _NEFORCE swap(key_compare_, other.key_compare_);
        _NEFORCE swap(extracter_, other.extracter_);
    }

    NEFORCE_NODISCARD bool equal_to(const rb_tree& rhs) const
            noexcept(noexcept(_NEFORCE equal(cbegin(), cend(), rhs.cbegin()))) {
        return size() == rhs.size() && _NEFORCE equal(cbegin(), cend(), rhs.cbegin());
    }

    NEFORCE_NODISCARD bool less_than(const rb_tree& rhs) const
            noexcept(noexcept(_NEFORCE lexicographical_compare(cbegin(), cend(), rhs.cbegin(), rhs.cend()))) {
        return _NEFORCE lexicographical_compare(cbegin(), cend(), rhs.cbegin(), rhs.cend());
    }
};
 // RBTree
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_CONTAINER_RB_TREE_HPP__