GxTree.h

Go to the documentation of this file.

//===========================================================================
//===========================================================================
#pragma once
 
GX_CORE_NAMESPACE_BEGIN()
 
//===========================================================================
//===========================================================================
class GxTreeBase : public GxClassBase
{
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    // RTTI定義
    GX_RTTI_CLASS(GxTreeBase, GxClassBase)
    // GxClassBase継承クラス用禁止宣言
    GX_PROHIBIT_CLASS_BASE(GxTreeBase)
 
    // NEW DELETE 定義
    GX_OPERATOR_NEW_DELETE(GxAllocatorList::ALLOCATOR_TYPE::TEMPORARY)
 
    // クラス宣言
    class GxNodeBase;
 
    // イテレータ宣言
    template <class T> class GxIteratorBase;
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    GxTreeBase(void)
        : _pRoot(nullptr)
    {}
    ~GxTreeBase(void) { erase(); }
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    GxTreeBase::GxNodeBase* addRootNode(void* pObject);
    GxTreeBase::GxNodeBase* addNextNode(GxTreeBase::GxNodeBase* pBase, void* pObject);
    GxTreeBase::GxNodeBase* addChildNode(GxTreeBase::GxNodeBase* pBase, void* pObject);
 
    void erase(GxTreeBase::GxNodeBase* pNode = nullptr);
 
    void eraseAll(GxTreeBase::GxNodeBase* pNode);
 
    GxTreeBase::GxNodeBase* find(const void* pObject);
 
protected:
    virtual GxNodeBase* allocateNode(void);
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    constexpr void setRootNode(GxTreeBase::GxNodeBase* pNode) { _pRoot = pNode; }
    constexpr GxTreeBase::GxNodeBase* getRootNode(void) const { return _pRoot; }
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
protected:
    GxTreeBase::GxNodeBase*     _pRoot;                     
    
};
 
//===========================================================================
//===========================================================================
class GxTreeBase::GxNodeBase : public GxClassBase
{
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    // RTTI定義
    GX_RTTI_CLASS(GxTreeBase::GxNodeBase, GxClassBase)
    // GxClassBase継承クラス用禁止宣言
    GX_PROHIBIT_CLASS_BASE(GxNodeBase)
 
    // NEW DELETE 定義
    GX_OPERATOR_NEW_DELETE(GxAllocatorList::ALLOCATOR_TYPE::TEMPORARY)
 
    
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    GxNodeBase(void)
        : _pTree(nullptr)
        , _pObject(nullptr)
        , _pParent(nullptr)
        , _pChild(nullptr)
        , _pPrevious(nullptr)
        , _pNext(nullptr)
    {}
 
    GxNodeBase(GxTreeBase* pTree)
        : _pTree(pTree)
        , _pObject(nullptr)
        , _pParent(nullptr)
        , _pChild(nullptr)
        , _pPrevious(nullptr)
        , _pNext(nullptr)
    {}
 
    ~GxNodeBase(void) { erase(); }
 
    //-------------------------------
    //-------------------------------
 
public:
    GX_FORCE_INLINE virtual void setObject(void* pObject) { _pObject = pObject; }
    constexpr void* getObject(void) const { return _pObject; }
    GX_FORCE_INLINE GxTreeBase::GxNodeBase* getParent(void){ return getPreviousTop()->_pParent; }
    constexpr GxTreeBase::GxNodeBase* getChild(void) const { return _pChild; }
    constexpr GxTreeBase::GxNodeBase* getPrevious(void) const { return _pPrevious; }
    constexpr GxTreeBase::GxNodeBase* getNext(void) const { return _pNext; }
    GxTreeBase::GxNodeBase* getPreviousTop(void);
    GxTreeBase::GxNodeBase* getNextEnd(void);
 
    b32 isRoot(void) const;
    b32 isChild(const GxTreeBase::GxNodeBase* pNode) const;
    b32 isBrother(const GxTreeBase::GxNodeBase* pNode) const;
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    virtual void erase(void);
 
    GxTreeBase::GxNodeBase* find(const void* pObject);
 
    void attachChild(GxTreeBase::GxNodeBase* pNode);
    void attachNext(GxTreeBase::GxNodeBase* pNode);
    void attachNextEnd(GxTreeBase::GxNodeBase* pNode);
 
    void detach(void);
    void detachParentPrevious(void);
    void detachExceptChild(void);
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
protected:
    GxTreeBase*             _pTree;         
    void*                   _pObject;       
    GxTreeBase::GxNodeBase* _pParent;       
    GxTreeBase::GxNodeBase* _pChild;        
    GxTreeBase::GxNodeBase* _pPrevious;     
    GxTreeBase::GxNodeBase* _pNext;         
    
};
 
//===========================================================================
//===========================================================================
template<class T> class GxTreeBase::GxIteratorBase
{
    //-----------------------------------------------------------
    //-----------------------------------------------------------
protected:
    GxIteratorBase(void) {}
 
public:
    GxIteratorBase(GxTreeBase* pTreeBase) : _pTreeBase(pTreeBase) { _pCurrent = _pTreeBase->getRootNode(); }
    virtual ~GxIteratorBase(void){}
 
    GxIteratorBase(const GxTreeBase::GxIteratorBase<T>& iterator) : _pTreeBase(iterator._pTreeBase), _pCurrent(iterator._pCurrent) {}
    const GxTreeBase::GxIteratorBase<T>& operator = (GxTreeBase::GxIteratorBase<T>& iterator) { _pTreeBase = iterator._pTreeBase; _pCurrent = iterator._pCurrent; return this; }
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
 
    T getTop(void);
    T getNext(void);
    T getCurrent(void);
    GxTreeBase::GxNodeBase* getCurrentNode(void);
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
 
protected:
    GxTreeBase*     _pTreeBase;             
    GxNodeBase*     _pCurrent;              
 
};
 
//===========================================================================
//===========================================================================
class GxTree : public GxTreeBase
{
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    // RTTI定義
    GX_RTTI_CLASS(GxTree, GxTreeBase)
    // GxClassBase継承クラス用禁止宣言
    GX_PROHIBIT_CLASS_BASE(GxTree)
 
    
    enum ATTRIBUTE
    {
        ATTRIBUTE_USE_REFERENCE_COUNT = 1 << 0              
    };
 
    // クラス宣言
    class GxNode;
 
    // イテレータ宣言
    template <class T> class GxIterator;
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    GxTree(u32 attribute = 0)
        : _attribute(attribute)
    {}
 
    ~GxTree(void) {}
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    GX_FORCE_INLINE GxTree::GxNode* addRootNode(GxClassBaseReference* pObject) { return reinterpret_cast<GxTree::GxNode*>(GxTreeBase::addRootNode(static_cast<void*>(pObject))); }
    GX_FORCE_INLINE GxTree::GxNode* addNextNode(GxTree::GxNode* pBase, GxClassBaseReference* pObject) { return reinterpret_cast<GxTree::GxNode*>(GxTreeBase::addNextNode(reinterpret_cast<GxTreeBase::GxNodeBase*>(pBase), static_cast<void*>(pObject))); }
    GX_FORCE_INLINE GxTree::GxNode* addChildNode(GxTree::GxNode* pBase, GxClassBaseReference* pObject) { return reinterpret_cast<GxTree::GxNode*>(GxTreeBase::addChildNode(reinterpret_cast<GxTreeBase::GxNodeBase*>(pBase), static_cast<void*>(pObject))); }
 
protected:
    GxNodeBase* allocateNode(void) override;
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    GX_FORCE_INLINE GxTree::GxNode* getRootNode(void) const { return reinterpret_cast<GxTree::GxNode*>(_pRoot); }
 
    constexpr u32 getAttribute(void) const { return _attribute; }
    constexpr void setAttribute(ATTRIBUTE attribute) { _attribute |= attribute; }
    constexpr void clearAttribute(ATTRIBUTE attribute) { _attribute &= ~attribute; }
    GX_FORCE_INLINE b32 isAttribute(ATTRIBUTE attribute) const { return (_attribute & attribute) ? true : false; }
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
protected:
    u32 _attribute; 
    
};
 
//===========================================================================
//===========================================================================
class GxTree::GxNode : public GxTreeBase::GxNodeBase
{
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    // RTTI定義
    GX_RTTI_CLASS(GxTree::GxNode, GxTreeBase::GxNodeBase)
    // GxClassBase継承クラス用禁止宣言
    GX_PROHIBIT_CLASS_BASE(GxNode)
 
    
    //-----------------------------------------------------------
    //-----------------------------------------------------------
protected:
    GxNode(void) {}
 
public:
    GxNode(GxTree* pTree)
        : GxTreeBase::GxNodeBase(pTree)
    {}
 
    ~GxNode(void) {}
 
    //-------------------------------
    //-------------------------------
public:
    void setObject(void* pObject) override;
    constexpr GxClassBaseReference* getObject(void) const { return static_cast<GxClassBaseReference*>(_pObject); }
    GX_FORCE_INLINE GxTree::GxNode* getParent(void){ return static_cast<GxTree::GxNode*>(getPreviousTop()->getParent()); }
    constexpr GxTree::GxNode* getChild(void) const { return static_cast<GxTree::GxNode*>(_pChild); }
    constexpr GxTree::GxNode* getPrevious(void) const { return static_cast<GxTree::GxNode*>(_pPrevious); }
    constexpr GxTree::GxNode* getNext(void) const { return static_cast<GxTree::GxNode*>(_pNext); }
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    void erase(void) override;
 
};
 
//===========================================================================
//===========================================================================
template<class T> class GxTree::GxIterator : public GxTreeBase::GxIteratorBase<T>
{
    //-----------------------------------------------------------
    //-----------------------------------------------------------
protected:
    GxIterator(void) {}
 
public:
    GxIterator(GxTreeBase* pTreeBase) : GxTreeBase::GxIteratorBase<T>(pTreeBase) {}
    ~GxIterator(void) override {}
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
 
    GX_FORCE_INLINE GxTree::GxNode* getCurrentNode(void) { return static_cast<GxTree::GxNode*>(GxIteratorBase<T>::getCurrentNode()); }
 
};
 
//===========================================================================
// ツリー構造イテレータクラス
//===========================================================================
//---------------------------------------------------------------------------
// 先頭オブジェクト取得
//---------------------------------------------------------------------------
template<class T> T GxTreeBase::GxIteratorBase<T>::getTop(void)
{
    _pCurrent = _pTreeBase->getRootNode();
    return getCurrent();
}
 
//---------------------------------------------------------------------------
// 次オブジェクト取得
//---------------------------------------------------------------------------
template<class T> T GxTreeBase::GxIteratorBase<T>::getNext(void)
{
    if( _pCurrent )
    {
        // 子ノード判定
        auto* pChild = _pCurrent->getChild();
        if( pChild )
        {
            // 子ノードある → 子ノードをカレントに設定
            _pCurrent = pChild;
        }
        else
        {
            // 子ノードない → 兄弟ノード判定
            auto* pNext = _pCurrent->getNext();
            if( pNext )
            {
                // 兄弟ノードある → 兄弟ノードをカレントに設定
                _pCurrent = pNext;
            }
            else
            {
                // 兄弟ノードない → 親ノードの兄弟判定
                auto* pParent = _pCurrent->getParent();
                for( ; pParent; pParent = pParent->getParent() )
                {
                    if( pParent->getNext() )
                    {
                        // 親ノードの兄弟がある → カレントに設定
                        _pCurrent = pParent->getNext();
                        break;
                    }
                }
                // 未発見 → nullptr設定
                if( !pParent )
                {
                    _pCurrent = nullptr;
                }
            }
        }
        return getCurrent();
    }
    return nullptr;
}
 
//---------------------------------------------------------------------------
// 現在オブジェクト取得
//---------------------------------------------------------------------------
template<class T> T GxTreeBase::GxIteratorBase<T>::getCurrent(void)
{
    if( _pCurrent )
    {
        return static_cast<T>(_pCurrent->getObject());
    }
    return nullptr;
}
 
//---------------------------------------------------------------------------
// 現在のノードを取得
//---------------------------------------------------------------------------
template<class T> GxTreeBase::GxNodeBase* GxTreeBase::GxIteratorBase<T>::getCurrentNode(void)
{
    return _pCurrent;
}
 
GX_CORE_NAMESPACE_END()