path: root/library/cpp/containers/intrusive_rb_tree/rb_tree.h

#pragma once

#include <util/generic/utility.h>
#include <util/generic/yexception.h>

using TRbTreeColorType = bool;

#define RBTreeRed false
#define RBTreeBlack true

struct TRbTreeNodeBase {
    using TColorType = TRbTreeColorType;
    using TBasePtr = TRbTreeNodeBase*;

    TColorType Color_;
    TBasePtr Parent_;
    TBasePtr Left_;
    TBasePtr Right_;
    size_t Children_;

    inline TRbTreeNodeBase() noexcept { 
        ReInitNode();
    }

    inline void ReInitNode() noexcept { 
        Color_ = RBTreeBlack;
        Parent_ = nullptr;
        Left_ = nullptr;
        Right_ = nullptr;
        Children_ = 1;
    }

    static TBasePtr MinimumNode(TBasePtr x) {
        while (x->Left_ != nullptr)
            x = x->Left_;

        return x;
    }

    static TBasePtr MaximumNode(TBasePtr x) {
        while (x->Right_ != nullptr)
            x = x->Right_;

        return x;
    }

    static TBasePtr ByIndex(TBasePtr x, size_t index) {
        if (x->Left_ != nullptr) {
            if (index < x->Left_->Children_)
                return ByIndex(x->Left_, index);
            index -= x->Left_->Children_;
        }
        if (0 == index)
            return x;
        if (!x->Right_)
            ythrow yexception() << "index not found";
        return ByIndex(x->Right_, index - 1);
    }
};

struct TRbTreeBaseIterator;

template <class TDummy>
class TRbGlobal {
public:
    using TBasePtr = TRbTreeNodeBase*;

    static void Rebalance(TBasePtr x, TBasePtr& root);
    static TBasePtr RebalanceForErase(TBasePtr z, TBasePtr& root, TBasePtr& leftmost, TBasePtr& rightmost);
    static void DecrementChildrenUntilRoot(TBasePtr x, TBasePtr root);
    static void RecalcChildren(TBasePtr x);

    static TBasePtr IncrementNode(TBasePtr);
    static TBasePtr DecrementNode(TBasePtr);
    static void RotateLeft(TBasePtr x, TBasePtr& root);
    static void RotateRight(TBasePtr x, TBasePtr& root);
};

using TRbGlobalInst = TRbGlobal<bool>;

struct TRbTreeBaseIterator {
    using TBasePtr = TRbTreeNodeBase*;
    TBasePtr Node_;

    inline TRbTreeBaseIterator(TBasePtr x = nullptr) noexcept 
        : Node_(x)
    {
    }
};

template <class TValue, class TTraits>
struct TRbTreeIterator: public TRbTreeBaseIterator {
    using TReference = typename TTraits::TReference;
    using TPointer = typename TTraits::TPointer;
    using TSelf = TRbTreeIterator<TValue, TTraits>;
    using TBasePtr = TRbTreeNodeBase*;

    inline TRbTreeIterator() noexcept = default;

    template <class T1>
    inline TRbTreeIterator(const T1& x) noexcept 
        : TRbTreeBaseIterator(x)
    {
    }

    inline TReference operator*() const noexcept { 
        return *static_cast<TValue*>(Node_);
    }

    inline TPointer operator->() const noexcept { 
        return static_cast<TValue*>(Node_);
    }

    inline TSelf& operator++() noexcept { 
        Node_ = TRbGlobalInst::IncrementNode(Node_);
        return *this;
    }

    inline TSelf operator++(int) noexcept { 
        TSelf tmp = *this;
        ++(*this);
        return tmp;
    }

    inline TSelf& operator--() noexcept { 
        Node_ = TRbGlobalInst::DecrementNode(Node_);
        return *this;
    }

    inline TSelf operator--(int) noexcept { 
        TSelf tmp = *this;
        --(*this);
        return tmp;
    }

    template <class T1>
    inline bool operator==(const T1& rhs) const noexcept { 
        return Node_ == rhs.Node_;
    }

    template <class T1>
    inline bool operator!=(const T1& rhs) const noexcept { 
        return Node_ != rhs.Node_;
    }
};

template <class TValue, class TCmp>
class TRbTree {
    struct TCmpAdaptor: public TCmp {
        inline TCmpAdaptor() noexcept = default;

        inline TCmpAdaptor(const TCmp& cmp) noexcept 
            : TCmp(cmp)
        {
        }

        template <class T1, class T2>
        inline bool operator()(const T1& l, const T2& r) const {
            return TCmp::Compare(l, r);
        }
    };

    struct TNonConstTraits {
        using TReference = TValue&;
        using TPointer = TValue*;
    };

    struct TConstTraits {
        using TReference = const TValue&;
        using TPointer = const TValue*;
    };

    using TNodeBase = TRbTreeNodeBase;
    using TBasePtr = TRbTreeNodeBase*;
    using TColorType = TRbTreeColorType;

public:
    class TRealNode: public TNodeBase {
    public:
        inline TRealNode()
            : Tree_(nullptr)
        {
        }

        inline ~TRealNode() { 
            UnLink();
        }

        inline void UnLink() noexcept { 
            if (Tree_) {
                Tree_->EraseImpl(this);
                ReInitNode();
                Tree_ = nullptr;
            }
        }

        inline void SetRbTreeParent(TRbTree* parent) noexcept { 
            Tree_ = parent;
        }

        inline TRbTree* ParentTree() const noexcept { 
            return Tree_;
        }

    private:
        TRbTree* Tree_;
    };

    using TIterator = TRbTreeIterator<TValue, TNonConstTraits>;
    using TConstIterator = TRbTreeIterator<TValue, TConstTraits>;

    inline TRbTree() noexcept { 
        Init();
    }

    inline TRbTree(const TCmp& cmp) noexcept 
        : KeyCompare_(cmp)
    {
        Init();
    }

    inline void Init() noexcept { 
        Data_.Color_ = RBTreeRed;
        Data_.Parent_ = nullptr;
        Data_.Left_ = &Data_;
        Data_.Right_ = &Data_;
        Data_.Children_ = 0;
    }

    struct TDestroy {
        inline void operator()(TValue& v) const noexcept { 
            v.SetRbTreeParent(nullptr);
            v.ReInitNode();
        }
    };

    inline ~TRbTree() { 
        ForEachNoOrder(TDestroy());
    }

    inline void Clear() noexcept { 
        ForEachNoOrder(TDestroy());
        Init();
    }

    template <class F>
    inline void ForEachNoOrder(const F& f) {
        ForEachNoOrder(Root(), f);
    }

    template <class F>
    inline void ForEachNoOrder(TNodeBase* n, const F& f) {
        if (n && n != &Data_) {
            ForEachNoOrder(n->Left_, f);
            ForEachNoOrder(n->Right_, f);
            f(ValueNode(n));
        }
    }

    inline TIterator Begin() noexcept { 
        return LeftMost();
    }

    inline TConstIterator Begin() const noexcept { 
        return LeftMost();
    }

    inline TIterator End() noexcept { 
        return &this->Data_;
    }

    inline TConstIterator End() const noexcept { 
        return const_cast<TBasePtr>(&this->Data_);
    }

    inline bool Empty() const noexcept { 
        return this->Begin() == this->End();
    }

    inline explicit operator bool() const noexcept { 
        return !this->Empty();
    }

    inline TIterator Insert(TValue* val) {
        return Insert(*val);
    }

    inline TIterator Insert(TValue& val) {
        val.UnLink();

        TBasePtr y = &this->Data_;
        TBasePtr x = Root();

        while (x != nullptr) {
            ++(x->Children_);
            y = x;

            if (KeyCompare_(ValueNode(&val), ValueNode(x))) {
                x = LeftNode(x);
            } else {
                x = RightNode(x);
            }
        }

        return InsertImpl(y, &val, x);
    }

    template <class F>
    inline void ForEach(F& f) {
        TIterator it = Begin();

        while (it != End()) {
            f(*it++);
        }
    }

    inline void Erase(TValue& val) noexcept { 
        val.UnLink();
    }

    inline void Erase(TValue* val) noexcept { 
        Erase(*val);
    }

    inline void Erase(TIterator pos) noexcept { 
        Erase(*pos);
    }

    inline void EraseImpl(TNodeBase* val) noexcept { 
        TRbGlobalInst::RebalanceForErase(val, this->Data_.Parent_, this->Data_.Left_, this->Data_.Right_);
    }

    template <class T1>
    inline TValue* Find(const T1& k) const {
        TBasePtr y = nullptr;
        TBasePtr x = Root(); // Current node.

        while (x != nullptr)
            if (!KeyCompare_(ValueNode(x), k))
                y = x, x = LeftNode(x);
            else
                x = RightNode(x);

        if (y) {
            if (KeyCompare_(k, ValueNode(y))) {
                y = nullptr;
            }
        }

        return static_cast<TValue*>(y);
    }

    size_t GetIndex(TBasePtr x) const {
        size_t index = 0;

        if (x->Left_ != nullptr) {
            index += x->Left_->Children_;
        }

        while (x != nullptr && x->Parent_ != nullptr && x->Parent_ != const_cast<TBasePtr>(&this->Data_)) {
            if (x->Parent_->Right_ == x && x->Parent_->Left_ != nullptr) {
                index += x->Parent_->Left_->Children_;
            }
            if (x->Parent_->Right_ == x) {
                index += 1;
            }
            x = x->Parent_;
        }

        return index;
    }

    template <class T1>
    inline TBasePtr LowerBound(const T1& k) const {
        TBasePtr y = const_cast<TBasePtr>(&this->Data_); /* Last node which is not less than k. */
        TBasePtr x = Root();                             /* Current node. */

        while (x != nullptr)
            if (!KeyCompare_(ValueNode(x), k))
                y = x, x = LeftNode(x);
            else
                x = RightNode(x);

        return y;
    }

    template <class T1>
    inline TBasePtr UpperBound(const T1& k) const {
        TBasePtr y = const_cast<TBasePtr>(&this->Data_); /* Last node which is greater than k. */
        TBasePtr x = Root();                             /* Current node. */

        while (x != nullptr)
            if (KeyCompare_(k, ValueNode(x)))
                y = x, x = LeftNode(x);
            else
                x = RightNode(x);

        return y;
    }

    template <class T1>
    inline size_t LessCount(const T1& k) const {
        auto x = LowerBound(k);
        if (x == const_cast<TBasePtr>(&this->Data_)) {
            if (const auto root = Root()) {
                return root->Children_;
            } else {
                return 0;
            }
        } else {
            return GetIndex(x);
        }
    }

    template <class T1>
    inline size_t NotLessCount(const T1& k) const {
        return Root()->Children_ - LessCount<T1>(k);
    }

    template <class T1>
    inline size_t GreaterCount(const T1& k) const {
        auto x = UpperBound(k);
        if (x == const_cast<TBasePtr>(&this->Data_)) {
            return 0;
        } else {
            return Root()->Children_ - GetIndex(x);
        }
    }

    template <class T1>
    inline size_t NotGreaterCount(const T1& k) const {
        return Root()->Children_ - GreaterCount<T1>(k);
    }

    TValue* ByIndex(size_t index) {
        return static_cast<TValue*>(TRbTreeNodeBase::ByIndex(Root(), index));
    }

private:
    // CRP 7/10/00 inserted argument on_right, which is another hint (meant to
    // act like on_left and ignore a portion of the if conditions -- specify
    // on_right != nullptr to bypass comparison as false or on_left != nullptr to bypass
    // comparison as true)
    TIterator InsertImpl(TRbTreeNodeBase* parent, TRbTreeNodeBase* val, TRbTreeNodeBase* on_left = nullptr, TRbTreeNodeBase* on_right = nullptr) {
        ValueNode(val).SetRbTreeParent(this);
        TBasePtr new_node = val;

        if (parent == &this->Data_) {
            LeftNode(parent) = new_node;
            // also makes LeftMost() = new_node
            Root() = new_node;
            RightMost() = new_node;
        } else if (on_right == nullptr &&
                   // If on_right != nullptr, the remainder fails to false
                   (on_left != nullptr ||
                    // If on_left != nullptr, the remainder succeeds to true
                    KeyCompare_(ValueNode(val), ValueNode(parent))))
 {
            LeftNode(parent) = new_node;
            if (parent == LeftMost())
                // maintain LeftMost() pointing to min node
                LeftMost() = new_node;
        } else {
            RightNode(parent) = new_node;
            if (parent == RightMost())
                // maintain RightMost() pointing to max node
                RightMost() = new_node;
        }
        ParentNode(new_node) = parent;
        TRbGlobalInst::Rebalance(new_node, this->Data_.Parent_);
        return new_node;
    }

    TBasePtr Root() const {
        return this->Data_.Parent_;
    }

    TBasePtr LeftMost() const {
        return this->Data_.Left_;
    }

    TBasePtr RightMost() const {
        return this->Data_.Right_;
    }

    TBasePtr& Root() {
        return this->Data_.Parent_;
    }

    TBasePtr& LeftMost() {
        return this->Data_.Left_;
    }

    TBasePtr& RightMost() {
        return this->Data_.Right_;
    }

    static TBasePtr& LeftNode(TBasePtr x) {
        return x->Left_;
    }

    static TBasePtr& RightNode(TBasePtr x) {
        return x->Right_;
    }

    static TBasePtr& ParentNode(TBasePtr x) {
        return x->Parent_;
    }

    static TValue& ValueNode(TBasePtr x) {
        return *static_cast<TValue*>(x);
    }

    static TBasePtr MinimumNode(TBasePtr x) {
        return TRbTreeNodeBase::MinimumNode(x);
    }

    static TBasePtr MaximumNode(TBasePtr x) {
        return TRbTreeNodeBase::MaximumNode(x);
    }

private:
    TCmpAdaptor KeyCompare_;
    TNodeBase Data_;
};

template <class TValue, class TCmp>
class TRbTreeItem: public TRbTree<TValue, TCmp>::TRealNode {
};

template <class TDummy>
void TRbGlobal<TDummy>::RotateLeft(TRbTreeNodeBase* x, TRbTreeNodeBase*& root) {
    TRbTreeNodeBase* y = x->Right_;
    x->Right_ = y->Left_;
    if (y->Left_ != nullptr)
        y->Left_->Parent_ = x;
    y->Parent_ = x->Parent_;

    if (x == root)
        root = y;
    else if (x == x->Parent_->Left_)
        x->Parent_->Left_ = y;
    else
        x->Parent_->Right_ = y;
    y->Left_ = x;
    x->Parent_ = y;
    y->Children_ = x->Children_;
    x->Children_ = ((x->Left_) ? x->Left_->Children_ : 0) + ((x->Right_) ? x->Right_->Children_ : 0) + 1;
}

template <class TDummy>
void TRbGlobal<TDummy>::RotateRight(TRbTreeNodeBase* x, TRbTreeNodeBase*& root) {
    TRbTreeNodeBase* y = x->Left_;
    x->Left_ = y->Right_;
    if (y->Right_ != nullptr)
        y->Right_->Parent_ = x;
    y->Parent_ = x->Parent_;

    if (x == root)
        root = y;
    else if (x == x->Parent_->Right_)
        x->Parent_->Right_ = y;
    else
        x->Parent_->Left_ = y;
    y->Right_ = x;
    x->Parent_ = y;
    y->Children_ = x->Children_;
    x->Children_ = ((x->Left_) ? x->Left_->Children_ : 0) + ((x->Right_) ? x->Right_->Children_ : 0) + 1;
}

template <class TDummy>
void TRbGlobal<TDummy>::Rebalance(TRbTreeNodeBase* x, TRbTreeNodeBase*& root) {
    x->Color_ = RBTreeRed;
    while (x != root && x->Parent_->Color_ == RBTreeRed) {
        if (x->Parent_ == x->Parent_->Parent_->Left_) {
            TRbTreeNodeBase* y = x->Parent_->Parent_->Right_;
            if (y && y->Color_ == RBTreeRed) {
                x->Parent_->Color_ = RBTreeBlack;
                y->Color_ = RBTreeBlack;
                x->Parent_->Parent_->Color_ = RBTreeRed;
                x = x->Parent_->Parent_;
            } else {
                if (x == x->Parent_->Right_) {
                    x = x->Parent_;
                    RotateLeft(x, root);
                }
                x->Parent_->Color_ = RBTreeBlack;
                x->Parent_->Parent_->Color_ = RBTreeRed;
                RotateRight(x->Parent_->Parent_, root);
            }
        } else {
            TRbTreeNodeBase* y = x->Parent_->Parent_->Left_;
            if (y && y->Color_ == RBTreeRed) {
                x->Parent_->Color_ = RBTreeBlack;
                y->Color_ = RBTreeBlack;
                x->Parent_->Parent_->Color_ = RBTreeRed;
                x = x->Parent_->Parent_;
            } else {
                if (x == x->Parent_->Left_) {
                    x = x->Parent_;
                    RotateRight(x, root);
                }
                x->Parent_->Color_ = RBTreeBlack;
                x->Parent_->Parent_->Color_ = RBTreeRed;
                RotateLeft(x->Parent_->Parent_, root);
            }
        }
    }
    root->Color_ = RBTreeBlack;
}

template <class TDummy>
void TRbGlobal<TDummy>::RecalcChildren(TRbTreeNodeBase* x) {
    x->Children_ = ((x->Left_) ? x->Left_->Children_ : 0) + ((x->Right_) ? x->Right_->Children_ : 0) + 1;
}

template <class TDummy>
void TRbGlobal<TDummy>::DecrementChildrenUntilRoot(TRbTreeNodeBase* x, TRbTreeNodeBase* root) {
    auto* ptr = x;
    --ptr->Children_;
    while (ptr != root) {
        ptr = ptr->Parent_;
        --ptr->Children_;
    }
}

template <class TDummy>
TRbTreeNodeBase* TRbGlobal<TDummy>::RebalanceForErase(TRbTreeNodeBase* z,
                                                      TRbTreeNodeBase*& root,
                                                      TRbTreeNodeBase*& leftmost,
                                                      TRbTreeNodeBase*& rightmost) {
    TRbTreeNodeBase* y = z;
    TRbTreeNodeBase* x;
    TRbTreeNodeBase* x_parent;

    if (y->Left_ == nullptr) // z has at most one non-null child. y == z.
        x = y->Right_;       // x might be null.
    else {
        if (y->Right_ == nullptr)                        // z has exactly one non-null child. y == z.
            x = y->Left_;                                // x is not null.
        else {                                           // z has two non-null children.  Set y to
            y = TRbTreeNodeBase::MinimumNode(y->Right_); //   z's successor.  x might be null.
            x = y->Right_;
        }
    }

    if (y != z) {
        // relink y in place of z.  y is z's successor
        z->Left_->Parent_ = y;
        y->Left_ = z->Left_;
        if (y != z->Right_) {
            x_parent = y->Parent_;
            if (x)
                x->Parent_ = y->Parent_;
            y->Parent_->Left_ = x; // y must be a child of mLeft
            y->Right_ = z->Right_;
            z->Right_->Parent_ = y;
        } else
            x_parent = y;
        if (root == z)
            root = y;
        else if (z->Parent_->Left_ == z)
            z->Parent_->Left_ = y;
        else
            z->Parent_->Right_ = y;
        y->Parent_ = z->Parent_;
        DoSwap(y->Color_, z->Color_);

        RecalcChildren(y);
        if (x_parent != y) {
            --x_parent->Children_;
        }
        if (x_parent != root) {
            DecrementChildrenUntilRoot(x_parent->Parent_, root);
        }
        y = z;
        // y now points to node to be actually deleted
    } else {
        // y == z
        x_parent = y->Parent_;
        if (x)
            x->Parent_ = y->Parent_;
        if (root == z)
            root = x;
        else {
            if (z->Parent_->Left_ == z)
                z->Parent_->Left_ = x;
            else
                z->Parent_->Right_ = x;
            DecrementChildrenUntilRoot(z->Parent_, root); // we lost y
        }

        if (leftmost == z) {
            if (z->Right_ == nullptr) // z->mLeft must be null also
                leftmost = z->Parent_;
            // makes leftmost == _M_header if z == root
            else
                leftmost = TRbTreeNodeBase::MinimumNode(x);
        }
        if (rightmost == z) {
            if (z->Left_ == nullptr) // z->mRight must be null also
                rightmost = z->Parent_;
            // makes rightmost == _M_header if z == root
            else // x == z->mLeft
                rightmost = TRbTreeNodeBase::MaximumNode(x);
        }
    }

    if (y->Color_ != RBTreeRed) {
        while (x != root && (x == nullptr || x->Color_ == RBTreeBlack))
            if (x == x_parent->Left_) {
                TRbTreeNodeBase* w = x_parent->Right_;
                if (w->Color_ == RBTreeRed) {
                    w->Color_ = RBTreeBlack;
                    x_parent->Color_ = RBTreeRed;
                    RotateLeft(x_parent, root);
                    w = x_parent->Right_;
                }
                if ((w->Left_ == nullptr ||
                     w->Left_->Color_ == RBTreeBlack) &&
                    (w->Right_ == nullptr ||
                     w->Right_->Color_ == RBTreeBlack))
                {
                    w->Color_ = RBTreeRed;
                    x = x_parent;
                    x_parent = x_parent->Parent_;
                } else {
                    if (w->Right_ == nullptr || w->Right_->Color_ == RBTreeBlack) {
                        if (w->Left_)
                            w->Left_->Color_ = RBTreeBlack;
                        w->Color_ = RBTreeRed;
                        RotateRight(w, root);
                        w = x_parent->Right_;
                    }
                    w->Color_ = x_parent->Color_;
                    x_parent->Color_ = RBTreeBlack;
                    if (w->Right_)
                        w->Right_->Color_ = RBTreeBlack;
                    RotateLeft(x_parent, root);
                    break;
                }
            } else {
                // same as above, with mRight <-> mLeft.
                TRbTreeNodeBase* w = x_parent->Left_;
                if (w->Color_ == RBTreeRed) {
                    w->Color_ = RBTreeBlack;
                    x_parent->Color_ = RBTreeRed;
                    RotateRight(x_parent, root);
                    w = x_parent->Left_;
                }
                if ((w->Right_ == nullptr ||
                     w->Right_->Color_ == RBTreeBlack) &&
                    (w->Left_ == nullptr ||
                     w->Left_->Color_ == RBTreeBlack))
                {
                    w->Color_ = RBTreeRed;
                    x = x_parent;
                    x_parent = x_parent->Parent_;
                } else {
                    if (w->Left_ == nullptr || w->Left_->Color_ == RBTreeBlack) {
                        if (w->Right_)
                            w->Right_->Color_ = RBTreeBlack;
                        w->Color_ = RBTreeRed;
                        RotateLeft(w, root);
                        w = x_parent->Left_;
                    }
                    w->Color_ = x_parent->Color_;
                    x_parent->Color_ = RBTreeBlack;
                    if (w->Left_)
                        w->Left_->Color_ = RBTreeBlack;
                    RotateRight(x_parent, root);
                    break;
                }
            }
        if (x)
            x->Color_ = RBTreeBlack;
    }
    return y;
}

template <class TDummy>
TRbTreeNodeBase* TRbGlobal<TDummy>::DecrementNode(TRbTreeNodeBase* Node_) {
    if (Node_->Color_ == RBTreeRed && Node_->Parent_->Parent_ == Node_)
        Node_ = Node_->Right_;
    else if (Node_->Left_ != nullptr) {
        Node_ = TRbTreeNodeBase::MaximumNode(Node_->Left_);
    } else {
        TBasePtr y = Node_->Parent_;
        while (Node_ == y->Left_) {
            Node_ = y;
            y = y->Parent_;
        }
        Node_ = y;
    }
    return Node_;
}

template <class TDummy>
TRbTreeNodeBase* TRbGlobal<TDummy>::IncrementNode(TRbTreeNodeBase* Node_) {
    if (Node_->Right_ != nullptr) {
        Node_ = TRbTreeNodeBase::MinimumNode(Node_->Right_);
    } else {
        TBasePtr y = Node_->Parent_;
        while (Node_ == y->Right_) {
            Node_ = y;
            y = y->Parent_;
        }
        // check special case: This is necessary if mNode is the
        // _M_head and the tree contains only a single node y. In
        // that case parent, left and right all point to y!
        if (Node_->Right_ != y)
            Node_ = y;
    }
    return Node_;
}

#undef RBTreeRed
#undef RBTreeBlack