Becoming a Code Surgeon: Using Objects to Delegate Responsibility

The Object-Oriented Space Invaders project is a project that I like to revisit from time to time. I find that each time I do I come up with different ways to solve problems that hadn’t previously occurred to me. This post will deal with one of these solutions which I recently came up with. It’s an interesting and simple way to address the first really vexing issue I encountered in my initial experience with this project, and object-oriented design in general. It involves the use of objects to delegate behavior, a trick which I have begun to use more often as the situation allows.

Before I get into the solution we first need to talk about the problem. This project uses object pooling extensively to avoid the cost of object creation while the game is running, instead creating objects before the game begins and reusing them. This is accomplished through the use of an abstract class, Manager, which defines the basic object pooling behaviors and which holds abstract objects, DLinks (which stands for Double Link) storing them in one of two doubly linked lists depending on whether an object is currently active or being held in reserve. Each pooled object derives from DLink and each specialized object manager derives from Manager, implementing behavior specific to the type of derived DLink that they hold. The following diagram shows this relationship using SpriteBatches as an example. If you didn’t already know, a Sprite is what draws a picture on the screen in a video game. SpriteBatches are just an object in this game that serves to group Sprites and invoke Sprite behaviors on these groups. Note the diagram omits some data fields / methods for clarity and conciseness.

As you can see, SpriteBatchManager derives from Manager and holds SpriteBatches which derive from DLink. Every Sprite has an Update() and Draw() method which must be called each frame if we intend to have it appear on screen. Granted sometimes we don’t want every Sprite to be drawn, but that’s a topic for another discussion. For simplicity let’s assume that each Sprite will be updated and drawn each frame. Every Sprite would be in some SpriteBatch, whose Update() and Draw() methods iterate through their Sprites and call their respective Update() or Draw() methods. Likewise the SpriteBatchManager’s Update() and Draw() methods iterate their batches and call the respective SpriteBatch method. But look again at the diagram. There is a problem here, specifically a problem of visibility. The list to be iterated and acted upon (the active list) is private to the Manager base class! After all, the Manager class is responsible for all object pooling and “creation / destruction,” so it is the only class that should have access to these lists. The SpriteBatchManager has no way of accessing this list to iterate it, and the Manager class has no way of knowing that this particular derived class holds SpriteBatches. So how can we deal with this? I’m going to walk through some naive workarounds first, talk about their shortcomings, then talk about my solution.

The first is the most straightforward. This is to simply change the visibility of the active list to protected so the SpriteBatchManager can get to it. It would look like this (changes in bold).

Now the SpriteBatchManager can grab the list and iterate through it. But is this a good thing? No. Why? It completely breaks the encapsulation of the list provided by the Manager class by giving the head of the list to the derived class and opens up the possibility that the derived class may alter the list in some way. Take the following for example:

class SpriteBatchManager : Manager
{
    public void Draw()
    {
        DLink head= this.activeList;
        SpriteBatch current = (SpriteBatch)head;    // cast is ok, all SpriteBatches are DLinks

        // bad behavior follows
        if (current.next != null)
        {
            current.next = null;                    // now the rest of the list is lost forever
        }

        while (current != null)
        {
            current.Draw();
            current = (SpriteBatch)current.next;    // current.next is still a DLink
        }
    }
}

In reality the mistake likely wouldn’t be an intentional act of sabotage like the above, but the point stands. By providing visibility of any list to the derived class that will be used by the client we open ourselves up to bad behavior, accidental or intentional. It so follows that the last thing we want to do is to pass the list to the derived class, due to the violation of data encapsulation, delegation of responsibility and the resulting risk of corruption. In fact, Bjarne Stroustrup says in the C++ Programming Language (pg. 604), “In particular, declaring data members protected is usually a design error.” And I doubt anyone reading this is in a position to argue with the creator of C++. So what other options do we have? Well, the previous train of thought sought to put both the iteration of the list and task execution in the derived class. What about trying to put it in the base class? What would this look like?

First, we would need to provide some sort of contract from our derived objects that will be acted upon, either through the form of abstract classes or interfaces. They both have pros and cons. Abstract classes can provide virtual function implementations, but most languages provide only single inheritance leading to potentially long inheritance chains. Interfaces provide no default implementation but offer something closer to the multiple inheritance of C++, at least as far as functions are concerned. Either will work for this case. Let’s use abstract classes for this example, but keep in mind the exact same thing can be achieved through the use of interfaces. The basic modeling of such would look as follows:

As you can see, the SpriteBatches now have two additional classes in their inheritance chain that provide some abstract methods for Update() and Draw() that SpriteBatch will implement. Manager has also picked up a few new protected methods, baseUpdate() and baseDraw(). Note that protected methods don’t pose the same problem as protected data members because they simply extend functionality. Let’s take a quick peek at what these may look like.

abstract class Manager
{
    protected void baseUpdate()
    {
        Updateable u;
        DLink current = activeList;

        while (current != null)
        {
            u = (Updateable)current;
            u.Update();
            current = current.next;
        }
    }

    protected void baseDraw()
    {
        Drawable d;
        DLink current = activeList;

        while (current != null)
        {
            d = (Drawable)current;
            d.Draw();
            current = current.next;
        }
    }
}

Then any derived class that holds Updateable or Drawable objects can provide public methods that call these base methods, like so:

class SpriteBatchManager : Manager
{
    public void Update()
    {
        this.baseUpdate();
    }

    public void Draw()
    {
        this.baseDraw();
    }
}

While this doesn’t provide list access to the derived class, it’s still not a good solution. Why? Well, the primary reason is that these base methods are available to every derived manager class, regardless of whether or not the objects they hold derive from / implement Updateable or Drawable. In this specific case its fine because SpriteBatch is both an Updateable and a Drawable. But what if it were not? Calling these methods would result in some type of invalid cast exception that will either kill the program (bad) or have to be caught (which is slow, also bad). Also of concern is that Manager will need a processing method for every type of derived DLink behavior, which will eventually result in the class becoming bloated with a ridiculous number of processing methods used by only a small number of derived Managers. Additionally, it is now aware of and responsible for calling operations that derived DLink classes will be performing, which should be the concern of the derived managers. It still breaks the inherent delegation of responsibilities. Manager should be responsible primarily for the lifetime of the objects (ie: managing them) and anything having to do with the lists, the derived Managers should be responsible for anything specific to the derived DLink objects. By shifting the traversal and task execution to the base Manager class, we have solved the problem of list visibility but not that of delegation of responsibility. In essence all we have done is over-correct the problem, and while this solution is a shade better, it is still not desirable.

What exactly would a desirable solution entail? Both previous solutions suffer from muddled delegation of responsibility in that one entity is trying to both iterate and specify the action to be performed on list objects, when in reality the base class should be responsible for iteration of the list, since it owns it and is the only object that should be able to access it, and the derived class should be responsible for defining how to treat the objects that comprise the list, since it is the object with knowledge of what type of derived DLink the list is made up of. These two acts, traversal and action, comprise any sort of processing that will need to be performed. In pseudocode it would look like this:

void process()
{
    node n = list head;
    while (terminate condition not met)
    {
        process n;
        n = n.next;
    }
}

It would be ideal to only write the traversal loop once and then only have to write the code that will be performed on the nodes as needed. This traversal loop would live in the base Manager class and the action definition would live in the derived Manager classes as it would be specific to the types of derived objects they manage. Also, as loop termination conditions will vary between derived Managers (not all Managers will process every node, some only process up to a certain node) these can also be defined in the derived class. The goal is to extract the pieces of code from the processing loop that will change and write them on an as needed basis. This is what the DRY (Don’t Repeat Yourself) principle advocates. In short, we want to be as lazy as possible. But how? This is what I propose.

Let’s put the main processing loop in the base class, define a contract for an object that will specify the behavior that will change and that this loop will depend upon, then pass that object from the derived class up to the base class whenever processing is necessary. What does this object need to specify? Just two things: what will be done to a node and when to stop doing it. And since it’s only going to be used by Manager and implemented by derived Managers we should probably make it a nested, protected class. Looks like this:

abstract class Manager
{
    protected abstract class ProcessingObject
    {
        public abstract bool Continue(DLink node);    // when do I stop?
        public abstract void Process(DLink node);     // what do I do?
    }

    protected void baseProcess(ProcessingObject derivedBehavior)
    {
        DLink current = activeList;
        DLink next;

        while (derivedBehavior.Continue(current))
        {
            next = current.next;    // processing might involve removal, grab next node now
            derivedBehavior.Process(current);
            current = next;
        }
    }
}

Using this, let’s implement Draw in SpriteBatchManager.

class SpriteBatchManager : Manager
{
    // define behavior object
    private class DrawBehavior : ProcessingObject
    {
        public override bool Continue(DLink node)
        {
            return node != null;
        }

        public override void Process(DLink node)
        {
            SpriteBatch batch = (SpriteBatch)node;    // SpriteBatchManager only holds SpriteBatches, this is safe
            batch.Draw();
        }
    }

    // Data
    private ProcessingObject drawBehavior;

    // Ctor
    public SpriteBatchManager()    
    {
        this.drawBehavior = new DrawBehavior();
    }

    public void Draw()
    {
        this.baseProcess(this.drawBehavior);
    }
}

As you can see it is rather straightforward. First we define the object, again using a nested class, although private in this case since it deals with SpriteBatch processing behavior which the SpriteBatchManager is responsible for, so it doesn’t need to be created anywhere else. SpriteBatchManager owns an instance of it and passes it to the base processing method when it calls Draw. Implementing Update would look the exact same only it would create a different ProcessingObject that would call Update in the Process() method. Now our UML looks like this.

This allows the processing loop to be written once in the base Manager with the derived managers defining the condition to stop processing and what to do. But the idea can go further. A common task in Managers is searching for a particular active node. This behavior can also be implemented following this scheme, by breaking out the comparative operation and delegating it to the derived manager class through the use of an object. For example, SpriteBatches each have a unique Type enum which is used in find operations. The compare object is responsible for casting the base DLink class to the derived type and comparing its Type enum to the search target, specified beforehand. It is as follows:

public abstract class Manager
{
    protected abstract class Comparator
    {
        public abstract void SetTarget(object toCompare);
        public abstract bool Compare(DLink other);
    }

    protected DLink baseFind(Comparator compareBehavior)
    {
        DLink out = null;
        DLink current = activeHead;

        while (current != null)
        {
            if (compareBehavior.Compare(current))
            {
                out = current;
                break;
            }

            current = current.next;
        }
        return out;
    }
}

public class SpriteBatchManager : Manager
{
    private class BatchTypeEquals : Comparator
    {
        // Data
        private SpriteBatch.Type target;

        public override void SetTarget(object toCompare)
        {
            this.target = (SpriteBatch.Type)toCompare;
        }

        public override bool Compare(DLink other)
        {
            SpriteBatch batch = (SpriteBatch)other;
            return target == other.GetBatchType();
        }
    }

    // Data
    private Comparator batchTypeEquals;

    // Ctor    
    public SpriteBatchManager()
    {
        this.batchTypeEquals = new BatchTypeEquals();
    }

    public SpriteBatch Find(SpriteBatch.Type target)
    {
        this.batchTypeEquals.SetTarget(target);
        DLink result = this.baseFind(this.batchTypeEquals);

        return (SpriteBatch)result;
    }
}

The above shows one thing that I really like about this approach, which is the ability of these objects to hold data as they are passed up to the base Manager class. Since this is in C#, the SetTarget method takes the highest level object, object, and the implementation will cast it to whatever data type the derived Comparator holds. Another thing that I find appealing about this approach is that while the derived managers all have access to the baseProcess / baseFind methods, they cannot be called unless the author deliberately implements a ProcessingObject / Comparator to pass as an argument.

This approach satisfies the aim to delegate responsibilities between base and derived Manager classes without breaking encapsulation. It is also language agnostic among any object-oriented language, requiring only a basic abstraction mechanism such as abstract classes or interfaces. Another place I have used this is within implementation of algorithms. For example, when implementing merge sort in a closest points algorithm where the points must be compared by either their x or y coordinates at different points in the algorithm, this technique allowed me to write the merge sort code once and extract the comparison code to an object that would compare by either x or y depending on need. In truth it is rather similar to how the C++ algorithm library uses function objects in algorithms like for_each and all_of.

So what do we call this? It looks most closely like an application of the Strategy pattern, as these behavior objects are defining the different derived behaviors at run-time when the derived managers are created. It also contains an aspect of the Template pattern with a base class depending upon an operation to be defined in the derived class, however this is more commonly done through abstract / virtual methods and here we move it into a new object with its own abstract methods. Although the act of storing data in these objects, as with the Comparator, is reminiscent of function objects, or functors. This idea actually came about after spending some time launching threads in C++ with different types of callable objects, of which the functor was my favorite so I initially thought of these along those lines. However, since the object is not being called as a function that name isn’t technically appropriate. So let’s call it a compound application of the Strategy and Template patterns, wherein the objects hold data as needed. Truthfully I’m less concerned about its name and more focused on the thought process behind it. As long as a name is enough to make sure people are talking about the same thing it’s serving its purpose. The important thing here is the use of abstraction to extract parts of code that will change between different derivations of a base object and delegate that portion to the derived objects while not repeating the common sections. That is the takeaway.