[boost] Review Request: Boost.Itl; The Interval Template Library

Subject: [boost] Review Request: Boost.Itl; The Interval Template Library
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2009-09-18 06:10:30

Dear developers,

the Interval Template Library is now in a state
where I think it does conform the requirements
and guidelines for boost libraries fairly well.
To decide, whether it's design, implementation
and overall usefulness is sufficient to be
accepted in the boost libraries collection is
now up to you.

In the last round of refactoring I concentrated on
efficiency and optimization issues.
The implementation of the itl's interval containers
is still based on std::set and std::map, but algorithms
are now exploiting hinted insert and are manipulating
intervals and values in place instead of copying in
many instances. This way, it has been possible to
improve performance significantly.

Along the way of implementing optimizations I have
documented the complexity guarantees for all important
functions of the library's interface.

Please note that the original ITL as presented in May 2008
has been split into 3 parts and only the *first* part is
submitted for review:

itl     : Core library, interval containers, SUBMITTED FOR REVIEW

Additional parts are:
itl_xt  : Extensions like histories and generalized crosstables
validate: The law based test automaton (LaBatea). A validation
         tool using laws aka axioms.

*itl* is a complete library containing all required ingredients
particularly a separate test suite (NOT using LaBatea) and the
quickbook documentation. The code is successfully compiled
and tested with gcc-3.4.4, 4.1.0, 4.3.2 and msvc-8.0, 9.0.
I have uploaded the review version as
itl_3_1_0.zip to the vault in section containers.

http://www.boostpro.com/vault/index.php?action=downloadfile&filename=itl_3_1_0.zip&directory=Containers

Another file itl_plus_3_1_0.zip contains all three parts
(itl, itl_xt and validate).

http://www.boostpro.com/vault/index.php?action=downloadfile&filename=itl_plus_3_1_0.zip&directory=Containers

Reviewers interested in the law based testing
part may have to refer to this file to examine
those tests. The law base testing examples
compile and run with gcc-4.3.2, msvc-8.0 and 9.0.
LaBatea does not compile with gcc-4.1.0 or older.

The quickbook generated documentation is included in the
zip files and is also available online at
http://herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/index.html

Sources are also available form the sandbox:
https://svn.boost.org/svn/boost/sandbox/itl/

To close my request for review, let me take the opportunity
to do some advertisement ;-) focusing on some of the itl's
highlights.

* The Itl emerged out of real world software development
 extracting generic functionality from numerous use
 cases of the date time problem domain.
 (http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/examples.html)
 But the need for the same data structures occurs in
 other fields as well. E.g. Zachary Turner uses a
 compressed_bitmap similar to an itl::interval_set to
 manage very large file system allocation bitmaps and
 gives more use cases here
 (http://lists.boost.org/Archives/boost/2009/06/152817.php).

* Aggregation on overlap not only provides a useful
 feature to compute aggregation results on interval_maps
 like statistics, it also leads to a generalized
 addition operation on maps that exhibits interesting
 semantical properties. E.g.
 (http://herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/semantics.html#boost_itl.semantics.concept_induction)

* The itl's design is based on sets of laws (aka axioms)
 that are described in the documentation.
 (http://herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/semantics.html)
 These law sets not only are giving a formal specification
 of the library. Using the law based testing tool (LaBatea)
 (https://svn.boost.org/svn/boost/sandbox/itl/boost/validate)
 allows to validate the library code for every specified
 law.

* For the itl, 18 laws have been validated on the
 7 container templates with varying instantiation types
 for template parameters, running a total of 719 different
 law instances (each of them for large numbers of
 randomly generated test data).
 (https://svn.boost.org/svn/boost/sandbox/itl/libs/validate/example/)
 This gives everyone a method to check semantical
 properties of the library in a way that is more
 powerful than traditional unit tests.

To get the 'complete picture' of the library's interface you
may want to refer to the synoptic function table first
(http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/interface/function_synopsis.html)
before looking at more specific topics.

Hoping to have quickened your appetite to take a closer
look at this library before and during the review process.

best regards
Joachim Faulhaber