| [/ |
| 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 |
| `template<class>class 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<T>`] [`inverse<Combine<T> >::type`]] |
| [[__ip_plus__`<T>`] [__ip_minus__`<T>`] ] |
| [[__ip_et__`<T>`] [__ip_caret__`<T>`] ] |
| [[__ip_star__`<T>`] [__ip_slash__`<T>`] ] |
| [[__ip_max__`<T>`] [__ip_min__`<T>`] ] |
| [[__ip_identity__`<T>`][__ip_erasure__`<T>`]] |
| [[`Functor`] [__ip_erasure__`<T>`]] |
| ] |
| |
| The meta function __inverse__ is mutually implemented for |
| all but the default functor `Functor` |
| such that e.g. |
| `inverse<inplace_minus<T> >::type` yields `inplace_plus<T>`. |
| 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<Combine<CodomainT> >((k,x))`] [`_subtract<inverse<Combine<CodomainT> >::type>((k,x))`]] |
| [[Instance] [`_add<inplace_plus<int> >((k,x))`] [`_subtract<inplace_minus<int> >((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<inplace_identity<CodomainT> >(const value_type&)`] [`insert(const value_type&)`]] |
| [[`_subtract<inplace_erasure<CodomainT> >(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<int,int,partial_absorber, |
| std::less, |
| inplace_identity //Combine parameter specified |
| > m; |
| interval<int>::type itv = interval<int>::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<T>`] [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<int>::identity_element() == 1 |
| // or more general |
| inplace_times<T>::identity_element() == unit_element<T>::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] |
| |
