[boost] proposal: interval containers

From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2008-05-12 11:35:46

Dear boost developers,

I would like to contribute some library code that covers the field of
interval containers, specifically interval_set and interval_map.

My design of interval sets is based on the fact that an
interval<T> is a set<T>, which implies that a set<T> t can be
represented as a set<interval<T>> s, where t is the union over
all intervals contained in s.

The implementation of a set<T> as a set<interval<T>> can be
beneficial whenever in a given problem domain the elements of
sets appear in contiguous chunks: intervals. This is obviously the
case in many problem domains, namely in fields that deal with problems
related to date and time.

The benefits of interval sets and maps are
1. The implementation of sets/maps via interval_set/map is very
space and also time efficient.
2. All problems concerning overlaps of intervals and their
handling can be encapsulated in the implementation and thus ...
3. A higher abstraction level dealing with interval and specifically
time interval related problems can be obtained.

I wrote a library that provides generic classes for interval_sets
and interval_maps and a few more things called "Interval
Template Library (itl)". I'd like to give a very brief
description of the library in this post. For more detailed
information and the current source code you might want to download
the itl from http://sourceforge.net/projects/itl.

The code contained in the library was originally developed
at Cortex Software GmbH Berlin (Clinic Information Systems), where
interval containers already proved to be very useful for
quite some years in almost all of our applications. In 2006
Cortex Software GmbH allowed the code to be released
as open source and I provided a preliminary version at sourceforge.

Meanwhile I have refactored the code to enhance it's fitness
for generic designs, portable usage and a possible integration
in the boost libraries. Since I have not (yet;) found
the functionality of the 'itl' in the boost libraries nor
a discussion about the rejection of such topics in the
boost archives I would like to offer parts of the library here.

interval_set:
itl::interval_set implements all functionality of std::set as a set
of intervals and in addition +=, -= and *= for set union, difference
and intersection. On insertion of neighbouring or overlapping
intervals inserted intervals are joined.

split_interval_set:
split_interval_set works like interval_set but borders of the
inserted intervals are preserved, so it can be used as time grid.
Using itl::split_interval_set you can partition other interval
containers using the *= operator to perform intersections.

split_interval_map:
A split_interval_map implements a map as a map of intervals
and associated values. For dealing with the insertion
of overlapping intervals the principle of "aggregation on
overlap" has proved to be very useful: It is shown by example:

typedef set<string> guests;
split_interval_map<time, guests> party;
guests mary; mary.insert("Mary");
guests harry; harry.insert("Harry");
party.insert(make_pair(rightopen_interval(20:00, 22:00), mary));
party.insert(make_pair(rightopen_interval(21:00, 23:00), harry));
// party now contains
[20:00, 21:00)->{"Mary"}
[21:00, 22:00)->{"Harry","Mary"} //guest sets aggregated on overlap
[22:00, 23:00)->{"Harry"}

As can be seen from the example a split_interval_map has both
a decompositional behavior (on the time dimension) as well as
a accumulative one (on the associated values).

Quality, validation, portability:

The library code of the itl has been validated with a law based
test automaton (LaBatea;) which is included in
the current release. It includes a testcase generator and law tester
that checks laws like e.g. commutativity<interval_set<double>, +=>:
the commutativity of interval_set<double> w.r.t. the operation +=.

The code has been compiled and tested with three compilers
(gcc 3.4.4, conceptgcc-boostcon, msvc 8.0 sp1) and with three
implementations of the stl (linux/gnu, stlport, msvc8) under
suse linux 10.1. and ms-windows xp.

I'd be happy if you found interval conainers as presented in this
post an interesting contribution to look at.

If so, I am looking forward to an inspiring discussion.

Best regards

Joachim Faulhaber