Developer.com content and product recommendations are editorially independent. We may make money when you click on links to our partners. Learn More.
A very interesting Java newsletter1 was the starting point of this article. After a swift presentation of a classic Strategy Pattern2, a TaxPayer Context paired with a TaxStrategy hierarchy, the newsletter tries to answer a more difficult problem: What happens if the Context becomes a hierarchy? How do you keep track of the real type of the TaxPayer inside TaxStrategy without downcasting?
You’ll find several answers in this article—from a Generic Programming perspective.
What’s the Buzz?
Consider the popular TaxPayer, paying unpopular taxes as dictated by TaxStrategies3:
struct TaxStrategy{
virtual void payTax ()=0;
};
struct TaxPayer{
TaxStrategy strategy_;
void payTax(){ strategy_.payTax();}
};
struct CompanyTaxStrategy : TaxStrategy{};
struct EmployeeTaxStrategy : TaxStrategy{};
In the real world, there is a family of TaxPayers, different enough to be hard to abstract behind an unique interface. Most probably, you’ll find TaxPayers in a loose hierarchy (if any at all)—Employees, Companies, a.s.o. TaxStrategy has to take this diversity into account—companies are not taxed the same way as their employees and employees expose different attributes than companies.
You have to make TaxStrategy aware of the different TaxPayers. One way to accomplish this is to pass TaxPayer as a parameter 1, 2.
struct Company: TaxPayer{
void payTax(){ strategy_.payTax(*this);}
};
If you like downcasts, this code is for you:
CompanyTaxStrategy : TaxStrategy{
void payTax (const TaxPayer& t){
if (Company c = dynamic_cast<Company&>(t)){...}
}
};
If not, you have to look at an alternative.
One obvious route is to use the Visitor pattern that offers double dispatching out of the box; this will be investigated in a future article4.
On the other hand, Reference 1 describes a non-trivial solution based on generics. You’ll try to match that implementation and even to improve it by using C++ templates and generic programming techniques. This has been done in a couple of steps, presented below.
Creating an Equivalent Solution (crtp.h)
A C++ replica of Reference 1 can be easily constructed by using the CRTP (The Curiously Recurring Template Pattern5). The payTax() mechanism is factored out in a TaxPayer base class:
namespace crtp
{
template <class TAX_PAYER>
struct TaxStrategy;
template <class TAX_PAYER>
struct TaxPayer
{
TaxPayer( TaxStrategy<TAX_PAYER>* strategy) :
strategy_(strategy) { }
void payTax()
{
TAX_PAYER& tp = static_cast< TAX_PAYER&>(*this);
strategy_->payTax(tp);
}
private:
TaxStrategy<TAX_PAYER>* strategy_;
};
struct Company : TaxPayer<Company>
{
Company( TaxStrategy<Company>* strategy) :
TaxPayer<Company>(strategy){ }
void only4companies() const {};
};
struct Employee : TaxPayer<Employee>
{
Employee( TaxStrategy<Employee>* strategy) :
TaxPayer<Employee>(strategy){ }
void only4employees() const {};
};
template <class TAX_PAYER>
struct TaxStrategy
{
void payTax(const TAX_PAYER& e)
{
std::cout << "generic payTax n" ;
}
};
template <>
struct TaxStrategy<Employee>
{
void payTax(const Employee& e)
{
e.only4employees();
std::cout << "payTax Employeen" ;
}
};
template<>
struct TaxStrategy<Company>
{
void payTax(const Company& e)
{
e.only4companies();
std::cout << "payTax Companyn" ;
}
};
void test()
{
TaxStrategy<Employee> tsEmp;
TaxPayer<Employee> e(&tsEmp);
e.payTax();
TaxStrategy<Company> tsComp;
TaxPayer<Company> c(&tsComp);
c.payTax();
}
}
Note how the downcast is avoided in this case: payTax is overloaded and CRTP helps call the correct version.
But, the resulting code is far from stellar, for the following reasons:
- TaxPayer is a type-dependent base class and cannot be used in generic sequences such as:
for (std::vector<TaxPayer>::iterator it = taxPayers.begin(); it != taxPayers.end(); ++it) { it->payTax(); }This works in Java due to raw types (but take into account that “The use of raw types in code written after the introduction of genericity into the Java programming language is discouraged. According to the Java Language Specification, it is possible that future versions of the Java programming language will disallow the use of raw types”6) , but not in C++.
- TaxStrategy should be a variation point (TaxStrategies of different types should be pluggable in taxPayer). This is not possible in the previous example, but is possible in Reference 1 where TaxStrategy is an interface allowing further customization in derived classes.
- TaxStrategy<T> are independent, unrelated classes. TaxStrategy should be seen as a family of algorithms more than anything else. (It can be a functor or a simple function as well.)
Improving the Equivalent Solution (virtual_crtp.h)
1 & 2 can be easily fixed by using abstract base classes:
template <class TAX_PAYER>
struct ITaxStrategy
{
virtual void payTax(TAX_PAYER*) = 0;
};
struct ITaxPayer
{
virtual void payTax() = 0;
};
and code like this is now possible:
void test()
{
TaxStrategy<Employee> tsEmp;
TaxPayer<Employee> e(&tsEmp);
e.payTax();
TaxStrategy1<Company> tsComp;
TaxPayer<Company> c(&tsComp);
c.payTax();
std::vector<ITaxPayer*> taxPayers;
taxPayers.push_back(&e);
taxPayers.push_back(&c);
for (std::vector<ITaxPayer*>::iterator it = taxPayers.begin();
it != taxPayers.end(); ++it)
{
(*it)->payTax();
}
}
This brings you on par with Reference 1 in terms of functionality, but the solution is suboptimal. As noted in Reference 7: “Operation polymorphism (keyword virtual in C++) is excluded [in parametric polymorphism; in other words, (compile-time) genericity] because dynamic binding is too expensive. Or, saying it differently, abstract methods are forbidden.”
Note: This is not always possible when mixing the two types of polymorphism or is not desirable—it adds complexity.
Further Improvements: Generic Programming Techniques (Improved_crtp_double_interface.h)
Static interfaces8 might provide the “missing link” in your endeavor. As a short recap, a static interface is a non-instantiable façade for all the classes having methods with the same signature as the methods exposed by the static interface. The static interface “hides” the real type of the wrapped class, doesn’t use virtual methods, and is very useful in interface-based dispatching.
namespace improved_crtp_double_interface
{
template <class TAX_PAYER>
struct TaxPayer
{
TaxPayer() : strategy_(0), fun_(0) { }
typedef void (*FUN)(void*, void*);
template <class STRATEGY>
TaxPayer( STRATEGY* strategy) : strategy_(strategy),
fun_(fun<STRATEGY>::payTaxIsFun) { }
template <class STRATEGY>
void setStrategy( STRATEGY* strategy)
{
strategy_ = strategy;
fun_ = fun<STRATEGY>::payTaxIsFun;
}
void payTax()
{
assert(strategy_);
assert(fun_);
fun_(strategy_, this);
}
private:
template <class F>
struct fun
{
static void payTaxIsFun(void* a, void* p)
{
TAX_PAYER* tp = static_cast< TAX_PAYER*>(p);
F* strategy = static_cast< F*>(a);
strategy->payTax(tp);
}
};
private:
void* strategy_;
FUN fun_;
};
struct Company : TaxPayer<Company >
{
template <class T>
Company( T* strategy) : TaxPayer<Company>(strategy){ }
void only4companies() const {};
};
struct Employee : TaxPayer<Employee >
{
template <class T>
Employee( T* strategy) : TaxPayer<Employee>(strategy){ }
void only4employees() const {};
};
struct TaxStrategy
{
template <class TAX_PAYER>
void payTax(const TAX_PAYER* e)
{
std::cout << "generic payTax n" ;
}
};
template <>
void TaxStrategy::payTax(const Employee* e)
{
e->only4employees();
std::cout << "payTax Employeen" ;
}
template<>
void TaxStrategy::payTax(const Company* e)
{
e->only4companies();
std::cout << "payTax Companyn" ;
}
struct TaxStrategy1
{
template <class TAX_PAYER>
void payTax(const TAX_PAYER* e)
{
std::cout << "generic payTax 1 n" ;
}
};
template <>
void TaxStrategy1::payTax(const Employee* e)
{
e->only4employees();
std::cout << "payTax Employee 1n" ;
}
template<>
void TaxStrategy1::payTax(const Company* e)
{
e->only4companies();
std::cout << "payTax Company 1n" ;
}
class ITaxPayer
{
private:
typedef void (*FP1)(void* );
public:
template <class T>
ITaxPayer(T& x)
: p_(&x),
pf1_(&functions<T>::payTax)
{}
void payTax()
{
pf1_(p_);
}
private:
template <class TT>
struct functions
{
static void payTax( void* a )
{
static_cast<TT*>(a)->payTax();
}
};
void* p_;
FP1 pf1_;
};
void test()
{
TaxStrategy1 ts1;
TaxStrategy ts;
TaxPayer<Employee> e(&ts);
ITaxPayer i(e);
i.payTax();
std::vector<ITaxPayer> taxPayers;
taxPayers.push_back(i);
TaxPayer<Company> c;
c.setStrategy(&ts1);
i=c;
i.payTax();
taxPayers.push_back(i);
for (std::vector<ITaxPayer>::iterator it = taxPayers.begin();
it != taxPayers.end(); ++it)
{
it->payTax();
}
}
}
The previous example uses static interfaces twice:
- To create an interface for all TaxPayers (ITaxPayer)
- To hide TaxStrategy inside TaxPayers (TaxPayer)
Note: All classes exposing a method named payTax with the signature void (*)(void) can be manipulated through ITaxPayer.
TaxPayer is more complicated; is not only an interface but it also hides the type of strategy as well as the mechanism of dispatching the call to the strategy. A strategy can be pushed into a TaxPayer at any time via setStrategy().
Another interesting addition is the way TaxStrategy is now factored as a single, non-parametric class exposing one template member function:
template <class TAX_PAYER> void payTax(const TAX_PAYER* e);
The class offers the generic, non-specialized version of the function. Specialization has to be done outside the class (template member specialization rule) making class extension a natural process.
Supplementary Code
In this section, you see some additional code—variations considered too interesting not to be at least mentioned.
- What happens if TaxStrategy degenerates into a family of functors or even a simple family of functions (stateless algorithms)? You’ll find the answer in improved_crtp_intreface.h and improved_crtp_interface_strategy_function.h.
- What if you vary the strategy through a compile-time versioning mechanism? Take a look at improved_crtp_interface_versioned.h.
- static_interface.h presents a “don’t do this at home” example. There are inherent dangers associated with static interfaces (actually static_cast) when trying to hide more than one type. The correct design is shown in static_T_interface_T.h.
Conclusion
After an initial mechanical reconstruction in C++ of a Strategy with Generics, you’ve seen the opportunity of improving the design in a more generic way, potentially increasing the code’s performance. Different versions of code were demonstrated and even more cases presented in the accompanying code snippets; some of them exemplify possible traps and design failures.
Download the Code
You can download the code that accompanies this article here.
References
- Dr. Heinz M. Kabutz. Strategy Pattern with Generics, http://www.javaspecialists.co.za/archive/newsletter.do?issue=123&locale=en_US
- Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley Professional, 1995
- The examples provided in this article are based on the same case study and names as in Reference 1, allowing the astute reader an easy comparison.
- If TaxPayers is a highly volatile hierarchy, the classic Visitor doesn’t scale well. There are ways to circumvent this undesired behavior, as a future article will prove.
- Nicolai M. Josuttis, David Vandevoorde. C++ Templates: The Complete Guide, Addison-Wesley Professional. 2002
- Angelika Langer—Java Generics FAQs, http://www.angelikalanger.com/GenericsFAQ/JavaGenericsFAQ.html
- Thierry Géraud and Alexandre Duret-Lutz. Generic Programming Redesign of Patterns, http://hillside.net/europlop/HillsideEurope/Papers/GenericProgrammingRedesignOfPatterns.pdf
- Radu Braniste. C++ Idioms in BREW: Better Interfaces. http://www.developer.com/ws/brew/article.php/3501761
- Robert C. Martin. The Open-Closed Principle, http://www.objectmentor.com/resources/articles/ocp.pdf
