Generic algorithms (idea)

Previous Topic Next Topic
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view

Generic algorithms (idea)

Martí Angelats i Ribera
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 possible).
 - 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.

geos-devel mailing list
[hidden email]
Reply | Threaded
Open this post in threaded view

Re: Generic algorithms (idea)

Sandro Santilli-4
On Sat, Aug 05, 2017 at 05:47:43PM +0200, Martí Angelats i Ribera wrote:

> 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.

You might be interested in boost::geometry and CGAL, both providing
such generalized functions.

geos-devel mailing list
[hidden email]