proposal interval container; ITL moved to the boost sandbox

[Joachim Faulhaber]

Dear boosters,

after completion of a lot of boostification work I moved
my Interval Template Library to the boost sandbox in the
boost project centric form:
https://svn.boost.org/trac/boost/browser/sandbox/itl

itl
  boost
    itl
    [itl_xt]
    [validate]
  libs
    itl
    [itl_xt]
    [validate]

I have split up the original library into three parts:
(1) itl, (2) itl_xt and (3) validate.

Core part 1 'ITL' contains all interval container class
templates. Only this part will be prepared for a formal
submission.

Part 2 'itl_xt' contains extended parts of the original
library that do not belong to the core interval container
data structures and might be proposed for later extensions.

Part 3 'validate' contains the sources for the law based test
automaton 'LaBatea' that has been used for an automated
check of the ITLs correctness.

Parts 2 and 3 do not yet conform boost standards and naming
conventions and are not yet intended as contributions to boost.

On the core ITL-part I have done the following:

+ Removed all virtual functions via introduction of mixins
+ Integrated deeper into boost libraries replacing own code
  by e.g. boost::type_traits and boost::mpl
+ Minimized the class template interfaces by
  transforming member functions into non member function
  templates.
+ Made interval containers more interoperable by overloading
  operators and global function templates.
+ Wrote a test suite using boost unit test tools. Tested for
  boost-instance types boost::date_time and boost::rational
+ Provided jamfiles to build and run examples and tests.
+ All examples and tests have been compiled, linked and run
  successfully with msvc_9.0 and gcc_3.4.4(cygwin).

Next I am going to write boost style html-documentation.

>From the boost web page I don't see a clear recommendation for
a preferable way of doing that. Handcoded? Generated with
BoostBook? Is there a reference library that has an exemplary
standard documentation?

Cheers
Joachim
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Paul A. Bristow-2]

 

>-----Original Message-----
>From: boost-bounces@...
>[mailto:boost-bounces@...] On Behalf Of Joachim Faulhaber
>Sent: 05 November 2008 14:14
>To: boost@...
>Subject: [boost] proposal interval container; ITL moved to the
>boost sandbox

<big snip>

>Next I am going to write boost style html-documentation.

I'm surprised you have the strength left ;-)
>
>>From the boost web page I don't see a clear recommendation for
>a preferable way of doing that. Handcoded? Generated with
>BoostBook? Is there a reference library that has an exemplary
>standard documentation?

As a joint (junior) author of one large library, I have no hesitation of recommending Quickbook as an author-friendly system.  From
a familiar WikiWiki language, it produces nice html and also even nicer pdf with no extra work.

It's weakness is the very complex toolchain, but if you copy other peoples examples (and watch out for the bizarre syntax) you will
find the actual writing fairly painless.  If you have lots of classes etc you can use DOxygen as well if you wish. Make sure you can
re-generate existing documentation before you start:  this will check you have got the toolchain set up right.  

For examples, see the nice'n'friendly Quickbook documentation - done with Quickbook of course ;-)

For outputs, see the Math Toolkit and Units documentation, both some 500 pages - more than you will produce I suspect.

I strongly recommend using 'Quickbook embedded in source code as comments' as a way of keeping your selected snippets of source code
synced with the documentation.  Many of the Math examples are done this way.  It means that if you read the example code, you have
the Quickbook commentary, or if you read the documentation, the (sElected) C++ code is shown in nice boxes.

Have fun!

Paul

---
Paul A Bristow
Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB
[phone] & SMS, Mobile [phone] & SMS
pbristow@...

 





_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Joachim Faulhaber]

2008/11/5 Paul A Bristow <pbristow@...>:
>
> I have no hesitation of recommending Quickbook as an author-friendly system.
>
Thank you for the quick help, Joachim
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Vicente Botet Escriba]

Hi Joachim,

happy to hear you library is ready for review.

I have a particular use case:
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?

Best,
Vicente

----- Original Message -----
From: "Joachim Faulhaber" <afojgo@...>
To: <boost@...>
Sent: Wednesday, November 05, 2008 3:14 PM
Subject: [boost] proposal interval container; ITL moved to the boost sandbox

>
> Dear boosters,
>
> after completion of a lot of boostification work I moved
> my Interval Template Library to the boost sandbox in the
> boost project centric form:
> https://svn.boost.org/trac/boost/browser/sandbox/itl
>
> itl
>  boost
>    itl
>    [itl_xt]
>    [validate]
>  libs
>    itl
>    [itl_xt]
>    [validate]
>
> I have split up the original library into three parts:
> (1) itl, (2) itl_xt and (3) validate.
>
> Core part 1 'ITL' contains all interval container class
> templates. Only this part will be prepared for a formal
> submission.
>
> Part 2 'itl_xt' contains extended parts of the original
> library that do not belong to the core interval container
> data structures and might be proposed for later extensions.
>
> Part 3 'validate' contains the sources for the law based test
> automaton 'LaBatea' that has been used for an automated
> check of the ITLs correctness.
>
> Parts 2 and 3 do not yet conform boost standards and naming
> conventions and are not yet intended as contributions to boost.
>
> On the core ITL-part I have done the following:
>
> + Removed all virtual functions via introduction of mixins
> + Integrated deeper into boost libraries replacing own code
>  by e.g. boost::type_traits and boost::mpl
> + Minimized the class template interfaces by
>  transforming member functions into non member function
>  templates.
> + Made interval containers more interoperable by overloading
>  operators and global function templates.
> + Wrote a test suite using boost unit test tools. Tested for
>  boost-instance types boost::date_time and boost::rational
> + Provided jamfiles to build and run examples and tests.
> + All examples and tests have been compiled, linked and run
>  successfully with msvc_9.0 and gcc_3.4.4(cygwin).
>
> Next I am going to write boost style html-documentation.
>
>>From the boost web page I don't see a clear recommendation for
> a preferable way of doing that. Handcoded? Generated with
> BoostBook? Is there a reference library that has an exemplary
> standard documentation?
>
> Cheers
> Joachim
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Joachim Faulhaber]

2009/11/11 vicente.botet <vicente.botet@...>:
> 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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost