Generic KDTree in C-CodePudding

I would like to have a generic KDTree implementation in C that can hold any kind of positionable object. Such objects have a 2D position.

Unfortunately. Positionable classes could have different ways of getting the position.

Getters getX() and getY()
std::pair<double, double>
sf::Vector2f
...

What would be the proper way to wrap such classes into my KDTree?

My Tree is composed of nodes such as:

template <typename T>
struct Node {
    int id;
    T element;
    Node *left, *right;
    Node(T element) : element(element), left(NULL), right(NULL)
    {
        static int id = 0;
        this->id = id  ;
    }
};

Somehow I would like to have a generic getter to the position of T element.

One possible solution is to define a positionable interface:

struct KDTreeElement {
    virtual getX() = 0;
    virtual getY() = 0;
}

The con of this method is that the positionable element must know the KDTree library

What are the alternatives?

CodePudding user response：

Check the design rationale of boost geometry for a solution to this problem. The methodology boils down to these steps:

Declare a class template that extracts position information from a type, e.g.
```
template <class Geometry>
struct Position;
```

To make your kd Tree usable with a new type, say MyAwesome2dPoint, specialize this template for it. In the specialization you can use the type's method of getting the position:

template <>
struct Position<MyAwesome2dPoint>
{
    static float getX(MyAwesome2dPoint const& p) const { return p.x; }
    static float getY(MyAwesome2dPoint const& p) const { return p.y; } 
}

Use this type system in your kd tree, i.e. instead of directly accessing positions, go through the Position class:

class KdTree 
{
    template <class PointType>
    auto contains(PointType const& g)
    {
        // Geometric properties are accessed through the traits system.
        return contains_impl(
            Position<PointType>::getX(g), 
            Position<PointType>::getY(g));
    }
}

For extra credit, create a concept to avoid the weird compilation errors when using a type that hasn't been configured to work with your library:

template <class G>
concept Positionable = requires (G g) { 
    Position<G>::getX()   Position<G>::getY(); 
}; 

// So now you can explicitly operate on such types
template <Positionable G>
auto contains(G const& g)
{
}

No inheritance, no virtuals, no modifications to existing types. Just create a layer that can be specialized for everyone (even C types) and you're good to go. Concepts will save your life when abstracting even further, e.g. boost geometry generalizes to N dimensions, different coordinate systems and more.