Click here to Skip to main content
15,868,440 members
Articles / Programming Languages / C++
Article

C++ Template class to walk through a tree

Rate me:
Please Sign up or sign in to vote.
3.86/5 (7 votes)
1 Apr 20033 min read 66.5K   837   26   3
An article decribing the use of templates in writing a tree walker

Introduction

The template class walker captures only the algorithm of walking and depends on ContextType, the template argument type, for context sensitive functionalities. The context based information are the context identifier type, filter type, context item, opening a context and reserved context. The ContextType template argument should support the required typedefs and inner classes, CItem and COpenContext.

Before going any further on the details of implementation, I would like to talk about the need for such a class. We program with different kind of structures that look like or are trees, and sometimes we will have to repeat the walking algorithm for a small variation in the structure. Repeating an algorithm like that has many problems we know, and that is the reason stl has for_each algorithm. Like the goals of stl, an algorithm should be independent of the data structure. The dependency of walk algorithm on data structure is moved to the ContextType class. The class should have types ContextIdentifierType, ContentFilterType, CItem and COpenContext and should support a static function IsReserved(const CItem*).

CItem should have the following interface :-

bool IsAContext() const

COpenContext should have the following interface

C'tor <BR>D'tor <BR>cont CItem* GetNext() <BR>const CItem* Get() const <BR>bool GetNewContextId(ContextIdentifierType& newId) const

For ContextIdentifierType and ContentFilterType there are no interface specification. None of the functions can throw exceptions.

Using the code

A class can derive from a particular instantiation of this template and override bool OnContextChange(UserDataType*, const ContextType::CItem&, const ContextType::ContextIdentifierType& , bool bMovedToNewOrBackToOld). This will be called by WalkI private method when entering or leaving a context.

The arguments are  :-

  • user data passed by reference to allow any modification
  • item, which is the new context here
  • present(old)/new context identifier
  • moving in to/moving out of the context

And there is void OnItemFound(UserDataType,const ContextType::CItem&,const ContextType::ContextIdentifierType&). This method will be called by WalkI private method when a new item is found. Even though a new context is an item in the present context only OnContextChange is called.

  • user data passed by value.
  • item
  • present context identifier

Both these methods are private. Here is the code for the template

template <class UserDataTypeT,class ContextTypeT>
class CWalker
{
public:
    typedef ContextTypeT ContextType;
    typedef UserDataTypeT UserDataType;
    typedef CWalker<UserDataType,ContextType> MyType;

    CWalker():m_bStopped(false)
    {}

    // Will walk through the specified context
    //
    int Walk(UserDataType userData,
        const ContextType::ContextIdentifierType& iContext
        )
    {
        ContextType::ContentFilterType filter = m_filter;
        int nRet = WalkI(userData,iContext,filter,m_bStopped);
        m_bStopped = false;
        return nRet;
    }
    // To set the content filter
    //
    void SetContentFilter(const ContextType::ContentFilterType& filter)
    {
        m_filter = filter;
    }

    void StopWalking()
    {
        m_bStopped = true;
    }

private:

    int WalkI(UserDataType userData,
        const ContextType::ContextIdentifierType& iContext,
        const ContextType::ContentFilterType& filter,
        bool& bStopped
        )
    {
        if(bStopped) return stopped;

        ContextType::COpenContext openContext(iContext,filter);

        const ContextType::CItem *item = openContext.Get();

        if(!item) return fail;

        if(!item->IsAContext())
        {
            this->OnItemFound(userData,*item,iContext);
        }
        else 
        {
            if(!ContextType::IsReserved(*item))
            {
                ContextType::ContextIdentifierType newContext;
                openContext.GetNewContextId(newContext);

                if(this->OnContextChange(&userData,*item,newContext,true))
                {
                    WalkI(userData,newContext,filter,bStopped);
                    if(bStopped) return stopped;
                    this->OnContextChange(&userData,*item,iContext,false);
                }
            }
            else this->OnItemFound(userData,*item,iContext);
        }

        while(true)
        {
            if(bStopped) return stopped;
            const ContextType::CItem *item = openContext.GetNext();
            if(!item)
                break;

            if(!item->IsAContext())
            {
                this->OnItemFound(userData,*item,iContext);
            }
            else 
            {
                if(!ContextType::IsReserved(*item))
                {
                    ContextType::ContextIdentifierType newContext;
                    openContext.GetNewContextId(newContext);

                    if(this->OnContextChange(&userData,*item,newContext,true))
                    {
                        WalkI(userData,newContext,filter,bStopped);
                        if(bStopped) return stopped;
                        this->OnContextChange(&userData,*item,iContext,false);
                    }
                }
                else this->OnItemFound(userData,*item,iContext);
            }
        }
        return success;
    }

    ContextType::ContentFilterType m_filter;

    virtual bool OnContextChange(UserDataType*,const ContextType::CItem&,
        const ContextType::ContextIdentifierType&,bool bMovedToNewOrBackToOld)
    {
        return false;
    }

    virtual void OnItemFound(UserDataType,const ContextType::CItem&,
        const ContextType::ContextIdentifierType&)
    {
    }

    bool m_bStopped;
};

An example context

For example we will create an FolderContext which, will capture the required function and details. The identifier type is string, because folders are uniquely identified through their names. The filter type is string, because the contents of folder are again uniquely identified through their names. Here is how CITem is coded  :-

...
class CItem
{
public:
    // Required function
    //
    bool IsAContext() const
    {
        return fileInfo.dwFileAttributes==FILE_ATTRIBUTE_DIRECTORY;
    }

    WIN32_FIND_DATA& GetInfo()
    {
        return fileInfo;
    }

    const WIN32_FIND_DATA& GetInfo() const
    {
        return fileInfo;
    }
private:
    WIN32_FIND_DATA fileInfo;
};
...
If you can see, the CItem wraps WIN32_FIND_DATA, and uses that structure to implement IsAContext method. Here is how COpenContext has been coded  :-
...
class COpenContext
{
public:
    COpenContext(const ContextIdentifierType& context, 
        const ContentFilterType& filter)
    {
        m_context = context;
        std::string szToSearchFor = context;
        if(!filter.empty())
            szToSearchFor += "\\" + filter;

        m_hFind = ::FindFirstFile(szToSearchFor.data(),&m_folderItem.GetInfo());
    }

    ~COpenContext()
    {
        if(m_hFind!=INVALID_HANDLE_VALUE) ::FindClose(m_hFind);
    }

    const CItem* GetNext()
    {
        if(m_hFind==INVALID_HANDLE_VALUE) return 0;
        if(!::FindNextFile(m_hFind,&m_folderItem.GetInfo()))
            return 0;
        return &m_folderItem;
    }

    const CItem* Get() const
    {
        if(m_hFind==INVALID_HANDLE_VALUE) return 0;
        return &m_folderItem;   
    }

    bool GetNewContextId(ContextIdentifierType& newId) const
    {
        if(m_folderItem.IsAContext())
        {
            newId = m_context + "\\" + m_folderItem.GetInfo().cFileName;
            return true;
        }
        return false;
    }

private:
    CItem m_folderItem;
    HANDLE m_hFind;
    ContextIdentifierType m_context;

    COpenContext(const COpenContext&);
    COpenContext& operator = (const COpenContext&);

};
...

Here the context is folder so a find handle on the folder is created when a COpenContext object is created. In the destructor we close the handle. GetNext will get the next file or folder in the present folder using the find handle. Get will return the current item. GetNewContextId will copy the new context id in to the out parameter using the present context and item name. The attributes are CITem, present context identifier and a handle to find. The copy c'tor and = operator are not a part of the interface specification so they not implemented and made private. Let's see IsReserved now :-

...
static bool IsReserved(const CItem& item)
{
    if(std::string(".")==item.GetInfo().cFileName || 
        std::string("..")==item.GetInfo().cFileName) return true;
    return false;
}
...
The reserved items of a folder are the '.' directory and '..' directory.

Points of Interest

One interesting idea I got to protect the call back function changing the attributes of the class is to provide a wrapper to the actual function whose job is to copy the required attributes. If you have noticed the WalkI function does not use any member variables. The list of possible uses I can think of is in :-

  • Walking through the MIB (snmp)
  • Walking through binary tree
  • Walking through linked list
  • Walking through xml document/element

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Web Developer
Singapore Singapore
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralMIB and SNMP Pin
conrad Braam14-Jan-04 18:47
conrad Braam14-Jan-04 18:47 
GeneralRe: MIB and SNMP Pin
Anonymous4-Aug-04 13:49
Anonymous4-Aug-04 13:49 
GeneralNote to author Pin
Nish Nishant2-Apr-03 15:57
sitebuilderNish Nishant2-Apr-03 15:57 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.