Home  Libraries  People  FAQ  More 
Copyright © 2007 2009 Joachim Faulhaber
Copyright © 1999 2006 Cortex Software GmbH
Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Table of Contents
Note  

This is not an official boost library The Interval Template Library is currently submitted for a formal review on the boost developer's list. The review will start on February 18, 2010 and will end on February 27, 2010. Depending on the review's result the library might or might not become a boost library. The name Interval Template Library (ITL) is provisional an will probably be changed, if the library is accepted into boost. A renaming will not be done before completion of the formal review. 
“A bug crawls across the boost docs on my laptop screen. Let him be! We need all the readers we can get.”  Freely adapted from Jack Kornfield
Intervals are almost ubiquitous in software development. Yet they are very easily coded into user defined classes by a pair of numbers so they are only implicitly used most of the time. The meaning of an interval is simple. They represent all the elements between their lower and upper bound and thus a set. But unlike sets, intervals usually can not be added to a single new interval. If you want to add intervals to a collection of intervals that does still represent a set, you arrive at the idea of interval_sets provided by this library.
Interval containers of the ITL have been developed initially at Cortex Software GmbH to solve problems related to date and time interval computations in the context of a Hospital Information System. Time intervals with associated values like amount of invoice or set of therapies had to be manipulated in statistics, billing programs and therapy scheduling programs. So the ITL emerged out of those industrial use cases. It extracts generic code that helps to solve common problems from the date and time problem domain and can be beneficial in other fields as well.
One of the most advantageous aspects of interval containers is their very compact representation of sets and maps. Working with sets and maps of elements can be very inefficient, if in a given problem domain, elements are typically occurring in contiguous chunks. Besides a compact representation of associative containers, that can reduce the cost of space and time drastically, the ITL comes with a universal mechanism of aggregation, that allows to combine associated values in meaningful ways when intervals overlap on insertion.
For a condensed introduction and overview you may want to look at the presentation material on the ITL from BoostCon2009.
The Interval Template Library (ITL) provides
intervals
and two kinds
of interval containers: interval_sets
and interval_maps
.
interval_set
is a set that is implemented as a set
of intervals.
interval_map
is a map that is implemented as a map
of interval value pairs.
Interval_sets
and interval_maps
expose two different aspects in their interfaces: (1) The functionality of
a set or a map, which is the more abstract
aspect. And (2) the functionality of a container of
intervals which is the more specific and implementation
related aspect. In practice both aspects are useful
and are therefore supported.
The first aspect, that will be called fundamental
aspect, is the more
important one. It means that we can use an interval_set
or interval_map
like
a set or map of elements.
It exposes the same functions.
interval_set<int> mySet; mySet.insert(42); bool has_answer = mySet.contains(42);
The second aspect, that will be called segmental
aspect, allows to exploit
the fact, that the elements of interval_sets
and interval_maps
are
clustered in intervals
or segments that we
can iterate over.
// Switch on my favorite telecasts using an interval_set interval<seconds> news(make_seconds("20:00:00"), make_seconds("20:15:00")); interval<seconds> talk_show(make_seconds("22:45:30"), make_seconds("23:30:50")); interval_set<seconds> myTvProgram; myTVProgram.add(news).add(talk_show); // Iterating over elements (seconds) would be silly ... for(interval_set<seconds>::iterator telecast = myTvProgram.begin(); telecast != myTvProgram.end(); ++telecast) //...so this iterates over intervals TV.switch_on(*telecast);
Working with interval_sets
and interval_maps
can be beneficial whenever the elements of sets appear in contiguous chunks:
intervals
. This is obviously
the case in many problem domains, particularly in fields that deal with computations
related to date and time.
Unlike std::sets
and maps
,
interval_sets
and interval_maps
implement concept Addable
and Subtractable
. So interval_sets
define an
operator +=
that is naturally implemented as set union
and an operator =
that is consequently implemented as set difference.
In the Itl interval_maps
are addable and subtractable as well. It turned out to be a very fruitful
concept to propagate the addition or subtraction to the interval_map's
associated values in cases where the insertion of an interval value pair
into an interval_map
resulted in a collision of the inserted interval value pair with interval
value pairs, that are already in the interval_map
.
This operation propagation is called aggregate
on overlap.
This is a first motivating example of a very small party, demonstrating the
aggregate on overlap
principle (aggrovering)
on interval_maps
:
In the example Mary enters the party first. She attends during the time interval
[20:00,22:00)
. Harry enters later. He stays within [21:00,23:00)
.
typedef itl::set<string> guests; interval_map<time, guests> party; party += make_pair(interval<time>::rightopen(time("20:00"), time("22:00")), guests("Mary")); party += make_pair(interval<time>::rightopen(time("21:00"), time("23:00")), guests("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"}
On overlap of intervals,
the corresponding name sets are accumulated.
At the points of overlap
the intervals are split.
The accumulation of content on overlap of intervals is done via an operator +=
that has to be implemented for the associated values of the interval_map
.
In the example the associated values are guest
sets
. Thus a guest
set
has to implement operator +=
as set union.
As can be seen from the example an interval_map
has both a decompositional behavior
(on the time dimension) as well as an accumulative
one (on the associated values).
Addability and aggregate on overlap are useful features on interval_maps
implemented via function add
and operator +=
.
But you can also use them with the traditional insert semantics
that behaves like std::map::insert
generalized for interval insertion.
In addition to interval containers the itl
provides element containers itl::set
and itl::map
.
itl::set
is behavioral
equal to interval_sets
on the fundamental
aspect.
itl::map
is behavioral
equal to interval_maps
on the fundamental
aspect. Specifically an itl::map
implements aggregate on overlap,
which is named aggregate on collision
for an element container.
The following table gives an overview over the main class templates provided by the itl.
Table 1.1. Synopsis over the itl's class templates
granularity 
style 
sets 
maps 

interval 




joining 


separating 



splitting 

element 

Interval
is placed deliberately
in column sets because an interval is a
set as well. Column style
refers to the different ways in which interval containers combine added intervals.
These combining styles
are described in the next section.
When we add intervals or interval value pairs to interval containers, the intervals can be added in different ways: Intervals can be joined or split or kept separate. The different interval combining styles are shown by example in the tables below.
Table 1.2. Interval container's ways to combine intervals

joining 
separating 
splitting 

set 

map 



Intervals are joined on overlap or touch 
Intervals are joined on overlap, not on touch. 
Intervals are split on overlap. 
Table 1.3. Interval combining styles by example

joining 
separating 
splitting 

set 


{[1 3) } + [2 4) + [4 5) = {[1 5)}

{[1 3)} } + [2 4) + [4 5) = {[1 4)[4 5)}

{[1 3) } + [2 4) + [4 5) = {[1 2)[2 3)[3 4)[4 5)}

map 



{[1 3)>1 } + [2 4)>1 + [4 5)>1 = {[1 2)[2 3)[3 5) }  >1 >2 >1 


{[1 3)>1 } + [2 4)>1 + [4 5)>1 = {[1 2)[2 3)[3 4)[4 5) }  >1 >2 >1 >1 

Note that interval_sets
A, B
and C represent the same set of elements {1,2,3,4}
and interval_maps
D and E
represent the same map of elements {1>1, 2>2, 3>1, 4>1}
.
See example program Interval
container for an additional demo.
Interval_set
and interval_map
are always in a
minimal representation.
This is useful in many cases, where the points of insertion or intersection
of intervals are not relevant. So in most instances interval_set
and interval_map
will
be the first choice for an interval container.
Split_interval_set
and split_interval_map
on the contrary have an insertion memory.
They do accumulate interval borders both from additions and intersections.
This is specifically useful, if we want to enrich an interval container with
certain time grids, like e.g. months or calendar weeks or both. See example
time grids for months
and weeks.
Separate_interval_set
implements the separating style. This style preserves borders, that are never
passed by an overlapping interval. So if all intervals that are inserted
into a separate_interval_set
are generated form a certain grid that never pass say month borders, then
these borders are preserved in the separate_interval_set
.
14:46 18.11.2008
Last revised: February 09, 2010 at 17:48:26 GMT 