I would like to check whether a boost::icl::right_open_interval<double> i1 and a boost::icl::closed_interval<double> i2 have an intersection. Unfortunately, the boost::icl::intersects(i1, i2) function only works when i1 and i2 share the same type. I was wondering
- why different interval types are not supported, as it seems natural for an interval library, and
- if there is a nice way to generalize the above function to different interval types.
CodePudding user response：
There type model the Static Interval concept:
There is also the Dynamic Interval concept, which basically adds runtime state indicating the interval_bounds:
using icl::interval_bounds;
using std::is_same_v;
using I = icl::interval<double>;
using CI = I::interval_type;
auto a = I::right_open(3, M_PI);
auto b = I::closed(3.14, 5);
auto c = I::left_open(7, std::numeric_limits<double>::infinity());
for (auto lhs : {a, b, c})
for (auto rhs : {a, b, c})
std::cout << lhs << " & " << rhs << " = " << (lhs & rhs) << "" << std::endl;
Prints
[3,3.14159) & [3,3.14159) = [3,3.14159)
[3,3.14159) & [3.14,5] = [3.14,3.14159)
[3,3.14159) & (7,inf] = ()
[3.14,5] & [3,3.14159) = [3.14,3.14159)
[3.14,5] & [3.14,5] = [3.14,5]
[3.14,5] & (7,inf] = (]
(7,inf] & [3,3.14159) = ()
(7,inf] & [3.14,5] = (]
(7,inf] & (7,inf] = (7,inf]
The effective types are all the same:
static_assert(is_same_v<decltype(a), CI>);
static_assert(is_same_v<decltype(b), CI>);
static_assert(is_same_v<decltype(c), CI>);
static_assert(is_same_v<CI, icl::continuous_interval<double>>);
You can use this for your use case:
auto i1 = icl::right_open_interval<double>(3, M_PI);
auto i2 = icl::closed_interval<double>(3.14, 5);
auto i3 = icl::left_open_interval(7.0, std::numeric_limits<double>::infinity());
As you know they do NOT have the same type:
static_assert(not is_same_v<decltype(i1), decltype(i2)>);
static_assert(not is_same_v<decltype(i1), decltype(i3)>);
static_assert(not is_same_v<decltype(i2), decltype(i3)>);
These static interval types exist so the library can have absolutely minimum runtime overhead/storage. Imagine storing a million intervals in an array. If you know the type, do you really want to incur the size overhead:
static_assert(sizeof(i1) == sizeof(i2));
static_assert(sizeof(i2) == sizeof(i3));
static_assert(sizeof(I::interval_type) == sizeof(i1) 8);
Of course not.
However, some operations are only statically implemented for homogenous operands, as you found out. Generic code can find out the bounds type for any given interval type:
static_assert(icl::interval_bound_type<decltype(i1)>::value == interval_bounds::static_right_open);
static_assert(icl::interval_bound_type<decltype(i2)>::value == interval_bounds::static_closed);
static_assert(icl::interval_bound_type<decltype(i3)>::value == interval_bounds::static_left_open);
static_assert(icl::interval_bound_type<CI>::value == interval_bounds::dynamic);
So, you can convert to suit your needs:
template <typename I>
auto make_dynamic(I const& in) {
static_assert(icl::is_interval<I>::value);
static_assert(icl::has_static_bounds<I>::value);
using T = icl::interval_traits<I>;
using D = typename T::domain_type;
using R = std::conditional_t<icl::is_continuous<D>::value,
icl::continuous_interval<D>,
icl::discrete_interval<D>>;
constexpr auto b = icl::interval_bound_type<I>::value;
return icl::dynamic_interval_traits<R>::construct(
T::lower(in), T::upper(in), static_cast<icl::interval_bounds>(b));
}
And then:
for (auto lhs : {make_dynamic(i1), make_dynamic(i2), make_dynamic(i3)})
for (auto rhs : {make_dynamic(i1), make_dynamic(i2), make_dynamic(i3)})
{
std::cout << lhs << " & " << rhs << " = " << (lhs & rhs) << "" << std::endl;
converted_results.push_back(lhs & rhs);
}
Prints the exact same as above:
[3,3.14159) & [3,3.14159) = [3,3.14159)
[3,3.14159) & [3.14,5] = [3.14,3.14159)
[3,3.14159) & (7,inf] = ()
[3.14,5] & [3,3.14159) = [3.14,3.14159)
[3.14,5] & [3.14,5] = [3.14,5]
[3.14,5] & (7,inf] = (]
(7,inf] & [3,3.14159) = ()
(7,inf] & [3.14,5] = (]
(7,inf] & (7,inf] = (7,inf]
Here's an applied example showing how create a mapping of intervals:
using Set = std::set<char>;
boost::icl::interval_map<double, Set> s;
s.add({a, Set{'a'}});
s.add({b, Set{'b'}});
s.add({c, Set{'c'}});
std::cout << "s: " << s << "\n";
Prints:
s: {([3,3.14)->{a })([3.14,3.14159)->{a b })([3.14159,5]->{b })((7,inf]->{c })}
See all the code Live On Coliru
Recommendation
This all looks a bit clumsy, right. Therefore I'd suggest picking a camp: dynamic bounds or static bounds.
If you really want static bounds, consider defining BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS:
// If this macro is defined, right_open_interval with static interval borders
// will be used as default for all interval containers.
// BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS should be defined in the application
// before other includes from the ITL
//#define BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS
// If BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS is NOT defined, ITL uses intervals
// with dynamic borders as default.
Note this has the effect of e.g. making interval sets/maps using right-open intervals always. See a more elaborate example: https://www.boost.org/doc/libs/1_78_0/libs/icl/doc/html/boost_icl/examples/static_interval.html, and the Interface documentation.
Listing
For future reference:
#include <boost/icl/interval_map.hpp>
#include <iostream>
namespace icl = boost::icl;
template <typename I>
auto make_dynamic(I const& in) {
static_assert(icl::is_interval<I>::value);
static_assert(icl::has_static_bounds<I>::value);
using T = icl::interval_traits<I>;
using D = typename T::domain_type;
using R = std::conditional_t<icl::is_continuous<I>::value,
icl::continuous_interval<D>,
icl::discrete_interval<D>>;
constexpr auto b = icl::interval_bound_type<I>::value;
return icl::dynamic_interval_traits<R>::construct(
T::lower(in), T::upper(in), static_cast<icl::interval_bounds>(b));
}
int main() {
using icl::interval_bounds;
using std::is_same_v;
using I = icl::interval<double>;
using CI = I::interval_type;
auto a = I::right_open(3, M_PI);
auto b = I::closed(3.14, 5);
auto c = I::left_open(7, std::numeric_limits<double>::infinity());
std::cout << "--------------" << std::endl;
std::vector<CI> dynamic_results;
for (auto lhs : {a, b, c})
for (auto rhs : {a, b, c})
{
std::cout << lhs << " & " << rhs << " = " << (lhs & rhs) << "" << std::endl;
dynamic_results.push_back(lhs & rhs);
}
static_assert(is_same_v<decltype(a), CI>);
static_assert(is_same_v<decltype(b), CI>);
static_assert(is_same_v<decltype(c), CI>);
static_assert(is_same_v<CI, icl::continuous_interval<double>>);
auto i1 = icl::right_open_interval<double>(3, M_PI);
auto i2 = icl::closed_interval<double>(3.14, 5);
auto i3 = icl::left_open_interval(7.0, std::numeric_limits<double>::infinity());
static_assert(not is_same_v<decltype(i1), decltype(i2)>);
static_assert(not is_same_v<decltype(i1), decltype(i3)>);
static_assert(not is_same_v<decltype(i2), decltype(i3)>);
static_assert(sizeof(i1) == sizeof(i2));
static_assert(sizeof(i2) == sizeof(i3));
static_assert(sizeof(I::interval_type) == sizeof(i1) 8);
static_assert(icl::interval_bound_type<decltype(i1)>::value == interval_bounds::static_right_open);
static_assert(icl::interval_bound_type<decltype(i2)>::value == interval_bounds::static_closed);
static_assert(icl::interval_bound_type<decltype(i3)>::value == interval_bounds::static_left_open);
static_assert(icl::interval_bound_type<CI>::value == interval_bounds::dynamic);
std::cout << "--------------" << std::endl;
std::vector<CI> converted_results;
for (auto lhs : {make_dynamic(i1), make_dynamic(i2), make_dynamic(i3)})
for (auto rhs : {make_dynamic(i1), make_dynamic(i2), make_dynamic(i3)})
{
std::cout << lhs << " & " << rhs << " = " << (lhs & rhs) << "" << std::endl;
converted_results.push_back(lhs & rhs);
}
assert(dynamic_results == converted_results);
using Set = std::set<char>;
boost::icl::interval_map<double, Set> s;
s.add({a, Set{'a'}});
s.add({b, Set{'b'}});
s.add({c, Set{'c'}});
std::cout << "s: " << s << "\n";
}
Prints
--------------
[3,3.14159) & [3,3.14159) = [3,3.14159)
[3,3.14159) & [3.14,5] = [3.14,3.14159)
[3,3.14159) & (7,inf] = ()
[3.14,5] & [3,3.14159) = [3.14,3.14159)
[3.14,5] & [3.14,5] = [3.14,5]
[3.14,5] & (7,inf] = (]
(7,inf] & [3,3.14159) = ()
(7,inf] & [3.14,5] = (]
(7,inf] & (7,inf] = (7,inf]
--------------
[3,3.14159) & [3,3.14159) = [3,3.14159)
[3,3.14159) & [3.14,5] = [3.14,3.14159)
[3,3.14159) & (7,inf] = ()
[3.14,5] & [3,3.14159) = [3.14,3.14159)
[3.14,5] & [3.14,5] = [3.14,5]
[3.14,5] & (7,inf] = (]
(7,inf] & [3,3.14159) = ()
(7,inf] & [3.14,5] = (]
(7,inf] & (7,inf] = (7,inf]
s: {([3,3.14)->{a })([3.14,3.14159)->{a b })([3.14159,5]->{b })((7,inf]->{c })}