How to avoid dynamic_cast/static_cast

[Graham]

Visitors can be useful in situations like this...

[wildfrog]

As Graham mentions you can use the Visitor Pattern to avoid both casting and your own RTTI implementation. Something like this:

#include <vector>

using namespace std;

// forward declerations
class File;
class Folder;

// visitor interface
class FSObjectVisitor
{
public:
    virtual void VisitFile(File* file)
    { 
        /* nop */
    }

    virtual void VisitFolder(Folder* folder)
    { 
        /* nop */ 
    }
};

class FSObject
{
public:
    // this class accepts visitors
    virtual void Accept(FSObjectVisitor& visitor) = 0;
};

class Folder : public FSObject
{
public:
    typedef vector<FSObject*> FileVector;
    typedef FileVector::iterator Iterator;
public:
    Iterator begin() { return containedItems.begin(); }
    Iterator end() { return containedItems.end(); }

    void AddItem(FSObject* pFSObject)
    {
        containedItems.push_back(pFSObject);
    }

    void Accept(FSObjectVisitor& visitor)
    {
        // tell the visitor that she is visiting a folder
        visitor.VisitFolder(this);
    }

private:
  FileVector containedItems;
};

class File : public FSObject
{
public:
    void Accept(FSObjectVisitor& visitor)
    {
        // tell the visitor that she is visiting a file
        visitor.VisitFile(this);
    }
};

// implement a visitor that searched for a file
class RecursiveSearchVisitor : public FSObjectVisitor
{
private:
    RecursiveSearchVisitor()
    {
        m_pResult = 0;
    }

public:

    void VisitFile(File* pFile)
    {
        // for this example we 'match' on the first file found
        if (/*some condition*/ true)
        {
            // it's match
            m_pResult = pFile;
        }
    }

    void VisitFolder(Folder* pFolder)
    {
        // Ok, we're visiting a folder.
        // Then iterate over it's 'contained items' and visit them as well
        for (Folder::Iterator it = pFolder->begin(); it != pFolder->end(); ++it )
        {
            // visit item
            (*it)->Accept(*this);
	
            // got a match?
            if (m_pResult)
                break;
        }
    }

    static File* RecursiveSearch(FSObject *pFSObject)
    {
        RecursiveSearchVisitor pRS;
        pFSObject->Accept(pRS);
        return pRS.m_pResult;
    }

private:
    // we store  the result here
    File* m_pResult;
};

int main(int argc, char* argv[])
{
    // create 'root' folder
    Folder* pRoot = new Folder();

    // add child folders
    pRoot->AddItem(new Folder());
    pRoot->AddItem(new Folder());
    pRoot->AddItem(new Folder());

    // add file
    pRoot->AddItem(new File());

    // do the search
    File* pFile = RecursiveSearchVisitor::RecursiveSearch(pRoot);

    return 0;
}

- petter

[jfaust]

Reading this thread, I was also going to suggest the Visitor pattern.

Be aware that having isFile()/isFolder() methods is just as bad as using dynamic_cast<> from a design standpoint. They both result in runtime type checking code.

The Visitor pattern deftly avoid these issues.




Some ruminations:
From an OS standpoint, files and folders are almost the same thing.
From a user standpoint, files and folders are completely different.

I would suggest modeling the user standpoint as it is more natural and easier to think about. To this end, I would completely the base class FSObject, do away with the inheritance, keeping FSFile and FSDirectory completely separate.

A folder is something that contains both folders and other files. This can be modeled rather simply as:

class FSFile
{
   ...
};

class FSFolder
{
private:
   std::vector<FSFolderPtr> m_folders;
   std::vector<FSFilePtr> m_files;
};

Why would you ever need to have a homogeneous collection of files and folders?

Jeff

[screetch]

he wanted to keep the order in which files and folders were added.

[jfaust]

he wanted to keep the order in which files and folders where added.

timestamp?

Jeff

[screetch]

it doesn't change the problem much, you have to order items whether they are files or folders, then treat folders and files differently.

[jfaust]

it doesn't change the problem much, you have to order items whether they are files or folders, then treat folders and files differently.

But that's a different problem, with varying solutions that don't sacrifice the fundamental design. The file/folder relationship is simple and obvious, and should be modeled in a simple and obvious manner.

Using inheritance because you want to order objects by some criteria is not sufficient reason to change this. You are basically using inheritance to make heterogeneous objects appear homogeneous.

Even if you want a base class to maintain access permissions, you'd be better making a base class 'HasAccessPermissions' rather than the miscellaneous bucket class that FSObject will surely become.

Even with a common base class, it's cleaner to keep directories and files in separate containers.

Jeff

[screetch]

yeah i agree with that, see my post above. I advised to keep separate containers for fils and folders, and an order index which helps sorting them.

Having files and folders sorted is not needed often, that's why I really recommand to keep them typed strongly and have a little overhead to recover the order rather than the opposit.

Abstraction is cool, the visitor stuff is cool too, but you'll probably end up having lots of operations working on only files and folder and you'll have a lot of stuff to visit :-/

[treuss]

Thanks Graham for pointing out the visitor pattern and especially wildfrog for the excellent example. Took me some time to grasp the principle, but now it looks like a very elegant way of doing this. However, I am a bit concerned about the overhead, so I will come back after I did some benchmarking of the visitor pattern approach against the static_cast approach.

@ jfaust and screetch: The folder/file thing is meant to be an example. You find tree structures like this in many other places in IT and while you can argue if the order is important in the filesystem, you cannot argue if you are keeping an XML document representation (e.g. DOM) in memory.

There is also a very clear is-a relationship between the items, so breaking the principal pattern of generalization/specialization is certainly going in the wrong direction.

Thanks again everybody for your thoughts.

[Graham]

You might also want to look up Composite pattern as an alternative.

It depends what you want to do, which one you use (or use both):

Composite models the situation you have - heterogeneous entities, some of which are, themselves, containers of those entities;

Visitor provides a way of adding functionalilty to a hierarchy without having to add new member functions to every element. The downside of Visitor is that you need a stable hierarchy - adding a new element involves a lot of work, since every visitor has to be updated for the new class.

[treuss]

[...]The downside of Visitor is that you need a stable hierarchy - adding a new element involves a lot of work, since every visitor has to be updated for the new class.

I can't see that as a real downside, at least not compared to my current way of doing things. If I add a new element, currently I would have to manually search throughout my whole code to find each and every "if (x->isFile())" statement. With the visitor pattern, I can make the function for the new element pure virtual and will have the compiler show me all places where my program needs to be extended. And that is really nice.

BTW, wildfrog, is there a reason why you do not make the functions of FSObjectVisitor pure virtual? I would always prefer that, as it forces me to think about each FSObject subclass, whenever I implement a new visitor.

[jfaust]

Thanks Graham for pointing out the visitor pattern and especially wildfrog for the excellent example. Took me some time to grasp the principle, but now it looks like a very elegant way of doing this. However, I am a bit concerned about the overhead.

The overhead isn't bad: it's a double-dispatch technique, resulting in two virtual function calls. This is usually not an issue.

@ jfaust and screetch: The folder/file thing is meant to be an example. You find tree structures like this in many other places in IT and while you can argue if the order is important in the filesystem, you cannot argue if you are keeping an XML document representation (e.g. DOM) in memory.

There is also a very clear is-a relationship between the items, so breaking the principal pattern of generalization/specialization is certainly going in the wrong direction.

Thanks again everybody for your thoughts.

One last recommendation: boost::variant is a simple object that can be one of several heterogeneous types (a file or a folder). These heterogeneous types can then be stored in a vector.

How you communicate with the actual object is through a built-in visitor interface.

I haven't had the oppurtunity to use this yet, but it looks pretty cool. It may be useful in your case.

Jeff

[TheCPUWizard]

you cannot argue if you are keeping an XML document representation (e.g. DOM) in memory.

Actually by specification, sibling nodes can be presented in any order within an XML document. If you have a document where the ordering of nodes is required, then it is non-conformant!

[wildfrog]

BTW, wildfrog, is there a reason why you do not make the functions of FSObjectVisitor pure virtual? I would always prefer that, as it forces me to think about each FSObject subclass, whenever I implement a new visitor.

What you're saying is probably a good idéa... I was probably thinking of future lazyness.

To have a choice I would probably do something like this:

// pure visitor interface
class IFSObjectVisitor
{
public:
    virtual void VisitFile(File* file) = 0;
    virtual void VisitFolder(Folder* folder) = 0;
};

// default implementation does nothing
class DefaultFSObjectVisitor : public IFSObjectVisitor
{
    virtual void VisitFile(File* file)
    {
    }

    virtual void VisitFolder(Folder* folder)
    {
    }
};

Then depending on the mood I would either inherit the pure interface, or the default implementation.

Actually by specification, sibling nodes can be presented in any order within an XML document. If you have a document where the ordering of nodes is required, then it is non-conformant!

Ok, that may be true for attributes, but I can't see how that fits for child elements, processing instructions, comments etc.

What your're saying is that a XHTML document like this:

...
<body>
    <b>This is </b><i>a test</i>
</body>
...

Is equvalent to

...
<body>
    <i>a test</i><b>This is </b>
</body>
...

And that the browser may choose how to render the page? And what about XML based language like VoiceXML, CCXML etc., are those non-conformant?

- petter

[jfaust]

What you're saying is probably a good idéa...

Definitely a Visitor should have a pure virtual interface. The resulting compile error generated when a new type is added is what separates the Visitor Pattern from type checking. It forces you to consider the new case. Notice that your DefaultFSObjectVisitor does still cause said compiler error.

Now, for the Observer pattern, I use default empty methods since the Observers carefully pick-and-choose what to listen to and often don't care about the other methods (Observers work more like events).

Jeff