Dr.Bob's C++Builder Gate: C++ Patterns and trees: separating knowledge

Delphi Clinic

C++Builder Gate

Training & Consultancy

Delphi Notes Weblog

Dr.Bob's Webshop


	C++ Patterns and trees: separating knowledge
See Also:	C++Builder Papers and Columns

In my dealings with C++ projects, a number of times I encountered the question of how to separate an object model of the world from its graphical representation, in particular, how to separate a tree-like structure of objects of different classes from a tree-like representation in a graphical user interface. After browsing around in Gamma, I stumbled among others on the Visitor pattern. Gamma tells us that we can use a Visitor to add operations to a class without adding an operation to the class interface itself. If you know the content of Gamma, you will know the patterns involved here: Composite and Visitor.

Composite
A Composite is a tree structure consisting of individual objects mixed with compositions of objects, that is, objects that have other objects as their children. The goal of the Composite pattern is to be able to treat individual objects and compositions of objects the same way. All objects in the Composite are derived from Composite itself.

Visitor
A Visitor is an object that adds an operation to a class without modifying that class. As a bonus, you can have your compiler determine which method must be called in the Visitor. Using a technique called double dispatch does this. Generally, Visitors are implemented as follows:

Every class has a virtual method Accept(Visitor& visitor)
For every concrete class that has Accept, the Visitor has a method VisitX(X* anX), where X marks the spot of the classname. So, if X is a Foo, the method is VisitFoo(Foo* aFoo).
An object of class Visitor is passed to the Accept method.
Accept immediately calls VisitX, passing the this-pointer as an argument

For example for a Composite:

  class Composite;
  class Component;  //  IS_A Composite
  class Leaf;       //  IS_A Composite

  class Visitor
  {
  public:
    virtual void VisitComponent(Component* object);
    virtual void VisitLeaf(Leaf* object);
  };

  class Composite
  {
  public:
    virtual void Accept(Visitor& visitor) = 0;
  };

  class Component: public Composite
  {
  public:
    virtual void Accept(Visitor& visitor);
  };

  class Leaf: public Composite
  {
  public:
    virtual void Accept(Visitor& visitor);
  };

  void Composite::Accept(Visitor& visitor)
  {}

  void Component::Accept(Visitor& visitor)
  {
    visitor.VisitComponent(this);
  }

  void Leaf::Accept(Visitor& visitor)
  {
    visitor.VisitLeaf(this);
  }

Drawing
As you might suspect, drawing an object from a tree that is structured after the Composite pattern is not exactly an operation you would like to add to the classes of the composite tree itself. For this purpose, we can use a Visitor. Using the Visitor pattern, we are able to specify exactly how an element from the tree looks like based on the class of the object the Visitor object is sent to. This makes our Visitor some sort of intermediary between that part of your code that fills a TTreeView and an abstract treelike structure that represents part of your program logic. Ergo:

  class DrawTreeVisitor: public Visitor
  {
  public:
    DrawTreeVisitor(TTreeView* theView);

     virtual void VisitComposite(Composite* object);
     virtual void VisitLeaf(Leaf* object);

  private:
    TTreeView* view;
  }

However, we are not done yet, because we need to have a method to traverse the tree in order to build the content of the TTreeView. Why? Because we would not want to add all knowledge about tree traversal in the Composite class hierarchy.

Traversal
Traversal of trees are well known algorithms. What we would like to do is to traverse a tree and send a Visitor to each node we encounter while traversing the tree. We already have two things, the Composite tree and the Visitor class. We now need a class that can do the traversal for us. What we do is use the interface of a Composite object to find out if it has children and to find out what those children are. For example:

  class Composite
  {
  public:
    bool HasChildren;
    CompositeIterator FirstChild();
    CompositeIterator LastChild();
  };

We can use these three methods of Composite to find out what we want. Now we can make the Algorithm class like this:

  class Algorithm
  {
  public:
    Algorithm(Visitor* theVisitor, Composite* theComposite);

    void Execute();

  protected:
    virtual void FindNextNode();
    virtual void SendVisitorToNode(Composite* theNode);

  private:
    Visitor*   visitor;
    Composite* current;
  };

The connoisseurs among us will see the Pattern applied here. Exactly, Template Method. What we do in the Execute member is to traverse the tree in a certain way by repeatedly and if necessary recursively calling the FindNextNode member. Every time we encounter a node, we call the SendVisitorToNode method. What we do in this method looks like:

  void Algorithm::SendVisitorToNode(Composite* theNode)
  {
   theNode->Accept(visitor);
  }

What we do with the Algorithm class is to specialize it and thus adapt it to our needs. If you want a different traversal algorithm, we implement that in the FindNextNode method of the Algorithm class. If we want to do some preprocessing or postprocessing before and after sending the Visitor object to the Composite object, we can do so in the SendVisitorToNode method of a derived class.

Conclusion
What we did here is apply the knowledge of patterns succesfully to divide separate pieces of knowledge about the world we model. We used the Visitor pattern to mediate between the world of TtreeView and our internal Composite tree. Furthermore, we successfully separated the knowledge about tree traversal from the tree itself.

Bibliography
Design Patterns, Elements of Reusable Object-Oriented Software, Gamma et al., Addison Wesley, ISBN 0-201-63361-2