Perfect match: Composite and Visitor Pattern


In one of my earliest post, I talked about the importantance of understanding principles of good programming, and the useful-ness of Design Patterns… in this post I intend to share some implementation of some of these patterns. Patterns are something I use from time to time on projects, and something that I’m continuously learning from reading and from others, and still enjoying it very much. Let’s proceed then…

Design Patterns can be categorized into creational, structural and behavioral. I find two patterns that work pretty well together being the Composite Pattern (structural) and the Visitor Pattern (behavior). Composite Pattern is a structural pattern that helps one create tree-like hierarchial structures whereas the Visitor Pattern is a behavioral pattern that allows a visitor object to “visit” each element in a structural hierarchy to perform some operation/behavior on that element.

If this is new to you, we’ll take it one pattern at a time. Firstly the class diagram on the left depicts the Composite Pattern, where a Composite and Leaf Class both inherit from an abstract Component base class. You can look upon a Composite as a tree node which contains children (of type Component) whereas a Leaf is a single node with no children. By recursively walking downwards, you can have build Composites which contains Composities or Leafs, and so on….which results in a tree like structure. I have used this pattern before to building TreeNodes for TreeView, and hierarchy of MenuItems in WinForms.

Composite Pattern
In this example, I’m using a XML document with some made up structure which I will read into an XmlDocument and recursively build a Composite Tree. Here’s what the XML looks like…with some text omitted.

<document>
  <title>This is a explanation of Composite and Visitor Design Patterns</title>
  <body>
    <section>
      <heading>Composite Design Pattern</heading>
<paragraph>In computer science, the composite pattern is a partitioning design pattern.......</paragraph>
<paragaph>Composite can be used when clients should ignore the difference between compositions of objects and individual objects.....</paragaph>
    </section>
    <section>
      <heading>Visitor Design Pattern</heading>
<paragraph>In object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm.....</paragraph>
<paragaph>In essence, the visitor allows one to add new virtual functions to a family of classes without modifying the classes themselves.......</paragaph>
    </section>
  </body>
</document>

It should be pretty easy to figure out which one is a Composite and what’s a Leaf from looking at the XML structure. Let’s have a look at the Component class.

  public abstract class Component
  {
    public Component(string name, string content)
    {
      this.Name = name;
      this.Content = content;
    }
    public virtual string Name { get; private set; }
    public virtual string Content { get; private set; }
    public abstract void Add(Component composite);
    public abstract void AddRange(IEnumerable<Component> composites);
    public abstract void Remove(Component composite);

    //visitor pattern
    public abstract T Accept(IVisitor visitor, T state);
  }

To keep this post succinct, I’m not going to post the implementation of the Composite and Leaf classes, but you can download the source code at the end. If you noticed, there’s a Accept method, which is part of the Visitor Pattern and we’ll go into that later.

Here’s the code that recursively iterates through the XML and build the Composite Tree.

  XDocument xDoc = XDocument.Load(@"..\..\root.xml", LoadOptions.None);
  Component aComposite = CreateComposite(xDoc.Root);

  public Component CreateComposite(XElement node)
  {
    if (!node.HasElements)
      return new Leaf(node.Name.LocalName, node.Value);
    Composite composite = new Composite(node.Name.LocalName, string.Empty);
    composite.AddRange(node.Elements().Select(x => CreateComposite(x)));
    return composite;
  }

Visitor Pattern
Let’s look at the Visitor Pattern.  Since we have two derived classes from the abstract Component class, let’s create an Interface for the visitor that “visits” two of them.

  public interface IVisitor<int>
  {
    T VisitComposite(Composite composite, T state);
    T VisitLeaf(Leaf leaf, T state);
  }

If you remember the Accept(IVisitor visitor, T state) method in the abstract Component class, this method does what it says, which is to accept a visitor. Here’s how the Composite and Leaf classes implement that method.

  // Composite class implementation
  public override T Accept(IVisitor visitor, T state)
  {
    return visitor.VisitComposite(this, state);
  }

  // Leaf class implementation
  public override T Accept(IVisitor visitor, T state)
  {
    return visitor.VisitLeaf(this, state);
  }

There can be many kind of visitors you can create. The main idea of a visitor is such that it will “visit” all the objects you are interested in and perform some kind of operation or behavior to them. I find that the Visitor Pattern really complements the Composite Pattern for just this. For this example, a visitor I can think of is a WordCountVisitor that “visit” each node in my Composite Tree and counts the number of words. So let’s go ahead and create this.

  public class WordCountVisitor : IVisitor<int>
  {
    public int VisitComposite(Composite composite, int state)
    {
        return composite.Children.Aggregate(state, (st, comp) => comp.Accept(this, st));
    }

    public int VisitLeaf(Leaf leaf, int state)
    {
        return state + leaf.Content.Split(' ').Length;
    }
  }

  // using the visitor
  int wordCount = aComposite.Accept(new WordCountVisitor(), 0);

As you can see, VisitComposite method passes itself (visitor) and state to the Accept method of it’s children using the Aggregate function (see my post on Higher Order Functions), and the VisitLeaf method just adds the word count to state. In my code sample, I also created a StringVisitor which uses a StringBuilder, and as it visits each node, the content is appended to a StringBuilder. This is indeed a very simplistic example…but consider slightly more complicated scenarios…what if you need to add a new Leaf node with special content to all Composites where name == “Section”, or a SpellCheckVisitor that checks the spelling of each node’s Content….you get the picture right…

In my opinion, these two patterns are made for each other,  and hopefully you can will find potential usages when the time comes….

Download code sample here.

Share this post :
Advertisements

2 Responses to “Perfect match: Composite and Visitor Pattern”

  1. Andre Marques de Araujo Says:

    It was good one, nice work! And yes, I got tha pictcha!

  2. Pter Says:

    The class diagram above implies that all components have a parent. What about the root of the tree?


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: