Epick_d and Has_filtered_predicates_tag

[afabri]

Issue Details

The upcoming Frechet distance package works in any dimension. Here we want to obtain K::Has_filtered_predicates_tag::value for the kernel, and we then want to access K::Exact_kernel.
@mglisse Can this be added to Epick_d without breaking its design?

[mglisse]

We can probably do something, but can you explain what you are trying to achieve there (otherwise I may answer the wrong question)? I see that you mostly ignore the input kernel and do some computations always with intervals, and keep a way to extract vertices as rational points, but that doesn't really give me a high level image of the goal and strategy.

[afabri]

The input points are transformed in points with interval arithmetic. In case of an uncertain exception we create a Sqrt_extension where we want to use the Exact_kernel::FT if available.
The table here shows also in which case we make a copy of the input.

[lrineau]

@mglisse

Would the following patch be acceptable?

diff --git a/NewKernel_d/include/CGAL/NewKernel_d/Cartesian_filter_K.h b/NewKernel_d/include/CGAL/NewKernel_d/Cartesian_filter_K.h
index ef44403f9f5..bc7d88deefa 100644
--- a/NewKernel_d/include/CGAL/NewKernel_d/Cartesian_filter_K.h
+++ b/NewKernel_d/include/CGAL/NewKernel_d/Cartesian_filter_K.h
@@ -58,11 +58,15 @@ struct Cartesian_filter_K : public Base_
     typedef Base_ Kernel_base;
     typedef AK_ AK;
     typedef EK_ EK;
+    typedef EK Exact_kernel;
     typedef typename Store_kernel<AK_>::reference_type AK_rt;
     AK_rt approximate_kernel()const{return sak.kernel();}
     typedef typename Store_kernel<EK_>::reference_type EK_rt;
     EK_rt exact_kernel()const{return sek.kernel();}

+    enum { Has_filtered_predicates = true };
+    typedef Boolean_tag<Has_filtered_predicates> Has_filtered_predicates_tag;
+
     // MSVC is too dumb to perform the empty base optimization.
     typedef std::bool_constant<
       internal::Do_not_store_kernel<Kernel_base>::value &&

[lrineau]

Plus the following:

diff --git a/NewKernel_d/test/NewKernel_d/Epick_d.cpp b/NewKernel_d/test/NewKernel_d/Epick_d.cpp
index 5693977869a..61fed477750 100644
--- a/NewKernel_d/test/NewKernel_d/Epick_d.cpp
+++ b/NewKernel_d/test/NewKernel_d/Epick_d.cpp
@@ -751,6 +751,9 @@ int main(){
   test2<Ker2>(); test2i<Ker2>();
   test3<Ker3>();
   test3<Kerd>();
+  static_assert(Ker2::Has_filtered_predicates_tag::value);
+  static_assert(Ker3::Has_filtered_predicates_tag::value);
+  static_assert(Kerd::Has_filtered_predicates_tag::value);

[mglisse]

Would the following patch be acceptable?

Yes, but

• can you put the 3 lines together with a comment saying that they are here for the sake of package XYZ? (so it doesn't look like unused cruft in need of cleanup)
• should we have a corresponding "false" enum/typedef somewhere like Cartesian_base_d?
• is that really sufficient?

The explanation was not super clear, it sounds vaguely like a Lazy_exact_nt<Sqrt_extension<Rat>> with a custom functor, but since I don't have a clear picture of what you are doing and why (is it the old idea that having 0 guarantee for the constructions in Epick is not good enough?), I can't comment.

[afabri]

I won't make a dedicated pull request, but it will go in PR #8284

[lrineau]

Would the following patch be acceptable?

Yes, but

• can you put the 3 lines together with a comment saying that they are here for the sake of package XYZ? (so it doesn't look like unused cruft in need of cleanup)

Right. We will do that.

But... to be honest, I have not the impression that the patch will decrease the readability of the code! :smiley:

https://github.com/CGAL/cgal/blob/1b534cd347d3795ca1ab574b46c45becf60b5d76/NewKernel_d/include/CGAL/NewKernel_d/Cartesian_filter_K.h#L43-L98

In my editor (VS Code), the TODO and FIXME are highlighted, there are.. a lot!

(click to see more...)

... and there are also several typedefs that are unused, and could now be replaced by `decltype(auto)`, for example. See the screenshot: 

• should we have a corresponding "false" enum/typedef somewhere like Cartesian_base_d?

Yes, probably. I will review Andreas's patch, once it is done.

• is that really sufficient?

I am not completely sure. Andreas will test in https://github.com/CGAL/cgal/pull/8284.

The explanation was not super clear, it sounds vaguely like a Lazy_exact_nt<Sqrt_extension<Rat>> with a custom functor, but since I don't have a clear picture of what you are doing and why (is it the old idea that having 0 guarantee for the constructions in Epick is not good enough?), I can't comment.

That is probably to construct kind of "filtered constructions", where the constructed objects are sometimes reconstructed using an exact kernel, if needed. I do not know the details.

See this example of a valid usage:

https://github.com/CGAL/cgal/blob/1b534cd347d3795ca1ab574b46c45becf60b5d76/Skin_surface_3/include/CGAL/Skin_surface_traits_3.h#L148-L181

[mglisse]

But... to be honest, I have not the impression that the patch will decrease the readability of the code! 😃

If we want the probability of a cleanup to be non-zero, we should

• avoid adding more things to clean up
• mark clearly the things that should not be cleaned up (this was my point here)

(I completely agree the code is not pretty)

In my editor (VS Code), the TODO and FIXME are highlighted, there are.. a lot!

Comments (whether they are marked TODO/FIXME or not) are a completely different thing. They usually contain important information. And yes, there are a lot of things that I never did because they were not priorities.

That is probably to construct kind of "filtered constructions", where the constructed objects are sometimes reconstructed using an exact kernel, if needed. I do not know the details.

I had an Epack_d branch (it should still exist) to do filtered constructions in dD, but it didn't offer the option for each functor to use a different exact type (rational, sqrt-extension, etc).

See this example of a valid usage:

It looks like it would have been much simpler to add Side_of_mixed_cell_3 to the kernel.

[afabri]

In fact I also need a function object for constructing the filtered type and the exact type, In Epick this are the classes C2F and C2E.

[lrineau]

But... to be honest, I have not the impression that the patch will decrease the readability of the code! 😃

If we want the probability of a cleanup to be non-zero, we should

• avoid adding more things to clean up
• mark clearly the things that should not be cleaned up (this was my point here)

You are right. And the comments are indeed very important for that (both TODO/FIXME and notes about why something has been added).

That is probably to construct kind of "filtered constructions", where the constructed objects are sometimes reconstructed using an exact kernel, if needed. I do not know the details.

I had an Epack_d branch (it should still exist) to do filtered constructions in dD, but it didn't offer the option for each functor to use a different exact type (rational, sqrt-extension, etc).

I was not able to retrieve the branch? Do you still have it? What is its name?

[mglisse]

I had an Epack_d branch (it should still exist) to do filtered constructions in dD, but it didn't offer the option for each functor to use a different exact type (rational, sqrt-extension, etc).

I was not able to retrieve the branch? Do you still have it? What is its name?

https://github.com/mglisse/cgal/tree/NewKernel_d-Epack-glisse

[mglisse]

In fact I also need a function object for constructing the filtered type and the exact type, In Epick this are the classes C2F and C2E.

There are typedefs C2A and C2E in Cartesian_filter_K. But you will probably have other issues. Approximate_kernel and Exact_kernel probably don't satisfy the Kernel_d concept. Maybe using Kernel_d_interface<Exact_kernel> in your code would help, but since I have never tried something like that, there may be issues. Global functions like CGAL::squared_distance are also not supported.

Kernels were designed for a separation of concerns between algorithms and predicates/constructions. Handling filtering by hand for a specific algorithm may indeed be more efficient, but it is bound to be a bit awkward.