[boost] [ICL] How to define infinite endpoint for the types without infinity?

Subject: [boost] [ICL] How to define infinite endpoint for the types without infinity?
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2011-05-15 13:38:23

Hi all,

Denis raised a question concerning handling of infinities in
icl::intervals in an off list email conversation. I thought this could
be of greater interest so I am posting it here.

> On Sat, May 14, 2011 at 4:23 PM, Joachim Faulhaber
> <afojgo_at_[hidden]> wrote:
>
>> 2011/5/14 Denis <denis_at_[hidden]>:
>>> Hello.
>>>
>>> Boost.Icl has four interval types: closed [a,b] for a<=x<=b, open
>>> (a,b) for a<x<b, left-open (a,b] for a<x<=b, rigth-open [a,b) for
>>> a<=x<b.
>>>
>>> That's enough for types which have explicit minimal and maximal
>>> values: double, all integers, boost::time_interval, boost::ptime, ...
>>> But there are types like string and vector, which have the minimal
>>> value (i.e. empty string) but not the maximal one. It makes impossible
>>> to define an interval with infinite right endpoint. Intervals (and
>>> intervals with infinite right end) have sense for strings end vectors,
>>> for sharding.
>>>
>>> Simplest solution looks like to use tuple<bool, string> in place of
>>> string (true means infinity so such a pair will be bigger than any
>>> string). But it will force me to use the pair instead of string
>>> everywhere in the program (or to create pairs before any interval
>>> operation, which implies string copying).
>>>
>>> Is there a better solution? Maybe to add a 5th and 6th interval types
>>> into Icl: closed_to_infinity [a,+inf) and open_to_infinity (a,+inf) ?
>>>
>>> I asked also here:
>>> http://stackoverflow.com/questions/6000655/boost-icl-how-to-define-infinite-endpoint-for-types-without-infinity
>>>
>>
>> Hi Denis,
>>
>> thank you for using Boost.Icl. The point that you are addressing is an
>> interesting one and I was thinking about the integration of infinities
>> while developing the library a few times. Introducing infinity for
>> icl::intervals has some problems. We would have to check for the
>> infinity condition in almost every function, which makes the code more
>> clumsy.
>>
>> I decided not to do this for pragmatic reasons: In most applications
>> of intervals and interval containers infinity is not needed or can be
>> replaced by a value that represents some sufficient maximum. So I
>> thought that this situation does not justify to bloat the code of the
>> interval concept by code related to infinities.
>>
>> I'd be nice if you could provide a small and compelling example using
>> interval containers, where infinities are really needed and can not be
>> replaced by some simple pragmatic means. I am always interested in
>> those use cases to demonstrate the possibilities and check the limits
>> of the usefulness of the ICL. In case you do and the example shows a
>> new important use case I will add it to the library's docs and give
>> credit to you as the author.
>>
>> This was the short answer. If this is o.k. for you, I will provide a
>> longer answer later this weekend and send it to the boost developers
>> and users list and also stack-overflow, because I think the topic is
>> of interest to others as well.
>>
>> Thanks again,
>> Joachim
>>
>
> 2011/5/14 Denis <denis_at_[hidden]>:
> Hi Joachim
>
> Well.
> That's all very depend on do we need to add both infinities or only +infinity.
> I need intervals with open end for arbitrary byte vectors, but I
> cannot imagine what negative infinity can be used for.
> Seems like all the types with negative infinity already have an
> explicit representation of the minimal value (maybe even signed
> biginteger?).

a limitless integer implementation can not have a fixed min and max,
of course, and whether it has a special value for +/-infinity is up to
the library author. To be able to express both infinities might be
interesting even for types like built in integers that have their min
and max values.

> So, hereinafter I talk only about the possibilities of adding +inf as
> endpoint of intervals.
> And I assume that the domain type has its minimal value.
>
> I have just made a small patch (about 30 lines) marking +inf in a bit
> in `interval_bounds` for dynamic bound intervals.
> It has little overhead (the bit is checked only in `bounded_upper()`
> `is_empty()` `exclusive_less()` `contains()` `upper_less()` and
> `operator <<()`) and enabled only for intervals which are dynamic
> bound and continuous.

I see that you have tried to keep the impact of the intended
infinity-extension of the code small...

> As a future optimization, the continuous realm can be divided to
> double-like and string-like ones in order to avoid checking this bit
> for double-likes.

... and thought even further, which is nice.

> Also it not easy to talk about performance when it comes to types like
> strings or vectors.
> Using something like "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF".... to
> represent the maximal blob could be slower and buggy than just an +inf
> bit .
>
>
> About the static intervals.
>
> In the classes `right_open_interval` and `open_interval`, if `_upb`
> contains domain's unit value it comes to an empty interval
> irregardless what is in `_lwb`.

nifty considerations ...

> This is not the only way to represent empty interval, any `_lwb` <=
> `_upb` would also work.
>
> So those extra invariants can be used to store infinity without adding
> extra fields to the static intervals classes.

... nifty but tricky

> Domain's unit in `_upb` can represent +inf, and be seen by comparison
> functions as the biggest value, but still the smallest when it is in
> `_lwb`.
> The case of both `_lwb` and `_upb` having unit will represent the
> whole interval so user's tries to construct a empty interval
> specifying two units (`open_interval("", "")`) should be corrected in
> the constructors (to "\1","\1")
>
> In order not to impact the performance of the existing
> `right_open_interval` and `open_interval`, two new classes
> `right_open_interval_with_inf` and `open_interval_with_inf` can be
> created by copying with small patching of the comparators and the
> constructors.

hmm... your posting is interesting with respect to different aspects.

You are obviously using icl::intervals (and I guess also
icl::interval_containers) with domain types of some types like string
and (byte)vector. It was my ambition to allow for such types as domain
types in addition to numbers. Of course you have to watch efficiency,
if your values get large (not to mention approaching infinity ;)
Because you are using icl in this realm you might experience
difficulties and even detect bugs that no one else has found. Also you
might explore properties of the underlying concept, which is the
concept of a sequence, I guess.

As I wrote in my first answer, I'd be very much interested in a short
compelling example for the tutorial that demonstrates the kind of use
case that you cover. It might be kind of unique and open up a new
horizon of icl usage.

I think it is a good idea to implement infinity as a property of
intervals instead of using special values. I had similar
considerations, but as I mentioned earlier, I didn't do that for
pragmatic considerations. I think a real need to work with infinities
does not occur in most applications. And even if someone want's to use
them, it is always only a phenomenom that applies to the very first or
last interval of an interval container. It might be true that by good
design and use of metaprogramming we might be able to limit the impact
a infinity extension to just a few functions and I acknowledge you
tried to demonstrate that. Still these are functions (e.g.
exclusive_less) that are called extremely frequently. So there is
performance penalty also on those majority of instances where
infinities are not needed at all.

I appreciate your ideas but I guess I need some more time to think
about them. One possibility might be to create a concept for infinity
bounded intervals on top of dynamic intervals. So only users who
explicitly need to model infinity bounded intervals would choose
those.

Regards,
Joachim

-- 
Interval Container Library [Boost.Icl]
http://www.joachim-faulhaber.de