DynamicTree.h

Go to the documentation of this file.

#ifndef DYNAMICTREE_H
#define DYNAMICTREE_H


template <class _Type>
class DynamicTree;


template <class _Type>
class DynTreeNode {
public:
//  LPVOID lpUserData;
    _Type *lpParent, *lpChild, *lpNext, *lpPrev; // pointers to the nearest objects
    DynamicTree<_Type> *tree; // pointer to the owner tree

    unsigned long GetDepth(); // = get number of lpParent->lpParent->lpParent->... (0 for the root)
};


// In fact, it is not tree but it can be multiple trees (forest).
template <class _Type>
class DynamicTree {
public:

    typedef bool (*DYNTREE_NODEALLOWED) (DynTreeNode<_Type>* node);
    typedef bool (*DYNTREE_SUBTREEALLOWED) (DynTreeNode<_Type>* node);

    DynamicTree (void);
    virtual ~DynamicTree (void);

    inline unsigned long GetCount (void) { return dwCount; };

    bool AddNode (_Type *lpParent, _Type *lpNode);
    // !! The node will be inserted BEFORE any other children of the parent node !!
    // [lpParent] == NULL => this will be the root node (or sibling to the root node)
    bool AddNodeLast (_Type *lpParent, _Type *lpNode);
    // !! The node will be inserted AFTER any other children of the parent node !!
    // This function is slower than AddNode().
    // [lpParent] == NULL => this will be the root node (or sibling to the root node)
    bool InsertNode (_Type *lpParent, _Type *lpPrevSibling, _Type *lpNode);
    // The node will be inserted AFTER the [lpPrevSibling]
    // [lpParent] == NULL => this will be the root node (or sibling to the root node)
    // [lpPrevSibling] == NULL => insert as a first child
    bool DeleteNode (_Type *lpNode, bool bCallDelete = false);
    // Deletes also subtree.
    // If lpNode is NULL whole tree will be deleted.

    inline _Type* GetRoot (void) { return lpRoot; }

    bool Clear (bool bCallDelete = false);

protected:
    _Type *lpRoot;
    unsigned long dwCount;
};



// These flags are mostly mutualy exclusive:
#define DTI_EXCLUDEROOT         0x00000001      // root will be excluded from traversing
#define DTI_ONLYLEAVES          0x00000002      // traverse only leaves
#define DTI_ONELAYERTRAVERSAL   0x00000004
    // Can not be specified together with DTI_ONLYLEAVES
    // if DTI_EXCLUDEROOT is also specified:
    //      traverse root's nearest children
    // if DTI_EXCLUDEROOT is NOT specified:
    //      traverse root and it's siblings


template <class _Type>
class DynamicTreeIterator { // depth-first style iterating through the tree
public:
    DynamicTreeIterator (void) { cbNodeAllowed = NULL; cbSubTreeAllowed = NULL; bStarting = false; Reset (); }
    inline void Reset (void) { nodePtr = (_Type*)0; tree = NULL; }

    void SetNodeAllowedCallback (typename DynamicTree<_Type>::DYNTREE_NODEALLOWED cb) { cbNodeAllowed = cb; };
    void SetSubTreeAllowedCallback (typename DynamicTree<_Type>::DYNTREE_SUBTREEALLOWED cb) { cbSubTreeAllowed = cb; };
    
    /* [dwFlags] is combination of DTI_* 
       [lpTravStart] is starting node to traverse form
                     (it will be something like temporary root).
        WARNING: lpTravStart can be NULL ONLY IF SetTree is called before. */
    void Start (_Type *lpTravStart, unsigned long dwFlags);
    inline bool IsFinished (void) { return (0 == nodePtr); }

    inline bool operator== (
        const DynamicTreeIterator<_Type>& iter)
    {
        return (nodePtr == iter.nodePtr);
    };
    inline friend bool operator!= (
        const DynamicTreeIterator<_Type>& iter1,
        const DynamicTreeIterator<_Type>& iter2)
    {
        return (iter1.nodePtr != iter2.nodePtr);
    };
    DynamicTreeIterator<_Type>& operator++ (void);
    DynamicTreeIterator<_Type> operator++ (int);

    _Type* GetNode (void) { return (nodePtr); };

    // This is only necessary when starting from the NULL object.
    void SetTree (DynamicTree<_Type> *_tree) { tree = _tree; };

//  DynTreeNode& operator* (void) { return (*nodePtr); };
//  DynTreeNode& operator-> (void) { return (*nodePtr); };

protected:
    DynamicTree<_Type> *tree;
    _Type *nodePtr;
    _Type *nodeStart;
    unsigned long dwFlags;
    typename DynamicTree<_Type>::DYNTREE_NODEALLOWED cbNodeAllowed;
    typename DynamicTree<_Type>::DYNTREE_SUBTREEALLOWED cbSubTreeAllowed;
    bool bStarting; // The first node is to be found

    inline bool IsNodeAllowed (_Type *node)
    {
        if ((dwFlags & DTI_EXCLUDEROOT) && (node == nodeStart))
            return false;
        if ((dwFlags & DTI_ONLYLEAVES) && (node->lpChild))
            return false;
        if (!cbNodeAllowed)
            return true;
        return cbNodeAllowed (node);
    };

    inline bool IsSubTreeAllowed (_Type *node)
    {
        if (!cbSubTreeAllowed)
            return true;
        return cbSubTreeAllowed (node);
    };
};


template <class _Type>
unsigned long DynTreeNode<_Type>::GetDepth()
{
    _Type *tmp = lpParent;
    unsigned long dw = 0;
    while (tmp) {
        tmp = tmp->lpParent;
        dw++;
    }
    return dw;
}


template <class _Type>
DynamicTree<_Type>::DynamicTree (void)
{
    lpRoot = NULL;
    dwCount = 0;
}

template <class _Type>
DynamicTree<_Type>::~DynamicTree (void)
{
    DeleteNode (NULL);
}


template <class _Type>
bool DynamicTree<_Type>::AddNode (_Type *lpParent, _Type *lpNode)
{
    lpNode->tree = this;

    lpNode->lpParent = lpParent;
    lpNode->lpChild = NULL;
    lpNode->lpPrev = NULL;

    if (lpParent) {
        lpNode->lpNext = lpParent->lpChild;
        if (lpParent->lpChild)
            lpParent->lpChild->lpPrev = lpNode;
        lpParent->lpChild = lpNode;
    } else {
        lpNode->lpNext = lpRoot;
        if (lpRoot)
            lpRoot->lpPrev = lpNode;
        lpRoot = lpNode;
    }

    dwCount++;
    return true;
}


template <class _Type>
bool DynamicTree<_Type>::AddNodeLast (_Type *lpParent, _Type *lpNode)
{
    lpNode->tree = this;

    lpNode->lpParent = lpParent;
    lpNode->lpChild = NULL;
    lpNode->lpPrev = NULL;
    lpNode->lpNext = NULL;

    if (lpParent) {
        if (!lpParent->lpChild) {
            lpParent->lpChild = lpNode;
        } else {
            _Type *child = lpParent->lpChild;
            while (child->lpNext)
                child = child->lpNext;
            child->lpNext = lpNode;
            lpNode->lpPrev = child;
        }
    } else {
        if (!lpRoot) {
            lpRoot = lpNode;
        } else {
            _Type *child = lpRoot;
            while (child->lpNext)
                child = child->lpNext;
            child->lpNext = lpNode;
            lpNode->lpPrev = child;
        }
    }

    dwCount++;
    return true;
}


template <class _Type>
bool DynamicTree<_Type>::InsertNode (_Type *lpParent, _Type *lpPrevSibling, _Type *lpNode)
{
    if (NULL == lpPrevSibling)
        return AddNode (lpParent, lpNode);

    lpNode->tree = this;

    lpNode->lpParent = lpParent;
    lpNode->lpChild = NULL;
    lpNode->lpPrev = lpPrevSibling;
    lpNode->lpNext = lpPrevSibling->lpNext;
    if (lpPrevSibling->lpNext)
        lpPrevSibling->lpNext->lpPrev = lpNode;
    lpPrevSibling->lpNext = lpNode;

    dwCount++;
    return true;
}


template <class _Type>
bool DynamicTree<_Type>::DeleteNode (_Type *lpNode, bool bCallDelete)
{
    if (lpNode) {
        if (lpNode->lpParent) {
            if (lpNode->lpParent->lpChild == lpNode)
                lpNode->lpParent->lpChild = lpNode->lpNext;
        }

        while (lpNode->lpChild) {
            if (!DeleteNode (lpNode->lpChild, bCallDelete))
                return false;
        }

        if (lpNode->lpPrev)
            lpNode->lpPrev->lpNext = lpNode->lpNext;

        if (lpNode->lpNext)
            lpNode->lpNext->lpPrev = lpNode->lpPrev;

        if (lpNode == lpRoot)
            lpRoot = lpNode->lpNext;

        lpNode->tree = NULL;

        if (bCallDelete)
            delete lpNode;

        dwCount--;
    } else {
        while (lpRoot) {
            if (!DeleteNode (lpRoot, bCallDelete))
                return false;
        }

        lpRoot = NULL;
    }

    return true;
}


template <class _Type>
bool DynamicTree<_Type>::Clear (bool bCallDelete)
{
    return DeleteNode (NULL, bCallDelete);
}


template <class _Type>
void DynamicTreeIterator<_Type>::Start (_Type *_lpTravStart, unsigned long _dwFlags)
{
    nodeStart = _lpTravStart;
    dwFlags = _dwFlags;
    nodePtr = NULL;

    bStarting = true;

    if (_lpTravStart) {
        if (dwFlags & DTI_EXCLUDEROOT)
            nodePtr = nodeStart->lpChild;
        else if (nodeStart)
            nodePtr = nodeStart;
    } else {
        if (tree)
            nodePtr = tree->GetRoot ();
    }

    ++*this;

    bStarting = false;
}


template <class _Type>
DynamicTreeIterator<_Type>& DynamicTreeIterator<_Type>::operator++ (void)
{
    if (!bStarting && !nodePtr)
        return *this;

    if (dwFlags & DTI_ONELAYERTRAVERSAL) {
        if (!bStarting)
            nodePtr = nodePtr->lpNext;

        while (nodePtr && !IsNodeAllowed (nodePtr)) 
            nodePtr = nodePtr->lpNext;

        return *this;
    }

    unsigned long dwState = 1;

    while (true) {
        if (!bStarting) {
            if (nodePtr->lpChild && IsSubTreeAllowed (nodePtr))
                nodePtr = nodePtr->lpChild;
            else {
                while (nodePtr && !nodePtr->lpNext) {
                    if (nodePtr == nodeStart) {
                        nodePtr = NULL;
                        break;
                    }
                    nodePtr = nodePtr->lpParent;
                }
                if (nodePtr == nodeStart) {
                    nodePtr = NULL;
                    break;
                }
                if (nodePtr)
                    nodePtr = nodePtr->lpNext;
            }
        }

        if (!nodePtr)
            break;

        if (IsNodeAllowed (nodePtr))
            break;

        bStarting = false;
    }

    return *this;
}


template <class _Type>
DynamicTreeIterator<_Type> DynamicTreeIterator<_Type>::operator++ (int)
{
    DynamicTreeIterator<_Type> *tmp = this;
    ++*this;
    return (*tmp);
}


#endif