When we design any container, our focus should be on data-structure which holds the data but not on algorithms which work on contained data. For instance, STL containers had been designed in such a way that algorithms can be developed independent of data containers. STL achieves this by the concept of iterators and by the uniformity of type of contained elements. Every container that supports iterators, can be used seamlessly in algorithms.
What if the contained elements are of disparate types? Now iterators wouldn't help this situation as types are varying. More importantly, if the contained elements need to be treated differently for different types, even deriving from a same base class wouldn't be much helpful. Consider an example of Shape objects like rectangle and Ellipse. Even though both can be described by Bounding rectangles, calculation of area would differ. So, a common algorithm for area is not possible, even though both are Shape objects. This is one of the scenarios in which Visitor can help.
In a nutshell, Visitor pattern can be used to add a new algorithm to work on a container without modifying the container itself. Now, let us translate the above line in OOP way.
Visitor is a way to add a new behavior to the existing class without modifying the class itself.
Perhaps, this is one more to way to achieve Open-Closed principle of OOP, Let us explore.
Let us implement some trivial examples to proceed further. Implementations are not of production quality; proper memory management is not there. This is just to explain the concepts.
Let us define an interface, IShape from which Rectangle and Ellipse are derived as given below.
struct Bounds
{
Bounds() : left(0), right(0), top(0), bottom(0)
{
}
Bounds(int ileft, int itop, int iright, int ibottom) : left(ileft), top(itop), right(iright), bottom(ibottom) { }
int left;
int right;
int top;
int bottom;
};
class IShape
{
public:
virtual Bounds GetBounds() = 0;
virtual void Draw() = 0;
};
class Rectangle : public IShape
{
public:
Rectangle(Bounds bounds) : currentBounds(bounds)
{
}
Bounds GetBounds()
{
return currentBounds;
}
void Draw()
{
// Draw Rectangle here.
}
private:
Bounds currentBounds;
};
class Ellipse : public IShape
{
public:
Ellipse(Bounds bounds) : currentBounds(bounds)
{
}
Bounds GetBounds()
{
return currentBounds;
}
void Draw()
{
// Draw Ellipse here.
}
private:
Bounds currentBounds;
};
Let us define a Graphics Designer, a composite class for Shapes. At Run-time several shape objects could be added to this toy Graphics Designer and Draw can be invoked to draw all the elements.
class GraphicsDesigner : IShape
{
public:
void AddRectangle(Bounds inBounds)
{
currentElements.push_back(new Rectangle(inBounds));
}
void AddEllipse(Bounds inBounds)
{
currentElements.push_back(new Ellipse(inBounds));
}
void Draw()
{
// Enumerate through the currentElements and Draw each.
}
private:
vector<IShape*> currentElements;
};
Given a class like GraphicsDesigner, How to add a new algorithm to work on contained elements! For instance, we need to find the Minimal rectangle which covers all the elements. In order to achieve this, we would need to add a method in container which enumerates through the elements and execute the algorithm. This violates OOP. And every time, we need to implement a new algorithm, we would end up adding new methods into the container class.
Algorithms are getting bound to the data container.
We will analyse further to understand the problem well.
Adding methods to the container is not a good idea as algorithms just depend upon the contained elements and not on the state of the container.
Needed algorithms can't be defined before hand, just think of possible algorithms on Integers containers, finitely huge, right.
Given that, we need to find out a way to dynamically add the behaviors on to the containers. Without further ado, we will define Visitor pattern and see how it resolves this.
For every algorithm, we should derive a class from Visitor interface; Visitor interface should contain a collection of overloaded Visit methods one for each different types of Visit-able classes. Visit-able classes as per our example, are Rectangle and Ellipse(and general Shape also). Every visit-able class should define a method "Accept".
Let me define a simple PrintVisitor to clarify the needs of all these interfaces.
Before that, given below are the example classes after the changes, made with Visit and Accept interfaces.
class Rectangle;
class Ellipse;
class IShapesVisitor
{
public:
virtual void Visit(Rectangle*) = 0;
virtual void Visit(Ellipse*) = 0;
};
class IShape
{
public:
virtual Bounds GetBounds() = 0;
virtual void Draw() = 0;
virtual void Accept(IShapesVisitor* visitor) = 0;
};
class Rectangle : public IShape
{
public:
Rectangle(Bounds bounds) : currentBounds(bounds)
{
}
Bounds GetBounds()
{
return currentBounds;
}
void Draw()
{
// Draw Rectangle here.
}
void Accept(IShapesVisitor* visitor)
{
visitor->Visit(this);
}
private:
Bounds currentBounds;
};
class Ellipse : public IShape
{
public:
Ellipse(Bounds bounds) : currentBounds(bounds)
{
}
Bounds GetBounds()
{
return currentBounds;
}
void Draw()
{
// Draw Ellipse here.
}
void Accept(IShapesVisitor* visitor)
{
visitor->Visit(this);
}
private:
Bounds currentBounds;
};
class GraphicsDesigner : IShape
{
public:
void AddRectangle(Bounds inBounds)
{
currentElements.push_back(new Rectangle(inBounds));
}
void AddEllipse(Bounds inBounds)
{
currentElements.push_back(new Ellipse(inBounds));
}
void Draw()
{
// Enumerate through the currentElements and Draw each.
}
Bounds GetBounds() { return Bounds(); }
void Accept(IShapesVisitor* visitor)
{
vector::iterator shapeItr = currentElements.begin();
for(; shapeItr != currentElements.end(); shapeItr++)
{
IShape *val = (*shapeItr);
val->Accept(visitor);
}
}
private:
vector<IShape*> currentElements;
};
Now, we will define a simple PrintVisitor to show the power of Visitor pattern.
class PrintVisitor : public IShapesVisitor
{
public:
void Visit(Rectangle* inShape)
{
cout << "This is a Rectangle" << endl;
}
void Visit(Ellipse* inShape)
{
cout << "This is an Ellipse" << endl;
}
};
Of course, "Print" is so trivial to be considered as an algorithm which works on the data. But it clearly avoided the need for having "Print" virtual function in Shape derived classes. Now let us think of a decent algorithm which could work on the data. Let us assume, we need to find the total area occupied by all shapes in GraphicsDesigner. Without Visitor pattern, we would have to add up a new member function in GraphicsDesigner class. But with Visitor pattern, things become very easy that we need to add a new class in Visitor hierarchy as given below.
class TotalAreaVisitor : public IShapesVisitor
{
public:
TotalAreaVisitor() : TotalArea(0.0)
{
}
void Visit(Rectangle* inShape)
{
Bounds bounds = inShape->GetBounds();
int width = bounds.right - bounds.left;
int height = bounds.bottom - bounds.top;
int currentArea = width * height;
TotalArea += currentArea;
}
void Visit(Ellipse* inShape)
{
Bounds bounds = inShape->GetBounds();
int width = bounds.right - bounds.left;
int height = bounds.bottom - bounds.top;
double currentArea = width * height * 3.14 / 4;
TotalArea += currentArea;
}
double GetTotalArea()
{
return TotalArea;
}
private:
double TotalArea;
};
I hope now the need for Visitor pattern is very clear. For every new algorithm, instead of adding a new method in container class, we can add a new visitor. This helps us to achieve one of the SOLID principles, Open-Closed principle. There are disadvantages also like a new Shape derived can't be easily added as it needs modification of all possible Visitors.
So, Visitor pattern trades off the ease of adding new behaviours into Visit-able hierarchy with not easily allowing to create a new derived class in Visit-able hierarchy.
Thanks for Reading.
Thank you, your example is so much more precise and has a hint of realism that the first link on google search doesn't have. Thanks for the excellent example and a lot less formalism. -D
ReplyDeleteits on to point and precise. Great way of explaining complex things in simple way without missing details.
DeleteReallly easy to understand
ReplyDeleteVery good explanation
ReplyDeleterly good example, ty
ReplyDeleteThank You. Good explanation and good example :)
ReplyDelete