Reducing code duplication while defining a commutative operation

I have a a set of overloads of a commutative binary function named overlap, which accepts two distinct types:

class A a; class B b;
bool overlap(A, B);
bool overlap(B, A);

My function overlap returns true if and only if one shape overlaps the other - this is one common example used when discussing multimethods.

Because overlap(a, b) is equivalent to overlap(b, a), I only need to implement one "side" of the relation. One repetitive solution is to write something like this:

bool overlap(A a, B b) { /* check for overlap */ }
bool overlap(B b, A a) { return overlap(a, b);   }

But I would prefer not to write an extra N! / 2 trivial versions of the same function by allowing them to be generated instead, using a template.

template <typename T, typename U> 
bool overlap(T&& t, U&& u) 
{ return overlap(std::forward<U>(u), std::forward<T>(t)); }

Unfortuately, this is prone to recurse infinitely, which is not acceptable: see http://coliru.stacked-crooked.com/a/20851835593bd557

How can I prevent such infinite recursion? Am I approaching the problem correctly?

Solution 1:

Here's a simple fix:

template <typename T, typename U> 
void overlap(T t, U u)
{
    void overlap(U, T);
    overlap(u, t);
}

The template itself declares the target function, which will be preferred over recursion because it is an exact match (be sure to take care of constness and reference-ness in your real case). If the function has not been implemented, you get a linker error:

/tmp/cc7zinK8.o: In function `void overlap<C, D>(C, D)':
main.cpp:(.text._Z7overlapI1C1DEvT_T0_[_Z7overlapI1C1DEvT_T0_]+0x20):
    undefined reference to `overlap(D, C)'
collect2: error: ld returned 1 exit status

... which points directly at the missing function :)

Solution 2:

As a wise man once said, there is no problem you cannot solve with an additional layer of indirection, except too many layers of indirection.

So, use SFINAE and some indirection to get it done:

template<class A, class B>
auto overlap(A&& a, B&& b)
-> decltype(overlap_impl('\0', std::forward<A>(a), std::forward<B>(b)))
{ return overlap_impl('\0', std::forward<A>(a), std::forward<B>(b)); }

template<class A, class B>
auto overlap_impl(int, A&& a, B&& b)
-> decltype(do_overlap(std::forward<A>(a), std::forward<B>(b)))
{ return do_overlap(std::forward<A>(a), std::forward<B>(b)); }

template<class A, class B>
auto overlap_impl(long, B&& b, A&& a)
-> decltype(do_overlap(std::forward<A>(a), std::forward<B>(b)))
{ return do_overlap(std::forward<A>(a), std::forward<B>(b)); }

// You can provide more choices if you want, for example to use member-functions.

// Implement `do_overlap(A, B)`, maybe with references, in at least one direction.

Solution 3:

You can rename the actual method to something like overlap_impl and call this one inside the template. I will break the recursion:

bool overlap_impl(A a, B b) { /* check for overlap */ }

template <typename T, typename U> 
bool overlap(T&& t, U&& u) 
{ return overlap_impl(std::forward<U>(u), std::forward<T>(t)); }

template<> bool overlap(A&& t, B&& u)
{ return overlap_impl(std::forward<A>(t), std::forward<B>(u)); }