BinTreeNode.h

#pragma once


#include <libutl/Object.h>


UTL_NS_BEGIN;



class BinTreeNode
{
public:
    BinTreeNode()
    {
        init();
    }

    virtual ~BinTreeNode()
    {
    }

    BinTreeNode(const Object* object)
    {
        init(object);
    }

    void dump(Stream& os, uint_t level);

    Object*
    get() const
    {
        return _object;
    }

    bool
    isLeaf() const
    {
        return (_object == nullptr);
    }

    bool
    isLeftChild() const
    {
        return ((_parent != nullptr) && (_parent->_left == this));
    }

    bool
    isRightChild() const
    {
        return ((_parent != nullptr) && (_parent->_right == this));
    }

    bool
    isRoot() const
    {
        return (_parent == nullptr);
    }

    BinTreeNode*
    left() const
    {
        return _left;
    }

    const BinTreeNode*
    leftMost() const
    {
        return const_cast_this->leftMost();
    }

    BinTreeNode* leftMost();

    BinTreeNode* next() const;

    BinTreeNode*
    parent() const
    {
        return _parent;
    }

    BinTreeNode* prev() const;

    void remove(BinTreeNode*& x, BinTreeNode*& y);

    BinTreeNode*
    right() const
    {
        return _right;
    }

    const BinTreeNode*
    rightMost() const
    {
        return const_cast_this->rightMost();
    }

    BinTreeNode* rightMost();

    virtual void addFixup() = 0;

    virtual void removeFixup(const BinTreeNode* removedNode) = 0;

    virtual void swapWith(BinTreeNode* rhs);

    void rotateLeft();

    void rotateRight();

    void
    set(const Object* object)
    {
        _object = const_cast<Object*>(object);
    }

    void
    setLeft(BinTreeNode* node)
    {
        _left = node;
        _left->_parent = this;
    }

    void
    setRight(BinTreeNode* node)
    {
        _right = node;
        _right->_parent = this;
    }

    BinTreeNode* sibling() const;

protected:
    BinTreeNode *_parent, *_left, *_right;
    Object* _object;

private:
    void init(const Object* object = nullptr);
    void
    deInit()
    {
    }
};


UTL_NS_END;