Best way to implement performing actions on tree nodes, preferably without using visitors.

Question

Hi, I have a user interface with a tree view on the left, and a viewer on the right (a bit like an email client). The viewer on the right displays the detail of whatever I have selected in the tree on the left.

The user interface has "add", "edit" and "delete" buttons. These buttons act differently depending on what "node" in the tree is selected.

If I have a node of a particular type selected, and the user clicks "edit", then I need to open the appropriate edit dialog for that particular type of node, with the details of that node.

Now, there's a lot of different types of node and implementing a visitor class feels a bit messy (currenty my visitor has about 48 entries....). It does work nicely though - basically for editing a have something like an OpenEditDialog class that inherits the visitor, and opens the appropriate edit dialog:

abstractTreeNode->accept(OpenEditDialog());

The problem is I have to implement the abstract visitor class for every "action" I want to perform on the node and for some reason I can't help thinking I'm missing a trick.

The other way could of been to implement the functions in the nodes themselves:

abstractTreeNode->openEditDialog();

I'm ording the node around a bit here, so maybe this is better:

abstractTreeNode->editClickedEvent();

I can't help but think this is polluting the node though.

I did think of a third way that I've not given that much thought yet. I could have a templated wrapper class that gets added to the tree instead which allows me to perhaps call free-functions to perform whatever actions, so I guess as it acts as a go between for nodes and interface:

(pseudo code off the top of my head just to give an idea):

template <class T>
TreeNode(T &modelNode)
{
    m_modelNode = modelNode;
}

template <>
void TreeNode<AreaNode>::editClickedEvent()
{
    openEditDialog(m_modelNode); // Called with concrete AreaNode
}

template <>
void TreeNode<LocationNode>::editClickedEvent()
{
    openEditDialog(m_modelNode); // Called with concrete LocationNode
}

etc..

So this is effectively extending the nodes but in a different way to using the visitor and it seems a little bit neater.

Now before I go ahead and take the plunge using one of these methods, I thought it'd be wise to get some input.

Thanks! I hope all this makes some sense..

EDIT:

I've mocked up the templated wrapper idea..

class INode
{
public:
    virtual ~INode() {}
    virtual void foo() = 0;
};

class AreaNode : public INode
{
public:
    AreaNode() {}
    virtual ~AreaNode() {}
    void foo() { printf("AreaNode::foo\r\n"); }
};

class RoleNode : public INode
{
public:
    RoleNode() {}
    virtual ~RoleNode() {}
    void foo() { printf("RoleNode::foo\r\n"); }
};

class ITreeNode
{
public:
    virtual ~ITreeNode() {}
    virtual void bar() = 0;
    virtual void foo() = 0;
};

template <class T>
class MainViewTreeNode : public ITreeNode
{
public:
    MainViewTreeNode() : m_node() {}
    virtual ~MainViewTreeNode() {}
    void bar() {}
    void foo() { m_node.foo(); }
protected:
    T m_node;
};

template <>
void MainViewTreeNode<AreaNode>::bar()
{
    printf("MainViewTreeNode<AreaNode>::bar\r\n");
}

template <>
void MainViewTreeNode<RoleNode>::bar()
{
    printf("MainViewTreeNode<RoleNode>::bar\r\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
    MainViewTreeNode<RoleNode> role;
    MainViewTreeNode<AreaNode> area;

    std::list<ITreeNode*> nodes;
    nodes.push_back(&role);
    nodes.push_back(&area);

    std::list<ITreeNode*>::iterator it = nodes.begin();

    for (; it != nodes.end(); ++it)
    {
        (*it)->foo();
        (*it)->bar();
    }

    getchar();
    return 0;
}

Thanks.

Answer 1

Visitor is useful when you have many operations and few types. If you have many types, but few operations, use normal polymorphism.

Answer 2

Such problems are, unfortunately, all too common with C++ and statically typed OO languages in general. I recently stumbled into this article which describes how to implement double dispatch with a custom-made lookup table.

I can see a similar approach working here. Basically, you build a table of function wrappers of the type Entry below:

class EntryBase {
    public:
        virtual bool matches(TreeNode const &node) const = 0;
        virtual void operator()(TreeNode &node) const = 0;
};

template<typename NodeType, typename Functor>
class Entry : public EntryBase {
    Functor d_func;
    public:
        Entry(Functor func) : d_func(func) { }
        virtual bool matches(TreeNode const &node) const {
            return dynamic_cast<NodeType const *>(&node) != 0;
        }
        virtual void operator()(TreeNode &node) const {
            d_func(dynamic_cast<NodeType &>(node));
        }
};

Each such table would then represent one type of Visitor (you can do this without Boost too, of course):

class NodeVisitor {
    typedef boost::shared_ptr<EntryBase> EntryPtr;
    typedef std::vector<EntryPtr> Table;
    Table d_entries;
    public:
        template<typename NodeType, typename Functor>
        void addEntry(Functor func) {
            EntryPtr entry(new Entry<NodeType, Functor>(func));
            d_entries.push_back(entry);
        }
        void visit(TreeNode &node) {
            EntryPtr entry = lookup(node);
            if (!entry)
                return; // this Visitor doesn't handle this type
            (*entry)(node);
        }
    private:
        EntryPtr lookup(TreeNode &node) {
            Table::const_iterator iter =
                std::find_if(d_entries.begin(), d_entries.end(),
                             boost::bind(&EntryBase::matches, _1, boost::ref(node)));
            if (iter != d_entries.end())
                return *iter;
            return 0;
        }
};

Construction of a table would be something like this:

void addToCompany(CompanyNode &company) { ... }
void addToEmployee(EmployeeNode &employee) { ... }

NodeVisitor nodeAdder;
nodeAdder.addEntry<CompanyNode>(&addToCompany);
nodeAdder.addEntry<EmployeeNode>(&addToEmployee);

After all that work, you could simply write (without any additions to TreeNode or any class that inherits from TreeNode):

nodeAdder.visit(someNode);

The templates ensure that the dynamic_cast always succeeds, so it's quite safe. The largest drawback is, of course, that it's not the fastest in the world. But for opening a dialog, the user is probably the slower factor, so it should be quite fast enough.

I just implemented this visitor in my own project, and it is working like a charm!

Answer 3

Instead of using m_node.foo(), what you should do is static inheritance. This is basically your "template wrapper" idea, but it's a well-established pattern.

class ITreeNode
{
public:
    virtual ~ITreeNode() {}
    virtual void bar() = 0;
    virtual void foo() = 0;
};

template <class T>
class MainViewTreeNode : public ITreeNode
{
public:
    MainViewTreeNode() : m_node() {}
    virtual ~MainViewTreeNode() {}
    void bar() {}
    void foo() { m_node.foo(); }
protected:
    T m_node;
};

becomes

class ITreeNode
{
public:
    virtual ~ITreeNode() {}
    virtual void bar() = 0;
    virtual void foo() = 0;
};

template <class T>
class MainViewTreeNode : public ITreeNode
{
public:
    MainViewTreeNode() {}
    virtual ~MainViewTreeNode() {}
    void bar() { T::bar(); }
    void foo() { T::foo(); }
};
class RoleNode : public MainViewTreeNode<RoleNode> {
    void bar() { std::cout << "Oh hai from RoleNode::bar()! \n"; }
    void foo() { std::cout << "Oh hai from RoleNode::foo()! \n"; }
};

Of course, if you already have regular inheritance in the mix, why not just use that? There's not going to be any easier solution than normal polymorphism here. It works well when the number of types is high and the number of operations is low. Perhaps the flaw in your design is how many types you have.

Answer 4

Another pattern to consider here is the Command pattern. You make your nodes store a list of commands that all have GetName & Execute methods. When a node is selected you enumerate the collection and call GetName on each command to get the menu items' name and when a menu item is clicked you call Execute. This gives you ultimate flexibility, you can set up the commands when the tree is created or in each node type's constructor. Either way you get to reuse commands accross types and have varying numbers of commands for each type.

Generally though, my experience would suggest that both this and the visitor pattern are probably overkill in this case and simply putting virtual Add, Edit and Delete methods on the base tree node type is the way to go.