Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
Next

Chapter 1. Boost.Icl

Joachim Faulhaber

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

Introduction
Definition and Basic Example
Icl's class templates
Interval Combining Styles
Examples
Overview
Party
Interval
Dynamic interval
Static interval
Interval container
Overlap counter
Party's height average
Party's tallest guests
Time grids for months and weeks
Man power
User groups
Std copy
Std transform
Custom interval
Projects
Large Bitset
Concepts
Naming
Aspects
Sets and Maps
Addability, Subtractability and Aggregate on Overlap
Map Traits
Semantics
Orderings and Equivalences
Sets
Maps
Collectors: Maps of Sets
Quantifiers: Maps of Numbers
Concept Induction
Interface
Class templates
Required Concepts
Associated Types
Function Synopsis
Customization
Intervals
Implementation
Iterative size
Complexity
Inplace and infix operators
Function Reference
Overload tables
Segmentational Fineness
Key Types
Construct, copy, destruct
Containedness
Equivalences and Orderings
Size
Range
Selection
Addition
Subtraction
Insertion
Erasure
Intersection
Symmetric Difference
Iterator related
Element iteration
Streaming, conversion
Interval Construction
Additional Interval Orderings
Miscellaneous Interval Functions
Acknowledgments
Interval Container Library Reference
Header <boost/icl/closed_interval.hpp>
Header <boost/icl/continuous_interval.hpp>
Header <boost/icl/discrete_interval.hpp>
Header <boost/icl/dynamic_interval_traits.hpp>
Header <boost/icl/functors.hpp>
Header <boost/icl/gregorian.hpp>
Header <boost/icl/impl_config.hpp>
Header <boost/icl/interval.hpp>
Header <boost/icl/interval_base_map.hpp>
Header <boost/icl/interval_base_set.hpp>
Header <boost/icl/interval_bounds.hpp>
Header <boost/icl/interval_combining_style.hpp>
Header <boost/icl/interval_map.hpp>
Header <boost/icl/interval_set.hpp>
Header <boost/icl/interval_traits.hpp>
Header <boost/icl/iterator.hpp>
Header <boost/icl/left_open_interval.hpp>
Header <boost/icl/map.hpp>
Header <boost/icl/open_interval.hpp>
Header <boost/icl/ptime.hpp>
Header <boost/icl/rational.hpp>
Header <boost/icl/right_open_interval.hpp>
Header <boost/icl/separate_interval_set.hpp>
Header <boost/icl/split_interval_map.hpp>
Header <boost/icl/split_interval_set.hpp>

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 ICL 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 ICL 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 ICL 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 ICL from BoostCon2009.

The Interval Container Library (ICL) provides intervals and two kinds of interval containers: interval_sets and interval_maps.

  • An interval_set is a set that is implemented as a set of intervals.
  • An interval_map is a map that is implemented as a map of interval value pairs.
Two Aspects

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 = contains(mySet, 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>::type news(make_seconds("20:00:00"), make_seconds("20:15:00"));
interval<seconds>::type 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.

Addabitlity and Subtractability

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 Icl 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.

Aggregate on Overlap

This is a first motivating example of a very small party, demonstrating the aggregate on overlap principle 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 std::set<string> guests;
interval_map<time, guests> party; 
party += make_pair(interval<time>::right_open(time("20:00"), time("22:00")), guests("Mary"));
party += make_pair(interval<time>::right_open(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 we can work with containers of elements that are behavioral equal to the interval containers: On the fundamental aspect they have exactly the same functionality. An std::set of the STL is such an equivalent set implementation. Due to the aggregation facilities of the icl's interval maps std::map is fundamentally not completely equivalent to an interval_map. Therefore there is an extra icl::map class template for maps of elements in the icl.

  • The std::set is behavioral equal to interval_sets on the fundamental aspect.
  • An icl::map is behavioral equal to interval_maps on the fundamental aspect. Specifically an icl::map implements aggregate on overlap, which is named aggregate on collision for an element container.

The following tables give an overview over the main class templates provided by the icl.

Table 1.1. Interval class templates

group

form

template

statically bounded

asymmetric

right_open_interval

left_open_interval

symmetric

closed_interval

open_interval

dynamically bounded

discrete_interval

continuous_interval


Statically bounded intervals always have the same kind of interval borders, e.g. right open borders[a..b) for right_open_interval. Dynamically bounded intervals can have different borders. Refer to the chapter about intervals for details.

Table 1.2. Container class templates

granularity

style

sets

maps

interval

joining

interval_set

interval_map

separating

separate_interval_set

splitting

split_interval_set

split_interval_map

element

(std::set )

map


Std::set is placed in paretheses, because it is not a class template of the ICL. It can be used as element container though that is behavioral equal to the ICL's interval sets on their fundamental aspect. 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.3. Interval container's ways to combine intervals

joining

separating

splitting

set

interval_set

separate_interval_set

split_interval_set

map

interval_map

split_interval_map

Intervals are joined on overlap or touch
(if associated values are equal).

Intervals are joined on overlap, not on touch.

Intervals are split on overlap.
All interval borders are preserved.


Table 1.4. Interval combining styles by example

joining

separating

splitting

set

interval_set A

separate_interval_set B

split_interval_set C

  {[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

interval_map D

split_interval_map E

  {[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.

Joining interval containers

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.

Splitting interval containers

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.

Separating interval containers

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 15.10.2010

Last revised: March 03, 2011 at 13:59:35 GMT


Next