2009/11/11 vicente.botet <vicente.botet@wanadoo.fr>:
Hi Joachim,
Hey Vicente! you digged up a pretty old thread on my lib *and completely post quoted* all the outdated stuff. I bet Dave won't like that ;-)
happy to hear you library is ready for review.
. . . but suffering from review manager starvation.
I have a particular use case:
I'm happy to hear that you are creatively using it :)
The intervals I need to store represent the memory used by data. As data can be composed either using arrays or structures we have that the intervals to be stored can overlap but only if one is included by the other. The operation I need is to know if a given interval overlaps with an interval set.
Do you see any possible optimization for this specific case?
First of all let me shortly review the operations that are already available (see also: http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/int...) If you have interval containers ic, ic_i, be it an interval_set or an interval_map and an interval i you can always use these functions: ic.intersects(i); // does ic overlap with i? ic &= i; // ic becomes the intersection of ic and i ic1 = ic & i; ic2 = i & ic; // the intersection of ic and i is assigned to ic{1,2} ic.add_intersection(ic3, i); // ic3 collects the intersections // of ic and i. (1) None of those knows about the new distinction between legal and illegal kinds of overlaps that you need. But the first thing you can do is, that you compute the intersection ic.add_intersection(overlaps, i); for(interval_set<some>::iterator it = overlaps.begin(); ...) // check and process legal overlaps and process the result. (2) The other possibility is to use an interval_map that has associated values providing information about the object nesting. typedef interval_map<Location, NestedObj> ObjectStorageT; NestedObj will probably be a class that expresses the include-property by some path concept: a.b : b is nested under a a.c : c is nested under a A set of such paths can represent a (sub)tree of your nested object structure. A name is 'legal' if it occurs in a path, as node or subpath. An intersecting operation on NestedObj could be something like: {a.b,a.c}&{b}->{a.b} //returns the path containing 'b' {a.b}&{c} -> {} //c is not included. Returns empty set {a.b,a.c}&{a}->{a.b,a.c}//all pathes containing a Now we can compute legal overlaps. (Use typewriter font to beautify) ObjectStorageT im; ObjectStorageT::segment_type s; Example 1: {[1 5)[5 9)} =: im ->{a.b} ->{a.c} & intersection with [3 7) segment s -> {a} s = (i,{a}) | V {[3 5)[5 7)} im2 = im & s ->{a.b} ->{a.c} Example 2: {[1 5)[5 9)} =: im ->{a.b} ->{a.c} & intersection with [3 7) segment s -> {b} s = (i,{b}) | V {[3 5)} im2 = im & s ->{a.b} Note: [5 7) is removed from im2 because ->{} the empty path set {} is a neutral element and will be 'absorbed'. Example 3: {[1 5)[5 9)} =: im ->{a.b} ->{a.c} & intersection with [3 7) segment s -> {d} s = (i,{d}) | V {} im2 = im & s These are some quick ideas about the way, in which I would use interval containers to solve such a problem. Please (don't;) take this as a ready-made solution. There will probably be some difficulties on the way to a real world implementation. What I would like to show though is that interval containers with aggregate on overlap can be viewed as a pattern or idiom that can generate a variety of solutions to different problems. HTH Joachim