Implementing Symmetric Functions Without Repeating Yourself
From Wiki
Contents |
[edit] The Problem
Assume we have a library of classes representing geometric objects, such as vectors, lines, triangles, etc. We want to implement a generic, extensible function template that computes the distance between two geometric objects of type T1 and T2. Consider the following declarations where N is the dimension of the Euclidean space the class' objects belong to and T is the value type used to store coordinates (it is the underlying type of the scalar field of the Euclidean space; any floating-point type, such as float, double, or long double, will do):
// assume these are fully implemented; furthermore, they all have a nested typedef called ValueType, which is T template <unsigned int N, typename T = float> class Vector; template <unsigned int N, typename T = float> class Line; template <unsigned int N, typename T = float> class Triangle; // this is the function we want to implement template <typename T1, typename T2> typename T1::ValueType GetDistance(const T1& object1, const T2& object2);
GetDistance is a symmetric function, i.e. given two objects it returns the same distance irrespective of the order of arguments. In other words, GetDistance(object1, object2) == GetDistance(object2, object1).
[edit] A First Attempt
Since we want clients to be able to partially specialize GetDistance, but function templates in C++ do not support partial specialization, we first declare a function object which is used internally by GetDistance and we specialize it for all the various distance computation variations:
template <typename ReturnT, typename T1, typename T2> struct GetDistanceFunctionObject; // left undefined on purpose; explicit specializations must be provided for all supported types T1 and T2 // specialize for point-point distance template <unsigned int N, typename T> struct GetDistanceFunctionObject<T, Vector<N, T>, Vector<N, T> > { typedef Vector<N, T> ObjectType1; typedef Vector<N, T> ObjectType2; ReturnT GetDistance(const Vector<N, T>& object1, const Vector<N, T>& object2) const { ... } }; // specialize for point-line distance template <unsigned int N, typename T> struct GetDistanceFunctionObject<T, Vector<N, T>, Line<N, T> > { typedef Vector<N, T> ObjectType1; typedef Line<N, T> ObjectType2; ReturnT GetDistance(const Vector<N, T>& object1, const Line<N, T>& object2) const { ... } }; // specialize for point-triangle distance template <unsigned int N, typename T> struct GetDistanceFunctionObject<T, Vector<N, T>, Triangle<N, T> > { typedef Vector<N, T> ObjectType1; typedef Triangle<N, T> ObjectType2; ReturnT GetDistance(const Vector<N, T>& object1, const Triangle<N, T>& object2) const { ... } }; // specialize for line-triangle distance template <unsigned int N, typename T> struct GetDistanceFunctionObject<T, Line<N, T>, Triangle<N, T> > { typedef Line<N, T> ObjectType1; typedef Triangle<N, T> ObjectType2; ReturnT GetDistance(const Line<N, T>& object1, const Triangle<N, T>& object2) const { ... } }; template <typename T1, typename T2> typename T1::ValueType GetDistance(const T1& object1, const T2& object2) { typedef typename T1::ValueType ReturnType; return GetDistanceFunctionObject<ReturnType, T1, T2>().GetDistance(object1, object2); }
Now, this works fine and we can now successfully do this:
GetDistance(Vector<3>(...), Vector<3>(...)); GetDistance(Vector<3>(...), Line<3>(...)); GetDistance(Vector<3, double>(...), Triangle<3, double>(...)); GetDistance(Line<3, long double>(...), Triangle<3, long double>(...));
However, GetDistance is not symmetric, so the following will not compile because there's no specialization of GetDistanceFunctionObject for the order of argument types:
GetDistance(Line<3>(...), Vector<3>(...)); // error! no specialization of GetDistanceFunctionObject for <Line, Vector> GetDistance(Triangle<3, double>(...), Vector<3, double>(...)); // error! no specialization of GetDistanceFunctionObject for <Triangle, Vector> GetDistance(Triangle<3, long double>(...), Line<3, long double>(...)); // error! no specialization of GetDistanceFunctionObject for <Triangle, Line>
So obviously we have not yet reached our goal of GetDistance being a symmetric function. An easy solution to the problem is to put the burden on the client. The client simply has to specialize GetDistanceFunctionObject for all possible variations. This results in a lot of copy & paste code, which is generally a bad idea and not a solution we will even consider.
[edit] Solving the Symmetry Problem
One can avoid copying the code by providing a specialization GetDistanceFunctionObject for T2, T1 that internally calls the GetDistance function of the specialization for T1, T2. This can be done by providing a SwappedGetDistanceFunctionObject template class, which we will use as base class for our specialization of GetDistanceFunctionObject for T2, T1.
template <typename ReturnT, typename T1, typename T2> struct SwappedGetDistanceFunctionObject { typedef T2 ObjectType1; typedef T1 ObjectType1; ReturnT GetDistance(const T2& object1, const T1& object2) const { // forward the call to an existing specialization for <T1, T2> return GetDistanceFunctionObject<ReturnT, T1, T2>().GetDistance(object2, object1); } }; // specialize for line-point distance that uses the previous specialization for point-line distance template <unsigned int N, typename T> struct GetDistanceFunctionObject<T, Line<N, T>, Vector<N, T> > : public SwappedGetDistanceFunctionObject<T, Vector<N, T>, Line<N, T> > {}; // specialize for triangle-point distance that uses the previous specialization for point-triangle distance template <unsigned int N, typename T> struct GetDistanceFunctionObject<T, Triangle<N, T>, Vector<N, T> > : public SwappedGetDistanceFunctionObject<T, Vector<N, T>, Triangle<N, T> > {}; // specialize for triangle-line distance that uses the previous specialization for line-triangle distance template <unsigned int N, typename T> struct GetDistanceFunctionObject<T, Triangle<N, T>, Line<N, T> > : public SwappedGetDistanceFunctionObject<T, Line<N, T>, Triangle<N, T> > {};
This works and avoids code duplication, but we still need to explicitly specialize GetDistanceFunctionObject twice for each combination of types T1 and T2. Can we do better?
[edit] Solving the Symmetry Problem - Take 2
We can do better by using the SFINAE principle (Substitution Failure Is Not An Error), which allows us to exclude function templates from the overload resolution set at compile-time. I wrote another article on the SFINAE Principle that gives an introduction to its application.
The basic idea is to use the ObjectType1 and ObjectType2 typedefs that every specialization of GetDistanceFunctionObject has to provide. At compile-time, using SFINAE, we check to see if GetDistanceFunctionObject<T1, T2> has a nested ObjectType1 typedef, and if it does, we use it. Otherwise, there's a second function template that checks to see if GetDistanceFunctionObject<T2, T1> (note the swapped order of T1 and T2) has a nested ObjectType1 typedef, and again if it does, we use it.
namespace GetDistanceFunctionObjectFinder { template <typename ReturnT, typename T1, typename T2> ReturnT GetDistance(const T1& object1, const T2& object2, typename GetDistanceFunctionObject<ReturnT, T1, T2>::ObjectType1* = 0) // due to SFINAE this overload is only used when there's a specialization for GetDistanceFunctionObject<T1, T2> { return GetDistanceFunctionObject<ReturnT, T1, T2>().GetDistance(object1, object2); } template <typename ReturnT, typename T1, typename T2> ReturnT GetDistance(const T1& object1, const T2& object2, typename GetDistanceFunctionObject<ReturnT, T2, T1>::ObjectType1* = 0) // due to SFINAE this overload is only used when there's a specialization for GetDistanceFunctionObject<T2, T1> { return GetDistanceFunctionObject<ReturnT, T2, T1>().GetDistance(object2, object1); } } template <typename T1, typename T2> typename T1::ValueType GetDistance(const T1& object1, const T2& object2) { typedef typename T1::ValueType ReturnType; return GetDistanceFunctionObjectFinder::GetDistance<ReturnType, T1, T2>(object1, object2); }
Great! Now we can get rid of our previous SwappedGetDistanceFunctionObject and the specializations of GetDistanceFunctionObject that used it. In fact, we have to get rid of them or else the two GetDistanceFunctionObjectFinder::GetDistance function templates would both be well-formed and the compiler couldn't choose between the two ambiguous functions when performing overload resolution.
There's one small problem with the above GetDistance function, though. If T1 == T2, for example T1 == T2 == Vector, we will get a compilation error because GetDistanceFunction<T1, T2> == GetDistanceFunction<T2, T1> and therefore both GetDistanceFunctionObjectFinder::GetDistance function templates are well-formed and ambigous.
To fix this, all we need to do is simply add another overload for GetDistance:
template <typename T> typename T::ValueType GetDistance(const T& object1, const T& object2) { typedef typename T::ValueType ReturnType; return GetDistanceFunctionObject<ReturnType, T, T>().GetDistance(object1, object2); }
Now we're done. We've succeeded in making GetDistance symmetric without requiring the client to provide additional specializations or resorting to code duplication. There's still one problem with our solution, though. Even though we determine at compile time using function overloads and SFINAE if a GetDistanceFunctionObject<T1, T2> or a GetDistanceFunctionObject<T2, T1> exists, we can only make use of this knowledge at runtime. It would certainly be nice to be able to determine the type of the existing partial specialization of GetDistanceFunctionObject at compile time.
[edit] Solving the Symmetry Problem - Take 3
In fact, we can determine at compile time whether the partial specialization GetDistanceFunctionObject<T1, T2> or GetDistanceFunctionObject<T2, T1> exists by using the SFINAE principle with partial specialization of class templates instead of function template overloading. Our goal is to write a template metafunction that given types T1 and T2 returns a valid GetDistanceFunctionObject specialization that we can then successfully instantiate at runtime and call GetDistance on passing in arguments in the order T1, T2. This template metafunction will be implemented using partial specialization and we shall give it the long but descriptive name GetSpecializedGetDistanceFunctionObject. Just like any Boost.MPL[1] template metafunction it will have a nested type called 'type'. This type will be the actually existing partial specialization of GetDistanceFunctionObject, i.e. either GetDistanceFunctionObject<T1, T2> or GetDistanceFunctionObject<T2, T1>. The type that we will instantiate at runtime (which needs to additionally swap the runtime arguments when we call its GetDistance member function) we shall call runtime_type.
First, we declare the primary template. We leave it undefined because we only want exactly one of our explicitly provided partial specializations to be used without an automatic fall back. Leaving it undefined will trigger a compile time error when trying to call the GetDistance function for types T1, T2 for which no GetDistanceFunctionObject specialization exists yet. In other words, no distance algorithm has been implemented yet for geometric object types T1 and T2.
// Primary template; intentionally left undefined template <typename ReturnT, typename T1, typename T2, typename EnableIf = void> struct GetSpecializedGetDistanceFunctionObject;
Note the EnableIf template parameter, which has a default argument of void. We will be using boost::enable_if[2] in some of our partial specializations of this primary template to enable/disable them with the help of this additional template parameter.
Next, we handle the easy case of T1 == T2, such as the distance between two lines, two points, two triangles, and so on. The partial specialization for this is simply:
// Partial specialization that is used if T1 == T2 template <typename ReturnT, typename T> struct GetSpecializedGetDistanceFunctionObject<ReturnT, T, T> { typedef GetDistanceFunctionObject<ReturnT, T, T> runtime_type; typedef GetDistanceFunctionObject<ReturnT, T, T> type; };
Now, we use boost::enable_if to enable the next partial specialization only if GetDistanceFunctionObject<T1, T2> exists.
// Partial specialization that is used if T1 != T2 and a partial // specialization GetDistanceFunctionObject<ReturnT, T1, T2> exists. template <typename ReturnT, typename T1, typename T2> struct GetSpecializedGetDistanceFunctionObject<ReturnT, T1, T2, typename boost::enable_if_c< !boost::is_same<T1, T2>::value && boost::is_same<typename GetDistanceFunctionObject<ReturnT, T1, T2>::ObjectType1, T1>::value >::type > { typedef GetDistanceFunctionObject<ReturnT, T1, T2> runtime_type; typedef GetDistanceFunctionObject<ReturnT, T1, T2> type; };
Note that we explicitly disable this partial specialization if T1 == T2. If we didn't do this, it would be ambiguous with the previous partial specialization when T1 == T2 and GetDistanceFunctionObject<T1, T2> actually existed.
Finally, we add another partial specialization that is enabled only if GetDistanceFunctionObject<T2, T1> exists. Since the caller of our template metafunction expects to get back a function object that behaves like a GetDistanceFunctionObject<T1, T2>, at runtime as well as compile time, we have to use a small wrapper that takes the existing GetDistanceFunctionObject<T2, T1> and swaps the order of the runtime arguments passed to the GetDistance member function of the function object.
// Partial specialization that is used if T1 != T2 and a partial // specialization GetDistanceFunctionObject<ReturnT, T2, T1> exists. // Returns a type whose GetDistance/GetSquaredDistance functions accept // their objects in swapped order. template <typename ReturnT, typename T1, typename T2> struct GetSpecializedGetDistanceFunctionObject<ReturnT, T1, T2, typename boost::enable_if_c< !boost::is_same<T1, T2>::value && boost::is_same<typename GetDistanceFunctionObject<ReturnT, T2, T1>::ObjectType1, T2>::value >::type > { // internal helper that forwards to GetDistanceFunctionObject<ReturnT, T1, T2> but behaves as if it // was a GetDistanceFunctionObject<ReturnT, T2, T1>, i.e. the order of arguments is swapped template <typename ReturnT, typename T1, typename T2> struct SwappedGetDistanceFunctionObject { typedef GetDistanceFunctionObject<ReturnT, T1, T2> ForwardFunctionObject; typedef ReturnT ReturnType; typedef T2 ObjectType1; typedef T1 ObjectType2; ReturnT GetDistance(const T2& object1, const T1& object2) const { return ForwardFunctionObject().GetDistance(object2, object1); } }; typedef SwappedGetDistanceFunctionObject<ReturnT, T2, T1> runtime_type; typedef GetDistanceFunctionObject<ReturnT, T2, T1> type; };
Let's take a look at how we can implement the GetDistance free function using our new template metafunction instead of the function template overloads we used previously. Note that we no longer need the special function overload GetDistance(T, T) because now the template metafunction takes care of handling this case.
template <typename T1, typename T2> typename T1::ValueType GetDistance(const T1& object1, const T2& object2) { typedef typename T1::ValueType ReturnType; typedef typename GetSpecializedGetDistanceFunctionObject<ReturnType, T1, T2>::runtime_type FunctionObject; return FunctionObject().GetDistance(object1, object2); }
This last solution provides the most flexibility because it allows us to determine which GetDistanceFunctionObject exists at compile-time using the template metafunction and at runtime using the template metafunction's result type and creating an instance of that object, which is what the GetDistance free function does.
