2 Copyright (c) 2008-2010 Joachim Faulhaber
4 Distributed under the Boost Software License, Version 1.0.
5 (See accompanying file LICENSE_1_0.txt or copy at
6 http://www.boost.org/LICENSE_1_0.txt)
13 The *icl* is about sets and maps and a useful
14 implementation of sets and maps using intervals.
15 In the documentation of the *icl* the different
16 set and map types are grouped in various ways.
17 In order to distinguish those groups we use
20 Names of concepts start with a capital letter.
21 So `Set` and `Map` stand for the /concept/ of
22 a set and a map as defined in the *icl*.
23 When we talk about `Sets` and `Maps` though,
24 most of the time we do not not talk about the
25 concepts themselves but the set of types
26 that implement those concepts in the *icl*.
27 The main groups, ['*icl containers*] can be
28 divided in, are summarized in the next table:
33 [[element container] [__std_set__] [__icl_map__]]
34 [[interval container][__itv_set__, __sep_itv_set__, __spl_itv_set__][__itv_map__, __spl_itv_map__]]
37 * Containers std:set, __itv_set__, __sep_itv_set__, __spl_itv_set__
38 are models of concept `Set`.
39 * Containers __icl_map__, __itv_map__, __spl_itv_map__
40 are models of concept `Map`.
41 * Containers that are ['*implemented*] using elements or element value pairs
42 are called ['*element containers*].
43 * Containers that are ['*implemented*] using intervals or interval value pairs
44 (also called segments) are called ['*interval containers*].
45 * When we talk about `Sets` or `Maps` we abstract from the way they are implemented.
46 * When we talk about /element containers/ or /interval containers/
47 we refer to the way they are implemented.
48 * __std_set__ is a model of the icl's `Set` concept.
49 * __std_map__ is ['*not*] a model of the icl's `Map` concept.
50 * The *icl's* element map
51 is always denoted qualified as __icl_map__
52 to avoid confusion with`std::map`.
58 There are two major ['*aspects*] or ['*views*] of icl containers. The first and predominant
59 aspect is called __bi_conceptual__. The second and minor aspect is called __bi_iterative__.
62 [[Aspect] [Abstraction level][] [] [Practical]]
63 [[__Conceptual__][more abstract][concept related] [iterator independent][interval_sets(maps) can be used as sets(maps)
64 except for element iteration.]]
65 [[__Iterative__] [less abstract][implementation related][iterator dependent] [interval_sets(maps) iterate over intervals]]
69 [[][__Conceptual__][__Iterative__]]
70 [[Abstraction level][more abstract][less abstract]]
71 [[][sequence of elements is irrelevant][sequence of elements is relevant]]
72 [[][iterator independent][iterator dependent]]
73 [[Informs about][membership of elements][sequence of intervals (segmentation)]]
74 [[Equality][equality of elements][equality of segments]]
75 [[Practical][interval_sets(maps) can be used as sets(maps)
76 of elements(element value pairs) ]
77 [Segmentation information is available.
78 See e.g. [link boost_icl.examples.time_grids Time grids for months and weeks]]]
81 On the __conceptual__ aspect
83 * an `interval` implements a set of elements partially.
84 * an __itv_set__ implements a set of elements.
85 * an __itv_map__ implements a map of element value pairs.
87 On the __iterative__ aspect
89 * an __itv_set__ implements a set of intervals.
90 * an __itv_map__ implements a map of interval value pairs.
95 [section Sets and Maps]
99 On the __conceptual__ aspect all __itv_bsets__ are models
101 The `Set` concept of the Interval Template Library refers to the
102 mathematical notion of a set.
105 [[Function] [Variant][implemented as] ]
106 [[empty set ] [] [`Set::Set()`] ]
107 [[subset relation] [] [`bool Set::within(const Set& s1, const Set& s2)const`] ]
108 [[equality ] [] [`bool is_element_equal(const Set& s1, const Set& s2)`]]
109 [[set union] [inplace][`Set& operator += (Set& s1, const Set& s2)`] ]
110 [[] [] [`Set operator + (const Set& s1, const Set& s2)`]]
111 [[set difference] [inplace][`Set& operator -= (Set& s1, const Set& s2)`] ]
112 [[] [] [`Set operator - (const Set& s1, const Set& s2)`]]
113 [[set intersection][inplace][`Set& operator &= (Set& s1, const Set& s2)`] ]
114 [[] [] [`Set operator & (const Set& s1, const Set& s2)`]]
117 Equality on `Sets` is not implemented as `operator ==`, because `operator ==`
118 is used for the stronger lexicographical equality on segments, that takes the
119 segmentation of elements into account.
121 Being models of concept `Set`, __icl_set__ and all __itv_bsets__
123 operations and obey the associated laws on `Sets`. See e.g.
124 [@http://en.wikipedia.org/wiki/Algebra_of_sets an algebra of sets here].
126 [h5 Making intervals complete]
128 An __itv__ is considered to be a set of elements as well.
129 With respect to the `Set` concept
130 presented above __itv__ implements the concept only partially. The reason for
131 that is that addition and subtraction can not
132 be defined on __itvs__. Two intervals `[1,2]` and `[4,5]` are not addable to
133 a ['*single*] new __itv__. In other words __itvs__ are incomplete w.r.t. union and
134 difference. __Itv_sets__ can be defined as the ['*completion*] of intervals
135 for the union and difference operations.
137 When we claim that addition or subtraction can not be defined
138 on intervals, we are not considering things like e.g.
139 interval arithmetics, where these operations can be defined,
140 but with a different semantics.
145 On the __conceptual__ aspect __icl_map__ and all __itv_bmaps__ are models of a
147 Since a `map` is a `set of pairs`, we try to design the `Map` concept in accordance
148 to the `Set` concept above.
151 [[Function] [Variant][implemented as] ]
152 [[empty map ] [] [`Map::Map()`] ]
153 [[subset relation] [] [`bool within(const Map& s2, const Map& s2)const`] ]
154 [[equality ] [] [`bool is_element_equal(const Map& s1, const Map& s2)`]]
155 [[map union] [inplace][`Map& operator += (Map& s1, const Map& s2)`] ]
156 [[] [] [`Map operator + (const Map& s1, const Map& s2)`]]
157 [[map difference] [inplace][`Map& operator -= (Map& s1, const Map& s2)`] ]
158 [[] [] [`Map operator - (const Map& s1, const Map& s2)`]]
159 [[map intersection][inplace][`Map& operator &= (Map& s1, const Map& s2)`] ]
160 [[] [] [`Map operator & (const Map& s1, const Map& s2)`]]
163 As one can see, on the abstract kernel the signatures of the icl's `Set` and `Map`
164 concepts are identical, except for the typename.
165 While signatures are identical
166 The sets of valid laws are different, which will be described in more detail
167 in the sections on the
168 [link boost_icl.semantics.sets semantics of icl Sets] and
169 [link boost_icl.semantics.maps Maps].
170 These semantic differences are mainly based on the implementation
171 of the pivotal member functions `add` and `subtract` for elements
172 and intervals that again serve for implementing
173 `operator +=` and `operator -=`.
174 [endsect][/ Abstract Sets and Maps]
176 [section:aggrovering Addability, Subtractability and Aggregate on Overlap]
178 While ['*addition*] and ['*subtraction*] on `Sets`
179 are implemented as ['*set union*] and ['*set difference*],
180 for `Maps` we want to implement ['*aggregation*] on
181 the associated values for the case of collision (of key elements)
182 or overlap (of key intervals), which has been refered to as
183 ['*aggregate on overlap*] above.
184 This kind of `Addability` and `Subtractability` allows to compute
185 a lot of useful aggregation results on an __itv_map_s__ associated
186 values, just by adding and subtracting value pairs.
187 Various examples of ['*aggregate on overlap*] are given in
188 [link boost_icl.examples section examples].
189 In addition, this concept of `Addability` and `Subtractability`
190 contains the classical `Insertability` and `Erasability` of
191 key value pairs as a special case so it provides a broader
192 new semantics without loss of the /classical/ one.
194 Aggregation is implemented for functions `add` and `subtract`
195 by propagating a `Combiner` functor to combine associated values
196 of type `CodomainT`. The standard `Combiner` is set as
197 default template parameter
198 `template<class>class Combine = inplace_plus`, which
199 is again generically implemented by `operator +=` for all
202 For `Combine` functors, the Icl provides an __inverse__ functor.
205 [[`Combine<T>`] [`inverse<Combine<T> >::type`]]
206 [[__ip_plus__`<T>`] [__ip_minus__`<T>`] ]
207 [[__ip_et__`<T>`] [__ip_caret__`<T>`] ]
208 [[__ip_star__`<T>`] [__ip_slash__`<T>`] ]
209 [[__ip_max__`<T>`] [__ip_min__`<T>`] ]
210 [[__ip_identity__`<T>`][__ip_erasure__`<T>`]]
211 [[`Functor`] [__ip_erasure__`<T>`]]
214 The meta function __inverse__ is mutually implemented for
215 all but the default functor `Functor`
217 `inverse<inplace_minus<T> >::type` yields `inplace_plus<T>`.
218 Not in every case, e.g. `max/min`, does the __inverse__ functor
219 invert the effect of it's antetype. But for the default
223 [[] [`_add<Combine<CodomainT> >((k,x))`] [`_subtract<inverse<Combine<CodomainT> >::type>((k,x))`]]
224 [[Instance] [`_add<inplace_plus<int> >((k,x))`] [`_subtract<inplace_minus<int> >((k,x))`]]
225 [[Inversion][adds `x` on overlap. This inverts a preceding `subtract` of `x` on `k`][subtracts `x` on overlap. This inverts a preceding `add` of `x` on `k`]]
229 As already mentioned aggregating `Addability` and `Subtractability`
230 on `Maps` contains the /classical/ `Insertability` and `Erasability` of
231 key value pairs as a special case:
234 [[aggregating function][equivalent /classical/ function]]
235 [[`_add<inplace_identity<CodomainT> >(const value_type&)`] [`insert(const value_type&)`]]
236 [[`_subtract<inplace_erasure<CodomainT> >(const value_type&)`][`erase(const value_type&)`]]
239 The aggregating member function templates `_add` and `_subtract`
240 are not in the public interface of __itv_bmaps__, because
241 the `Combine` functor is intended to be an invariant
243 template instance to avoid, that clients
244 spoil the aggregation by accidentally calling
245 varying aggregation functors.
246 But you could instantiate an __itv_map__ to have
247 `insert/erase` semantics this way:
249 interval_map<int,int,partial_absorber,
251 inplace_identity //Combine parameter specified
253 interval<int>::type itv = interval<int>::rightopen(2,7);
254 m.add(make_pair(itv,42)); //same as insert
255 m.subtract(make_pair(itv,42)); //same as erase
258 This is, of course, only a clarifying example. Member functions
259 `insert` and `erase` are available in __itv_bmap_s__ interface
260 so they can be called directly.
262 [endsect][/ Addability, Subtractability and Aggregation on Overlap]
267 Icl maps differ in their behavior dependent on how they handle
268 [@http://en.wikipedia.org/wiki/Identity_element ['*identity elements*]]
269 of the associated type `CodomainT`.
271 [h4 Remarks on Identity Elements]
273 In the pseudo code snippets below `0` will be used to denote
274 [@http://en.wikipedia.org/wiki/Identity_element `identity elements`],
276 different objects like `const double 0.0`, empty sets, empty strings,
277 null-vectors etc. dependent of the instance type for parameter `CodomainT`.
278 The existence of an ['*identity element*] wrt. an `operator+=` is a requirement
279 for template type `CodomainT`.
283 [[type] [operation] [identity element]]
284 [[`int`] [addition] [`0`] ]
285 [[`string`] [concatenation] [`""`] ]
286 [[`set<T>`] [union] [`{}`] ]
289 In these cases the `identity element` value is delivered by the default constructor
290 of the maps `CodomainT` type. But there are well known exceptions
291 like e.g. numeric multiplication:
294 [[type] [operation] [identity element]]
295 [[`int`] [multiplication] [`1`] ]
298 Therefore icl functors,
299 that serve as `Combiner` parameters of icl Maps
300 implement a static function `identity_element()` to make
301 sure that the correct `identity_element()` is used
302 in the implementation
303 of ['aggregate on overlap].
305 inplace_times<int>::identity_element() == 1
307 inplace_times<T>::identity_element() == unit_element<T>::value()
310 [h4 Definedness and Storage of Identity Elements]
312 There are two /properties/ or /traits/ of icl maps that can be
313 chosen by a template parameter `Traits`.
314 The ['*first trait*] relates to the ['*definedness*] of the map. Icl
315 maps can be *partial* or *total* on the set of values given by
316 domain type `DomainT`.
318 * A ['*partial*] map is only defined on those key elements that have been
319 inserted into the Map. This is usually expected and so ['*partial definedness*]
322 * Alternatively an icl Map can be ['*total*]. It is then considered to
323 contain a ['*neutral value*] for all key values that are not
326 The ['*second trait*] is related to the representation of `identity elements` in
327 the map. An icl map can be a ['*identity absorber*] or a ['*identity enricher*].
329 * A ['*identity absorber*] never stores value pairs `(k,0)` that carry identity elements.
330 * A ['*identity enricher*] stores value pairs `(k,0)`.
332 For the template parameter `Traits` of icl Maps we have the following
336 [[] [identity absorber] [identity enricher]]
337 [[partial][partial_absorber /(default)/][partial_enricher]]
338 [[total] [total_absorber] [total_enricher]]
341 [h4 Map Traits motivated]
343 Map traits are a late extension to the *icl*. Interval maps have
344 been used for a couple of years
345 in a variety of applications at Cortex Software GmbH
346 with an implementation that resembled the default trait.
347 Only the deeper analysis of the icl's ['*aggregating Map's
348 concept*] in the course of preparation of the library for boost
349 led to the introduction of map Traits.
351 [h5 Add-Subtract Antinomy in Aggregating Maps]
353 Constitutional for the absorber/enricher propery is a little
356 We can insert value pairs to the map by ['*adding*] them to the map
357 via operations `add, +=` or `+`:
358 ``{} + {(k,1)} == {(k,1)} // addition``
360 Further addition on common keys triggers aggregation:
361 ``{(k,1)} + {(k,1)} == {(k,2)} // aggregation for common key k``
363 A subtraction of existing pairs
364 ``{(k,2)} - {(k,2)} == {(k,0)} // aggregation for common key k``
365 yields value pairs that are associated with 0-values or `identity elements`.
367 So once a value pair is created for a key `k` it can not be
368 removed from the map via subtraction (`subtract, -=` or `-`).
370 The very basic fact on sets, that we can remove what we have
375 This is the motivation for the ['*identity absorber*] Trait.
376 A identity absorber map handles value pairs that carry
377 identity elements as ['*non-existent*], which saves the law:
380 Yet this introduces a new problem: With such a /identity absorber/
381 we are /by definition/ unable to store a value `(k,0)` in
382 the map. This may be unfavorable because it is not inline with the
383 behavior of stl::maps and this is not necessarily expected by clients
386 [/ CL On the other hand, the notion of a identity absorbing map
387 is more than just an akademic rescue effort for a formal law.
388 It turns out that absorber maps have desirable properties
389 for aggregation computations (see section semantics)
390 that proved to be useful in practice and are in many cases
391 just what is needed.]
393 The solution to the problem is the introduction of the
394 identity enricher Trait, so the user can choose a map variant
395 according to her needs.
397 [h5 Partial and Total Maps]
399 The idea of a identity absorbing map is,
400 that an ['*associated identity element*] value of a pair `(k,0)`
401 ['*codes non-existence*] for it's key `k`.
402 So the pair `(k,0)` immediately tunnels from
403 a map where it may emerge into the realm
407 If identity elements do not code ['*non-existence*] but
408 ['*existence with null quantification*],
409 we can also think of a map
410 that has an associated identity element
411 ['*for every*] key `k` that has no associated value
413 So in contrast to modelling *all* neutral
414 value pairs `(k,0)` as being ['*non-existent*]
415 we can model *all* neutral value pairs `(k,0)` as being
416 ['*implicitly existent*].
419 A map that is modelled in this way, is one large vector with
420 a value `v` for every key `k` of it's domain type `DomainT`.
421 But only non-identity values are actually stored.
422 This is the motivation for the definedness-Trait on `icl Maps`.
424 A ['*partial*] map models the intuitive view that only value
425 pairs are existent, that are stored in the map.
426 A ['*total*] map exploits the possibility that all
427 value pairs that are not stored can be considered
428 as being existent and ['*quantified*] with the identity element.
431 partial existential view
432 total quantifying view
436 [h4 Pragmatical Aspects of Map Traits]
438 From a pragmatic perspective value pairs that carry `identity elements` as
439 mapped values can often be ignored.
440 If we count, for instance,
441 the number of overlaps of inserted intervals in an __itv_map__
442 (see example [link boost_icl.examples.overlap_counter overlap counter]),
443 most of the time, we are not
444 interested in whether an overlap has been counted `0` times or
445 has not been counted at all. A identity enricher map
446 is only needed, if we want to distinct between non-existence
447 and 0-quantification.
449 The following distinction can *not* be made for a __pabsorber__ map
450 but it can be made for an __penricher__ map:
452 (k,v) does not exist in the map: Pair (k,v) has NOT been dealt with
453 (k,0) key k carries 0 : Pair (k,v) has been dealt with resulting in v=0
456 Sometimes this subtle distinction is needed. Then a __penricher__
457 is the right choice. Also, If we want to give two `icl::Maps`
458 a common set of keys in order to, say, iterate synchronously
459 over both maps, we need /enrichers/.
462 [endsect] [/ Map Traits]
464 [endsect][/ Concepts]