Hello, 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. I can get the AND part with the intersect function. I can guess the OR part if there is any intersection or not (and then use hull). I handle the priorities myself (I split the expression with Spirit). This expression can be easily solved. 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... Is there anything I can do ? Is there any way to 'combine' intervals (ie keeping the union somewhere)? I believe this is easy to solve, I just don't know where to look for. Thank you, John
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
Guillaume Melquiond <guillaume.melquiond <at> ens-lyon.fr> writes:
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.
I want to simplify the expression as much as possible. IE if I have as input to my program " ( (1,15) AND ( 10,20) ) OR (25,30)" I want to get as output " (10,15) OR (25,30)"
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.
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?
Best regards,
Guillaume
Thank you for your help. John
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
Guillaume Melquiond <guillaume.melquiond <at> ens-lyon.fr> writes:
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.
Yes, that's what I meant. See attached file for an example with std::set_* look-alike functions. They should fit your application.
Guillaume
I have looked at your file, and apart from the lists it looks like what I was trying. The list looks useful I have to look more into that (well for now I have a Group class holding intervals and keywords with vectors). Also like you said in your first comment it looks like I won't be able to only use one tree (priorities). So I need to find a distributive function too. If you have anything on that too I'd gladly take it :) Thank you Guillaume, John
Actually I may have a simple solution in mind using the file you sent me yesterday. It may be a lot easier than I expected, I just need to try that and see how it works. I'll give you the results today or next week. Again thank you for your help Guillaume, it has been very helpful! John
Ok after spending much more time than I thought on things, I have finished my program. Thanks a lot for your example file, I actually used it instead of the functions I had written. I modify it for my needs, added an AND NOT function and now this helper does exactly what I need. Your code was also very clean and allowed me to learn a few things I did not know (like the back_inserter). Again Guillaume thanks a lot for your help, it was really helpful. John
participants (2)
-
Guillaume Melquiond -
john