Coder Notepad

the first very usefull pattern

One of the first patterns explained on that book is the Policy pattern. It is the static (or compile-time) version of the Strategy pattern. That is, it will let you extract some of the algorithm behavior to be selected not at runtime but in different code positions with minimal code effort. It is, in other word a way of write, in C++, higher order functions (functions that have other functions as their parameters).

an application

Here i want to explain what I find a usefull application of this pattern in every day programming. I find it really usefull and I really "discovered" it in my every day work.

Consider a situation in witch an object's list, can be ordered by its different properties. Here I'll consider a simple example with a class Person describing people by three properties:

• Name
• Surname
• age

Here is the code:

class Person {
        string name, surname ;
        unsigned int age;

public:
        Person(string name, string surname, unsigned int age){
                this->name = name;
                this->surname = surname;
                this->age = age;
        }

        string toString(){
                stringstream s;
                s << name << " " << surname << " [age: "<< age <<"]";
                return s.str();
        }
};

Suppose, some reason another, you want to order lists of people by different criteria in different part of you code, what I find a good solution is to implement some internal functor objects that implements different ordering functions. So, the Person class, it will enriched with:

class Person {
        ...
public:
        struct OrderByName {
                bool operator() (const Person& p1, const Person& p2){
                        return p1.name < p2.name;
                }
        };

        struct OrderBySurname {
                bool operator() (const Person& p1, const Person& p2){
                        return p1.surname < p2.surname;
                }
        };

        struct OrderByAge {
                bool operator() (const Person& p1, const Person& p2){
                        return p1.age < p2.age;
                }
        };

        ...
};

At this point you can sort (or operate on them in some other way requiring an ordering function) Person objects like this:

vector<Person> people;
people.push_back(Person("Jill", "Evans", 29));
people.push_back(Person("Jill", "Evans", 23));
people.push_back(Person("Jill", "Doe", 31));
people.push_back(Person("Joe", "Doe", 34));
people.push_back(Person("Alan",  "Doe", 68));

cout << "Original dataset: " << endl;
for(unsigned int i = 0; i<people.size(); ++i){
        cout << people[i].toString() << endl;
}

cout << endl << "Ordering by surnames..."<< endl;
sort(people.begin(), people.end(), Person::OrderBySurname());

cout << "Ordered dataset:" << endl;
for(unsigned int i = 0; i<people.size(); ++i){
        cout << people[i].toString() << endl;
}

to obtain this result:

Original dataset:
Jill Evans [age: 29]
Jill Evans [age: 23]
Jill Doe [age: 31]
Joe Doe [age: 34]
Alan Doe [age: 68]

Ordering by surnames...
Ordered dataset:
Jill Doe [age: 31]
Joe Doe [age: 34]
Alan Doe [age: 68]
Jill Evans [age: 29]
Jill Evans [age: 23]

In a real world situation this is not a so good way of order list of people, you' ll be probably required to refine the sorting using a different and more complex ordering that will list Alan before Jill and Joe Doe. You could follow the naive approch and write more and more ordering functors but they will multiplicate exponentially so that, simply give that criteria a name, can be quite a complex issue. You could have:

• OrderBySurnameAndThenName
• OrderBySurnameAndThenAge
• OrderByAgeAndThenSurname

This solution is not that well, here I'll propose something more beautifull.

The SmartOrderBy solution

The solution I want to propose require the writing of an ordering functor whose only purpose is to combine two other ordering functor types.

So, SmartOrderBy is a functor type that depends on two other functor types that evaluates to true if the first object is less then the second when considering the first functor or, if they are equal for the first, the first object is less then the second when considering the second ordering functor.

Consider for example you want to order a list of people by their surname and, in case of same surname, by their name. You could write just another functor OrderBySurnameAndName or use SmartOrderBy like in the following exaple:

cout << endl << "Ordering by surnames then names..."<< endl;
sort(people.begin(), people.end(), SmartOrderBy<Person::OrderBySurname, Person::OrderByName>());

cout << "Ordered dataset:" << endl;
for(unsigned int i = 0; i<people.size(); ++i){
        cout << people[i].toString() << endl;
}

this will write:

Ordering by surnames then names...
Ordered dataset:
Alan Doe [age: 68]
Jill Doe [age: 31]
Joe Doe [age: 34]
Jill Evans [age: 29]
Jill Evans [age: 23]

Of course you may want to see the SmartOrderBy definition, and here is how it looks like:

template <class Ord1, class Ord2>
struct SmartOrderBy{
private:
        Ord1 o1;
        Ord2 o2;

public:
        template <typename Obj>
        bool operator() (const Obj& obj1, const Obj& obj2){
                if(!o1(obj1, obj2) && !o1(obj2, obj1) ){
                        return o2(obj1, obj2);
                }
                return o1(obj1, obj2);
        }



};

The template parameters Ord1 and Ord2 are the component ordering functor types. In this simple example they must be default constructable but different semantics can be implemented refinig the implementation. For example it is possible to arrange thinks so that component functors are created (and initialized) by the callee. The operator() is a template method itself so that the resulting functor may be applied to any object the component functors can both operate on.

I've used a little trick to not require the specification of equality operator corresponding to each of the functors:

Consider o1 as ordering functor we can write:

not (obj1 < obj2) equals to obj1 >= obj2

and, obviously:

if obj1 >= obj2 and obj2 >= obj1 then obj1 == obj2.

SmartOrderBy template instantiation may be a component functor type itself so that you can sort a list of people by their surnames and then, in case of same surname by their names and then, in case of same name and surname, by their age, as follow:

cout << endl << "Ordering by surnames then names then age..."<< endl;
typedef SmartOrderBy<Person::OrderBySurname, Person::OrderByName> OrderByName;          // a temporary shortcut
sort(people.begin(), people.end(), SmartOrderBy<OrderByName, Person::OrderByAge>());

cout << "Ordered dataset:" << endl;
for(unsigned int i = 0; i<people.size(); ++i){
        cout << people[i].toString() << endl;
}

and obtain:

Ordering by surnames then names then age...
Ordered dataset:
Alan Doe [age: 68]
Jill Doe [age: 31]
Joe Doe [age: 34]
Jill Evans [age: 23]
Jill Evans [age: 29]

The wonderfull think of this approch is that, if you need to order in a slightly different way, for example by age and then by surname and then by name you can implement it as simple as:

cout << endl << "Ordering by age then surnames then names..."<< endl;
typedef SmartOrderBy<Person::OrderBySurname, Person::OrderByName> OrderByName;          // a temporary shortcut
sort(people.begin(), people.end(), SmartOrderBy<*Person::OrderByAge, OrderByName*>());

cout << "Ordered dataset:" << endl;
for(unsigned int i = 0; i<people.size(); ++i){
        cout << people[i].toString() << endl;
}

I've just swapped the two component ordering functors!

More to come

Hope you'll find this usefull, I want to close this article here to not overcharge it, but here come a quite natural question, what if we old the list of objects (people) as a list of pointers, can we still use this approch? I'll write some more on the argument soon, stay tuned!