[boost] proposal: interval containers; boost examples and more

From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2008-07-29 02:51:46

Dear boost developers,

after encouraging feedback by Paul A Bristow, Vicente Botet and
Luke Simonson to my proposal on interval containers from end of May
(http://lists.boost.org/Archives/boost/2008/05/137301.php), I started to
boostify my interval template library (ITL). Even though there is a lot left
to be done for the ITL to become fully boost compliant I'd like to report on
some aspects of my current work.

(1) As suggested by Paul A Bristow I have prepared some new examples that
 are using boost::date_time as instance types for the interval containers.

* Example boost_party.cpp is a boostified instance of the introductory example
  party.cpp that demonstrates the 'aggregate on overlap' mechanism of
interval maps
  (see: http://www.herold-faulhaber.de/itl/boost__party_8cpp.html).

* Example month_and_weeks_grid.cpp demonstrates how different time grids
  can be merged in split_interval_sets by intersection
  (see: http://www.herold-faulhaber.de/itl/month__and__week__grid_8cpp.html).

* Example man_power.cpp shows how calculations on interval_sets and maps can
  be obtained using set type operations. In the example the available
man power in
  a small company is calculated accounting for weekends, holidays vacations etc.
  (see: http://www.herold-faulhaber.de/itl/man__power_8cpp.html).

* Example user_groups shows how interval maps can be unified or intersected
  (see: http://www.herold-faulhaber.de/itl/user__groups_8cpp.html).

(2) In the course of boostification of my code I have reviewed the design
 and completed the interval container classes as follows:

* interval_set
* split_interval_set
* separate_interval_set (added)

* interval_map (added)
* split_interval_map

You can see an overview these interval containers and some basic
characteristics in the ITL's documentation here:
http://www.herold-faulhaber.de/itl/interval__container__conduct_8h.html

The major addition here is the class template interval_map. In contrast to a
split_interval_map that preserves all interval borders that may emerge due to
insertion and intersection operations, an interval_map keeps itself always
minimal: Whenever two neighbouring interval-value pairs
([a,b), v), ([b,c),v) emerge, they will be joined to ([a,c),v).

(3) Reviewing the overall design of the interval containers I have
separated the
meaning of insert/add and erase/subtract, which had been confounded in
the previous version of the ITL. This has consequences especially for
interval maps:

As a design decision I'd like to choose that interval maps are addable and
subtractable objects having operators += and -= that implement these
properties.
Addition and subtraction is then defined via element addition
(add(value_type&))
and element subtraction (subtract(value_type&)).

At a general level I can define add<inplace_op>(value_type&) and
subtract<inplace_op>(value_type&)as member function templates,
that implement aggregation on overlap (aggovering) not only for
inplace_plus (+=) but also for arbitrary aggregate operations (inplace_op).

It turned out, that function insert (std::insert semantics) can be expressed
by the general add template (as well as erase can expressed by the subtract
member function template):

add<inplace_identity>(value_type&) is equivalent to insert(value_type&)
subtract<inplace_erasure>(value_type&) is equivalent to erase(value_type&)

In addition we can also define 'plain' element add and subtract by means of
these templates:
add(value_type&) can be defined as: add<inplace_plus>(value_type&)
subtract(value_type&) can be defined as: subtract<inplace_minus>(value_type&)

So for the ITL container classes I do provide now insert and erase
that covers the
std::semantics and I provide add and subtract that is the basis for
addability and
subtractability of itl::maps and itl::interval_maps.

You can find an overview over all insert/erase and add/subtact
functions and their
relationships to std::semantics in the ITL's documentation here:
http://www.herold-faulhaber.de/itl/interval__container__design_8h.html

I find these design and semantical questions quite rich, and sometimes
surprising ;-) and I have found many more aspects and properties while
reviewing the ITL's design. I am planning to prepare a more detailed article
about these topics in the next months to come.

(4) I have prepared a new release 2.0.1 of the ITL for the current
state that can be
downloaded from: http://www.sourceforge.net/projects/itl
Documentation is availabe online also from here:
http://www.herold-faulhaber.de/itl
The code is well tested using the Law Based Test Automaton (LaBatea) and is
protabel for gcc 3.4.4 and msvc 8.0 sp1.
I am sorry the ITL is still not in the boost standard directory
structure. This will be
one of the next steps on my todo list.

(5) Concerning boostification of ITL there is still a lot to be done.
Besides reviewing
of the overall design reported above, I have removed virtual functions from all
interval container classes using the curiously recurring template
pattern (CRTP).

To prevent you repeating advices that already found their way into my todo list
I am listing it roughly as appendix to this posting.

Cheers
Joachim Faulhaber

---
Boostification todo list:
- Extracting a subset of the ITL as boost proposal
- Providing the code in boost directory structure
- Replacing own metaprogramming code by boost::mpl,fusion etc.
- Using boost::value_initialized for generic initialisations
- Further minimizing of class template interfaces and...
- Providing more operators and functions as itl::global algorithms
- Providing as much std::semantics as possible for interval containers
  (viewed as set<interval<T>> or map<interval<T>,U>)
- Adapting testcode to boost testing standards
- Improving documentation especially for issues of design and complexity
- Providing boost style documentation
- Preparing a proposal on the addition of open interval bounds to
boost::interval