Re: [boost] proposal interval container; ITL moved to the boost sandbox

Subject: Re: [boost] proposal interval container; ITL moved to the boost sandbox
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2009-11-11 11:21:52

2009/11/11 vicente.botet <vicente.botet_at_[hidden]>:
> 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/interface/function_synopsis.html)

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