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