[/ 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 Concepts] [section Naming] The *icl* is about sets and maps and a useful implementation of sets and maps using intervals. In the documentation of the *icl* the different set and map types are grouped in various ways. In order to distinguish those groups we use a naming convention. Names of concepts start with a capital letter. So `Set` and `Map` stand for the /concept/ of a set and a map as defined in the *icl*. When we talk about `Sets` and `Maps` though, most of the time we do not not talk about the concepts themselves but the set of types that implement those concepts in the *icl*. The main groups, ['*icl containers*] can be divided in, are summarized in the next table: [table [] [[] [`Set`] [`Map`] ] [[element container] [__std_set__] [__icl_map__]] [[interval container][__itv_set__, __sep_itv_set__, __spl_itv_set__][__itv_map__, __spl_itv_map__]] ] * Containers std:set, __itv_set__, __sep_itv_set__, __spl_itv_set__ are models of concept `Set`. * Containers __icl_map__, __itv_map__, __spl_itv_map__ are models of concept `Map`. * Containers that are ['*implemented*] using elements or element value pairs are called ['*element containers*]. * Containers that are ['*implemented*] using intervals or interval value pairs (also called segments) are called ['*interval containers*]. * When we talk about `Sets` or `Maps` we abstract from the way they are implemented. * When we talk about /element containers/ or /interval containers/ we refer to the way they are implemented. * __std_set__ is a model of the icl's `Set` concept. * __std_map__ is ['*not*] a model of the icl's `Map` concept. * The *icl's* element map is always denoted qualified as __icl_map__ to avoid confusion with`std::map`. [endsect][/ Naming] [section Aspects] There are two major ['*aspects*] or ['*views*] of icl containers. The first and predominant aspect is called __bi_conceptual__. The second and minor aspect is called __bi_iterative__. [/ table [[Aspect] [Abstraction level][] [] [Practical]] [[__Conceptual__][more abstract][concept related] [iterator independent][interval_sets(maps) can be used as sets(maps) except for element iteration.]] [[__Iterative__] [less abstract][implementation related][iterator dependent] [interval_sets(maps) iterate over intervals]] ] [table [[][__Conceptual__][__Iterative__]] [[Abstraction level][more abstract][less abstract]] [[][sequence of elements is irrelevant][sequence of elements is relevant]] [[][iterator independent][iterator dependent]] [[Informs about][membership of elements][sequence of intervals (segmentation)]] [[Equality][equality of elements][equality of segments]] [[Practical][interval_sets(maps) can be used as sets(maps) of elements(element value pairs) ] [Segmentation information is available. See e.g. [link boost_icl.examples.time_grids Time grids for months and weeks]]] ] On the __conceptual__ aspect * an `interval` implements a set of elements partially. * an __itv_set__ implements a set of elements. * an __itv_map__ implements a map of element value pairs. On the __iterative__ aspect * an __itv_set__ implements a set of intervals. * an __itv_map__ implements a map of interval value pairs. [endsect][/ Aspects] [section Sets and Maps] [h5 A Set Concept] On the __conceptual__ aspect all __itv_bsets__ are models of a concept `Set`. The `Set` concept of the Interval Template Library refers to the mathematical notion of a set. [table [[Function] [Variant][implemented as] ] [[empty set ] [] [`Set::Set()`] ] [[subset relation] [] [`bool Set::within(const Set& s1, const Set& s2)const`] ] [[equality ] [] [`bool is_element_equal(const Set& s1, const Set& s2)`]] [[set union] [inplace][`Set& operator += (Set& s1, const Set& s2)`] ] [[] [] [`Set operator + (const Set& s1, const Set& s2)`]] [[set difference] [inplace][`Set& operator -= (Set& s1, const Set& s2)`] ] [[] [] [`Set operator - (const Set& s1, const Set& s2)`]] [[set intersection][inplace][`Set& operator &= (Set& s1, const Set& s2)`] ] [[] [] [`Set operator & (const Set& s1, const Set& s2)`]] ] Equality on `Sets` is not implemented as `operator ==`, because `operator ==` is used for the stronger lexicographical equality on segments, that takes the segmentation of elements into account. Being models of concept `Set`, __icl_set__ and all __itv_bsets__ implement these operations and obey the associated laws on `Sets`. See e.g. [@http://en.wikipedia.org/wiki/Algebra_of_sets an algebra of sets here]. [h5 Making intervals complete] An __itv__ is considered to be a set of elements as well. With respect to the `Set` concept presented above __itv__ implements the concept only partially. The reason for that is that addition and subtraction can not be defined on __itvs__. Two intervals `[1,2]` and `[4,5]` are not addable to a ['*single*] new __itv__. In other words __itvs__ are incomplete w.r.t. union and difference. __Itv_sets__ can be defined as the ['*completion*] of intervals for the union and difference operations. When we claim that addition or subtraction can not be defined on intervals, we are not considering things like e.g. interval arithmetics, where these operations can be defined, but with a different semantics. [h5 A Map Concept] On the __conceptual__ aspect __icl_map__ and all __itv_bmaps__ are models of a concept `Map`. Since a `map` is a `set of pairs`, we try to design the `Map` concept in accordance to the `Set` concept above. [table [[Function] [Variant][implemented as] ] [[empty map ] [] [`Map::Map()`] ] [[subset relation] [] [`bool within(const Map& s2, const Map& s2)const`] ] [[equality ] [] [`bool is_element_equal(const Map& s1, const Map& s2)`]] [[map union] [inplace][`Map& operator += (Map& s1, const Map& s2)`] ] [[] [] [`Map operator + (const Map& s1, const Map& s2)`]] [[map difference] [inplace][`Map& operator -= (Map& s1, const Map& s2)`] ] [[] [] [`Map operator - (const Map& s1, const Map& s2)`]] [[map intersection][inplace][`Map& operator &= (Map& s1, const Map& s2)`] ] [[] [] [`Map operator & (const Map& s1, const Map& s2)`]] ] As one can see, on the abstract kernel the signatures of the icl's `Set` and `Map` concepts are identical, except for the typename. While signatures are identical The sets of valid laws are different, which will be described in more detail in the sections on the [link boost_icl.semantics.sets semantics of icl Sets] and [link boost_icl.semantics.maps Maps]. These semantic differences are mainly based on the implementation of the pivotal member functions `add` and `subtract` for elements and intervals that again serve for implementing `operator +=` and `operator -=`. [endsect][/ Abstract Sets and Maps] [section:aggrovering Addability, Subtractability and Aggregate on Overlap] While ['*addition*] and ['*subtraction*] on `Sets` are implemented as ['*set union*] and ['*set difference*], for `Maps` we want to implement ['*aggregation*] on the associated values for the case of collision (of key elements) or overlap (of key intervals), which has been refered to as ['*aggregate on overlap*] above. This kind of `Addability` and `Subtractability` allows to compute a lot of useful aggregation results on an __itv_map_s__ associated values, just by adding and subtracting value pairs. Various examples of ['*aggregate on overlap*] are given in [link boost_icl.examples section examples]. In addition, this concept of `Addability` and `Subtractability` contains the classical `Insertability` and `Erasability` of key value pairs as a special case so it provides a broader new semantics without loss of the /classical/ one. Aggregation is implemented for functions `add` and `subtract` by propagating a `Combiner` functor to combine associated values of type `CodomainT`. The standard `Combiner` is set as default template parameter `templateclass Combine = inplace_plus`, which is again generically implemented by `operator +=` for all Addable types. For `Combine` functors, the Icl provides an __inverse__ functor. [table [[`Combine`] [`inverse >::type`]] [[__ip_plus__``] [__ip_minus__``] ] [[__ip_et__``] [__ip_caret__``] ] [[__ip_star__``] [__ip_slash__``] ] [[__ip_max__``] [__ip_min__``] ] [[__ip_identity__``][__ip_erasure__``]] [[`Functor`] [__ip_erasure__``]] ] The meta function __inverse__ is mutually implemented for all but the default functor `Functor` such that e.g. `inverse >::type` yields `inplace_plus`. Not in every case, e.g. `max/min`, does the __inverse__ functor invert the effect of it's antetype. But for the default it does: [table [[] [`_add >((k,x))`] [`_subtract >::type>((k,x))`]] [[Instance] [`_add >((k,x))`] [`_subtract >((k,x))`]] [[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`]] ] As already mentioned aggregating `Addability` and `Subtractability` on `Maps` contains the /classical/ `Insertability` and `Erasability` of key value pairs as a special case: [table [[aggregating function][equivalent /classical/ function]] [[`_add >(const value_type&)`] [`insert(const value_type&)`]] [[`_subtract >(const value_type&)`][`erase(const value_type&)`]] ] The aggregating member function templates `_add` and `_subtract` are not in the public interface of __itv_bmaps__, because the `Combine` functor is intended to be an invariant of __itv_bmap_s__ template instance to avoid, that clients spoil the aggregation by accidentally calling varying aggregation functors. But you could instantiate an __itv_map__ to have `insert/erase` semantics this way: `` interval_map m; interval::type itv = interval::rightopen(2,7); m.add(make_pair(itv,42)); //same as insert m.subtract(make_pair(itv,42)); //same as erase `` This is, of course, only a clarifying example. Member functions `insert` and `erase` are available in __itv_bmap_s__ interface so they can be called directly. [endsect][/ Addability, Subtractability and Aggregation on Overlap] [section Map Traits] Icl maps differ in their behavior dependent on how they handle [@http://en.wikipedia.org/wiki/Identity_element ['*identity elements*]] of the associated type `CodomainT`. [h4 Remarks on Identity Elements] In the pseudo code snippets below `0` will be used to denote [@http://en.wikipedia.org/wiki/Identity_element `identity elements`], which can be different objects like `const double 0.0`, empty sets, empty strings, null-vectors etc. dependent of the instance type for parameter `CodomainT`. The existence of an ['*identity element*] wrt. an `operator+=` is a requirement for template type `CodomainT`. [table [[type] [operation] [identity element]] [[`int`] [addition] [`0`] ] [[`string`] [concatenation] [`""`] ] [[`set`] [union] [`{}`] ] ] In these cases the `identity element` value is delivered by the default constructor of the maps `CodomainT` type. But there are well known exceptions like e.g. numeric multiplication: [table [[type] [operation] [identity element]] [[`int`] [multiplication] [`1`] ] ] Therefore icl functors, that serve as `Combiner` parameters of icl Maps implement a static function `identity_element()` to make sure that the correct `identity_element()` is used in the implementation of ['aggregate on overlap]. `` inplace_times::identity_element() == 1 // or more general inplace_times::identity_element() == unit_element::value() `` [h4 Definedness and Storage of Identity Elements] There are two /properties/ or /traits/ of icl maps that can be chosen by a template parameter `Traits`. The ['*first trait*] relates to the ['*definedness*] of the map. Icl maps can be *partial* or *total* on the set of values given by domain type `DomainT`. * A ['*partial*] map is only defined on those key elements that have been inserted into the Map. This is usually expected and so ['*partial definedness*] is the default. * Alternatively an icl Map can be ['*total*]. It is then considered to contain a ['*neutral value*] for all key values that are not stored in the map. The ['*second trait*] is related to the representation of `identity elements` in the map. An icl map can be a ['*identity absorber*] or a ['*identity enricher*]. * A ['*identity absorber*] never stores value pairs `(k,0)` that carry identity elements. * A ['*identity enricher*] stores value pairs `(k,0)`. For the template parameter `Traits` of icl Maps we have the following four values. [table [[] [identity absorber] [identity enricher]] [[partial][partial_absorber /(default)/][partial_enricher]] [[total] [total_absorber] [total_enricher]] ] [h4 Map Traits motivated] Map traits are a late extension to the *icl*. Interval maps have been used for a couple of years in a variety of applications at Cortex Software GmbH with an implementation that resembled the default trait. Only the deeper analysis of the icl's ['*aggregating Map's concept*] in the course of preparation of the library for boost led to the introduction of map Traits. [h5 Add-Subtract Antinomy in Aggregating Maps] Constitutional for the absorber/enricher propery is a little antinomy. We can insert value pairs to the map by ['*adding*] them to the map via operations `add, +=` or `+`: ``{} + {(k,1)} == {(k,1)} // addition`` Further addition on common keys triggers aggregation: ``{(k,1)} + {(k,1)} == {(k,2)} // aggregation for common key k`` A subtraction of existing pairs ``{(k,2)} - {(k,2)} == {(k,0)} // aggregation for common key k`` yields value pairs that are associated with 0-values or `identity elements`. So once a value pair is created for a key `k` it can not be removed from the map via subtraction (`subtract, -=` or `-`). The very basic fact on sets, that we can remove what we have previously added ``x - x = {}`` does not apply. This is the motivation for the ['*identity absorber*] Trait. A identity absorber map handles value pairs that carry identity elements as ['*non-existent*], which saves the law: ``x - x = {}`` Yet this introduces a new problem: With such a /identity absorber/ we are /by definition/ unable to store a value `(k,0)` in the map. This may be unfavorable because it is not inline with the behavior of stl::maps and this is not necessarily expected by clients of the library. [/ CL On the other hand, the notion of a identity absorbing map is more than just an akademic rescue effort for a formal law. It turns out that absorber maps have desirable properties for aggregation computations (see section semantics) that proved to be useful in practice and are in many cases just what is needed.] The solution to the problem is the introduction of the identity enricher Trait, so the user can choose a map variant according to her needs. [h5 Partial and Total Maps] The idea of a identity absorbing map is, that an ['*associated identity element*] value of a pair `(k,0)` ['*codes non-existence*] for it's key `k`. So the pair `(k,0)` immediately tunnels from a map where it may emerge into the realm of non existence. ``{(k,0)} == {}`` If identity elements do not code ['*non-existence*] but ['*existence with null quantification*], we can also think of a map that has an associated identity element ['*for every*] key `k` that has no associated value different from 0. So in contrast to modelling *all* neutral value pairs `(k,0)` as being ['*non-existent*] we can model *all* neutral value pairs `(k,0)` as being ['*implicitly existent*]. A map that is modelled in this way, is one large vector with a value `v` for every key `k` of it's domain type `DomainT`. But only non-identity values are actually stored. This is the motivation for the definedness-Trait on `icl Maps`. A ['*partial*] map models the intuitive view that only value pairs are existent, that are stored in the map. A ['*total*] map exploits the possibility that all value pairs that are not stored can be considered as being existent and ['*quantified*] with the identity element. [/ partial existential view total quantifying view ] [h4 Pragmatical Aspects of Map Traits] From a pragmatic perspective value pairs that carry `identity elements` as mapped values can often be ignored. If we count, for instance, the number of overlaps of inserted intervals in an __itv_map__ (see example [link boost_icl.examples.overlap_counter overlap counter]), most of the time, we are not interested in whether an overlap has been counted `0` times or has not been counted at all. A identity enricher map is only needed, if we want to distinct between non-existence and 0-quantification. The following distinction can *not* be made for a __pabsorber__ map but it can be made for an __penricher__ map: [pre (k,v) does not exist in the map: Pair (k,v) has NOT been dealt with (k,0) key k carries 0 : Pair (k,v) has been dealt with resulting in v=0 ] Sometimes this subtle distinction is needed. Then a __penricher__ is the right choice. Also, If we want to give two `icl::Maps` a common set of keys in order to, say, iterate synchronously over both maps, we need /enrichers/. [endsect] [/ Map Traits] [endsect][/ Concepts]