0

I have a simple design question. I have a tree based C++ class. It needs to use a distance function in order to calculate nearest neighbors. But the distance function is available from an external library such as GeographicLib or others. Ideally you want to vary the distance function based on client preferences. If they have Cartesian coordinates they can use a Euclidean distance. They can also provide a user based distance function.

I want to be able to pass to the tree class a function pointer that represents the distance function as this distance function will be used in several places in the tree class and needs to have instance scope. Right now I have hard coded a single type of distance function in the code and hence the class is not very reusable.

So as an example( I do not have access to sophisticated modeling tools) Some psuedo code

Include External Distance Library

ABCTree()

Distance = ExternalDistanceLibrary.calculateDistance(point1, point2)

As you can see I have hard coded the type in the source code(as well as in the header file). I do not wish to do this.

What I would like to do is to do something like this. I would like the client to pass in a function pointer (have the client to the tree class define the implementation of the function pointer)

 //Constructor
 ABCTree(pointer_to_func distance_func)

 Distance = pointer_to_func(point1,point2);

It has been a while since I used design patterns. Would any design pattern be applicable here ? I have been thinking about the Adapter and Strategy pattern but I am not sure whether that is applicable here or there is any other one. Any guidance is appreciated.

3

The way the standard library deals with this is to use a template parameter, often with a default.

E.g. std::accumulate

template< class InputIt, class T >
T accumulate( InputIt first, InputIt last, T init );

template< class InputIt, class T, class BinaryOperation >
T accumulate( InputIt first, InputIt last, T init, BinaryOperation op );

The first version uses operator+ to sum up the elements, the second version uses the given binary function op

std::set has two

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

These are both compile time choices. If you want to vary it at runtime, you might need the type erasure of std::function, to allow you to generalise to function objects as well.

In terms of named patterns, these are all variation on Strategy.

So for your tree:

template <typename T /* Datatype held */, typename Distance /* Calculation */>
class ABCTree
{
    Distance distance;
    void something_using_distance(T first, T second)
    {
        auto d = distance(first, second);
        // stuff here
    }
};

// A tree holding Points, calculated using manhattan distance
using ManhattanTree = ABCTree<Point, ExternalDistanceLibrary::manhattanDistance>;
// A tree holding text, calculated using levenshtein distance
using LevenshteinTree = ABCTree<std::string, OtherDistanceLibrary::levenshtein>;
  • Thanks for your answer. I would like to accept it but can you explain it in terms of my question - what would be the equivalent of the distance library etc ? – gansub Apr 9 at 8:39
  • 1
    The basic idea is: the code in the existing tree class has to be modified in order to: (1) remember the choice of distance function that the user has configured for this tree class (e.g. a std::function, or a raw function pointer), (2) the tree class has to call this function somehow. There is an alternative choice in C++, namely C++ class templates. Templates are advanced techniques; it is not recommended unless one is extremely familiar with the ins and outs of C++ templates. – rwong Apr 9 at 10:46
  • @rwong can you provide an alternate answer ? – gansub Apr 9 at 12:56
  • 2
    @Caleth - I can start to see the path you have put forward. Give it a couple of days and I will accept your answer. – gansub Apr 9 at 12:57
  • @gansub my comment is just a rearrangement of Caleth's answer. I concur that the answer can be improved by listing the major approaches in short concise sentences upfront, before going into the details and the recommendations. – rwong Apr 9 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.