1 [/ 2 Copyright (c) 2008-2010 Joachim Faulhaber 3 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) 7 ] 8 9 [section Concepts] 10 11 [section Naming] 12 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 18 a naming convention. 19 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: 29 30 [table 31 [] 32 [[] [`Set`] [`Map`] ] 33 [[element container] [__std_set__] [__icl_map__]] 34 [[interval container][__itv_set__, __sep_itv_set__, __spl_itv_set__][__itv_map__, __spl_itv_map__]] 35 ] 36 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`. 53 54 [endsect][/ Naming] 55 56 [section Aspects] 57 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__. 60 61 [/ table 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]] 66 ] 67 68 [table 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]]] 79 ] 80 81 On the __conceptual__ aspect 82 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. 86 87 On the __iterative__ aspect 88 89 * an __itv_set__ implements a set of intervals. 90 * an __itv_map__ implements a map of interval value pairs. 91 92 [endsect][/ Aspects] 93 94 95 [section Sets and Maps] 96 97 [h5 A Set Concept] 98 99 On the __conceptual__ aspect all __itv_bsets__ are models 100 of a concept `Set`. 101 The `Set` concept of the Interval Template Library refers to the 102 mathematical notion of a set. 103 104 [table 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)`]] 115 ] 116 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. 120 121 Being models of concept `Set`, __icl_set__ and all __itv_bsets__ 122 implement these 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]. 125 126 [h5 Making intervals complete] 127 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. 136 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. 141 142 143 [h5 A Map Concept] 144 145 On the __conceptual__ aspect __icl_map__ and all __itv_bmaps__ are models of a 146 concept `Map`. 147 Since a `map` is a `set of pairs`, we try to design the `Map` concept in accordance 148 to the `Set` concept above. 149 150 [table 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)`]] 161 ] 162 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] 175 176 [section:aggrovering Addability, Subtractability and Aggregate on Overlap] 177 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. 193 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 200 Addable types. 201 202 For `Combine` functors, the Icl provides an __inverse__ functor. 203 204 [table 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>`]] 212 ] 213 214 The meta function __inverse__ is mutually implemented for 215 all but the default functor `Functor` 216 such that e.g. 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 220 it does: 221 222 [table 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`]] 226 ] 227 228 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: 232 233 [table 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&)`]] 237 ] 238 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 242 of __itv_bmap_s__ 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: 248 `` 249 interval_map<int,int,partial_absorber, 250 std::less, 251 inplace_identity //Combine parameter specified 252 > m; 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 256 `` 257 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. 261 262 [endsect][/ Addability, Subtractability and Aggregation on Overlap] 263 264 265 [section Map Traits] 266 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`. 270 271 [h4 Remarks on Identity Elements] 272 273 In the pseudo code snippets below `0` will be used to denote 274 [@http://en.wikipedia.org/wiki/Identity_element `identity elements`], 275 which can be 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`. 280 281 282 [table 283 [[type] [operation] [identity element]] 284 [[`int`] [addition] [`0`] ] 285 [[`string`] [concatenation] [`""`] ] 286 [[`set<T>`] [union] [`{}`] ] 287 ] 288 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: 292 293 [table 294 [[type] [operation] [identity element]] 295 [[`int`] [multiplication] [`1`] ] 296 ] 297 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]. 304 `` 305 inplace_times<int>::identity_element() == 1 306 // or more general 307 inplace_times<T>::identity_element() == unit_element<T>::value() 308 `` 309 310 [h4 Definedness and Storage of Identity Elements] 311 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`. 317 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*] 320 is the default. 321 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 324 stored in the map. 325 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*]. 328 329 * A ['*identity absorber*] never stores value pairs `(k,0)` that carry identity elements. 330 * A ['*identity enricher*] stores value pairs `(k,0)`. 331 332 For the template parameter `Traits` of icl Maps we have the following 333 four values. 334 335 [table 336 [[] [identity absorber] [identity enricher]] 337 [[partial][partial_absorber /(default)/][partial_enricher]] 338 [[total] [total_absorber] [total_enricher]] 339 ] 340 341 [h4 Map Traits motivated] 342 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. 350 351 [h5 Add-Subtract Antinomy in Aggregating Maps] 352 353 Constitutional for the absorber/enricher propery is a little 354 antinomy. 355 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`` 359 360 Further addition on common keys triggers aggregation: 361 ``{(k,1)} + {(k,1)} == {(k,2)} // aggregation for common key k`` 362 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`. 366 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 `-`). 369 370 The very basic fact on sets, that we can remove what we have 371 previously added 372 ``x - x = {}`` 373 does not apply. 374 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: 378 ``x - x = {}`` 379 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 384 of the library. 385 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.] 392 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. 396 397 [h5 Partial and Total Maps] 398 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 404 of non existence. 405 ``{(k,0)} == {}`` 406 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 412 different from 0. 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*]. 417 418 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`. 423 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. 429 430 [/ 431 partial existential view 432 total quantifying view 433 ] 434 435 436 [h4 Pragmatical Aspects of Map Traits] 437 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. 448 449 The following distinction can *not* be made for a __pabsorber__ map 450 but it can be made for an __penricher__ map: 451 [pre 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 454 ] 455 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/. 460 461 462 [endsect] [/ Map Traits] 463 464 [endsect][/ Concepts] 465 466