BinTree.h

#pragma once


#include <libutl/BinTreeNode.h>
#include <libutl/MaxObject.h>
#include <libutl/SortedCollection.h>


UTL_NS_BEGIN;


class BinTreeBfsIt;
class BinTreeIt;



class BinTree : public SortedCollection
{
    UTL_CLASS_DECL_ABC(BinTree, SortedCollection);

public:
    typedef BinTreeIt iterator;

public:
    BinTree(bool owner, bool multiSet = false, Ordering* ordering = nullptr);

    virtual void steal(Object& rhs);



    void
    dumpTree(Stream& os) const
    {
        _root->dump(os, 0);
    }



    void
    serializeFast(Stream& stream, uint_t io, uint_t mode = ser_default)
    {
        serializeFast(nullptr, stream, io, mode);
    }

    void
    serializeFast(const RunTimeClass* rtc, Stream& stream, uint_t io, uint_t mode = ser_default);


    virtual Object* find(const Object& key) const;

    iterator findIt(const Object& key) const;

    iterator findIt(const Object& key);

    void
    findIt(const Object& key, BidIt& it) const
    {
        const_cast_this->findIt(key, it);
        IFDEBUG(it.setConst(true));
    }

    virtual void findIt(const Object& key, BidIt& it);

    void
    findFirstIt(const Object& key, BidIt& it, bool insert = false) const
    {
        const_cast_this->findFirstIt(key, it, insert);
        IFDEBUG(it.setConst(true));
    }

    virtual void findFirstIt(const Object& key, BidIt& it, bool insert = false);

    iterator findFirstIt(const Object& key, bool insert = false) const;

    iterator findFirstIt(const Object& key, bool insert = false);

    void
    findLastIt(const Object& key, BidIt& it) const
    {
        const_cast_this->findLastIt(key, it);
        IFDEBUG(it.setConst(true));
    }

    virtual void findLastIt(const Object& key, BidIt& it);

    iterator findLastIt(const Object& key) const;

    iterator findLastIt(const Object& key);


    bool
    add(const Object& object)
    {
        return super::add(object);
    }

    virtual bool add(const Object* object);

    void
    add(const Collection& collection)
    {
        super::add(collection);
    }

    void
    insert(const Object& object, const BidIt& it)
    {
        return super::insert(object, it);
    }

    virtual void insert(const Object* object, const BidIt& it);


    virtual void clear();

    bool
    remove(const Object* key)
    {
        ASSERTD(key != nullptr);
        return remove(*key);
    }

    virtual bool remove(const Object& key);

    virtual void removeIt(BidIt& it);

    virtual void
    removeIt(BidIt& begin, BidIt& end)
    {
        super::removeIt(begin, end);
    }



    inline iterator begin() const;

    inline iterator begin();

    inline BinTreeBfsIt beginBFS() const;

    inline BinTreeBfsIt beginBFS();

    inline virtual BidIt* beginNew() const;

    inline virtual BidIt* beginNew();

    inline BinTreeBfsIt* beginBFSNew() const;

    inline BinTreeBfsIt* beginBFSNew();

    inline iterator end() const;

    inline iterator end();

    inline BinTreeBfsIt endBFS() const;

    inline BinTreeBfsIt endBFS();

    inline virtual BidIt* endNew() const;

    inline virtual BidIt* endNew();

    inline BinTreeBfsIt* endBFSNew() const;

    inline BinTreeBfsIt* endBFSNew();

    inline iterator root() const;

    inline iterator root();

#ifdef DEBUG
    iterator begin(bool notifyOwner);

    virtual void sanityCheck() const;
#endif
protected:
    inline int
    compareObjects(const Object* lhs, const Object* rhs) const
    {
        return (lhs == &maxObject) ? 1 : super::compareObjects(lhs, rhs);
    }
    void clear(BinTreeNode* node);
    virtual BinTreeNode* createNode(const Object* object) = 0;
    BinTreeNode* findFirstMatch(const Object& key, BinTreeNode* node) const;
    BinTreeNode* findInsertionPoint(const Object& key, bool* insertLeft = nullptr) const;
    iterator findIt(const Object& key, uint_t findType) const;
    iterator findIt(const Object& key, uint_t findType);
    BinTreeNode* findLastMatch(const Object& key, BinTreeNode* node) const;
    BinTreeNode* findNode(const Object& key, uint_t findType) const;
    BinTreeNode* removeNode(BinTreeNode* node);
    virtual void resetRoot();

protected:
    BinTreeNode* _root;

private:
    void init(bool owner = true, bool multiSet = false, Ordering* ordering = nullptr);
    void deInit();
};


UTL_NS_END;


#include <libutl/BinTreeIt.h>
#include <libutl/BinTreeBfsIt.h>