Friday, June 15, 2007

Using Factory Method to Link Parallel Inheritance Hierarchies

Another interesting usage for the factory method pattern is to link parallel inheritance hierarchies. Before getting into this let's examine what parallel inheritance hierarchies are (for a general discussion of the pattern itself please read here):

During design we sometimes have to create inheritance hierarchies which are very similar and pretty much follow the same structure but are designed for different concepts. For example consider the following diagram:



 

The above diagram might be a simple and effective way of explaining the power of inheritance and polymorphism to someone who is starting to learn object oriented concepts but it's definitely poor design in a real system. Let me elaborate: One major concern for the above design is the fact that cohesion (and more specifically technology cohesion) has been ignored. We have implementation code packaged inside a class (i.e. the Circle or Rectangle) class, that although related from a domain perspective (all circle functions in one place and all rectangle functions in another class), are absolutely unrelated from a technology perspective. The technology and techniques needed to save an object to a database (the SaveToDB method) and what is required to display an object on a windows form using the Graphics class (the Draw method) are completely irrelevant to each other. So it looks like we have a design at the logical cohesion level (when unrelated code is implemented in one place due to an arbitrary reason, in this case the arbitrary reason is that they are doing work on the same problem domain concept (i.e. Circle) ).

Although the above design might be considered good from a "domain cohesion" perspective where the designer is only concerned about cohesion from a problem domain perspective, it is an absolute nightmare from a "technology cohesion" perspective. Unfortunately most designers only think in terms of "domain cohesion" and don't bother with "technology cohesion" and this causes many problems down the road. For example once they want to distribute their application on multiple servers or create other similar changes they are stuck with assemblies that don't work in other environments. Consider the fact that the above design basically means that we have got to have database related libraries, windows graphics related libraries, and any other technology that we are using in the above code all as dependencies of our assembly. And if we want to send the above objects (serialized) to some other place where these libraries aren't available we are going to have a problem. It also means that once someone involved in the maintenance of the code needs to change something related to lets say the Draw method they are basically involved in the code related to a lot of different technologies which they might be completely unfamiliar with causing problems during maintenance. And similar issues that arise when you write bad code, period! J

So how can we solve the above problem? One of the solutions that can be used to create technology cohesive design is to put the implementation that uses different technologies into separate but similar inheritance hierarchies. This is only one method to solve it, there are other methods that work a lot better in similar situations, but we are going to investigate this method because it's completely related to this posts discussion. By following this technique we have a set of core objects that contain the data and behaviour related to what the object's true nature is and then other code such as code to save it to a DB or draw it as output on a windows form will be in their own separate classes. So the above diagram becomes something like this:



 

To complete the above design each class in the secondary hierarchies is going to accept as input to it's constructor an object of the core type and will be working on that to do what ever it's expected to do. So for example the RectangleDrawer class will be something like this:


class RectangleDrawer : IDrawer
{
private Shape WorkOn;
public RectangleDrawer(Shape s)
{
WorkOn = s;
}
public void Draw()
{
//use the WorkOn object’s data to draw it.
}
}

In other cases you might decide to pass the WorkOn object to the Draw method, you have to make a decision based on other design factors.

So once we start designing this way the only big question is how do we relate these objects to each other? If you look at the original design drawing an array of Shape objects would have been very simple:


Shape[] shapes = //loaded somehow
foreach(Shape s in shapes)
s.Draw();

What happens in the new design? Here is where the Factory Method pattern can become useful. As mentioned one of the less known but useful uses of this pattern is to relate parallel hierarchies of inheritance. If we create abstract factory methods in the Shape class and hold each subclass accountable for the creation of the related class from the other hierarchy our problem is solved! For example the Shape & Rectangle core objects would look like this:


class Shape
{
public abstract IDrawer CreateDrawer();
public abstract IDBAccess CreateDBAccess();
}
class Rectangle : Shape
{
/* rectangle related code */
public override IDrawer CreateDrawer()
{
return new RectangleDrawer(this);
}
public override IDBAccess CreateDBAccess()
{
return new RectangleDBAccess(this);
}
}

So with the above code, creating similar functionality as the above foreach loop is very easy:


Shape[] shapes = //loaded somehow
foreach(Shape s in shapes)
s.CreateDrawer().Draw();


 

Now the above example is kind of excessive in its use of this pattern and in a similar situation (a CAD application or a Drawing app) you probably have other issues involved that would prevent such a design but it provides a good example of what parallel hierarchies of inheritance are and how to relate them.

As a final note I should mention that the above code doesn't fix the un-needed assembly reference issue mentioned as the problems with bad technology cohesion, since our core classes (Shape, Rectangle, etc.) will need to reference the assembly containing the Drawer (RectangleDrawer, …) classes & the DBAccess (RectangleDBAccess, …) classes and those assemblies would in turn access the technology related libraries. So in other words the above example has only fixed the problem from a code separation point of view (putting technology specific code in its own assembly), but it hasn't solved the dependency issue.

Solving the dependency issue can be achieved by using another pattern in between the core objects and the actual classes doing the technology related work which will eventually use reflection to load the technology specific assemblies that it needs on demand. A good example would be the prototype pattern so the core objects would only ask a general purpose prototype factory to create what they want. The prototype factory and the abstract interface (such as IDrawer & IDBAccess) would be in an independent assembly that the technology specific assemblies will use. In this solution the core objects are only dependent on some independent assemblies that can be taken anywhere and are not physically related to the technology specific assemblies. This diagram better shows the assemblies and their relations:



 

Obviously the technology specific assemblies must be present for the technology specific functions (such as Draw or Save) to work. But the good thing is that we would only have to deploy them on the hardware or location that they will actually be used. So for example the back end server doesn't need the Drawer assembly while the front end UI (client side) probably doesn't need the DBAccess assembly.

Friday, June 8, 2007

Factory Method

Factory Method is an extremely simple yet very useful design pattern. I'd rather call it a simple programming technique. A technique that might be second nature to most people designing OO these days but since it's part of Gamma's design patterns book, albeit a terse discussion, I'd rather talk about it here since I know it will come up in other discussions that I'm planning on posting down the road.

The factory method pattern is based on a simple concept: I'll call you when I need to create something. Unlike other patterns we have discussed where the client code will use the results of the pattern to do something, the factory method's client code is usually a class which extends the abstract class available in this pattern and the abstract class will call the client code whenever it needs a new object. For a simple definition please see here.

The best example (which you usually find in any discussion in regards to this pattern) is the Application framework example. For those who are familiar with MFC and have used it during their Visual C++ days or for those who had worked with Borland C++ (for Windows) this example is quite familiar. You are designing an application framework which will handle most generic application functionality. Stuff like bringing up the open dialog when the user chooses File – Open or taking care of 'Save As…', toolbars, status bar etc. But this application framework wouldn't be able to do anything useful since it's just a framework. The person responsible for the actual development of the concrete requirements would take the framework, probably inherit from it and fill in the blanks for example when the actual save happens (after the save dialog has been taken care of etc.) write the information needed to the file. Write the program logic and things like that.

This application framework can be reusable and developed independent of any specific requirement or domain due to the fact that it leaves the details out for the person doing the implementation based on the framework. One of the things that the framework needs is documents created whenever the framework needs them or in the case of the MFC framework Views were also another example. So we have some logic at the framework level that takes care of different things but this logic is unable to finish the job unless we (the class extending the framework) create the specific product that we need and hand it back to the application. This is one of the major uses of the factory method pattern. Let's take a look at all this discussion from a programming point of view:

When I'm developing the application framework I would write code like this:


abstract class Application
{
/* complex logic in relation to how the application will work
during this complex logic at some points I need the document
class so I call CreateDocument() and use whatever is returned
*/
protected abstract Document CreateDocument();
}
abstract class Document
{
/* abstract and concrete methods implementing the Document class */
}

When a developer comes along and wants to use my framework to create an actual application and provide the logic for that application's specific requirements they would write this:


class MyApp : Application
{
/* logic related to this application’s specific requirements. Some of this
logic might be new methods and others will be overrides of the base
classes methods.
*/
protected override Document CreateDocument()
{
return new MyDoc();
}
}
class MyDoc : Document
{
/* implementation related to this application’s requirements */
}

It's quite obvious from the above code that this pattern is relying on a very simple concept: polymorphism. But there are a couple of interesting things in regards to the way this is used:

Use of this pattern will provide a simple alternative to other creational patterns where you need to provide future users of a class (or framework) that you develop to decide what type of a product will be created and used.

It's very important to only use this pattern in scenarios where the inheritance is natural and due to other design decisions not specifically because of the use of this pattern. In other words if in the above example I had to create a subclass of the Application class only to override the CreateDocument method it would have been too much work and wouldn't have made any sense. But if I had to do the inheritance for other reasons (i.e. needed to override other methods and extend the general functionality provided by the base class) then using this pattern to create a flexible creation mechanism is a good choice.

In every single scenario that you can use this pattern you can also use the abstract factory pattern. Obviously it's not a good choice to use the abstract factory pattern in place of this pattern every time but it's good to know that this pattern doesn't really add anything to your patterns repository except for the fact that it's a simplification of the abstract factory pattern which you can use in special occasions. Let's examine this in more detail:

What happens with this pattern is that the client code from the abstract factory pattern and the abstract factory itself are squished together to form the Abstract Creator (the Application class in the above example) of the pattern. So in every example you can do the re-design using abstract factory with this pattern by simply separating these two pieces. Let's assume that we want to take the above example and re-design it using the abstract factory pattern. Here is what we get:


class Application
{
/* the logic related to app.
when ever this class needs a Document
it will call Creator.CreateDocument();
*/
public DocumentAbstractFactory Creator = //initialized in some way that fits your problem
}
abstract class DocumentAbstractFactory
{
public abstract Document CreateDocument();
}

As you can see we re-configured the Application class to call an abstract factory that we have configured into the Application object (Creator). So the person extending this framework to create specific Documents (such as MyDoc) would need to create a concrete factory class that implements the CreateDocument method and somehow configure the Application object to use that specific Concrete Factory.

To wrap things up I should add that usually the requirements of the problem we are trying to solve will point us to either the Abstract Factory pattern or the Factory Method pattern so we should be careful to analyze the requirements in detail but it's comforting to know how close these two patterns are. Just to help you decide here are my criteria for deciding between these two patterns:

  1. Use the factory method pattern when you want to allow future programmers to extend a class and provide different products for the class's use. The sub-classes created should be because of other decisions and not the use of this pattern.
  2. In scenarios where multiple products exist or multiple product families exist and there is going to be switching between the different families based on specific criteria the use of abstract factory is usually much more helpful.
  3. If you want to map two parallel hierarchies of inheritance to one another the factory method pattern will help a lot. I will discuss this in future posts.
  4. If you get stuck and can't decide use the abstract factory pattern. You might have to write a little bit more code but you have a whole lot more flexibility.

Thursday, June 7, 2007

Mt. Damavand

Cool photo taken from Mt. Damavand by NASA. The summit is 5671 meters. The highest summit in the middle east. Enjoy!

Tuesday, June 5, 2007

Deep Copy vs. Shallow Copy

The concept of deep vs. shallow copy is one of the decisions that a designers/programmers make on a daily basis yet in my tutoring experience I've seen a lot of people who don't know it by this name or aren't familiar with all the issues & techniques that relate to this issue. This topic is also one of the issues that needs to be thought about and decided when a designer want to use the prototype design pattern.

The question of deep vs. shallow copy usually pops up when a designer has to create a copy (or clone) method for a class that he/she has designed. When creating the clone method (especially when it relates to the prototype pattern) the designer has to decide between these scenarios:

  1. The clone method is only going to create an object exactly the same as the current object but no data copying happens (the simple case of the prototype pattern).
  2. The clone method is going to create an object exactly the same as the current object and is also going to copy the current object's data into the new object.

The second decision will create the deep vs. shallow dilemma. To show the difference let's examine a simple example:



As the example above illustrates the car's member data are body and engine. Body has its own member data, so does engine but the Engine class is also specialized with two different sub-classes. Now suppose we have created an instance of the Car class, filled it with the right information and now we want to copy it. For example:



Car c1 = new Car();
c1.MaxSpeed = 240;
c1.body = new Body();
c1.body.NumOfDoors = 2;
c1.engine = new FastEngine();
c1.engine.CapacityInLiters = 2.0;
Car c2 = MakeCopyOf(c);

The MakeCopyOf() method is responsible for copying the car. Or better yet if our Car class has implemented the ICloneable method then the above line of code will look like this:

Car c2 = (Car)c.Clone();


 

Now the question of how to implement the Clone (or the MakeCopyOf) method. This is where deep and shallow copies come into play. If you implement the Clone method like this:



class Car : ICloneable {
public Body body;
public Engine engine;
public int MaxSpeed;

public object Clone() {
Car c = new Car();
c.MaxSpeed = this.MaxSpeed;
c.body = this.body;
c.engine = this.engine;
return c;
}
}

You have implemented the shallow copy method. It's called shallow copy because your copying only makes sure that the new object has a copy of the current object's memory space. It doesn't really care what the current object's memory space is composed of and if it contains references to other objects it doesn't try to duplicate those other objects either. To explain this better, take a look at the following diagram. It shows the original Car object (c1), its memory space and the fact that the memory space is filled with data (MaxSpeed) & references (body & engine).



Now when you clone the above object and get c2 using the method described above we are only copying whatever is in the c1 memory space into the c2 memory space. This will mean that the data are being copied fresh into the new space, so are the references, but when we manipulate the data held in an object being referenced by the new c2 we are actually changing the same data that c1 is using too. So if I write this code after creating the c2 object:

c2.MaxSpeed = 300;
c2.engine.CapacityInLiters = 2.5;

The change to MaxSpeed is only a change to the c2 object but the change to the c2 engine's capacity also affects c1. The following diagram better explains this:



As can be seen in the above diagram in the case of a shallow copy the objects referenced by the first object are shared between the two objects.

Now this can be a very good thing in many situations: Imagine you have a Receipt object and that Receipt object is referencing a Customer object (for which the receipt was created for), then you make a copy of the Receipt basically to change a few items, prices, etc. and re-save it as a new receipt. In this case you don't want a separate Customer object but you want the Customer object to be shared between the two receipts. That's what the requirements and the problem domain are dictating to us so we use Shallow copy.

As most of you .net developers know there is also a an easier way to implement a shallow copy and that's to use the MemberwiseClone() method. This protected method which is implemented at the object level can be used to create an exact copy of the current object (but a shallow copy) so when all we need is a shallow copy the Clone method is usually implemented like this:


class Car : ICloneable {
public Body body;
public Engine engine;
public int MaxSpeed;

public object Clone() {
return this.MemberwiseClone();
}
}

Other situations do occur in design where a shallow copy will not do, we want the full graph of objects to be copied over and a new graph created so any change to any object in the graph will not affect the previous copy. Suppose in the previous example we wanted to make a copy of the receipt object with all other objects attached so we are sure that we can recover any changes made to the original objects by other pieces of code. In this case we need to perform a deep copy. The deep copy will ensure that the full graph of objects will be copied and a new object graph created.

Going back to the previous car example once we do a deep copy the second car would be a new object with a new engine etc. So changes to the direct fields of the car object or any of the objects it points to (or the objects they point to etc. etc.) are going to be separate from the original copy. So the following piece of code will only change c2's engine capacity:


c2 = c1.DeepCopy();
c2.MaxSpeed = 300;
c2.engine.CapacityInLiters = 2.5;

Now assuming that all the objects in the graph we are going to clone (using deep copy) have implemented the ICloneable interface we can implement our clone method like this:


/* Deep copy clone */
class Car : ICloneable {
public Body body;
public Engine engine;
public int MaxSpeed;

public object Clone() {
Car c = (Car)this.MemberwiseClone(); //create a copy so everything comes across
c.engine = (Engine)engine.Clone(); //for properties that are objects call their clones to get a deep copy
c.body = (Body)body.Clone(); //for properties that are objects call their clones to get a deep copy
}
}

Obviously the above code will only produce a deep copy if the clone methods of engine & body also perform a deep copy. So usually when we have related objects the decision to perform a shallow or deep copy is one that has to be made for that graph of object together. As a designer you might even face situations where you would prefer to implement both deep and shallow copy in one class and use the appropriate clone as needed.

When deciding to use deep copy there is usually a problem to consider: If the graph of objects we want to perform a deep copy on have a cycle implementing the deep copy isn't going to be easy. A cycle occurs when multiple objects reference each other so that these references create a closed circuit. This could be as simple as two objects pointing to each other or a complex path between objects which eventually turns around and points at the original object. Usually when we have two way referencing linked lists or trees we are faced with this issue or any other fairly complex data structure where direct traversal between the elements in the structure in both ways is needed. For example let's say we have a Company class which references multiple Department objects which in turn hold multiple Employee objects. But for some reason the designer has decided that each Employee should also know (directly) which company it works for. So you have a design like this:



Now if we implement a deep copy where each object is going to clone itself by calling the clone of the objects it holds reference to, we will get into a never ending loop and obviously this solution will not work.

As far as deep copy complexity is concerned the above issue also happens when you don't have a cycle but have multiple objects referencing the same object, so again in the above example suppose we had department holding a collection of its employees and the company also holding a collection of all its employees. The employee objects where referenced by the department and by the company so if we tried to clone a graph of objects starting at company we would get two sets of employees (the ones that the departments reference and the ones that the company references). Obviously this wasn't what we wanted either, we wanted one company object referenced by both the company and the department it belongs to.

In these scenarios the designer must either change the way he/she is looking at the problem and consequently the solution. In other words come up with a solution where a deep copy is not needed or we can recalculate one of the links based on some other data therefore not needing Clone across that link and breaking the infinite loop. Alternatively he/she can accept the little more complex scenario of implementing deep copies as described below:

Another more elaborate (and more costly) solution would be to pass a context object along to every clone method. The context object will hold all the original objects that have already been cloned and what they have been cloned to. This way wherever in the cycle of objects we start a clone the whole network will be cloned once and only once. A perfect context for these scenarios is the Dictionary generic collection (or the Hashtable class). So for example the clone of the above mentioned Employee class would look like this:



class Employee : ICloneable
{
/* other properties that we don’t care about */
public Company company;
public object Clone()
{
return Clone(new Dictionary()); //create an empty context and start cloning
}
public Employee Clone(Dictionary context)
{
Employee e = this.MemberwiseClone();
context.Add(this, e);
If (context.ContainsKey(company))
e.company = (Company)context[company];
else
e.company = (Company)this.company.Clone(context);
return e;
}
}

Now before I get into the other classes' code (which would be very similar to the above) let's see what happened. The original Clone basically means that a client code has called and started the clone recursive call. This original clone will create an empty context and call the clone that is context aware. The context aware clone will lookup the company object (the object that might be the cause of the infinite loop) in the context, if it doesn't exist it means that it hasn't been cloned yet, so clone it and use the newly created company in the output, otherwise just use the previously cloned object that is stored in the context. As can be seen the context will get filled by each object after it creates a shallow copy of itself (before getting into anymore clones). This is the only place where we can be sure that this object hasn't been used anywhere else (yet) and it's immediately after the new object has been created (albeit incomplete: it's still only a shallow copy) so let's add the old object (which other objects might be referencing) to the context alongside it's new version, since the reference to the new version isn't going to change it's not going to cause a problem for others and we will complete the new version's other members (such as company in this example) afterwards.

Let's take a look at the other classes:


class Company : ICloneable
{
/* other member variables */
public List departments = new List();
public object Clone()
{
return Clone(new Dictionary());
}
public Company Clone(Dictionary context)
{
Company c = this.MemberwiseClone();
context.Add(this, c);
c.departments = new List();
foreach(Department d in departments)
{
if (context.ContainsKey(d))
c.departments.Add((Department)context[d]);
else
c.departments.Add(d.Clone(context));
}
return c;
}
}

class Department : ICloneable
{
/* other member variables */
public List employees = new List();
public object Clone()
{
return Clone(new Dictionary());
}
public Department Clone(Dictionary context)
{
Department d = this.MemberwiseClone();
context.Add(this, d);
d.employees = new List();
foreach(Employee e in employees)
{
if (context.ContainsKey(e))
d.employees.Add((Employee)context[e]);
else
d.employees.Add(e.Clone(context));
}
return d;
}
}

The above code guarantees the fact that if you call Clone() on any object in the above graph the whole graph will get duplicated without creating any object more than once.

Let's also examine another alternative to the above deep copy problem:

Readers familiar with .net's serialization technology know that the above deep copy can also be achieved among object graphs which have serializable objects. Just serialize one of the objects in the graph and then deserializing it. In other words you can create a deep copy of objects without the need for the ICloneable interface and the time consuming implementation mentioned above by simply using the technology available (the only drawback being the fact that the serialize/deserialize technique is a lot slower than the above code.

So let's say we had the following three classes:


[Serializable]
class Company
{
/* other fields */
public List departments = new List();
}
[Serializable]
class Department
{
/* other fields */
public List employees = new List();
}
[Serializable]
Class Employee
{
/* other fields */
public Company company;
}

So assuming we have the above serializable classes we can create a deep copy of any graph of the above design using serialization:


Company c = //assume we have a fully loaded company with departments and employees;
MemoryStream ms = new MemoryStream();
new BinaryFormatter().Serialize(ms, c);
byte[] data = ms.ToArray();
ms = new MemoryStream(data);
Company c2 = (Company)new BinaryFormatter().Deserialize(ms);
 

Three problems exist with the above technique:

  1. It's slow.
  2. All objects have to be serializable.
  3. Since we are using .net's serialization routines all attributes (or at least attributes that has been marked as serializable) will be copied while in certain custom deep copy implementations we might want to control what gets copied and what is reset in the new object.