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
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Joachim Faulhaber Sent: 05 November 2008 14:14 To: boost@lists.boost.org 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 +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS pbristow@hetp.u-net.com
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@googlemail.com> To: <boost@lists.boost.org> 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
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
participants (3)
-
Joachim Faulhaber -
Paul A Bristow -
vicente.botet