[geos-devel] Generic algorithms (idea)

Martí Angelats i Ribera marti.angelats at psig.cat
Sat Aug 5 08:47:43 PDT 2017

Hello everyone,
I had this idea and I think you may be interested in it, so I decided to
sign up in the mailing discussion and send this mail.

The idea is to make a collection of generalized functions for geometry (and
possibly cartography) algorithms; trying to detach the algorithms from the
data structure.
I know it can be hard to imagine so I did this very trivial example:

inline constexpr auto supernaive_add_points(auto&& pointA, auto&& pointB) {
    return pointA + pointB;

This is probably the most naive approach. This will require the points to
have the operator+ overloaded. In this theoretical case, whoever did the
operator+ would had actually done all the work. So an actual addition could
look something like this:

template<typename Point>
inline constexpr Point naive_add_points(auto&& pointA, auto&& pointB) {
    // Both points actually need the x() and y() getter; otherwise an error
will be thrown by the compiler (this are parts of the requirements to
execute this function).
    // The x and y types are deduced automatically so they may be a float,
an integer or even a custom type with overridden operator+. x and y may
actually have different types.
    auto x = pointA.x() + pointB.x();
    auto y = pointA.y() + pointB.y();

    // We make the object resulting of the addition and return it. If there
isn't an exact mach C++ will try to find an alternative.
    return Point(x, y);

This function requires both points to have the getters `x()` and `y()`, and
Point to have a constructor compatible with the returned types. This is a
little bit more mature but still very naive since the return type is a
template argument. In reality, you would try to deduce its return type with
some template tricks.

It would be possible to use any data structure as long as your class has
the functions requirements. It would NOT use an interface (or in C++ terms,
a pure virtual class) to get the functions; this would allow the developers
to use any class that already met the requirements.

So let me list all the pros, cons and things to keep in mind that I can
came up with about this approach:

 - 0 overhead approach.
 - Very portable between projects.
 - Separates algorithm from data structure.
 - If you don't use an algorithm, it won't exist in your binary (because it
uses templates and/or auto, it is not fully defined until it's called).
 - Can have multiple implementations simultaneously and let the developer
choose the best one for their needs.
 - Everyone can add a new algorithm or implementation.
 - Adding a new algorithm or implementation will not break all the existing
code nor any project using it.
 - It would be really easy to add a new algorithm or implementation, and it
wouldn't break any code.
 - Requires modern C++.

 - Required modern C++.
 - Need to rewrite code.
 - It cannot be exported to a dynamic library by itself: you'll need a data
structure and a C binding.
 - Developers must know the difference between implementations.
 - Documentation has to be really clear to prevent misunderstandings,
specially each implementation's requirements.
 - May need to rewrite an implementation changing just a little part.

To keep in mind:
 - Requiring modern C++ have its own pros and cons. With C++11 would be
enough but later versions can have more features.
 - You need to be consistent with the requirements (to be as useful as
 - You can use perfect forwarding in the C bound functions to call your
functions (to make a dynamic library).
 - Having a "main" function that defaults to an implementation could help
the developers to choose one.
 - Anyone can copy an algorithm implementation without the need to make
changes, without adding the entire project as dependency.

Thank you for reading,
Martí Angelats i Ribera

PS: This mail ended up being a longer mail than I initially expected. Sorry
for that.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20170805/5dff2907/attachment.html>

More information about the geos-devel mailing list