123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465 |
- [/
- 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]
|