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@googlemail.com> wrote:
2011/5/14 Denis <denis@camfex.cz>:
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-...
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@camfex.cz>: 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