Re: [Boost-users] Interval library

From: Guillaume Melquiond (guillaume.melquiond_at_[hidden])
Date: 2007-11-14 16:07:09

Le mercredi 14 novembre 2007 à 18:43 +0000, john a écrit :

> I am trying to use the Interval library to solve boolean expressions like this:
> 
> (I1 AND I2) or I3, where I1, I2 and I3 are intervals.

Sorry, I don't understand what you mean by solving boolean expressions.
So my reply may be off. Please detail a bit more if that is so.

> My problem is working with big expressions including OR. 
> For example if I have "(I1 OR I2) AND I3" I cannot call intersect( I1|I2, I3).
> This is easy as it is a small expression, but when it gets to 10+ members...

Note that you can use distributivity of one operation with respect to
the other. Your example can be transformed into (I1 AND I3) OR (I2 AND
I3), which is as simple to solve as your first case, since all the
unions have been moved to the top of the expression.

> Is there anything I can do ? 
> Is there any way to 'combine' intervals (ie keeping the union somewhere)?

Unfortunately, the interval library does not provide any helper code to
handle (disjoint) sets of intervals. This should not be too hard to
implement in your own code though. For example, you can decide to
represent these sets with the type std::list< interval<...> > and with
the invariant that the upper bound of an interval in a list is strictly
less than the lower bound of the next interval of the list. Then union
and intersection become operations with linear complexity in the size of
the lists.

Best regards,

Guillaume