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! 😃

cgal/NewKernel_d/include/CGAL/NewKernel_d/Cartesian_filter_K.h

Lines 43 to 98 in 1b534cd

	// FIXME:
	// - Uses_no_arithmetic predicates should not be filtered
	// - Functors_without_division should be defined near/in the actual functors
	template < typename Base_, typename AK_, typename EK_, typename Pred_list = typeset_all >
	struct Cartesian_filter_K : public Base_
	{
	CGAL_NO_UNIQUE_ADDRESS Store_kernel<AK_> sak;
	CGAL_NO_UNIQUE_ADDRESS Store_kernel<EK_> sek;
	constexpr Cartesian_filter_K(){}
	constexpr Cartesian_filter_K(int d):Base_(d){}
	//FIXME: or do we want an instance of AK and EK belonging to this kernel,
	//instead of a reference to external ones?
	constexpr Cartesian_filter_K(AK_ const&a,EK_ const&b):Base_(),sak(a),sek(b){}
	constexpr Cartesian_filter_K(int d,AK_ const&a,EK_ const&b):Base_(d),sak(a),sek(b){}
	typedef Base_ Kernel_base;
	typedef AK_ AK;
	typedef EK_ EK;
	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();}
	// MSVC is too dumb to perform the empty base optimization.
	typedef std::bool_constant<
	internal::Do_not_store_kernel<Kernel_base>::value &&
	internal::Do_not_store_kernel<AK>::value &&
	internal::Do_not_store_kernel<EK>::value > Do_not_store_kernel;
	//TODO: C2A/C2E could be able to convert *this into this->kernel() or this->kernel2().
	typedef KernelD_converter<Kernel_base,AK> C2A;
	typedef KernelD_converter<Kernel_base,EK> C2E;
	// fix the types
	// TODO: only fix some types, based on some criterion?
	template<class T> struct Type : Get_type<Kernel_base,T> {};
	template<class T,class D,bool=Uses_no_arithmetic<typename Get_functor<Kernel_base,T,D>::type>::value> struct Pred_helper {
	typedef typename Get_functor<AK, T>::type AP;
	typedef typename Get_functor<EK, T>::type EP;
	typedef Filtered_predicate2<Cartesian_filter_K,EP,AP,C2E,C2A> type;
	};
	// Less_cartesian_coordinate doesn't usually need filtering
	// This fixes the predicate, as opposed to Inherit_functor which would leave it open (is that good?)
	template<class T,class D> struct Pred_helper<T,D,true> :
	Get_functor<Kernel_base,T,D> {};
	template<class T,class D=void,class=typename Get_functor_category<Cartesian_filter_K,T>::type, bool=Pred_list::template contains<T>::value> struct Functor :
	Inherit_functor<Kernel_base,T,D> {};
	template<class T,class D> struct Functor<T,D,Predicate_tag,true> :
	Pred_helper<T,D> {};
	// TODO:
	// template<class T> struct Functor<T,No_filter_tag,Predicate_tag> :
	// Kernel_base::template Functor<T,No_filter_tag> {};
	};

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 #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:

cgal/Skin_surface_3/include/CGAL/Skin_surface_traits_3.h

Lines 148 to 181 in 1b534cd

	template < class K, bool UseFilteredPredicates=K::Has_filtered_predicates >
	class Skin_surface_traits_3
	: public Skin_surface_traits_base_3<K>
	{
	typedef Skin_surface_traits_base_3<K> Base;
	public:
	Skin_surface_traits_3() {}
	Skin_surface_traits_3(typename Base::FT s) : Base(s) {}
	enum { Has_filtered_predicates=false };
	};
	} //namespace CGAL
	// Now specialize for Filtered_kernel<CK>, to get
	// the filtered traits automatically.
	#include <CGAL/Skin_surface_filtered_traits_3.h>
	#include <CGAL/Filtered_kernel.h>
	namespace CGAL {
	// Just FK would be nicer, but VC 2005 messes it up with an "FK" in a base class when compiling degenerate_test.cpp
	template < typename Sst3FK >
	class Skin_surface_traits_3 < Sst3FK, true >
	: public Skin_surface_filtered_traits_3 < Sst3FK >
	{
	typedef Skin_surface_filtered_traits_3 < Sst3FK > Base;
	public:
	typedef Sst3FK Kernel;
	Skin_surface_traits_3() {}
	Skin_surface_traits_3(typename Base::FT s) : Base(s) { }
	};

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