使用 Boost ICL 交叉不同的间隔类型
Intersecting dfferent interval types with Boost ICL
我想检查 boost::icl::right_open_interval<double> i1 和 boost::icl::closed_interval<double> i2 是否有交集。不幸的是，boost::icl::intersects(i1, i2) 函数仅在 i1 和 i2 共享同一类型时才有效。我在想
- 为什么不支持不同的间隔类型，因为间隔库似乎很自然，并且
- 如果有一种很好的方法可以将上述函数推广到不同的区间类型。
有类型模型静态间隔概念：
还有动态间隔概念，它基本上添加了指示 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;
版画
[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]
有效类型都一样：
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)>);
存在这些静态间隔类型，因此库可以具有绝对最小的运行时间 overhead/storage。想象一下在数组中存储一百万个间隔。如果你知道类型，你真的想要承担大小开销：
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);
因此，您可以根据需要进行转换：
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));
}
然后：
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);
}
打印与上面完全相同的内容：
[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]
下面是一个应用示例，展示了如何创建间隔映射：
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";
打印：
s: {([3,3.14)->{a })([3.14,3.14159)->{a b })([3.14159,5]->{b })((7,inf]->{c })}
查看全部代码Live On Coliru
推荐
这一切看起来有点笨拙，对吧。因此我建议选择一个阵营：动态边界或静态边界。
如果你真的想要静态边界，考虑定义 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.
请注意，这具有例如始终使用 right-open 间隔制作间隔 sets/maps。请参阅更详细的示例：https://www.boost.org/doc/libs/1_78_0/libs/icl/doc/html/boost_icl/examples/static_interval.html, and the Interface documentation.
列表
供将来参考：
#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";
}
版画
--------------
[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 })}
我想检查 boost::icl::right_open_interval<double> i1 和 boost::icl::closed_interval<double> i2 是否有交集。不幸的是，boost::icl::intersects(i1, i2) 函数仅在 i1 和 i2 共享同一类型时才有效。我在想
- 为什么不支持不同的间隔类型，因为间隔库似乎很自然，并且
- 如果有一种很好的方法可以将上述函数推广到不同的区间类型。
有类型模型静态间隔概念：
还有动态间隔概念，它基本上添加了指示 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;
版画
[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]
有效类型都一样：
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)>);
存在这些静态间隔类型，因此库可以具有绝对最小的运行时间 overhead/storage。想象一下在数组中存储一百万个间隔。如果你知道类型，你真的想要承担大小开销：
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);
因此，您可以根据需要进行转换：
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));
}
然后：
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);
}
打印与上面完全相同的内容：
[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]
下面是一个应用示例，展示了如何创建间隔映射：
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";
打印：
s: {([3,3.14)->{a })([3.14,3.14159)->{a b })([3.14159,5]->{b })((7,inf]->{c })}
查看全部代码Live On Coliru
推荐
这一切看起来有点笨拙，对吧。因此我建议选择一个阵营：动态边界或静态边界。
如果你真的想要静态边界，考虑定义 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.
请注意，这具有例如始终使用 right-open 间隔制作间隔 sets/maps。请参阅更详细的示例：https://www.boost.org/doc/libs/1_78_0/libs/icl/doc/html/boost_icl/examples/static_interval.html, and the Interface documentation.
列表
供将来参考：
#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";
}
版画
--------------
[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 })}