xref: /third_party/boost/libs/icl/doc/introduction.qbk

[/
    Copyright (c) 2008-2010 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)
]

[section Introduction]

[/ note [* The Interval Container Library is accepted into Boost]

The [*Interval Container Library] (formerly /Interval Template Library/) underwent
a formal review on the boost developer's list
from February 18, 2010 to March 08, 2010 and has been accepted
by declaration of review manager Hartmut Kaiser
into the boost library collection on April 18, 2010.


The library has been refactored for the suggestions and requests
that came up during the review. The current version is now
ready for inclusion into the next boost release.
The name ['*Interval Template Library (ITL)*]
has been changed to ['*Interval Container Library (ICL)*].

If you find bugs in the library or typos or other shortcomings in
the documentation please send reports to the boost developers list
boost@lists.boost.org
the boost users list or
boost-users@lists.boost.org
to `[afojgo<AT>gmail dot com]`.

]

["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 [@http://en.wikipedia.org/wiki/Jack_Kornfield 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
[@http://www.cortex-software.de/desktopdefault.aspx 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
[@http://www.herold-faulhaber.de/boost_icl/doc/libs/icl/doc/boostcon09/intro_to_itl.pdf
presentation material on the *ICL* from ['*BoostCon2009*]].


[section Definition and Basic Example]

The [*Interval Container Library (ICL)] provides __itvs__ and two kinds of
interval containers: __itv_sets__ and __itv_maps__.

* An __itv_bset__ is a *set* that is implemented as a set of intervals.
* An __itv_bmap__ is a *map* that is implemented as a map of interval value pairs.

[h4 Two Aspects]

__Itv_bsets__ and __itv_bmaps__ 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 __bi_conceptual__ ['*aspect*], is the more important one.
It means that we can use an __itv_set__ or __itv_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 __bi_iterative__ ['*aspect*], allows to exploit the
fact, that the elements of __itv_sets__ and __itv_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 __itv_bsets__ and __itv_bmaps__ can be
beneficial whenever the elements of
sets appear in contiguous chunks: __itvs__. This is obviously the
case in many problem domains, particularly in fields that deal with
computations related to date and time.

[h4 Addabitlity and Subtractability]

Unlike `std::sets` and `maps`, __itv_bsets__ and __itv_bmaps__ implement
concept `Addable` and `Subtractable`. So __itv_bsets__ define an
`operator +=` that is naturally implemented as ['*set union*] and an
`operator -=` that is consequently implemented as ['*set difference*].
In the *Icl* __itv_bmaps__ are addable and subtractable as well.
It turned out to be a very fruitful concept to propagate the
addition or subtraction to the __itv_bmap_s__ associated values
in cases where the insertion of an interval value pair into an
__itv_map__ resulted in a collision of the inserted interval
value pair with interval value pairs, that are already in the
__itv_map__. This operation propagation is called ['*aggregate on overlap*].


[h4 Aggregate on Overlap]

This is a first motivating example of a very small party, demonstrating the
['*aggregate on overlap*] principle on __itv_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 __itv_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 __itv_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
__itv_maps__ implemented via function `add` and `operator +=`.
But you can also use them with the ['traditional]
[link boost_icl.function_reference.insertion insert semantics]
that behaves like `std::map::insert` generalized for
interval insertion.

[endsect]

[section Icl's class templates]

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 __itv_map__.
Therefore there is an extra __icl_map__ class template for maps of
elements in the icl.


* The __std_set__ is behavioral equal to __itv_bsets__ on the __bi_conceptual__ aspect.

* An __icl_map__ is behavioral equal to __itv_bmaps__ on the __bi_conceptual__  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 Interval class templates
[[group]              [form]      [template]          ]
[[statically bounded] [asymmetric][__ro_itv__]        ]
[[ ]                  []          [__lo_itv__]        ]
[[ ]                  [symmetric] [__cl_itv__]        ]
[[ ]                  []          [__op_itv__]        ]
[[dynamically bounded][]          [__dc_itv__]        ]
[[ ]                  []          [__ct_itv__]        ]
]

Statically bounded intervals always have the same kind of interval borders,
e.g. right open borders`[a..b)` for __ro_itv__. Dynamically bounded intervals
can have different borders. Refer to the chapter about
[link boost_icl.interface.class_templates.intervals ['*intervals*]]
for details.

[table Container class templates
[[granularity][style]     [sets]           [maps]           ]
[[interval]   [joining]   [__itv_set__]    [__itv_map__]    ]
[[]           [separating][__sep_itv_set__][]               ]
[[]           [splitting] [__spl_itv_set__][__spl_itv_map__]]
[[element]    []          [(__ele_set__)]  [__ele_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.


[endsect]

[section Interval Combining Styles]

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 Interval container's ways to combine intervals
    [[]         [joining]       [separating]            [splitting]]
    [[set]      [[classref boost::icl::interval_set          interval_set]]
                [[classref boost::icl::separate_interval_set separate_interval_set]]
                [[classref boost::icl::split_interval_set    split_interval_set]]]
    [[map]      [[classref boost::icl::interval_map          interval_map]]
                []
                [[classref boost::icl::split_interval_map    split_interval_map]]]
    [[]         [Intervals are joined on overlap or touch\n(if associated values are equal).]
                [Intervals are joined on overlap, not on touch.]
                [Intervals are split on overlap.\nAll interval borders are preserved.]]
]

[table Interval combining styles by example
    [[]         [joining]       [separating]            [splitting]]
    [[set]      [[classref boost::icl::interval_set          interval_set] /A/]
                [[classref boost::icl::separate_interval_set separate_interval_set] /B/]
                [[classref boost::icl::split_interval_set    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]      [[classref boost::icl::interval_map          interval_map] /D/]
                []
                [[classref boost::icl::split_interval_map    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 [link boost_icl.examples.interval_container Interval container]
for an additional demo.

[h4 Joining interval containers]

__Itv_set__ and __itv_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 __itv_set__ and
__itv_map__ will be the first choice
for an interval container.

[h4 Splitting interval containers]

__Spl_itv_set__ and __spl_itv_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 [link boost_icl.examples.time_grids time grids for months and weeks].

[h4 Separating interval containers]

__Sep_itv_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 __sep_itv_set__
are generated form a certain grid that never pass say month borders, then
these borders are preserved in the __sep_itv_set__.

[endsect]

[endsect][/ Introduction]