Re: [Boost-users] Interval library

From: Guillaume Melquiond (guillaume.melquiond_at_[hidden])
Date: 2007-11-15 06:22:52

Le mercredi 14 novembre 2007 à 22:16 +0000, john a écrit :

> > 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.
> Yep, that is the option I have in mind, I just don't have the slightest idea as
> how to do that on big expressions keeping priorities. Well it's probably
> feasible I just need to think a little more.

You probably cannot perform the computations on the fly. I guess you
have to store your expressions as trees, and then to transform these
trees so that the disjunction nodes are at the root.

> > 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.
> Can you elaborate on that part please? Do you mean something like having my own
> function working on those lists and then the small elements would be passed to
> the existing functions withing Interval?

Yes, that's what I meant. See attached file for an example with
std::set_* look-alike functions. They should fit your application.

Guillaume