How can I allow statically bounded, continuous singleton intervals in boost::icl containers

Question

I use boost ICL to model a mapping of time to states and event, where I model time as double. Some events are momentary, i.e. they do not occur over an interval of time, but rather at a single point of time, which I can model conceptually as a singleton interval. When trying to add these concept as singleton intervals to boost ICL, I am facing some problems however.

• A boost::icl::right_open_interval (the default type when with #define BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS) singleton appears to not be valid - boost::icl::intersects returns false in all cases and the intersection returns [0,0) in all cases. The latter seems to even indicate an invalid interval. This is understandable insofar as [a,a) denotes the set {x | a <= x < a}, i.e. an empty set.

• A boost::icl::closed_interval seems therefore more suited to model a singleton. It is however, not default-constructible with a DomainT of double due to a static assert BOOST_STATIC_ASSERT((icl::is_discrete<DomainT>::value));. The interval containers require default constructible intervals however.

So I am a bit stuck on what to do. Is this just a question of choosing the right interval type or defining a custom one? Do singleton intervals even work at all with continuous types, or is this a conceptual misunderstanding on my part? After all, the concepts of "touching" intervals and intersections with singletons get very muddied. The intervals [a,b), [b,c) obviously touch, whereas with closed intervals [a,b], [b,c] would intersect in the singleton [b,b]. So maybe singletons don't work at all and need to be modeled by some finite [a, a+ε)?

Answer 1

Yes, I think you can remove all the issues you describe by using a discrete time domain. It moves all the "muddy-ness" to the sampling edge of your data, instead of encumbering your logic with the complexities.

Also, it will be fit for use with more operations on statically bounded intervals. E.g. continuous domains do not allow singletons with static intervals. This restriction is documented in Table 1.14

T	discrete _interval	continuous _interval	right_open _interval	left_open _interval	closed _interval	open _interval
Interval bounds	dynamic	dynamic	static	static	static	static
Form	asymmetric	asymmetric	symmetric	symmetric
Construct
T singleton(const P&)	d	c	d	d	d	d
T construct(const P&, const P&)	d	c	d c	d c	d	d
...

and more detailed under Interval Construction:

Construct	Description
T singleton(const P& value)	Constructs an interval that contains exactly one element value. For all interval types of the icl sigletons can be constructed for discrete domain types. For continuous domain types, only continuous_interval is capable to construct a singleton.

Example

There's a library example that demonstrates/clarifies most of these points, and the comments are worth reading. It even defines a toy Time type to model time discretely. It should be easy to replace it with std::chrono time_point e.g. since C++11 is probably ubiquitous. Here's the example mildly modernized:

#include <cmath>

// We can change the library default for the interval types by defining 
#define BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS
// prior to other inluces from the icl.
// The interval type that is automatically used with interval
// containers then is the statically bounded right_open_interval.

#include <boost/icl/interval_set.hpp>
#include <boost/icl/split_interval_set.hpp>
// The statically bounded interval type 'right_open_interval'
// is indirectly included via interval containers.

#include "toytime.hpp"
#include <boost/icl/rational.hpp>

using namespace boost::icl;

int main() {
    std::cout << ">> Interval Container Library: Sample static_interval.cpp <<\n";

    // Statically bounded intervals are the user defined library default for 
    // interval parameters in interval containers now.
    static_assert(std::is_same_v<interval_set<int>::interval_type, right_open_interval<int>>);
    static_assert(std::is_same_v<interval_set<float>::interval_type, right_open_interval<float>>);

    // As we can see the library default both for discrete and continuous
    // domain_types T is 'right_open_interval<T>'.
    // The user defined library default for intervals is also available via 
    // the template 'interval':
    static_assert(std::is_same<interval<int>::type, right_open_interval<int>>::value);

    // Again we are declaring and initializing the four test intervals that have been used
    // in the example 'interval' and 'dynamic_interval'
    interval<int>::type    int_interval  = interval<int>::right_open(3, 8); // shifted the upper bound
    interval<double>::type sqrt_interval = interval<double>::right_open(1/sqrt(2.0), sqrt(2.0));

    // Interval ("Barcelona", "Boston"] can not be represented because there is no 'steppable next' on
    // lower bound "Barcelona". Ok. this is a different interval:
    interval<std::string>::type city_interval = interval<std::string>::right_open("Barcelona", "Boston");

    // Toy Time is discrete again so we can transfrom open(Time(monday,8,30), Time(monday,17,20))
    //                                       to right_open(Time(monday,8,31), Time(monday,17,20))
    auto time_interval = interval<Time>::right_open({monday, 8, 31}, {monday, 17, 20});

#define CONTAINED(ival, val)                                                                                 \
    ival << " does " << (contains(ival, val) ? "" : "NOT ") << "contain " << #val << std::endl

    std::cout << "right_open_interval<int>   : " << int_interval  << std::endl;
    std::cout << "right_open_interval<double>: " << CONTAINED(sqrt_interval, sqrt(2.0));
    std::cout << "right_open_interval<string>: " << CONTAINED(city_interval, "Barcelona");
    std::cout << "right_open_interval<string>: " << CONTAINED(city_interval, "Boston");
    std::cout << "right_open_interval<Time>  : " << time_interval << "\n";

    using Ratio = boost::rational<int>;

    // Using statically bounded intervals does not allows to apply operations
    // with elements on all interval containers, if their domain_type is continuous.
    // The code that follows is identical to example 'dynamic_interval'. Only 'internally'
    // the library default for the interval template now is 'right_open_interval'
    auto unit_interval = interval<Ratio>::right_open(0, 1);
    interval_set<Ratio>  unit_set(unit_interval);
    interval_set<Ratio > ratio_set(unit_set);
    //ratio_set -= Ratio(1, 3); // This line will not compile, because we can not
                              //// represent a singleton interval as right_open_interval.
}

Printing

>> Interval Container Library: Sample static_interval.cpp <<
right_open_interval<int>   : [3,8)
right_open_interval<double>: [0.707107,1.41421) does NOT contain sqrt(2.0)
right_open_interval<string>: [Barcelona,Boston) does contain "Barcelona"
right_open_interval<string>: [Barcelona,Boston) does NOT contain "Boston"
right_open_interval<Time>  : [mon:08:31,mon:17:20)