Improving Set Algorithm Implementation with the Method Template Pattern

mgcadmin 06-07-2024

A fundamental concept for software engineers when it comes to writing maintainable software is the DRY principle: Don't repeat yourself. Many times when writing code we may find ourselves implementing algorithms that are very similar in structure to each other, and may share large blocks of identical code. This is less than desirable for a multitude of reasons, no least of all being the mental strain of keeping seemingly identical code logically separated. A fantastic example of this is the set theoretical algorithms discussed in yesterdays post. Four separate algorithms that differ from each other only in their choice of when to add an item to a result set.

The template method pattern is a software design pattern created for exactly the scenario at hand. By extracting the decision logic to separate, overloadable methods we can create one base class, and derive classes from that which do the assigned task, drastically reducing the amount of code needed to be written for each algorithm.

Lets take a look at the main loop of our merge() from my previous post to get a clearer picture of what I'm talking about.

    while (lit != lhs.end() && rit != rhs.end()) {
           if (*lit < *rit) {
               lit++;
           } else if (*rit < *lit) {
               rit++;
           } else {
               result.insert(*lit);
               lit++;
               rit++;
           }
    } 

Inside the loop we have conditional branches for three cases. Lets call them predicate A, predicate B, and predicate C. Predicate A checks whether the left item is less than the right item, predicate B checks if the right item is less than left item, and predicate C checks if the two items are equal. By replacing the code blocks inside of the if statements with procedure calls, we end up with the following refactored code:

     while (lit != lhs.end() && rit != rhs.end()) {
           if (*lit < *rit) {
               predicateA();
           } else if (*rit < *lit) {
               predicateB();
           } else {
               predicateC();
           }
     } 

Not only is it more compact, but easier to read as well. Of more importance, is the fine grained control we now have over the merge process by employing template methods. This allows us to very easily implement all four set algorithms using the same merge() algorithm. All we need to do is implement the proper predicate() methods for the task at hand. Because of this, the template method design pattern has the added bonus of greatly reducing the number of areas where bugs can potentially sneak in to our code.

The Base SetMerger Class

Our base class should contain our templated merge method, along with the methods needed by our predicate implementations to interface with the sets, takeFromLeft() and takeFromRight() which retrieve the current item, and advance the iterator to the "left" and "right' set respectively. I chose to implement these algorithms as Function Objects, and thus the only public interface is operator().

 template <class T, typename comp = std::less<T>>
class SetMerger {
    private:
        virtual void predicateA(Set<T>& result) = 0;
        virtual void predicateB(Set<T>& result) = 0;
        virtual void predicateC(Set<T>& result) = 0;
        bool leftHasMore() {
            return lit != set_a.end();
        }
        bool rightHasMore() {
            return rit != set_b.end();
        }
        void init(Set<T>& a, Set<T>& b) {
            set_a = a; set_b = b;
            lit = set_a.begin(); rit = set_b.begin();
        }
    protected:
        T takeFromLeft() {
            return *lit++;
        }
        T takeFromRight() {
            return *rit++;
        } 
        void merge(Set<T>& lhs, Set<T>& rhs, Set<T>& result) {
            init(lhs, rhs);
            while (leftHasMore() && rightHasMore()) {
                if (comp()(*lit , *rit)) {
                    predicateA(result);
                } else if (comp()(*rit, *lit)) {
                    predicateB(result);
                } else {
                    predicateC(result);
                }
            }
            while (leftHasMore()) result.insert(takeFromLeft());
            while (rightHasMore()) result.insert(takeFromRight()); 
        } 
        typename Set<T>::iterator lit;
        typename Set<T>::iterator rit;
        Set<T> set_a;
        Set<T> set_b;
}; 

The SetMerger class is not meant to be instantized, as evidences both by the lack of constructor nor any public methods. In addition, the predicate methods are declared as purely virtual. With our base class completed all we need to do to implement our set algorithms is derive a class from the SetMerger class and implement the appropriate predicate methods.

Derived Classes As Function Objects

Our classes are being implemented as function objects. As such, the only public interface is the constructor, which simply calls our merge method on the given arguments. set intersection, which only adds items to the result set if they are in both sets (predicate C) is now implemented as follows:

template <class T>
class Intersection : public SetMerger<T> {
    private:
        void predicateA(Set<T>& result) {
            this->takeFromLeft();
        }
        void predicateB(Set<T>& result) {
            this->takeFromRight();
        }
        void predicateC(Set<T>& result) {
            result.insert(this->takeFromLeft());
            this->takeFromRight();
        }
 
    public:
        Intersection(Set<T>& lhs, Set<T>& rhs, Set<T>& result) {
            this->merge(lhs, rhs, result);
        } 
}; 

Had we chosen a concrete implementation for all of the algorithms every other part of the code would have been duplicated. Instead, we only implement those parts which are different. With that in mind, implementing the remaining 3 set algorithms proceeds the same as it did for Intersection.

template <class T>
class Difference : public SetMerger<T> {
    private:
        void predicateA(Set<T>& result) {
            result.insert(this->takeFromLeft());
        }
        void predicateB(Set<T>& result) {
            this->takeFromRight();
        }
        void predicateC(Set<T>& result) {
            this->takeFromLeft();
            this->takeFromRight();
        }
 
     public:
        Difference(Set<T>& lhs, Set<T>& rhs, Set<T>& result) {
            this->merge(lhs, rhs, result);
        } 
};

template <class T>
class SymmetricDifference : public SetMerger<T> {
    private:
        void predicateA(Set<T>& result) {
            result.insert(this->takeFromLeft());
        }
        void predicateB(Set<T>& result) {
            result.insert(this->takeFromRight());
        }
        void predicateC(Set<T>& result) {
            this->takeFromLeft();
            this->takeFromRight();
        }
     public:
        SymmetricDifference(Set<T>& lhs, Set<T>& rhs, Set<T>& result) {
            this->merge(lhs, rhs, result);
        } 
};

template <class T>
class Union : public SetMerger<T> {
    private:
        void predicateA(Set<T>& result) {
            result.insert(this->takeFromRight());
        }
        void predicateB(Set<T>& result) {
            result.insert(this->takeFromLeft());
        }
        void predicateC(Set<T>& result) {
            result.insert(this->takeFromLeft());
            this->takeFromRight();
        }
    public:
       Union(Set<T>& lhs, Set<T>& rhs, Set<T>& result) {
            this->merge(lhs, rhs, result);
        }  
}; 

So remember kids: Don't Repeat Yourself! Until next time, Happy Hacking!

---