Subject: [boost] Review Request: Boost.Itl; The Interval Template Library
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2009-09-18 06:10:30
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.
Another file itl_plus_3_1_0.zip contains all three parts
(itl, itl_xt and validate).
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
Sources are also available form the sandbox:
To close my request for review, let me take the opportunity
to do some advertisement ;-) focusing on some of the itl's
* The Itl emerged out of real world software development
extracting generic functionality from numerous use
cases of the date time problem domain.
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
* 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.
* The itl's design is based on sets of laws (aka axioms)
that are described in the documentation.
These law sets not only are giving a formal specification
of the library. Using the law based testing tool (LaBatea)
allows to validate the library code for every specified
* 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).
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
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk