[Boost-commit] svn:boost r66438 - in trunk/libs/icl/doc: . boostcon09

Subject: [Boost-commit] svn:boost r66438 - in trunk/libs/icl/doc: . boostcon09
From: afojgo_at_[hidden]
Date: 2010-11-07 12:38:36

Author: jofaber
Date: 2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
New Revision: 66438
URL: http://svn.boost.org/trac/boost/changeset/66438

Log:
Boost.Icl version 4.0.0 initial import
Added:
   trunk/libs/icl/doc/
   trunk/libs/icl/doc/Jamfile.v2   (contents, props changed)
   trunk/libs/icl/doc/acknowledgments.qbk   (contents, props changed)
   trunk/libs/icl/doc/boostcon09/
   trunk/libs/icl/doc/boostcon09/intro_to_itl.odp   (contents, props changed)
   trunk/libs/icl/doc/boostcon09/intro_to_itl.pdf   (contents, props changed)
   trunk/libs/icl/doc/boostcon09/intro_to_itl_3_0_0_bc09.odp   (contents, props changed)
   trunk/libs/icl/doc/boostcon09/intro_to_itl_3_0_0_bc09.pdf   (contents, props changed)
   trunk/libs/icl/doc/boostcon09/intro_to_itl_3_1_0.odp   (contents, props changed)
   trunk/libs/icl/doc/boostcon09/intro_to_itl_3_1_0.pdf   (contents, props changed)
   trunk/libs/icl/doc/concepts.qbk   (contents, props changed)
   trunk/libs/icl/doc/customization.qbk   (contents, props changed)
   trunk/libs/icl/doc/examples.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_addition.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_cons_copy_dest.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_containedness.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_ctor_dtor.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_element_iteration.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_equivs_orderings.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_erasure.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_insertion.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_intersection.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_interval_construct.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_interval_misc.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_interval_orderings.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_iterator_related.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_range.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_selection.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_size.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_streaming.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_subtraction.qbk   (contents, props changed)
   trunk/libs/icl/doc/functions_symmetric_difference.qbk   (contents, props changed)
   trunk/libs/icl/doc/icl.qbk   (contents, props changed)
   trunk/libs/icl/doc/implementation.qbk   (contents, props changed)
   trunk/libs/icl/doc/interface.qbk   (contents, props changed)
   trunk/libs/icl/doc/introduction.qbk   (contents, props changed)
   trunk/libs/icl/doc/projects.qbk   (contents, props changed)
   trunk/libs/icl/doc/semantics.qbk   (contents, props changed)

Added: trunk/libs/icl/doc/Jamfile.v2
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/Jamfile.v2	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,55 @@
+# Boost.Icl
+#
+# Copyright (c) 2008-2009 Joachim Faulhaber
+# Copyright (c) 2000-2006 Cortex Software GmbH
+#
+# 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)
+
+import doxygen ;
+import quickbook ;
+
+# -----------------------------------------------------------------------------
+# Doxygen
+# -----------------------------------------------------------------------------
+
+doxygen icldoc
+    :
+        [ glob ../../../boost/icl/*.hpp ]
+    :
+        <doxygen:param>EXTRACT_ALL=YES
+        <doxygen:param>HIDE_UNDOC_MEMBERS=NO
+        <doxygen:param>EXTRACT_PRIVATE=NO
+        <doxygen:param>ENABLE_PREPROCESSING=YES
+        <doxygen:param>MACRO_EXPANSION=NO
+        <doxygen:param>EXPAND_ONLY_PREDEF=YES
+        <doxygen:param>SEARCH_INCLUDES=NO
+        <reftitle>"Interval Container Library Reference"
+    ;
+
+
+# -----------------------------------------------------------------------------
+# Quickbook
+# -----------------------------------------------------------------------------
+
+import quickbook ;
+
+xml icl
+    :
+        icl.qbk
+    ;
+
+boostbook standalone
+    :
+        icl
+    :
+        <xsl:param>boost.root=../../../..
+        <xsl:param>boost.libraries=../../../libraries.htm
+        <xsl:param>toc.max.depth=2
+        <xsl:param>toc.section.depth=2
+        <xsl:param>chunk.section.depth=2
+		<dependency>icldoc
+
+    ;
+

Added: trunk/libs/icl/doc/acknowledgments.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/acknowledgments.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,42 @@
+[/
+    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 Acknowledgments]
+
+I would like to thank CEO Hermann Steppe and Chief Developer Peter Wuttke
+of Cortex Software GmbH for their friendly support of my work on the
+Icl and their permission to release the library as open source.
+For her genuine interest in my work and many creative and
+uplifting talks I want to thank my colleague Axinja Ott who
+contributed a lot to the success of the project. 
+
+Many thanks to Paul A. Bristow, Vicente Botet, Luke Simonson,
+Alp Mestan, David Abrahams, Steven Watanabe, Neal Becker, Phil Endecott,
+Robert Stewart, Jeff Flinn, Zachary Turner
+and other developers
+form the Boost community who supported the development of the 
+Interval Template Library by numerous hints and feedbacks on 
+the boost mailing list.
+Also helpful have been conversations, hints and contributions
+at the BoostCon 2009 by Jeff Garland, David Jenkins, Tobias Loew,
+Barend Gehrels, Luke Simonson and Hartmut Kaiser. 
+Special thanks for reading and improving this documentation to
+Neal Becker, Ilya Bobir and Brian Wood.
+Jeff Flinn provided valuable feedback and a codepatch to fix 
+portability problems with CodeWarrior 9.4. Many thanks for that.
+
+I am grateful to Hartmut Kaiser for managing the formal review of 
+this library and to all the reviewers and participants
+in the related discussions, including Jeff Flinn, Luke Simonson, 
+Phil Endecott, Eric M. Jonas, Peter Wuttke, Robert Stewart,
+Barend Gehrels, Vicente Botet, Thomas Klimpel, Paul A. Bristow,
+Jerry Jeremiah, John Reid, Steven Watanabe, Brian Wood, Markus Werle 
+and Michael Caisse. 
+
+[endsect]
+

Added: trunk/libs/icl/doc/boostcon09/intro_to_itl.odp
==============================================================================
Binary file. No diff available.

Added: trunk/libs/icl/doc/boostcon09/intro_to_itl.pdf
==============================================================================
Binary file. No diff available.

Added: trunk/libs/icl/doc/boostcon09/intro_to_itl_3_0_0_bc09.odp
==============================================================================
Binary file. No diff available.

Added: trunk/libs/icl/doc/boostcon09/intro_to_itl_3_0_0_bc09.pdf
==============================================================================
Binary file. No diff available.

Added: trunk/libs/icl/doc/boostcon09/intro_to_itl_3_1_0.odp
==============================================================================
Binary file. No diff available.

Added: trunk/libs/icl/doc/boostcon09/intro_to_itl_3_1_0.pdf
==============================================================================
Binary file. No diff available.

Added: trunk/libs/icl/doc/concepts.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/concepts.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,465 @@
+[/
+    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.month_and_week_grid 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 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*] or ['*aggrovering*] 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 ['*aggrovering*] 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 protonic value 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]
+

Added: trunk/libs/icl/doc/customization.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/customization.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,40 @@
+[/
+    Copyright (c) 2010-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 Customization]
+
+[section Intervals]
+
+The *icl* provides the possibility of customizing user defined interval class templates
+and class types with static interval borders to be used with interval containers. 
+
+There is a template __itv_tr__, that has to be instatiated for the user defined
+interval type, in order to provide associated types and basic functions.
+Bound types of the interval are assigned by specializing the template 
+`interval_bound_type`.
+
+[table
+[[Customize]        [Name]             [Description]]
+[[associated types] [`interval_type`]  [interval type of the partial specialisation for the user defined type] ]
+[[]                 [`domain_type`]    [the domain or element type of the interval]                            ]
+[[]                 [`domain_compare`] [the ordering on the elements]                                          ]
+[[basic functions]  [`construct(const domain_type&, const domain_type&)`] [construct an interval]              ]
+[[]                 [`lower(const interval_type&)`]                       [select the interval's lower bound]  ]
+[[]                 [`upper(const interval_type&)`]                       [select the interval's upper bound]  ]
+[[interval bounds]  [`interval_bound_type<interval_type>{...}`] [specialize meta function `interval_bound_type`
+                                                                 to assign one of the 4 bound types to the user defined interval. ]  ]
+]
+
+How to do the customization in detail is shown in example 
+[link boost_icl.examples.custom_interval custom interval].
+
+[endsect][/ Intervals]
+
+[endsect][/ Customization]
+
+

Added: trunk/libs/icl/doc/examples.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/examples.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,387 @@
+[/
+    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 Examples]
+
+[section Overview]
+
+[table Overview over Icl Examples
+    [[level]   [example] [classes] [features]]
+    [[intro][[link boost_icl.examples.party Party]]
+        [__itv_map__][Generates an attendance history of a party
+                      by inserting into an __itv_map__. 
+                      Demonstrating 
+                      ['*aggregate on overlap*].]]
+    [[basic]   [[link boost_icl.examples.interval Interval]]
+        [__dc_itv__, __ct_itv__  ] [Intervals for discrete and continuous instance types. 
+                   Closed and open interval borders.]]
+    [[basic]   [[link boost_icl.examples.dynamic_interval Dynamic intervals]]
+        [__dc_itv__, __ct_itv__, __itv__ ] [Intervals with dynamic interval bounds as library default.]]
+    [[basic]   [[link boost_icl.examples.static_interval Static intervals]]
+        [__ro_itv__, __itv__ ] [Intervals with static interval bounds and changing the library default.]]
+    [[basic]   [[link boost_icl.examples.interval_container Interval container]]
+        [__itv_set__,\n__sep_itv_set__,\n__spl_itv_set__,\n__spl_itv_map__,\n__itv_map__]
+                                   [Basic characteristics of interval containers.]]
+    [[basic]   [[link boost_icl.examples.overlap_counter Overlap counter]]
+        [__itv_map__][The most simple application of an interval map: 
+                      Counting the overlaps of added intervals.]]
+    [[advanced][[link boost_icl.examples.partys_height_average Party's height average]]
+        [__itv_map__][Using /aggregate on overlap/ a history of height averages of party guests is computed.  
+                      Associated values are user defined class objects, that implement
+                      an appropriate `operator +=` for the aggregation.]]
+    [[advanced][[link boost_icl.examples.partys_tallest_guests Party's tallest guests]]
+        [__itv_map__,\n__spl_itv_map__]
+                     [Using /aggregate on overlap/ the heights of the party's tallest guests are computed.  
+                      Associated values are aggregated via a maximum functor, that can 
+                      be chosen as template parameter of an interval_map class template.]]
+    [[advanced][[link boost_icl.examples.time_grids_for_months_and_weeks Time grids for months and weeks]]
+                                [__spl_itv_set__]
+                                             [Shows how the ['*border preserving*]
+                                              __spl_itv_set__ can be used to create time partitions where different
+                                              periodic time intervals overlay each other.]]
+    [[advanced][[link boost_icl.examples.man_power Man power]]      
+        [__itv_set__,\n__itv_map__]
+        [Set style operations on __itv_sets__ and __itv_maps__ like union, difference
+         and intersection can be used to obtain calculations in a flexible way. Example
+         [*man_power] demonstrates such operations in the process of calculating the
+         available man-power of a company in a given time interval.]]
+    [[advanced][[link boost_icl.examples.user_groups User groups]][__itv_map__]
+        [Example [*user_groups] shows how interval_maps can be unified or 
+         intersected to calculate desired information.]]
+         
+    [[and std]   [[link boost_icl.examples.std_copy Std copy]]
+        [__itv_map__][Fill interval containers using `std::copy`.]]
+    [[and std]   [[link boost_icl.examples.std_transform Std transform]]
+        [__itv_map__,\n__sep_itv_set__][Fill interval containers from user defined objects using `std::transform`.]]
+        
+    [[customize] [[link boost_icl.examples.custom_interval Custom interval]]
+        [__itv_tr__][Use interval containers with your own interval class types.]]
+
+]
+
+[endsect]
+
+[section Party]
+[import ../example/boost_party_/boost_party.cpp]
+
+Example *party* demonstrates the possibilities of an interval map 
+(__itv_map__ or __spl_itv_map__). 
+An __itv_map__ maps intervals to a given content. In this case the 
+content is a set of party guests represented by their name strings.
+
+As time goes by, groups of people join the party and leave later in the evening.
+So we add a time interval and a name set to the __itv_map__ for the attendance
+of each group of people, that come together and leave together.
+On every overlap of intervals, the corresponding name sets are accumulated. At
+the points of overlap the intervals are split. The accumulation of content
+is done via an operator += that has to be implemented
+for the content parameter of the __itv_map__.
+Finally the interval_map contains the history of attendance and all points in
+time, where the group of party guests changed.
+
+Party demonstrates a principle that we call 
+['*aggregate on overlap (aggrovering)*]:
+On insertion a value associated to the interval is aggregated with those
+values in the interval_map that overlap with the inserted value.
+There are two behavioral aspects to ['*aggrovering*]: a ['*decompositional
+behavior*] and an ['*accumulative behavior*].
+
+* The ['*decompositional behavior*] splits up intervals on the /time/ /dimension/ of the 
+  interval_map so that the intervals are split whenever associated values
+  change.
+
+* The ['*accumulative behavior*] accumulates associated values on every overlap of
+  an insertion for the associated values.
+    
+The aggregation function is += by default. Different aggregations can
+be used, if desired.
+
+    
+[example_boost_party]
+
+[caution
+
+We are introducing __itv_maps__ using an 
+['interval map ['*of sets of strings*]],
+because of it's didactic advantages. The party example is
+used to give an immediate access to the basic ideas of
+interval maps and /aggregate on overlap/.
+For real world applications, an interval_map of sets is
+not necessarily recommended.
+It has the same efficiency problems as
+a `std::map` of `std::sets`.
+There is a big realm though of using
+interval_maps with numerical and other
+efficient data types for the associated values.
+]
+
+[endsect] [/ Party]
+
+
+[section Interval]
+
+Example *interval* shows some basic functionality of __itvs__. 
+
+* Different instances of __itvs__ for integral ([^int, Time]) and
+  continuous types ([^double, std::string]) are used.
+
+* The examples uses open and closed intervals bounds.
+
+* Some borderline functions calls on open interval borders are tested e.g.:
+  `interval<double>::rightopen(1/sqrt(2.0), sqrt(2.0)).contains(sqrt(2.0));`
+
+[import ../example/interval_/interval.cpp]
+[example_interval]
+[endsect]
+
+[section Dynamic interval]
+[import ../example/dynamic_interval_/dynamic_interval.cpp]
+[example_dynamic_interval]
+[endsect]
+
+[section Static interval]
+[import ../example/static_interval_/static_interval.cpp]
+[example_static_interval]
+[endsect]
+
+
+[section Interval container]
+
+Example [*interval container] demonstrates the characteristic behaviors
+of different interval containers that are also summarized
+in the introductory [link boost_icl.introduction.interval_combining_styles Interval Combining Styles].
+
+[import ../example/interval_container_/interval_container.cpp]
+[example_interval_container]
+[endsect]
+
+
+[section Overlap counter]
+
+Example [*overlap counter] provides the simplest application
+of an interval_map that maps intervals to integers. 
+An interval_map<int,int> serves as an overlap counter
+if we only add interval value pairs that carry 1 as
+associated value.
+
+Doing so, the associated values that are accumulated in
+the interval_map are just the number of overlaps of all added
+intervals.
+
+[import ../example/overlap_counter_/overlap_counter.cpp]
+[example_overlap_counter]
+[endsect]
+
+
+
+[section:partys_height_average Party's height average]
+
+In the example `partys_height_average.cpp` we compute yet another aggregation:
+The average height of guests. This is done by defining a `class counted_sum` 
+that sums up heights and counts the number of guests
+via an `operator +=`.
+
+Based on the `operator +=` we can aggregate counted sums on addition
+of interval value pairs into an interval_map.
+
+[import ../example/partys_height_average_/partys_height_average.cpp]
+[example_partys_height_average]
+
+Required for `class counted_sum` is a default constructor 
+`counted_sum()`and
+an `operator ==` to test equality.
+To enable additive aggregation on overlap also
+an `operator +=` is needed.
+
+Note that no `operator -=` for a subtraction of `counted_sum` values
+is defined. So you can only add to the 
+`interval_map<ptime, counted_sum>`
+but not subtract from it.
+
+In many real world applications only addition is needed and user 
+defined classes will work fine, if they only implement 
+`operator +=`. Only if any of the `operator`s `-=` or `-`
+is called on the interval_map, the user defined class has to
+implement it's own `operator -=` to provide the subtractive
+aggregation on overlap.
+
+[endsect]
+
+
+[section:partys_tallest_guests Party's tallest guests]
+
+Defining `operator +=` (and `-=`) is probably the most important
+method to implement arbitrary kinds of user defined aggregations.
+An alternative way to choose a desired aggregation is to
+instantiate an interval_map class template with an 
+appropriate ['*aggregation functor*]. For the most common 
+kinds of aggregation the [*icl]
+provides such functors as shown in the example.
+
+Example `partys_tallest_guests.cpp` also demonstrates 
+the difference between an __itv_map__
+that joins intervals for equal associated values and a
+__spl_itv_map__ that preserves all borders of inserted
+intervals.
+
+[import ../example/partys_tallest_guests_/partys_tallest_guests.cpp]
+[example_partys_tallest_guests]
+
+[endsect]
+
+[section Time grids for months and weeks]
+
+A __spl_itv_set__ preserves all interval borders on insertion
+and intersection operations. So given a __spl_itv_set__ and an addition of an interval
+``
+x =  {[1,     3)}
+x.add(     [2,     4)) 
+``
+then the intervals are split at their borders
+``
+x == {[1,2)[2,3)[3,4)}
+``
+Using this property we can intersect __spl_itv_maps__ in
+order to iterate over intervals accounting for all occurring
+changes of interval borders.
+
+In this example we provide an intersection of two __spl_itv_sets__
+representing a month and week time grid. 
+
+[import ../example/month_and_week_grid_/month_and_week_grid.cpp]
+[example_month_and_week_grid]
+[endsect]
+
+[section Man power]
+
+__Itv_sets__ and __itv_maps__ can be filled and manipulated using
+set style operations such as union `+=`, difference `-=` and 
+intersection `&=`.
+
+In this example [*man power] a number of those operations are
+demonstrated in the process of calculation the available working 
+times (man-power) of a company's employees accounting for weekends,
+holidays, sickness times and vacations.
+
+[import ../example/man_power_/man_power.cpp]
+[example_man_power]
+[endsect]
+
+[section User groups]
+
+Example [*user groups] shows the availability of set operations
+on __itv_maps__. 
+
+In the example there is a user group `med_users` of a hospital staff
+that has the authorisation to handle medical data of patients.
+User group `admin_users` has access to administrative data like
+health insurance and financial data.
+
+The membership for each user in one of the user groups has a time
+interval of validity. The group membership begins and ends.
+
+* Using a union operation `+` we can have an overview over the unified
+  user groups and the membership dates of employees.
+
+* Computing an intersection `&` shows who is member of both med_users 
+  and admin_users at what times.
+
+[import ../example/user_groups_/user_groups.cpp]
+[example_user_groups]
+[endsect]
+
+
+[section Std copy]
+
+The standard algorithm 
+[@http://www.cplusplus.com/reference/algorithm/copy/ `std::copy`]
+can be used to fill interval containers
+from standard containers of intervals or
+interval value pairs (segments). Because intervals
+do not represent ['*elements*] but ['*sets*], that
+can be empty or contain more than one element,
+the usage of `std::copy` differs from what we
+are familiar with using ['containers of elements].
+
+* Use `icl::inserter` from `#include <boost/icl/iterator.hpp>`
+  instead of `std::inserter` to call insertions on the target
+  interval container.
+  
+* As shown in the examples above and below this point, most of
+  the time we will not be interested to `insert` segments
+  into __itv_maps__ but to __biLadd__
+  them, in order to generate the desired aggregation results.
+  You can use `std::copy` with an `icl::adder` instead of an
+  `icl::inserter` to achieve this.
+
+[import ../example/std_copy_/std_copy.cpp]
+[example_std_copy]
+
+[endsect][/ Std copy]
+
+
+[section Std transform]
+
+Instead of writing loops, the standard algorithm 
+[@http://www.cplusplus.com/reference/algorithm/transform/ `std::transform`]
+can be used to fill interval containers
+from std containers of user defined objects.
+We need a function, that
+maps the ['user defined object] into the
+['segement type] of an interval map or the
+['interval type] of an interval set.
+Based on that we can use `std::transform`
+with an `icl::inserter` or `icl::adder`
+to transform the user objects into interval
+containers. 
+
+[import ../example/std_transform_/std_transform.cpp]
+[example_std_transform]
+
+To get clear about the different behaviors of interval containers 
+in the example, you may want to refer to the section about 
+[link boost_icl.introduction.interval_combining_styles interval combining styles]
+that uses the same data.
+
+[/
+Instead of `icl::inserter` we could also use an `std::inserter`
+with algorithms `std::copy` and `std::transform`.
+This is ['*depreciated*], because `std::inserter` is designed for
+containers of elements, where ['*exacty one*] element is inserted 
+via `std::inserter` if it is not already in the container. 
+In contrast to that, an interval or segemnt can represent zero, one, 
+or many elements of an interval container.
+
+You can use `std::inserter` *only*, if you actively take care of
+two preconditions:
+
+# None of the intervals or segements of the source containers
+  must be empty.
+  
+# A segment never carries a neutral element when your target 
+  interval map absorbs identities.
+
+Violating those preconditions leads to ['*undefined behavior*].
+]
+
+[endsect][/ std::transform]
+
+
+[section Custom interval]
+
+Example *custom interval* demonstrates how to use interval 
+containers with an own interval class type. 
+
+[import ../example/custom_interval_/custom_interval.cpp]
+[example_custom_interval]
+[endsect][/ Custom interval]
+
+
+
+[endsect][/ examples]
+

Added: trunk/libs/icl/doc/functions.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,269 @@
+[/
+    Copyright (c) 2008-2009 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 Function Reference]
+
+Section [link boost_icl.interface.function_synopsis Function Synopsis] 
+above gave an overview of the polymorphic functions of the icl.
+This is what you will need to find the desired possibilities to combine icl 
+functions and objects most of the time.
+The functions and overloads that you intuitively expect
+should be provided, so you won't need to refer to the documentation very often.
+
+If you are interested 
+
+* in the ['*specific design of the function overloads*],
+* in ['*complexity characteristics*] for certain overloads 
+* or if the compiler ['*refuses to resolve*] specific function application you want to use,
+
+refer to this section that describes the polymorphic function families of the icl
+in detail.
+
+[h5 Placeholders]
+
+For a concise representation the same __eiS_phs__ will be used that have been
+introduced in section [link boost_icl.interface.function_synopsis Function Synopsis].
+
+[h5 More specific function documentation]
+
+This section covers the most important polymorphical and namespace global
+functions of the *icl*. More specific functions can be looked up
+in the doxygen generated
+[link interval_template_library_reference reference documentation].
+
+[section Overload tables]
+
+Many of the *icl's* functions are overloaded for
+elements, segments, element and interval containers.
+But not all type combinations are provided. Also
+the admissible type combinations are different for
+different functions and operations.
+To concisely represent the overloads that can be
+used we use synoptical tables that contain 
+possible type combinations for an operation.
+These are called ['*overload tables*]. As an example
+the overload tables for the inplace intersection 
+`operator &=` are given:
+
+``
+// overload tables for
+T& operator &= (T&, const P&)
+
+element containers:     interval containers:  
+&= | e b s m            &= | e i b p S M    
+---+--------            ---+------------    
+s  | s   s              S  | S S     S       
+m  | m m m m            M  | M M M M M M    
+``
+
+For the binary `T& operator &= (T&, const P&)` there are two
+different tables for the overloads of element and interval containers.
+The first argument type `T` is displayed as row headers
+of the tables. 
+The second argument type `P` is displayed as column headers
+of the tables. 
+If a combination of `T` and `P` is admissible the related 
+cell of the table is non empty.
+It displays the result type of the operation. In this example
+the result type is always equal to the first argument.
+
+The possible types that can be instantiated for `T` and `P`
+are element, interval and container types abbreviated by
+placeholders that are defined 
+[link boost_icl.interface.function_synopsis here]
+and can be summarized as
+
+__s : element set, __S : interval sets, __e : elements, __i : intervals\n
+__m:element map,   __M:interval maps,   __b:element-value pairs, __p:interval-value pairs
+
+
+[endsect][/ Overload tables]
+
+[section Segmentational Fineness]
+
+For overloading tables on infix operators, we need to
+break down __itv_sets__ and __itv_maps__ to the
+specific class templates
+
+[table
+[[][] [][] [][]]
+[[[#ph_def_S1][*S1]][__itv_set__][[#ph_def_S2][*S2]][__sep_itv_set__][[#ph_def_S3][*S3]][__spl_itv_set__]]
+[[[#ph_def_M1][*M1]][__itv_map__][][]                                [[#ph_def_M3][*M3]][__spl_itv_map__]]
+]
+
+
+choosing *Si* and *Mi* as placeholders.
+
+The indices *i* of *Si* and *Mi* represent a property
+called ['*segmentational fineness*] or short ['*fineness*], 
+which is a ['*type trait*] on interval containers.
+
+[table
+[[]]
+[[`segmentational_fineness<`[*Si]`>::value` == *i*]]
+[[`segmentational_fineness<`[*Mi]`>::value` == *i*]]
+]
+
+
+Segmentational fineness represents the fact, 
+that for interval containers holding the same elements, a
+splitting interval container may contain more segments as
+a separating container which in turn may contain more
+segments than a joining one. So for an 
+``
+operator >
+``
+where
+``
+x > y   // means that
+x is_finer_than y
+
+// we have
+
+finer                                             coarser
+split_interval_set                           interval_set
+                   > separate_interval_set >  
+split_interval_map                           interval_map
+``
+
+This relation is needed to resolve the instantiation of
+infix operators e.g. `T operator + (P, Q)` for two interval container types
+`P` and `Q`. If both `P` and `Q` are candidates for the result
+type `T`, one of them must be chosen by the compiler.
+We choose the type that is segmentational finer as
+result type `T`. This way we do not loose the ['*segment information*]
+that is stored in the ['*finer*] one of the container types `P` and `Q`.
+
+``
+// overload tables for
+T operator + (T, const P&)
+T operator + (const P&, T)
+
+element containers:     interval containers:
++  | e b s m            +  | e  i  b  p  S1 S2 S3 M1 M3     
+---+--------            ---+---------------------------
+e  |     s              e  |             S1 S2 S3 
+b  |       m            i  |             S1 S2 S3 
+s  | s   s              b  |                      M1 M3  
+m  |   m   m            p  |                      M1 M3
+                        S1 | S1 S1       S1 S2 S3 
+                        S2 | S2 S2       S2 S2 S3 
+                        S3 | S3 S3       S3 S3 S3 
+                        M1 |       M1 M1          M1 M3
+                        M3 |       M3 M3          M3 M3
+``
+
+
+So looking up a type combination for e.g. 
+`T operator + (interval_map, split_interval_map)`
+which is equivalent to
+`T operator + (M1, M3)`
+we find for row type `M1` and column type `M3`
+that `M3`
+will be assigned as result type, because `M3`
+is finer than `M1`.
+So this type combination will result in
+choosing this
+``
+split_interval_map operator + (const interval_map&, split_interval_map)
+``
+implementation by the compiler.
+
+[endsect][/ Segmentational Fineness]
+
+[section Key Types]
+
+In an *stl* map `map<K,D>` the first parameter type of the map
+template `K` is called `key_type`. It allows to select key-value pairs
+pairs via `find(const K&)` 
+and to remove key-value pairs using `erase(const K&)`.
+For icl Maps we have generalized key types to a larger
+set of types. Not only the `key_type` (`domain_type`)
+but also an interval type and a set type can be ['*key types*],
+that allow for ['*selection*] and ['*removal*] of map elements 
+segments and submaps.
+
+[table Selection of elements, segments and sub maps using key types
+[[                     ][  __M: __itv_maps__    ][  __m: icl_map        ]]
+[[__e: `domain_type`   ][  key value pair       ][   key value pair ]]
+[[__i: `interval_type` ][  interval value pair  ][                     ]]
+[[__S: __itv_sets__    ][  interval map            ][                     ]]
+[[__s: __icl_set__     ][                       ][   interval map     ]]
+]
+
+__biLSubtraction__, __biLerasure__, __biLintersection__
+[/ , which is a generalized find ]
+and __biLcontainedness__ predicates
+can be used with those kinds of key types.
+For instance, the overload table for intersection 
+
+``
+// overload tables for
+T& operator &= (T&, const P&)
+
+element containers:     interval containers:  
+&= | e b s m            &= | e i b p S M    
+---+--------            ---+------------    
+s  | s   s              S  | S S     S       
+m  | m m m m            M  | M M M M M M    
+``
+
+has a part that that allows for selection by key objects
+
+``
+element containers:     interval containers:  
+&= | e b s m            &= | e i b p S M    
+---+--------            ---+------------    
+s  | s   s              S  | S S     S       
+m  | m   m              M  | M M     M      
+``
+
+and another part that provides overloads for 
+generalized intersection:
+
+``
+element containers:     interval containers:  
+&= | e b s m            &= | e i b p S M    
+---+--------            ---+------------    
+s  | s   s              S  | S S     S       
+m  |   m   m            M  |     M M   M      
+``
+
+For `Sets`, the ['*key types*] defined for maps
+are identical with the set types themselves.
+So the distinction between the function groups
+['*selection by key*] and ['*generalized intersection*]
+fall together in the well known ['*set intersection*].
+
+[endsect][/ Key Types]
+
+[include functions_cons_copy_dest.qbk]
+[include functions_containedness.qbk]
+[include functions_equivs_orderings.qbk]
+[include functions_size.qbk]
+[include functions_range.qbk]
+[include functions_selection.qbk]
+[include functions_addition.qbk]
+[include functions_subtraction.qbk]
+[include functions_insertion.qbk]
+[include functions_erasure.qbk]
+[include functions_intersection.qbk]
+[include functions_symmetric_difference.qbk]
+[include functions_iterator_related.qbk]
+[include functions_element_iteration.qbk]
+[include functions_streaming.qbk]
+
+[include functions_interval_construct.qbk]
+[include functions_interval_orderings.qbk]
+[include functions_interval_misc.qbk]
+
+
+[endsect][/ Function Reference]
+
+

Added: trunk/libs/icl/doc/functions_addition.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_addition.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,257 @@
+[/
+    Copyright (c) 2008-2009 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)
+]
+
+
+[/ //= Addition ===============================================================]
+[section Addition]
+
+[section Synopsis]
+
+[table
+
+[[Addition]                                [__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__] ]
+
+[[`T& T::add(const P&)`]                           [__ei]    [__bp]   [ ]     [__b]  ]
+[[`T& add(T&, const P&)`]                          [__ei]    [__bp]   [__e]   [__b]  ]
+[[`T& T::add(J pos, const P&)`]                    [__i]     [__p]    [ ]     [__b]  ]
+[[`T& add(T&, J pos, const P&)`]                   [__i]     [__p]    [__e]   [__b]  ]
+
+[[`T& operator +=(T&, const P&)`]                  [__eiS]   [__bpM]  [__es]  [__bm] ]
+[[`T operator + (T, const P&)`\n
+  `T operator + (const P&, T)`]
+                                                   [__eiS]   [__bpM]  [__es]  [__bm] ]
+[[`T& operator |=(      T&, const P&)`]            [__eiS]   [__bpM]  [__es]  [__bm] ]
+[[`T operator | (T, const P&)`\n
+  `T operator | (const P&, T)`]
+                                                   [__eiS]   [__bpM]  [__es]  [__bm] ]
+
+]
+
+Functions and operators that implement ['*Addition*] on *icl* objects
+are given in the table above.
+`operator |=` and `operator |` are behavioral identical to 
+`operator +=` and `operator +`.
+This is a redundancy that has been introduced deliberately, because 
+a /set union/ semantics is often attached `operators |=` and `|`. 
+
+[table
+[[]      [Description of Addition]]
+[[`Sets`][Addition on Sets implements ['*set union*]]]
+[[`Maps`][Addition on Maps implements a ['*map union*] function similar to /set union/.
+          If, on insertion of an element value pair `(k,v)` it's key `k` is in the map 
+          already, the addition function is propagated to the associated value.
+          This functionality has been introduced as /aggregate on collision/
+          for element maps and /aggregate on overlap/ for interval maps. 
+        
+          Find more on 
+          [link boost_icl.concepts.addability__subtractability_and_aggregate_on_overlap ['addability of maps]]
+          and related 
+          [link boost_icl.semantics.maps ['semantic issues]] 
+          following the links. 
+        
+          Examples, demonstrating Addition on interval containers are
+          [link boost_icl.examples.overlap_counter ['overlap counter]],
+          [link boost_icl.examples.party ['party]] and
+          [link boost_icl.examples.partys_height_average ['party's height average.]] 
+         ]]
+]
+
+For `Sets` ['*addition*] and ['*insertion*] are implemented identically.
+Functions `add` and `insert` collapse to the same function. 
+For `Maps` ['*addition*] and ['*insertion*] work differently. 
+Function `add` performs aggregations on collision or overlap, 
+while function `insert` only inserts values that do not yet have key values. 
+
+[endsect][/ Synopsis]
+
+[section Functions][/ Addition]
+
+The admissible combinations of types for member function 
+`T& T::add(const P&)` can be summarized in the 
+['*overload table*] below:
+
+``
+// overload table for    T\P| e i b p  
+T& T::add(const P&)      ---+--------
+T& add(T&, const P&)      s | s
+                          m |     m
+                          S | S S      
+                          M |     M M  
+``
+
+The next table contains complexity characteristics for `add`.
+
+[table Time Complexity for member function add on icl containers
+[[`T& T::add(const P&)`\n
+  `T& add(T&, const P&)`]      [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
+[[__icl_set__]                 [__Olgn__] []          []        []          ]
+[[__icl_map__]                 []         []          [__Olgn__][]          ]
+[[__itv_set__\n__sep_itv_set__][__Olgn__] [__a_Olgn__][]        []          ]
+[[__spl_itv_set__]             [__Olgn__] [__On__]    []        []          ]
+[[__itv_map__\n__spl_itv_map__][]         []          [__Olgn__][__On__]    ]
+]
+
+[h5 Hinted addition]
+
+Function `T& T::add(T::iterator prior, const P& addend)` allows
+for an addition in ['*constant time*], if `addend` can be inserted
+right after iterator `prior` without collision. If this is not possible
+the complexity characteristics are as stated for the non hinted addition
+above. Hinted addition is available for these combinations of types:
+``
+// overload table for addition with hint        T\P| e i b p   
+T& T::add(T::iterator prior, const P&)          ---+--------
+T& add(T&, T::iterator prior, const P&)          s | s
+                                                 m |     m
+                                                 S |   S      
+                                                 M |       M   
+``
+
+[endsect][/ Functions Addition]
+
+[section Inplace operators]
+
+The possible overloads of inplace `T& operator += (T&, const P&)`
+are given by two tables, that show admissible combinations of types.
+Row types show instantiations of argument type `T`. Columns types
+show show instantiations of argument type `P`. If a combination
+of argument types is possible, the related table cell contains
+the result type of the operation. 
+__eiS_Phs__ __eibpsSmM__ will be used to denote 
+/elements, intervals, 
+element value pairs, interval value pairs, 
+element sets, interval sets, 
+element maps/ and /interval maps/. 
+The first table shows the 
+overloads of `+=` for /element containers/ the second table
+refers to /interval containers/. 
+
+``
+// overload tables for             element containers:     interval containers:  
+T& operator += (T&, const P&)      += | e b s m            += | e i b p S M    
+                                   ---+--------            ---+------------    
+                                   s  | s   s              S  | S S     S       
+                                   m  |   m   m            M  |     M M   M    
+``
+
+For the definition of admissible overloads
+we separate /element containers/ from /interval containers/.
+Within each group all combinations of types are supported 
+for an operation, that are in line with the *icl's* 
+design and the sets of laws, that establish the *icl's*
+[link boost_icl.semantics semantics].
+
+
+Overloads between /element containers/ and /interval containers/
+could also be defined. But this has not been done for
+pragmatical reasons: Each additional combination of types
+for an operation enlarges the space of possible overloads.
+This makes the overload resolution by compilers more complex,
+error prone and slows down compilation speed. Error messages
+for unresolvable or ambiguous overloads are difficult
+to read and understand. Therefore overloading of namespace
+global functions in the *icl* are limited to a reasonable
+field of combinations, that are described here.
+
+[endsect][/ Inplace operators]
+
+
+[h4 Complexity]
+
+For different combinations of argument types `T` and `P`
+different implementations of the `operator +=` are 
+selected. These implementations show different complexity
+characteristics. 
+If `T` is a container type, 
+the combination of 
+domain elements (__e) or element value pairs (__b)
+is faster than a combination of intervals (__i) or
+interval value pairs (__p) which in turn is faster than
+the combination of element or interval containers.
+The next table shows /time complexities/ of addition for
+*icl's* element containers.
+
+Sizes `n` and `m` are in the complexity statements are sizes
+of objects `T y` and `P x`:
+``
+n = iterative_size(y);
+m = iterative_size(x); //if P is a container type
+``
+Note, that for an interval container the number of elements `T::size` is
+different from the number of intervals that you can iterate over.
+Therefore a function `T::iterative_size()` is used that provides the
+desired kind of size.
+
+[table Time Complexity for inplace Addition on element containers
+[[`T& operator += (T& y, const P& x)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_sets__][__ch_icl_maps__]]
+[[__icl_set__]                        [__Olgn__]    []               [__Om__]         []               ]
+[[__icl_map__]                        []            [__Olgn__]       []               [__Om__]         ]
+]
+
+Time complexity characteristics of inplace addition for interval containers
+is given by this table.
+
+[table Time Complexity for inplace Addition on interval containers
+[[`T& operator += (T& y, const P& x)`][][__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
+[[interval_sets][__itv_set__\n__sep_itv_set__][__Olgn__] [__a_Olgn__][]        []        [__Omlgnpm__]    []               ]
+[[]             [__spl_itv_set__]             [__Olgn__] [__On__]    []        []        [__Omlgnpm__]    []               ]
+[[interval_maps][]                            []         []          [__Olgn__][__On__]  []               [__Omlgnpm__]    ]
+]
+
+Since the implementation of
+element and interval containers is based on the 
+[link boost_icl.implementation link red-black tree implementation]
+of std::AssociativeContainers, we have a logarithmic complexity for
+addition of elements.
+Addition of intervals or interval value pairs is amortized logarithmic
+for __itv_sets__ and __sep_itv_sets__ and linear for __spl_itv_sets__
+and __itv_maps__.
+Addition is linear for element containers and
+loglinear for interval containers.
+
+
+[section Infix operators]
+
+The admissible type combinations for infix `operator +`
+are defined by the overload tables below. 
+
+``
+// overload tables for          element containers:     interval containers:
+T operator + (T, const P&)      +  | e b s m            +  | e  i  b  p  S1 S2 S3 M1 M3  
+T operator + (const P&, T)      ---+--------            ---+---------------------------
+                                e  |     s              e  |             S1 S2 S3 
+                                b  |       m            i  |             S1 S2 S3 
+                                s  | s   s              b  |                      M1 M3  
+                                m  |   m   m            p  |                      M1 M3
+                                                        S1 | S1 S1       S1 S2 S3 
+                                                        S2 | S2 S2       S2 S2 S3 
+                                                        S3 | S3 S3       S3 S3 S3 
+                                                        M1 |       M1 M1          M1 M3
+                                                        M3 |       M3 M3          M3 M3
+``
+
+[endsect][/ Infix operators]
+
+
+['*See also . . .*]
+[table
+[]
+[[[link boost_icl.function_reference.subtraction ['*Subtraction*]]   ]]
+[[[link boost_icl.function_reference.insertion ['*Insertion*]]       ]]
+]
+
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]]    ]]
+[[[link boost_icl.interface ['*Interface*]]                ]]
+]
+
+[endsect][/ Addition]
+
+

Added: trunk/libs/icl/doc/functions_cons_copy_dest.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_cons_copy_dest.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,107 @@
+[/
+    Copyright (c) 2008-2009 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)
+]
+
+
+[/ //= Construct, copy, destruct ===================================================================]
+[section Construct, copy, destruct]
+
+[table
+[[['*Construct, copy, destruct*]]      [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__] ]
+[[`T::T()`]                                    [1]       [1]      [1]     [1]      [1]   ]
+[[`T::T(const P&)`]                            [A]   [__eiS]  [__bpM]     [1]      [1]   ]
+[[`T& T::operator=(const P&)`]                 [A]     [__S]    [__M]     [1]      [1]   ]
+[[`void T::swap(T&)`]                          [ ]       [1]      [1]     [1]      [1]   ]
+]
+
+All *icl* types are ['*regular types*]. They are ['*default constructible*], 
+['*copy constructible*] and ['*assignable*]. On icl Sets and Maps a `swap`
+function is available, that allows for *constant time* swapping of 
+container contents.
+The /regular and swappable part/ of the basic functions and their complexities
+are described in the tables below. 
+
+[table
+[[['*Regular and swap*]]      [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__] ]
+[[`T::T()`]                                 [__O1__]  [__O1__] [__O1__][__O1__] [__O1__] ]
+[[`T::T(const T&)`]                         [__O1__]  [__On__] [__On__][__On__] [__On__] ]
+[[`T& T::operator=(const T&)`]              [__O1__]  [__On__] [__On__][__On__] [__On__] ]
+[[`void T::swap(T&)`]                          [ ]    [__O1__] [__O1__][__O1__] [__O1__] ]
+]
+
+where /n/ `= iterative_size(x)`.
+
+[table
+[[['*Construct, copy, destruct*]] [Description] ]
+[[`T::T()`]                       [Object of type T is default constructed.] ]
+[[`T::T(const T& src)`]           [Object of type T is copy constructed from object `src`. ] ]
+[[`T& T::operator=(const T& src)`][Assigns the contents of src to `*this` object. Returns a reference to the assigned object.] ]
+[[`void T::swap(T& src)`]         [Swaps the content containers `*this` and `src` in constant time. ] ]
+]
+
+In addition we have overloads of constructors and assignment operators
+for icl container types.
+``
+// overload tables for constructors
+T::T(const P& src)
+
+element containers:     interval containers:  
+T \ P | e b s m         T \ P | e i b p S M    
+------+--------         ------+------------    
+s     | s   s           S     | S S     S       
+m     |   m   m         M     |     M M   M    
+``
+
+For an object `dst` of type `T` and an argument `src` of type `P` let
+``
+n = iterative_size(dst);
+m = iterative_size(src);
+``
+in the following tables.
+
+[table Time Complexity for overloaded constructors on element containers
+[[`T(const P& src)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
+[[__icl_set__]      [__Olgn__]    []               [__Om__]         []               ]
+[[__icl_map__]      []            [__Olgn__]       []               [__Om__]         ]
+]
+
+Time complexity characteristics of inplace insertion for interval containers
+is given by this table.
+
+[table Time Complexity for overloaded constructors on interval containers
+[[`T(const P& src)`] [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
+[[interval_sets]     [__O1__] [__O1__][]      []      [__Om__]    []          ]
+[[interval_maps]     []       []      [__O1__][__O1__][]          [__Om__]    ]
+]
+
+``
+// overload tables for assignment
+T& operator = (const P& src)
+
+interval containers:  
+T \ P | S M    
+------+----    
+S     | S       
+M     |   M    
+``
+
+The assignment `T& operator = (const P& src)` is overloaded within interval containers.
+For all type combinations we have ['*linear time complexity*]
+in the maximum of the `iterative_size` of `dst` and `src`.
+
+
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]]]]
+[[[link boost_icl.interface ['*Interface*]]                          ]]
+]
+
+
+[endsect][/ Construct, copy, destruct]
+
+

Added: trunk/libs/icl/doc/functions_containedness.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_containedness.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,134 @@
+[/
+    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)
+]
+
+
+[/ //= Containedness ===================================================================]
+[section Containedness]
+
+[table
+[[['*Containedness*]]       [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]  ]
+[[`bool T::empty()const`]                         [ ]       [1]      [1]     [1]      [1]   ]
+[[`bool is_empty(const T&)`]                      [1]       [1]      [1]     [1]      [1]   ]
+[[`bool contains(const T&, const P&)`\n
+  `bool within(const P&, const T&)`]            [__ei]  [__eiS][__eiS __bpM][__es]   [__bm] ]
+]
+
+This group of functions refers to ['*contain*]edness which should 
+be fundamental to ['*contain*]ers. The function `contains`
+is overloaded. It covers different kinds of containedness:
+Containedness of elements, segments, and sub containers.
+
+[table
+[[['*Containedness*]]                         [ /O(...)/ ][Description ]  ]
+[[`bool T::empty()const`\n
+  `bool is_empty(const T&)`]                  [__O1__][Returns `true`, if the container is empty, `false` otherwise.]      ]
+[[`bool contains(const T&, const P&)`\n
+  `bool within(const P&, const T&)`]          [[link complexities_contains ['see below]]]
+                                                      [Returns `true`, if `super` container contains object `sub`.]    ]
+[[ ]                                          [where] [ /n/` = iterative_size(sub)`]     ]
+[[ ]                                          [     ] [ /m/` = iterative_size(super)`]     ]
+]
+
+``
+// overload tables for 
+bool contains(const T& super, const P& sub)
+bool   within(const P& sub, const T& super)
+
+element containers:   interval containers:  
+T\P| e b s m          T\P| e i b p S M    
+--------+---          --------+-------    
+ s | 1   1             S | 1 1     1       
+ m | 1 1 1 1           M | 1 1 1 1 1 1    
+``
+
+The overloads of `bool contains(const T& super, const P& sup)` 
+cover various kinds
+of containedness. We can group them into a part (1) that checks
+if an element, a segment or a container /of same kinds/ is contained in
+an element or interval container
+
+``
+// (1) containedness of elements, segments or containers of same kind
+T\P| e b s m          T\P| e i b p S M    
+---+--------          ---+------------    
+ s | 1   1             S | 1 1     1       
+ m |   1   1           M |     1 1   1    
+``
+
+and another part (2) that checks the containedness of 
+/key objects/, which can be /elements/ an /intervals/ or a /sets/.
+
+``
+// (2) containedness of key objects.
+T\P| e b s m          T\P| e i b p S M    
+---+--------          ---+------------    
+ s | 1   1             S | 1 1     1       
+ m | 1   1             M | 1 1     1      
+``
+
+For type *m* = __icl_map__, 
+a key element (*m*`::domain_type`) and an __icl_set__ 
+(*m*`::set_type`) can be a ['*key object*].
+
+For an interval map type *M*, 
+a key element (*M*`::domain_type`), 
+an interval (*M*`::interval_type`) and an 
+['*interval set*], can be ['*key objects*]. 
+
+[#complexities_contains] Complexity characteristics for function
+`bool contains(const T& super, const P& sub)const`
+are given by the next tables where 
+``
+n = iterative_size(super);
+m = iterative_size(sub); //if P is a container type
+``
+
+[table Time Complexity for function contains on element containers
+[[`bool contains(const T& super, const P& sub)`\n
+  `bool   within(const P& sub, const T& super)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_set__][__ch_icl_map__]]
+[[__icl_set__]                          [__Olgn__]    []               [__Omlgn__]     []              ]
+[[__icl_map__]                          [__Olgn__]    [__Olgn__]       [__Omlgn__]     [__Omlgn__]     ]
+]
+
+
+[table Time Complexity for functions contains and within on interval containers
+[[`bool contains(const T& super, const P& sub)`\n
+  `bool   within(const P& sub, const T& super)`][][__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
+[[interval_sets]             [__itv_set__][__Olgn__]    [__Olgn__]    []               []               [__Omlgn__]      []               ]
+[[]     [__sep_itv_set__\n__spl_itv_set__][__Olgn__]    [__On__  ]    []               []               [__Omlgn__]      []               ]
+[[interval_maps]             [__itv_map__][__Olgn__]    [__Olgn__]    [__Olgn__]       [__Olgn__]       [__Omlgn__]      [__Omlgn__]      ]
+[[]                      [__spl_itv_map__][__Olgn__]    [__On__  ]    [__Olgn__]       [__On__]         [__Omlgn__]      [__Omlgn__]      ]
+]
+
+All overloads of containedness of containers in containers
+``
+bool contains(const T& super, const P& sub)
+bool   within(const P& sub, const T& super)
+``
+are of ['*loglinear*] time: __Omlgn__. 
+If both containers have same iterative_sizes so that /m = n/
+we have the worst case ( __Onlgn__ ).
+There is an alternative implementation that has a ['*linear*]
+complexity of __Onpm__. 
+The loglinear implementation has been chosen,
+because it can be faster, if the container argument is
+small. In this case the loglinear implementation approaches
+logarithmic behavior, whereas the linear implementation
+stays linear.
+
+
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]]]]
+[[[link boost_icl.interface ['*Interface*]]                          ]]
+]
+
+[endsect][/ Containedness]
+
+

Added: trunk/libs/icl/doc/functions_ctor_dtor.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_ctor_dtor.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,49 @@
+[/
+    Copyright (c) 2008-2009 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)
+]
+
+
+[/ //= Range ===================================================================]
+[section Range]
+
+[table
+[[['*Range*]]                 [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][condition]   ]
+[[`interval<domain_type> hull(const T&)`] [      ]  [__O1__] [__O1__][]          ]
+[[`domain_type T::lower()const`]          [__O1__]  [__O1__] [__O1__][]          ]
+[[`domain_type T::upper()const`]          [__O1__]  [__O1__] [__O1__][]          ]
+[[`domain_type T::first()const`]          [__O1__]  [__O1__] [__O1__][`!is_continuous<domain_type>::value`]]
+[[`domain_type T::last()const`]           [__O1__]  [__O1__] [__O1__][`!is_continuous<domain_type>::value`]]
+]
+
+The table above shows the availability of functions 
+`hull`, `lower`, `upper`, `first` and `last` on intervals 
+and interval containers that are all of ['*constant time complexity*].
+Find the functions description and some simple properties below.
+
+[table
+[[['*Range*]]                               [Types] [Description]                                        ]
+[[`interval<domain_type> hull(const T&)`] [__S __M] [`hull(x)` returns the smallest interval that contains all intervals of an interval container `x`.] ]
+[[`domain_type T::lower()const`]       [__i __S __M][`x.lower()` returns the lower bound of an interval or interval container `x`.]  ]
+[[`domain_type T::upper()const`]       [__i __S __M][`x.upper()` returns the upper bound of an interval or interval container `x`.]         ]
+[[`domain_type T::first()const`]       [__i __S __M][`x.first()` returns the first element of an interval or interval container `x`. 
+                                                     `T::first()` is defined for a non continuous `domain_type` only.] ]
+[[`domain_type T::last()const`]        [__i __S __M][`x.last()` returns the last element of an interval or interval container `x`. 
+                                                     `T::last()` is defined for a non continuous `domain_type` only.] ]                                                                                                     
+]
+
+``
+// for interval_containers x:
+hull(x).lower() == x.lower()
+hull(x).upper() == x.upper()
+hull(x).first() == x.first()
+hull(x).last()  == x.last()
+``
+
+
+[endsect][/ Range]
+
+

Added: trunk/libs/icl/doc/functions_element_iteration.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_element_iteration.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,93 @@
+[/
+    Copyright (c) 2008-2009 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)
+]
+
+
+[/ //= Element iteration ===================================================================]
+[section Element iteration]
+
+This section refers to ['*element iteration*] over ['*interval containers*].
+Element iterators are available as associated types on interval sets and interval maps.
+
+[table
+[[Variant]      [Associated element iterator type for interval container `T`]]
+[[forward]      [`T::element_iterator`]                                    ]
+[[const forward][`T::element_const_iterator`]                              ]
+[[reverse]      [`T::element_reverse_iterator`]                            ]
+[[const reverse][`T::element_const_reverse_iterator`]                      ]
+]
+
+There are also associated iterators types 
+`T::iterator`, `T::const_iterator`, 
+`T::reverse_iterator` and `T::reverse_const_iterator`
+on interval containers.
+These are ['*segment iterators*]. Segment iterators are 
+"first citizen iterators". [/ NOTE Identical to interface.qbk from here]
+Iteration over segments is fast, compared to an iteration over elements,
+particularly if intervals are large. 
+But if we want to view our interval containers as containers
+of elements that are usable with std::algoritms, we need to
+iterate over elements. 
+
+Iteration over elements . . .
+
+* is possible only for integral or discrete `domain_types`
+* can be very ['*slow*] if the intervals are very large.
+* and is therefore ['*depreciated*]
+
+On the other hand, sometimes iteration over interval containers
+on the element level might be desired, if you have some 
+interface that works for `std::SortedAssociativeContainers` of 
+elements and you need to quickly use it with an interval container.
+Accepting the poorer performance might be less bothersome at times
+than adjusting your whole interface for segment iteration.
+
+[caution So we advice you to choose element iteration over
+interval containers ['*judiciously*]. Do not use element iteration
+['*by default or habitual*]. Always try to achieve results using
+member functions, global functions or operators 
+(preferably inplace versions)
+or iteration over segments first.]
+
+
+[table
+[[['*Synopsis Complexities*]]   [__ch_itv_sets__][__ch_itv_maps__]]
+[[`J T::elements_begin()`]               [__O1__]    [__O1__]     ]
+[[`J T::elements_end()`]                 [__O1__]    [__O1__]     ]
+[[`J T::elements_rbegin()`]              [__O1__]    [__O1__]     ]
+[[`J T::elements_rend()`]                [__O1__]    [__O1__]     ]
+]
+
+[table
+[[['*Element iteration*]]                                      [Description]     ]
+[[``      T::element_iterator T::elements_begin()
+T::element_const_iterator T::elements_begin()const``]          [Returns an element iterator to the first element of the container.]                        ]
+[[``      T::element_iterator T::elements_end()
+T::element_const_iterator T::elements_end()const``]            [Returns an element iterator to a position `elements_end()` after the last element of the container.]]
+[[``      T::element_reverse_iterator T::elements_rbegin()
+T::element_const_reverse_iterator T::elements_rbegin()const``] [Returns a reverse element iterator to the last element of the container.]                  ]
+[[``      T::element_reverse_iterator T::elements_rend()
+T::element_const_reverse_iterator T::elements_rend()const``]   [Returns a reverse element iterator to a position `elements_rend()` before the first element of the container.]]
+]
+
+
+['*See also . . .*]
+[table
+[]
+[[[link boost_icl.function_reference.iterator_related ['*Segment iteration*]]   ]]
+]
+
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]]]]
+[[[link boost_icl.interface ['*Interface*]]                          ]]
+]
+
+[endsect][/ Element iteration]
+
+

Added: trunk/libs/icl/doc/functions_equivs_orderings.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_equivs_orderings.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,154 @@
+[/
+    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)
+]
+
+
+[/ //= Equivalences and Orderings ===================================================]
+[section Equivalences and Orderings]
+
+[section Synopsis][/ Equivalences and Orderings]
+
+[table
+[[['*Equivalences and Orderings*]][__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
+[[['Segment Ordering]]                         [ ]       [ ]      [ ]     [ ]      [ ]   ]
+[[`bool operator == (const T&, const T&)`]     [1]       [1]      [1]     [1]      [1]   ]
+[[`bool operator != (const T&, const T&)`]     [1]       [1]      [1]     [1]      [1]   ]
+[[`bool operator <  (const T&, const T&)`]     [1]       [1]      [1]     [1]      [1]   ]
+[[`bool operator >  (const T&, const T&)`]     [1]       [1]      [1]     [1]      [1]   ]
+[[`bool operator <= (const T&, const T&)`]     [1]       [1]      [1]     [1]      [1]   ]
+[[`bool operator >= (const T&, const T&)`]     [1]       [1]      [1]     [1]      [1]   ]
+[[['Element Ordering]]                         [ ]       [ ]      [ ]     [ ]      [ ]   ]
+[[`bool is_element_equal(const T&, const P&)`] [ ]     [__S]    [__M]     [1]      [1]   ]
+[[`bool is_element_less(const T&, const P&)`]  [ ]     [__S]    [__M]     [1]      [1]   ]
+[[`bool is_element_greater(const T&, const P&)`][ ]    [__S]    [__M]     [1]      [1]   ]
+[[['Distinct Equality]]                        [ ]       [ ]      [ ]     [ ]      [ ]   ]
+[[`bool is_distinct_equal(const T&, const P&)`][ ]       [ ]    [__M]     [ ]      [1]   ]
+]
+
+
+[endsect][/ Synopsis Equivalences and Orderings]
+
+[section Less on Intervals]
+
+[
+[[ ]    [Types][]]
+[[`x < y`]   [__i]   [`x` begins before `y` or, for equal beginnings `x` ends before `y`]]
+]
+
+[endsect][/ Less on Intervals]
+
+[section Lexicographical Ordering][/ Equivalences and Orderings]
+
+All common equality and compare operators are defined for
+all objects of the *icl*. For all *icl* containers
+equality and compare operators implement lexicographical
+equality and lexicographical comparison, that depends on
+the equality of template parameter `Compare`.
+This includes the less ordering on intervals, that can be
+perceived as the sequence of elements between their lower and upper
+bound. This generalized lexicogrphical comparison in intervals
+can also be specified this way:
+
+`x < y := x` begins before `y` or, for equal beginnings `x` ends before `y`
+
+[
+[]
+[[`x < y`]  [`:=`]  [`x` begins before `y` or, for equal beginnings `x` ends before `y`.
+              
+                     The other operators can be deduced in the usual way]]
+[[`x > y`]  [`:=`]  [`y < x`] ] 
+[[`x <= y`] [`:=`]  [`!(y < x)`] ] 
+[[`x >= y`] [`:=`]  [`!(x < y)`] ] 
+[[`x == y`] [`:=`]  [`!(x < y) && !(y < x)` induced equivalence] ] 
+[[`x != y`] [`:=`]  [`!(x == y)`] ] 
+]
+
+
+Equality and compare operators are defined for all *icl*
+objects but there are no overloads between different types.
+
+Containers of different segmentation are different,
+even if their elements are the same:
+``
+split_interval_set<time> w1, w2; //Pseudocode
+w1 = {[Mon       ..       Sun)}; //split_interval_set containing a week
+w2 = {[Mon .. Fri)[Sat .. Sun)}; //Same week split in work and week end parts.
+w1 == w2;                        //false: Different segmentation
+is_element_equal(w1,w2);         //true:  Same elements contained  
+``   
+
+[*Complexity] is ['*linear*] in the `iterative_size` of the shorter
+container to compare.
+
+[endsect][/ Lexicographical Ordering; Equivalences and Orderings]
+
+
+[/ ----------------------------------------------------------------------------]
+
+[section Sequential Element Ordering][/ Equivalences and Orderings]
+
+The ['*Sequential Element Ordering*] abstracts from the way in which
+elements of interval containers are clustered into intervals:
+it's ['*segmentation*].
+
+So these equality and compare operations can be applied within
+interval container types. The admissible type combinations are summarized
+in the next overload table.
+
+``
+// overload tables for
+bool is_element_equal  (const T&, const P&)
+bool is_element_less   (const T&, const P&)
+bool is_element_greater(const T&, const P&)
+
+element containers:     interval containers:  
+T\P| s m                T\P| S1 S2 S3 M1 M3    
+---+----                ---+---------------    
+s  | 1                  S1 | 1  1  1    
+m  |   1                S2 | 1  1  1    
+                        S3 | 1  1  1
+                        M1 |          1  1
+                        M3 |          1  1
+``
+
+For element containers lexicographical equality and
+sequential element equality are identical.
+
+The *complexity* of sequential element comparison functions
+is ['*linear*] in the `iterative_size` of the larger
+container.
+
+[endsect]
+
+[section Distinct Equality]
+
+['*Distinct Equality*] is an equality predicate that is available
+for __icl_maps__ and __itv_maps__. It yields true, if
+two maps are sequential element equal except for value
+pairs whose associated values are identity elements.
+
+[*Complexity] is linear in the `iterative_size` of the
+larger container to compare.
+
+[endsect]
+
+
+['*See also . . .*]
+[table
+[]
+[[[link boost_icl.semantics.orderings_and_equivalences ['*Semantics*]]]]
+]
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]]]]
+[[[link boost_icl.interface ['*Interface*]]                          ]]
+]
+
+[endsect][/ Equivalences and Orderings]
+
+

Added: trunk/libs/icl/doc/functions_erasure.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_erasure.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,163 @@
+[/
+    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)
+]
+
+
+[/ //= Erasure ===================================================================]
+[section Erasure]
+
+[section Synopsis][/ Erasure]
+
+[table
+[[['*Erasure*]]                 [__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]  ]
+[[`T& T::erase(const P&)`]              [__ei ]   [__ei __bp]     [__e]      [__bp]     ]
+[[`T& erase(T&, const P&)`]             [__eiS]  [__eiS __bpM]    [__es]     [__bm]     ]
+[[`void T::erase(iterator)`]               [1]        [1]         [1]        [1]        ]
+[[`void T::erase(iterator,iterator)`]      [1]        [1]         [1]        [1]        ]
+]
+
+[h5 Erasure]
+
+The effects of ['*erasure*] implemented by `erase` and ['*subtraction*]
+implemented by `subtract` and `operator -=` are identical for all Set-types of
+the *icl*.
+
+For Map-types, `erase` provides the *stl* semantics of erasure in
+contrast to `subtract` and `operator -=`, that implement a generalized subtraction,
+that performs inverse aggregations if key values collide or key intervals overlap.
+
+Using iterators it is possible to erase objects or ranges of 
+objects the iterator is pointing at from icl Sets and Maps.
+
+[endsect][/ Synopsis Erasure]
+
+
+[section Erasure of Objects]
+
+
+``
+/* overload table for */       T\P| e i b p 
+T& T::erase(const P&)          ---+--------
+T& erase(T&, const P&)          s | s
+                                m |     m
+                                S | S S     
+                                M |     M M    
+``
+
+The next table contains complexity characteristics for the `erase` function on elements and segments.
+
+[table Time Complexity for erasure of elements and segments on icl containers
+[[`T& T::erase(const P&)`\n
+  `T& erase(T&, const P&)`] [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
+[[__icl_set__]                 [__Olgn__]   []            []           []          ]
+[[__icl_map__]                 [__Olgn__]   []            [__Olgn__]   []          ]
+[[__itv_sets__]                [__Olgn__]   [__a_Olgn__]  []           []          ]
+[[__itv_maps__]                [__Olgn__]   [__On__]      [__Olgn__]   [__On__]    ]
+]
+
+
+As presented in the overload tables for inplace function `erase` below,
+more type combinations are available for /erasure/ than for
+/insertion/. 
+
+``
+// overload tables for function    element containers:     interval containers: 
+T& erase(T&, const P&)             T\P| e b s m            T\P| e i b p S M  
+                                   ---+--------            ---+------------  
+                                    s | s   s               S | S S     S    
+                                    m | m m m m             M | M M M M M M  
+``
+We can split up these overloads in two groups.
+The first group can be called /reverse insertion/.
+``
+/* (1) Reverse insertion */        T\P| e b s m            T\P| e i b p S M  
+                                   ---+--------            ---+------------  
+                                    s | s   s               S | S S     S    
+                                    m |   m   m             M |     M M   M  
+``
+The second group can be viewed as an /erasure by key objects/
+``
+/* (2) Erasure by key objects */   T\P| e b s m            T\P| e i b p S M
+                                   ---+--------            ---+------------
+                                    s | s   s               S | S S     S  
+                                    m | m   m               M | M M     M  
+``
+
+On Maps ['*reverse insertion (1)*] is different from
+*stl's* erase semantics, because value pairs are deleted only,
+if key ['*and*] data values are found. Only 
+['*erasure by key objects (2)*] works like the erase function
+on *stl's* std::maps, that passes a ['*key value*] as argument.
+
+On Sets both function groups fall together
+as ['*set difference*].
+
+
+Complexity characteristics for inplace erasure operations are 
+given by the next tables where 
+``
+n = iterative_size(y);
+m = iterative_size(x); //if P is a container type
+``
+
+[table Time Complexity for inplace erasure on element containers
+[[`T& erase(T& y, const P& x)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_set__][__ch_icl_map__]]
+[[__icl_set__]                    [__Olgn__]    []               [__Omlgn__]     []              ]
+[[__icl_map__]                    [__Olgn__]    [__Olgn__]       [__Omlgn__]     [__Omlgn__]     ]
+]
+
+
+[table Time Complexity for inplace erasure on interval containers
+[[`T& erase(T& y, const P& x)`][__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
+[[interval_sets]                  [__Olgn__]    [__a_Olgn__]  []               []               [__Omlgnpm__]    []               ]
+[[interval_maps]                  [__Olgn__]    [__a_Olgn__]  [__Olgn__]       [__On__]         [__Omlgnpm__]    [__Omlgnpm__]    ]
+]
+
+[endsect][/ Erasure of Objects]
+
+[section Erasure by Iterators]
+
+The next table shows the *icl* containers that erasure with iterators is
+available for. Erase on iterators erases always one `value` of `value_type`
+for an iterator pointing to it.
+So we erase
+
+* elements from __icl_sets__
+* element-value pairs from __icl_maps__
+* intervals from __itv_sets__ and
+* interval-value-pairs from __itv_maps__
+
+[table
+[[['*Erasure by iterators*]]                [__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]  ]
+[[`void T::erase(iterator pos)`]                   [__aO1__]   [__aO1__]    [__aO1__]   [__aO1__]   ]
+[[`void T::erase(iterator first, iterator past)`]  [__Ok__]    [__Ok__]     [__Ok__]    [__Ok__]    ]
+]
+
+Erasing by a single iterator need only ['*amortized constant time*].
+Erasing via a range of iterators `[first, past)` is of ['*linear time*]
+in the number `k` of iterators in range `[first, past)`.
+
+[endsect][/ Erasure by Iterators]
+
+
+['*See also . . .*]
+[table
+[]
+[[[link boost_icl.function_reference.insertion   ['*Insertion*]]      ]]
+[[[link boost_icl.function_reference.subtraction ['*Subtraction*]]    ]]
+]
+
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]] ]]
+[[[link boost_icl.interface ['*Interface*]]             ]]
+]
+
+[endsect][/ Erasure]
+
+

Added: trunk/libs/icl/doc/functions_insertion.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_insertion.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,156 @@
+[/
+    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)
+]
+
+
+[/ //= Insertion ===================================================================]
+[section Insertion]
+
+[section Synopsis][/ Insertion]
+
+[table
+[[['*Insertion*]][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]  ]
+
+[[`V T::insert(const P&)`]                         [__ei]    [__bp]   [__e]    [__b]  ]
+[[`V insert(T&, const P&)`]                        [__ei]    [__bp]   [__e]    [__b]  ]
+[[`V T::insert(J pos, const P&)`]                  [__i]     [__p]    [__e]    [__b]  ]
+[[`V insert(T&, J pos, const P&)`]                 [__i]     [__p]    [__e]    [__b]  ]
+[[`T& insert(T&, const P&)`]                      [__eiS]   [__bpM]   [__es]   [__bm] ]
+[[`T& T::set(const P&)`]                             [ ]     [__bp]   [ ]      [1]    ]
+[[`T& set_at(T&, const P&)`]                         [ ]     [__bp]   [ ]      [1]    ]
+
+]
+
+[h5 Insertion]
+
+The effects of ['*insertion*] implemented by `insert` and ['*addition*]
+implemented by `add` and `operator +=` are identical for all Set-types of
+the *icl*.
+
+For Map-types, `insert` provides the *stl* semantics of insertion in
+contrast to `add` and `operator +=`, that implement a generalized addition,
+that performs aggregations if key values collide or key intervals overlap.
+`insert` on Maps does not alter a maps content at the points, where
+the keys of the object to inserted overlap or collide with keys that
+are already in the map. 
+
+
+[h5 Setting values]
+
+Overwriting values using `operator[]` like in
+``
+my_map[key] = new_value;
+``
+is not provided for __itv_maps__ because an `operator[]` is not 
+implemented for them. As a substitute a function
+`T& T::set(const P&)` can be used to achieve the same effect:
+``
+my_map.set(make_pair(overwrite_this, new_value));
+``
+
+[endsect][/ Synopsis Insertion]
+
+[section Insertion]
+
+``
+// overload table for functions      T\P| e i b p  
+V T::insert(const P&)                ---+--------
+V insert(T&, const P&)                s | s
+                                      m |     m
+                                      S |   S      
+                                      M |       M  
+``
+
+[table Time Complexity for member function insert on icl containers
+[[`T& T::insert(const P&)`]    [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
+[[__icl_set__]                 [__Olgn__] []          []        []          ]
+[[__icl_map__]                 []         []          [__Olgn__][]          ]
+[[__itv_set__\n__sep_itv_set__][__Olgn__] [__a_Olgn__][]        []          ]
+[[__spl_itv_set__]             [__Olgn__] [__On__]    []        []          ]
+[[__itv_map__\n__spl_itv_map__][]         []          [__Olgn__][__On__]    ]
+]
+
+``
+// overload tables for function      element containers:     interval containers:  
+T& insert(T&, const P&)              T\P| e b s m            T\P| e i b p S M 
+                                     ---+--------            ---+------------ 
+                                      s | s   s               S | S S     S   
+                                      m |   m   m             M |     M M   M    
+``
+
+
+[table Time Complexity for inplace insertion on element containers
+[[`T& insert(T& y, const P& x)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
+[[__icl_set__]                  [__Olgn__]    []               [__Om__]         []               ]
+[[__icl_map__]                  []            [__Olgn__]       []               [__Om__]         ]
+]
+
+Time complexity characteristics of inplace insertion for interval containers
+is given by this table.
+
+[table Time Complexity for inplace insertion on interval containers
+[[`T& insert(T& y, const P& x)`][][__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
+[[interval_sets][__itv_set__\n__sep_itv_set__][__Olgn__] [__a_Olgn__][]        []        [__Omlgnpm__]    []               ]
+[[]             [__spl_itv_set__]             [__Olgn__] [__On__]    []        []        [__Omlgnpm__]    []               ]
+[[interval_maps][]                            []         []          [__Olgn__][__On__]  []               [__Omlgnpm__]    ]
+]
+
+
+[h4 Hinted insertion]
+
+Function `T& T::insert(T::iterator prior, const P& addend)` allows
+for an insertion in ['*constant time*], if `addend` can be inserted
+right after iterator `prior` without collision. If this is not possible
+the complexity characteristics are as stated for the non hinted insertion
+above. Hinted insertion is available for these combinations of types:
+``
+// overload table for insertion with hint     T\P| e i b p  
+V T::insert(J pos, const P&)                  ---+--------
+V insert(T&, J pos, const P&)                  s | s
+                                               m |     m
+                                               S |   S     
+                                               M |       M 
+``
+
+[endsect][/ Insertion]
+
+
+
+[section Setting values]
+
+``
+// overload table for member function         T\P| b p 
+T& T::set(const P&)                           ---+---- 
+T& set_at(T&, const P&)                        m | m   
+                                               M |   M 
+``
+
+[table Time Complexity for member function `set`
+[[`T& set(T&, const P&)`] [domain_mapping_type] [interval_mapping_type] ]
+[[icl::map]               [__Olgn__]            [ ]                     ]
+[[interval_maps]          []                    [__a_Olgn__]            ]
+]
+
+[endsect][/ Set]
+
+['*See also . . .*]
+[table
+[]
+[[[link boost_icl.function_reference.addition ['*Erasure*]]          ]]
+[[[link boost_icl.function_reference.addition ['*Addition*]]         ]]
+]
+
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]]]]
+[[[link boost_icl.interface ['*Interface*]]                          ]]
+]
+
+[endsect][/ Insertion]
+
+    

Added: trunk/libs/icl/doc/functions_intersection.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_intersection.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,271 @@
+[/
+    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)
+]
+
+[/ //= Intersection ============================================================]
+[section Intersection][/ Intersection]
+
+[section Synopsis][/ Intersection]
+
+[table
+[[Intersection]                             [__ch_itv_t__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
+
+[[`void add_intersection(T&, const T&, const P&)`][ ]   [__eiS][__eiS __bpM][ ]     [ ]       ]
+[[`T& operator &=(T&, const P&)`]                 [ ]   [__eiS][__eiS __bpM][__es]  [__bm]    ]
+[[`T  operator & (T, const P&)`\n
+  `T  operator & (const P&, T)`]                 [__i]  [__eiS][__eiS __bpM][__es]  [__bm]    ]
+[[`bool intersects(const T&, const P&)`\n
+  `bool disjoint(const T&, const P&)`]           [__i]  [__eiS][__eiS __bpM][__es]  [__bm]    ]
+]
+
+Functions and operators that are related to ['*intersection*] on *icl* objects
+are given in the table above.
+
+
+[table
+[[]      [Description of Intersection]]
+[[`Sets`][Intersection on Sets implements ['*set intersection*]]]
+[[`Maps`][Intersection on Maps implements a ['*map intersection*] function similar to /set intersection/.
+          If, on intersection, an element value pair `(k,v)` it's key `k` is in the map 
+          already, the intersection function is propagated to the associated value,
+          if it exists for the Map's codomain_type. 
+          
+          If the codomain_type has no intersection operation, associated 
+          values are combined using addition. For partial map types this
+          results in an addition on the intersection of the domains of
+          the intersected sets. For total maps intersection and
+          addition are identical in this case.
+                  
+          See also
+          [link boost_icl.semantics.quantifiers__maps_of_numbers.intersection_on_quantifiers ['intersection on Maps of numbers]]. 
+        
+          A Map can be intersected with key types: an element 
+          (an interval for interval_maps) and and a Set. This 
+          results in the selection of a submap, and can be
+          defined as a generalized selection function on Maps.
+         ]]
+]
+
+[endsect][/ Synopsis Intersection]
+
+
+[section Functions][/ Intersection]
+
+The overloaded function 
+
+`void add_intersection(T& result, const T& y, const P& x)`
+
+allows to accumulate the intersection of `y` and `x` in the first argument `result`. 
+`Result` might already contain data. In this case the intersection of `y` and `x` 
+is `added` the the contents of `result`.
+``
+T s1 = f, s2 = f, y = g; P x = h; // The effect of 
+add_intersection(s1, y, x);       // add_intersection 
+s2 += (y & x);                    // and & followed by +=
+assert(s1==s2);                   // is identical
+``
+
+This might be convenient, if intersection is used like a generalized selection function.
+Using element or segment types for `P`, we can select small parts of a container
+`y` and accumulate them in `section`.
+
+The admissible combinations of types for function 
+`void add_intersection(T&, const T&, const P&)` can be summarized in the 
+['*overload table*] below. 
+Compared to other overload tables, placements of function arguments are
+different: Row headers denote type `T` of `*this` object.
+Columns headers denote type `P` of the second function argument.
+The table cells contain the arguments `T` of the intersections
+`result`, which is the functions first argument.
+
+``
+/* overload table for */                                T\P| e i b p 
+void T::add_intersection(T& result, const P&)const      ---+--------
+                                                         s | s
+                                                         m | m   m
+                                                         S | S S     
+                                                         M | M M M M 
+``
+
+The next table contains complexity characteristics for function `add_intersection`.
+
+[table Time Complexity for function add_intersection on icl containers
+[[`void add_intersection(T&, const T&, const P&)const`] [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
+[[__icl_set__]                                   [__Olgn__]    []            []           []          ]
+[[__icl_map__]                                   [__Olgn__]    []            [__Olgn__]   []          ]
+[[__itv_sets__]                                  [__Olgn__]    [__On__]      []           []          ]
+[[__itv_maps__]                                  [__Olgn__]    [__On__]      [__On__]     [__On__]    ]
+]
+
+[endsect][/ Function Intersection]
+
+
+[section Inplace operators][/ Intersection]
+
+The overload tables below are giving admissible
+type combinations for the intersection `operator &=`.
+As for the overload patterns of /subtraction/
+intersections are possible within Sets and Maps
+but also for Maps combined with /key objects/
+which are /key elements, intervals/ and /Sets of keys/.
+
+``
+// overload tables for             element containers:     interval containers:
+T& operator &= (T&, const P&)      &= | e b s m            &= | e i b p S M    
+                                   ---+--------            ---+------------    
+                                   s  | s   s              S  | S S     S      
+                                   m  | m m m m            M  | M M M M M M    
+``
+
+While intersection on maps can be viewed as
+a ['*generalisation of set intersection*]. The
+combination on Maps and Sets can be interpreted as
+a ['*generalized selection function*], because it
+allows to select parts of a maps using
+/key/ or /selection objects/.
+So we have a ['*generalized intersection*] for
+these overloads,
+
+``
+/* (Generalized) intersection */   &= | e b s m            &= | e i b p S M  
+                                   ---+--------            ---+------------  
+                                   s  | s   s              S  | S S     S    
+                                   m  |   m   m            M  |     M M   M  
+``
+
+[*and] a ['*selection by key objects*] here:
+
+``
+/* Selection by key objects */     &= | e b s m            &= | e i b p S M 
+                                   ---+--------            ---+------------ 
+                                   s  | s   s              S  | S S     S   
+                                   m  | m   m              M  | M M     M   
+``
+
+The differences for the different functionalities
+of `operator &=` are on the Map-row of the
+tables. Both functionalities fall together
+for Sets in the function ['*set intersection*].
+
+Complexity characteristics for inplace intersection operations are 
+given by the next tables where 
+``
+n = iterative_size(y);
+m = iterative_size(x); //if P is a container type
+``
+
+[table Time Complexity for inplace intersection on element containers
+[[`T& operator &= (T& y, const P& x)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_set__][__ch_icl_map__]]
+[[__icl_set__]                    [__Olgn__]    []               [__Omlgn__]     []              ]
+[[__icl_map__]                    [__Olgn__]    [__Olgn__]       [__Omlgn__]     [__Omlgn__]     ]
+]
+
+[table Time Complexity for inplace intersection on interval containers
+[[`T& operator &= (T& y, const P& x)`][__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
+[[interval_sets]                  [__Olgn__]    [__On__]      []               []               [__Omlgnpm__]    []               ]
+[[interval_maps]                  [__Olgn__]    [__On__]      [__Olgn__]       [__On__]         [__Omlgnpm__]    [__Omlgnpm__]    ]
+]
+
+[endsect][/ Inplace operators Intersection]
+
+[section Infix operators][/ Intersection]
+
+For the *icl's* infix intersection the
+following overloads are available:
+
+``
+// overload tables for             element containers:     interval containers:
+T operator & (T, const P&)         &  | e b s m            &  | e  i  b  p  S1 S2 S3 M1 M3
+T operator & (const P&, T)         ---+--------            ---+---------------------------
+                                   e  |     s m            e  |             S1 S2 S3 M1 M3
+                                   b  |       m            i  |    i        S1 S2 S3 M1 M3
+                                   s  | s   s m            b  |                      M1 M3
+                                   m  | m m m m            p  |                      M1 M3
+                                                           S1 | S1 S1       S1 S2 S3 M1 M3
+                                                           S2 | S2 S2       S2 S2 S3 M1 M3
+                                                           S3 | S3 S3       S3 S3 S3 M1 M3
+                                                           M1 | M1 M1 M1 M1 M1 M1 M1 M1 M3
+                                                           M3 | M3 M3 M3 M3 M3 M3 M3 M3 M3
+``
+
+To resolve ambiguities among interval containers
+the ['*finer*] container type is chosen as result type.
+
+Again, we can split up the overload tables of
+`operator &` in a part describing
+the ['*generalized intersection] on interval containers
+and a second part defining the
+['*selection by key object] functionality.
+
+``
+/* (Generalized) intersection */   &  | e b s m            &  | e  i  b  p  S1 S2 S3 M1 M3
+                                   ---+--------            ---+---------------------------
+                                   e  |     s              e  |             S1 S2 S3      
+                                   b  |       m            i  |    i        S1 S2 S3      
+                                   s  | s   s              b  |                      M1 M3
+                                   m  |   m   m            p  |                      M1 M3
+                                                           S1 | S1 S1       S1 S2 S3      
+                                                           S2 | S2 S2       S2 S2 S3      
+                                                           S3 | S3 S3       S3 S3 S3      
+                                                           M1 |       M1 M1          M1 M3
+                                                           M3 |       M3 M3          M3 M3
+``
+
+``
+/* Selection by key objects */     &  | e b s m            &  | e  i  b  p  S1 S2 S3 M1 M3
+                                   ---+--------            ---+---------------------------
+                                   e  |     s m            e  |             S1 S2 S3 M1 M3
+                                   b  |                    i  |    i        S1 S2 S3 M1 M3
+                                   s  | s   s m            b  |                           
+                                   m  | m   m              p  |                           
+                                                           S1 | S1 S1       S1 S2 S3 M1 M3
+                                                           S2 | S2 S2       S2 S2 S3 M1 M3
+                                                           S3 | S3 S3       S3 S3 S3 M1 M3
+                                                           M1 | M1 M1       M1 M1 M1      
+                                                           M3 | M3 M3       M3 M3 M3      
+``
+
+[endsect][/ Inplace operator Intersection]
+
+[section Intersection tester]
+
+[table
+[[Tester]                                          [Desctription]]
+[[`bool intersects(const T& left, const P& right)`][Tests, if `left` and `right` intersect.]]
+[[`bool disjoint(const T& left, const P& right)`]  [Tests, if `left` and `right` are disjoint.]]
+[[]                                                [`intersects(x,y) == !disjoint(x,y)`]]
+]
+
+``
+bool intersects(const T&, const P&)      T\P| e b s m      T\P| e i b p S M 
+bool   disjoint(const T&, const P&)      ---+--------      ---+------------
+                                          s | 1   1         S | 1 1     1  
+                                          m | 1 1 1 1       M | 1 1 1 1 1 1
+``
+
+[endsect][/ Intersection tester]
+
+
+['*See also . . .*]
+[table
+[]
+[[[link boost_icl.function_reference.symmetric_difference ['*Symmetric difference*]] ]]
+[[[link boost_icl.function_reference.subtraction  ['*Subtraction*]]  ]]
+[[[link boost_icl.function_reference.addition     ['*Addition*]]     ]]
+]
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]]    ]]
+[[[link boost_icl.interface ['*Interface*]]                ]]
+]
+
+
+[endsect][/ Intersection]
+
+
+

Added: trunk/libs/icl/doc/functions_interval_construct.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_interval_construct.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,124 @@
+[/
+    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)
+]
+
+
+[/ //= Interval Construction ===================================================================]
+[section Interval Construction]
+
+[table
+[[T]                                       [__ch_dsc_itv__] [__ch_cnt_itv__] [__ch_ro_itv__] [__ch_lo_itv__]  [__ch_cl_itv__] [__ch_op_itv__]      ]
+[[Interval bounds]                                     [dynamic]  [dynamic]    [static]     [static]     [static]    [static]    ]
+[[Form]                                                [ ]        [ ]          [asymmetric] [asymmetric] [symmetric] [symmetric] ]
+[[['*Construct*]]                                      [ ]        [ ]          [ ]          [ ]          [ ]         [ ]         ]
+[[`T singleton(const P&)`]                             [__d]      [__c]        [__d]        [__d]        [__d]       [__d]       ]
+[[`T construct(const P&, const P&)`]                   [__d]      [__c]        [__dc]       [__dc]       [__d]       [__d]       ]
+[[``
+T construct(const P&, const P&, 
+            interval_bounds   )
+``]                                                    [__d]      [__c]        [ ]          [ ]          [ ]         [ ]         ]
+[[`T hull(const P&, const P&)`]                        [__d]      [__c]        [__dc]       [__dc]       [__d]       [__d]       ]
+[[`T span(const P&, const P&)`]                        [__d]      [__c]        [__dc]       [__dc]       [__d]       [__d]       ]
+[[`static T right_open(const P&, const P&)`]           [__d]      [__c]        [ ]          [ ]          [ ]         [ ]         ]
+[[`static T left_open(const P&, const P&)`]            [__d]      [__c]        [ ]          [ ]          [ ]         [ ]         ]
+[[`static T closed(const P&, const P&)`]               [__d]      [__c]        [ ]          [ ]          [ ]         [ ]         ]
+[[`static T open(const P&, const P&)`]                 [__d]      [__c]        [ ]          [ ]          [ ]         [ ]         ]
+]
+
+The table above shows the availability of functions, that allow the construction
+of intervals. All interval constructin functins are of ['*constant time and space complexity*].
+
+[table
+[[['*Construct*]]                                      [Description]         ]
+[[`T singleton(const P& value)`]                       [Constructs an interval that contains exactly one element `value`. 
+                                                        For all interval types of the icl sigletons can be constructed
+                                                        for /discrete/ domain types. For continuous domain types, only
+                                                        __ct_itv__ is capable to construct a singleton. ]       ]
+[[`T construct(const P& lower, const P& upper)`]       [Contructs an interval with lower bound `lower` and upper bound `upper` ] ]
+[[``
+T construct(const P& lower, const P& upper,
+            interval_bounds bounds 
+            = interval_bounds::right_open())
+``]  
+                                                       [For dynamically bounded intervals this function constructs an
+                                                        interval with interval bounds specified by the third parameter. ]     ]
+[[`T hull(const P& x1, const P& x2)`]                  [`hull(x1,x2)` constructs the smallest interval that contains both `x1` and `x2`.
+                                                        `x2` may be smaller than `x1`. ]       ]
+[[`T span(const P& x1, const P& x2)`]                  [`span(x1,x2)` constructs the interval `construct(min(x1,x2), max(x1,x2))`.
+                                                        Note the differences between `span`, `hull` and `construct`:
+``
+span<right_open_interval<int> >(2,1)      == [1,2) // does NOT contain 2
+hull<right_open_interval<int> >(2,1)      == [1,3) // contains 2
+construct<right_open_interval<int> >(2,1) == [)    // is empty
+``                                                                   
+                                                                   ]   ]
+[[``
+static T right_open(const P&, const P&)
+static T left_open(const P&, const P&)
+static T closed(const P&, const P&)
+static T open(const P&, const P&)
+``                                       ]             [For dynamically bounded intervals there are for static functions to
+                                                        construct intervals with the four interval bound types:
+``
+discrete_interval<int>      itv1 = discrete_interval<int>::closed(0,42);
+continuous_interval<double> itv2 = continuous_interval<double>::right_open(0.0, 1.0);
+``
+                                                               ]         ]
+[[['*Using the interval default*]]                     [ ]]                                                        
+[[`interval<P>::type`]                                 [There is a library default, for all interval containers of the *icl*.
+                                                        The intension of the library default is to minimize the need for parameter
+                                                        specification, when working with *icl* class templates.
+                                                        We can get the library default interval type as `interval<P>::type`. 
+                                                        The library default uses ['*dynamically bounded intervals*]. You
+                                                        can switch to ['*statically bounded intervals*] by 
+                                                        `#define BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS` prior to icl includes. ]]
+[[``
+static T right_open(const P&, const P&)
+static T left_open(const P&, const P&)
+static T closed(const P&, const P&)
+static T open(const P&, const P&)
+``                                     ]               [For template struct `interval` that always uses the library default
+                                                        the static functions for the four interval bound types are also available. 
+``
+interval<int>::type    itv1 = interval<int>::closed(0,42);
+interval<double>::type itv2 = interval<double>::right_open(0.0, 1.0);
+``
+                                                        This works with the statically bounded intervals as well, 
+                                                        with the restriction that for continuous domain types the 
+                                                        matching function has to be used:
+``
+#define BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS
+. . .
+// library default is the statically bounded right_open_interval
+interval<int>::type    itv1 = interval<int>::closed(0,42); //==[0,43) //ok, bounds are shifted
+interval<double>::type itv2 = interval<double>::right_open(0.0, 1.0); //ok. right_open matches
+interval<double>::type itv3 = interval<double>::closed(0.0, 1.0);     //will NOT compile
+``
+                                                        See also examples 
+                                                        [link boost_icl.examples.dynamic_interval Dynamic intervals] and
+                                                        [link boost_icl.examples.static_interval Static intervals]   
+                                                        ]]
+] 
+
+['*See also . . .*]
+[table
+[]
+[[[link boost_icl.examples.dynamic_interval ['*Example: Dynamically bounded intervals and the library default*]] ]]
+[[[link boost_icl.examples.static_interval  ['*Example: Statically bounded intervals, changing the library default*]] ]]
+]
+
+['*Back to section . . .*]
+[table
+[]
+[[[link additional_interval_functions ['*Additional interval functions*]] ]]
+[[[link function_synopsis_table ['*Function Synopsis*]]          ]]
+[[[link boost_icl.interface ['*Interface*]]                      ]]
+]
+
+[endsect][/ Interval Construction]
+
+

Added: trunk/libs/icl/doc/functions_interval_misc.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_interval_misc.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,48 @@
+[/
+    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)
+]
+
+
+[/ //= Miscellaneous Interval Functions ===================================================================]
+[section Miscellaneous Interval Functions]
+
+
+[table
+[[T]                                       [__ch_dsc_itv__] [__ch_cnt_itv__] [__ch_ro_itv__] [__ch_lo_itv__]  [__ch_cl_itv__] [__ch_op_itv__]      ]
+[[Interval bounds]                                     [dynamic]  [dynamic]    [static]     [static]     [static]    [static]    ]
+[[Form]                                                [ ]        [ ]          [asymmetric] [asymmetric] [symmetric] [symmetric] ]
+
+[[['*Miscellaneous*]]                                  [ ]        [ ]          [ ]          [ ]          [ ]         [ ]         ]
+[[`bool touches(const T&, const T&)`]                  [1]        [1]          [1]          [1]          [1]         [1]         ]
+[[`T inner_complement(const T&, const T&)`]            [1]        [1]          [1]          [1]          [1]         [1]         ]
+[[`difference_type distance(const T&, const T&)`]      [1]        [1]          [1]          [1]          [1]         [1]         ]
+
+]
+
+
+[table
+
+[[['*Miscellaneous Interval Functions*]]               [Description]         ]
+[[`bool touches(const T&, const T&)`]                  [`touches(x,y)` Between the disjoint intervals `x` and `y` are no elements. ] ]
+[[`T inner_complement(const T&, const T&)`]            [`z = inner_complement(x,y)` `z` is the interval between `x` and `y`] ]
+[[`difference_type distance(const T&, const T&)`]      [`d = distance(x,y)` If the domain type of the interval has a difference_type, 
+                                                         `d` is the distance between `x` and `y`.]         ]
+
+]
+
+
+['*Back to section . . .*]
+[table
+[]
+[[[link additional_interval_functions ['*Additional interval functions*]] ]]
+[[[link function_synopsis_table ['*Function Synopsis*]]          ]]
+[[[link boost_icl.interface ['*Interface*]]                      ]]
+]
+
+[endsect][/ Miscellaneous Interval Functions]
+
+

Added: trunk/libs/icl/doc/functions_interval_orderings.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_interval_orderings.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,90 @@
+[/
+    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)
+]
+
+
+[/ //= Additional Interval Orderings ===================================================================]
+[section Additional Interval Orderings]
+
+In addition to the standard orderings `operator <` and rleated `> <= >=` that you will find in the 
+[link function_synopsis_table ['*librarie's function synopsis*]], intervals
+implement some additional orderings that can be useful.
+
+[table
+[[T]                                       [__ch_dsc_itv__] [__ch_cnt_itv__] [__ch_ro_itv__] [__ch_lo_itv__]  [__ch_cl_itv__] [__ch_op_itv__]      ]
+[[Interval bounds]                                     [dynamic]  [dynamic]    [static]     [static]     [static]    [static]    ]
+[[Form]                                                [ ]        [ ]          [asymmetric] [asymmetric] [symmetric] [symmetric] ]
+[[['*Orderings*]]                                      [ ]        [ ]          [ ]          [ ]          [ ]         [ ]         ]
+[[`bool exclusive_less(const T&, const T&)`]           [1]        [1]          [1]          [1]          [1]         [1]         ]
+[[``
+bool lower_less(const T&, const T&)
+bool lower_equal(const T&, const T&)
+bool lower_less_equal(const T&, const T&)
+``]                                                    [1]        [1]          [1]          [1]          [1]         [1]         ]
+[[``
+bool upper_less(const T&, const T&)
+bool upper_equal(const T&, const T&)
+bool upper_less_equal(const T&, const T&)
+``]                                                 
+                                                       [1]        [1]          [1]          [1]          [1]         [1]         ]
+]
+
+A central role for the *icl* plays the 
+`exclusive_less` ordering, which is used 
+in all interval containers.
+The other orderings can be useful to simplify
+comparison of intervals specifically for 
+dynamically bounded ones.
+
+[table
+[[['*Orderings*]]                                      [Description]         ]
+[[`bool exclusive_less(const T&, const T&)`]           [`exclusive_less(x1, x2)` is true if every element of interval `x1` is less than
+                                                         every element of interval `x2` w.r.t. the the intervals `Compare` ordering ]     ]
+[[``
+bool lower_less(const T&, const T&)
+bool lower_equal(const T&, const T&)
+bool lower_less_equal(const T&, const T&)
+``]                                                    [Compares the beginnings of intervals.
+``
+lower_less(x,y)  == true; // x begins before y
+lower_equal(x,y) == true; // x and y begin at the same element
+lower_less_equal(x,y) == lower_less(x,y) || lower_equal(x,y);
+``
+                                                       ]         ]
+[[``
+bool upper_less(const T&, const T&)
+bool upper_equal(const T&, const T&)
+bool upper_less_equal(const T&, const T&)
+``]                                                 
+                                                       [Compares the endings of intervals.
+``
+upper_less(x,y)  == true; // x ends before y
+upper_equal(x,y) == true; // x and y end at the same element
+upper_less_equal(x,y) == upper_less(x,y) || upper_equal(x,y);
+``                                                                                          
+                                                       ]         ]
+]
+
+
+['*See also . . .*]
+[table
+[]
+[[ __biLEquivsOrderings__ ]]
+]
+
+
+['*Back to section . . .*]
+[table
+[]
+[[[link additional_interval_functions ['*Additional interval functions*]] ]]
+[[[link function_synopsis_table ['*Function Synopsis*]]          ]]
+[[[link boost_icl.interface ['*Interface*]]                      ]]
+]
+
+[endsect][/ Additional Interval Orderings]
+
+

Added: trunk/libs/icl/doc/functions_iterator_related.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_iterator_related.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,76 @@
+[/
+    Copyright (c) 2008-2009 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)
+]
+
+
+[/ //= Iterator related ===================================================================]
+[section Iterator related]
+
+
+[table
+[[['*Synopsis Complexities*]]                [__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]   ]
+[[`J T::begin()`]                                  [__O1__]    [__O1__]   [__O1__]    [__O1__]   ]
+[[`J T::end()`]                                    [__O1__]    [__O1__]   [__O1__]    [__O1__]   ]
+[[`J T::rbegin()`]                                 [__O1__]    [__O1__]   [__O1__]    [__O1__]   ]
+[[`J T::rend()`]                                   [__O1__]    [__O1__]   [__O1__]    [__O1__]   ]
+[[`J T::lower_bound(const key_type&)`]            [__Olgn__]  [__Olgn__] [__Olgn__]  [__Olgn__] ]
+[[`J T::upper_bound(const key_type&)`]            [__Olgn__]  [__Olgn__] [__Olgn__]  [__Olgn__] ]
+[[`pair<J,J> T::equal_range(const key_type&)`]    [__Olgn__]  [__Olgn__] [__Olgn__]  [__Olgn__] ]
+]
+
+[table
+[[['*Iterator related*]]                                                                                    []     ]
+[[``      iterator T::begin()
+const_iterator T::begin()const``]                          [Returns an iterator to the first value of the container.]                        ]
+[[``      iterator T::end()
+const_iterator T::end()const``]                            [Returns an iterator to a position `end()` after the last value of the container.]]
+[[``      reverse_iterator T::rbegin()
+const_reverse_iterator T::rbegin()const``]                 [Returns a reverse iterator to the last value of the container.]                  ]
+[[``      reverse_iterator T::rend()
+const_reverse_iterator T::rend()const``]                   [Returns a reverse iterator to a position `rend()` before the first value of the container.]]
+[[``      iterator T::lower_bound(const key_type& k)
+const_iterator T::lower_bound(const key_type& key)const``][Returns an iterator that points to the first element `first`, that does not compare less than `key_type key`.
+                                                            `first` can be equal or greater than `key`, or it may overlap `key` for interval containers.]]
+[[``      iterator T::upper_bound(const key_type&)
+const_iterator T::upper_bound(const key_type&)const``]    [Returns an iterator that points to the first element `past`, that compares greater than `key_type key`.]]
+[[``
+            pair<iterator,iterator> T::equal_range(const key_type& key)
+pair<const_iterator,const_iterator> T::equal_range(const key_type& key)const
+``
+]                                                                                                           
+    [Returns a range `[first, past)` of iterators to all elements of the container
+     that compare neither less than nor greater than `key_type key`.
+     For element containers __icl_set__ and __icl_map__, `equal_range` 
+     contains at most one iterator pointing the element equal to `key`,
+     if it exists.
+     
+     For interval containers `equal_range` contains iterators to all
+     intervals that overlap interval `key`.
+    ]]
+]
+
+[/
+Functions `begin`, `end`, `rbegin`, `rend` need ['*constant time*].
+Complexity of `lower_bound`, `upper_bound` and `equal_range` are 
+['*logarithmic*] in the `iterative_size` of the container. 
+]
+
+['*See also . . .*]
+[table
+[]
+[[[link boost_icl.function_reference.element_iteration ['*Element iteration*]] ]]
+]
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]]    ]]
+[[[link boost_icl.interface ['*Interface*]]                ]]
+]
+
+[endsect][/ Iterator related]
+
+

Added: trunk/libs/icl/doc/functions_range.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_range.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,57 @@
+[/
+    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)
+]
+
+
+[/ //= Range ===================================================================]
+[section Range]
+
+[table
+[[['*Range*]]                 [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][condition]   ]
+[[`interval_type hull(const T&)`]         [      ]  [__O1__] [__O1__][]          ]
+[[`T hull(const T&, const T&)`]           [__O1__]  [      ] [      ][]          ]
+[[`domain_type lower(const T&)`]          [__O1__]  [__O1__] [__O1__][]          ]
+[[`domain_type upper(const T&)`]          [__O1__]  [__O1__] [__O1__][]          ]
+[[`domain_type first(const T&)`]          [__O1__]  [__O1__] [__O1__][`is_discrete<domain_type>::value`]]
+[[`domain_type last(const T&)`]           [__O1__]  [__O1__] [__O1__][`is_discrete<domain_type>::value`]]
+]
+
+The table above shows the availability of functions 
+`hull`, `lower`, `upper`, `first` and `last` on intervals 
+and interval containers that are all of ['*constant time complexity*].
+Find the functions description and some simple properties below.
+
+[table
+[[['*Range*]]                               [Types] [Description]                                        ]
+[[`interval_type hull(const T&)`]      [__S __M] [`hull(x)` returns the smallest interval that contains all intervals of an interval container `x`.] ]
+[[`T hull(const T&, const T&)`]        [__S __M] [`hull(i,j)` returns the smallest interval that contains intervals `i` abd 'j'.] ]
+[[`domain_type lower(const T&)`]       [__i __S __M][`lower(x)` returns the lower bound of an interval or interval container `x`.]  ]
+[[`domain_type upper(const T&)`]       [__i __S __M][`upper(x)` returns the upper bound of an interval or interval container `x`.]         ]
+[[`domain_type first(const T&)`]       [__i __S __M][`first(x)` returns the first element of an interval or interval container `x`. 
+                                                     `first(const T&)` is defined for a discrete `domain_type` only.] ]
+[[`domain_type last(const T&)`]        [__i __S __M][`last(x)` returns the last element of an interval or interval container `x`. 
+                                                     `last(const T&)` is defined for a discrete `domain_type` only.] ]                                                                                                     
+]
+
+``
+// for interval_containers x:
+lower(hull(x)) == lower(x)
+upper(hull(x)) == upper(x)
+first(hull(x)) == first(x)
+last(hull(x))  == last(x)
+``
+
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]]    ]]
+[[[link boost_icl.interface ['*Interface*]]                ]]
+]
+
+[endsect][/ Range]
+
+

Added: trunk/libs/icl/doc/functions_selection.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_selection.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,53 @@
+[/
+    Copyright (c) 2008-2009 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)
+]
+
+
+[/ //= Selection ===================================================================]
+[section Selection]
+
+[table
+[[['*Selection*]]                          [__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]     [condition]            ]
+[[`const_iterator T::find(const domain_type&)const`]     [__Olgn__] [__Olgn__] [__Olgn__]  [__Olgn__] []                     ]
+[[`iterator T::find(const domain_type&)`]                [ ]        [ ]        [__Olgn__]  [__Olgn__] []                     ]
+[[`codomain_type& operator[] (const domain_type&)`]      [ ]        [ ]        [ ]         [__Olgn__] []                     ]
+[[`codomain_type operator() (const domain_type&)const`]  [ ]        [__Olgn__] [ ]         [__Olgn__] [`is_total<T>::value`] ]
+]
+
+* All time *complexities* are ['*logarithmic*] in the containers `iterative_size()`.
+* `operator()` is available for total maps only.
+
+
+[table
+[[['*Selection*]]                                        [Types]     [Description]                                        ]
+[[`iterator T::find(const domain_type& x)`]              [__s __m]   [Searches the container for the element `x` and return an iterator to it, if `x` is found. 
+                                                                      Otherwise `find` returns iterator `end()`.] ]
+[[`const_iterator T::find(const domain_type& x)const`]   [__s __m]   [Const version of `find` above.] ]
+[[`const_iterator T::find(const domain_type& x)const`]   [__S __M]   [For interval containers `find(x)` searches a key element `x` but returns an iterator to an interval
+                                                                      containing the element.] ]
+[[`codomain_type& operator[] (const domain_type& x)`]    [__m ]      [For the key element `x` the operator returns a reference to the mapped value.
+                                                                      A pair `std::pair(x,codomain_type())` will be inserted, of `x` is not found in the map.] ]
+[[`codomain_type operator() (const domain_type& x)const`][__M __m ]  [Returns the mapped value for a key `x`. The operator is only available for ['*total*] maps. ] ]
+]
+
+
+
+['*See also . . .*]
+[table
+[]
+[[[link boost_icl.function_reference.intersection ['*Intersection*]] ]]
+]
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]]    ]]
+[[[link boost_icl.interface ['*Interface*]]                ]]
+]
+
+[endsect][/ Selection]
+
+

Added: trunk/libs/icl/doc/functions_size.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_size.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,56 @@
+[/
+    Copyright (c) 2008-2009 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)
+]
+
+
+[/ //= Size ===================================================================]
+[section Size]
+
+[table
+[[['*Size*]]                    [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
+[[`size_type T::size()const`\n
+  `size_type size(const T&)`]               [__O1__]  [__On__] [__On__] [__O1__] [__O1__]   ]
+[[`size_type cardinality(const T&)`]        [__O1__]  [__On__] [__On__] [__O1__] [__O1__]   ]
+[[`difference_type length(const T&)`]       [__O1__]  [__On__] [__On__]   [ ]      [ ]      ]
+[[`size_type iterative_size(const T&)`]        [ ]    [__O1__] [__O1__] [__O1__] [__O1__]   ]
+[[`size_type interval_count(const T&)`]        [ ]    [__O1__] [__O1__]   [ ]      [ ]      ]
+]
+
+For *icl* containers the single `size` function known from std containers
+branches into tree to five different members functions.
+The table above shows the types, `size` functions are implemented for,
+together with their *complexities*. Linear complexities __On__ refer to the container's
+`iterative_size`: 
+``
+n = y.iterative_size()
+``
+
+The next table gives a short definition for the different size functions.
+
+[table
+[[['*Size*]]                                      [Types] [Description]                                        ]
+[[`size_type interval_count(const T&)`]            [__S __M] [The number of intervals of an interval container.]                         ]
+[[`size_type iterative_size(const T&)`]    [__S __M __s __m] [The number of objects in an icl container that can be iterated over.]      ]
+[[`difference_type length(const T&)`]       [__i __S __M] [The length of an interval or the sum of lengths of
+                                                          an interval container's intervals, that's `domain_type` has a `difference_type`.]     ]
+[[`size_type cardinality(const T&)`][__i __S __M __s __m] [The number of elements of an interval or a container.
+                                                           For continuous data types cardinality can be /infinite/.]                ]
+[[`size_type T::size()const`\n
+  `size_type size(const T&)`]       [__i __S __M __s __m] [The number of elements of an interval or a container,
+                                                           which is also it's `cardinality`.]                                        ]
+]
+
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]] ] ]
+[[[link boost_icl.interface ['*Interface*]]             ] ]
+]
+
+[endsect][/ Size]
+
+

Added: trunk/libs/icl/doc/functions_streaming.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_streaming.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,36 @@
+[/
+    Copyright (c) 2008-2009 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)
+]
+
+
+[/ //= Streaming, conversion ===================================================================]
+[section Streaming, conversion]
+
+[table
+[[['*Streaming, conversion*]]             [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]  ]
+[[`std::basic_ostream operator << (basic_ostream&, const T&)`]      [1]       [1]      [1]     [1]      [1]      ]
+[[`std::string T::as_string()`]                [1]       [1]      [1]     [1]      [1]      ]
+]
+
+[table
+[[['*Streaming, conversion*]]                         [Description]  ]
+[[`std::basic_ostream operator << (basic_ostream&, const T&)`] 
+                                [Serializes the argument of type T to an output stream]   ]
+[[`std::string T::as_string()`] [Returns a string representation of the object of type `T`]]
+]
+
+
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]]]]
+[[[link boost_icl.interface ['*Interface*]]                          ]]
+]
+
+[endsect][/ Streaming, conversion]
+
+

Added: trunk/libs/icl/doc/functions_subtraction.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_subtraction.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,202 @@
+[/
+    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)
+]
+
+
+[/ //= Subtraction ============================================================]
+[section Subtraction]
+
+[section Synopsis]
+
+[table
+[[Subtraction]                        [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
+[[`T& T::subtract(const P&)`]                     [ ]     [__ei]    [__bp]   [ ]     [__b]  ]
+[[`T& subtract(T&, const P&)`]                    [ ]     [__ei]    [__bp]   [__e]   [__b]  ]
+
+[[`T& operator -=(T&, const P&)`]                 [ ]    [__eiS][__eiS __bpM][__es]  [__bm] ]
+[[`T  operator - (T, const P&)`]                  [ ]    [__eiS][__eiS __bpM][__es]  [__bm] ]
+
+[[`T left_subtract(T, const T&)`]                 [1]       [ ]      [ ]     [ ]      [ ]   ]
+[[`T right_subtract(T, const T&)`]                [1]       [ ]      [ ]     [ ]      [ ]   ]
+]
+
+Functions and operators that implement ['*Subtraction*] on *icl* objects
+are given in the table above.
+
+[table
+[[]      [Description of Subtraction]]
+[[`Sets`][Subtraction on Sets implements ['*set difference*]]]
+[[`Maps`][Subtraction on Maps implements a ['*map difference*] function similar to /set difference/.
+          If, on subtraction of an element value pair `(k,v)` it's key `k` is in the map 
+          already, the subtraction function is propagated to the associated value.
+          On the associated value an aggregation is performed, that reverses 
+          the effect of the corresponding addition function.
+        
+          Find more on 
+          [link boost_icl.concepts.addability__subtractability_and_aggregate_on_overlap ['subtractability of maps]]
+          and related 
+          [link boost_icl.semantics.maps ['semantic issues]] 
+          following the links. 
+        
+         ]]
+]
+
+[endsect][/ Synopsis]
+
+
+
+[section Functions][/ Subtraction]
+
+The admissible combinations of types for subtraction functions 
+can be summarized in the 
+['*overload table*] below:
+
+``
+// overload table for              T\P| e i b p  
+T& T::subtract(const P&)           ---+--------
+T& subtract(T&, const P&)           s | s
+                                    m |     m
+                                    S | S S      
+                                    M |     M M  
+``
+
+The next table contains complexity characteristics for `subtract`.
+
+[table Time Complexity for function subtract on icl containers
+[[`T& T::subtract(const P&)`\n
+  `T& subtract(T&, const P&)`] [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
+[[__icl_set__]                 [__Olgn__]   []            []           []          ]
+[[__icl_map__]                 [__Olgn__]   []            [__Olgn__]   []          ]
+[[__itv_sets__]                [__Olgn__]   [__a_Olgn__]  []           []          ]
+[[__itv_maps__]                [__Olgn__]   [__On__]      [__Olgn__]   [__On__]    ]
+]
+
+[endsect][/ Member function Subtraction]
+
+
+[section Inplace operators][/ Subtraction]
+
+As presented in the overload tables for `operator -=`
+more type combinations are provided for subtraction than for
+addition. 
+
+``
+// overload tables for             element containers:     interval containers:  
+T& operator -= (T&, const P&)      -= | e b s m            -= | e i b p S M    
+                                   ---+--------            ---+------------    
+                                   s  | s   s              S  | S S     S       
+                                   m  | m m m m            M  | M M M M M M    
+``
+
+Subtraction provides the /reverse/ operation
+of an addition for these overloads,
+
+``
+// Reverse addition                -= | e b s m            -= | e i b p S M 
+                                   ---+--------            ---+------------ 
+                                   s  | s   s              S  | S S     S   
+                                   m  |   m   m            M  |     M M   M 
+``
+
+[*and] you can erase parts of __icl_maps__ or __itv_maps__ 
+using
+/key values/, /intervals/ or /element or interval sets/
+using these overloads:
+
+``
+// Erasure by key objects          -= | e b s m            -= | e i b p S M  
+                                   ---+--------            ---+------------  
+                                   s  | s   s              S  | S S     S    
+                                   m  | m   m              M  | M M     M    
+``
+
+On Sets both function groups fall together
+as ['*set difference*].
+
+Complexity characteristics for inplace subtraction operations are 
+given by the next tables where 
+``
+n = iterative_size(y);
+m = iterative_size(x); //if P is a container type
+``
+
+[table Time Complexity for inplace Subtraction on element containers
+[[`T& operator -= (T&, const P&)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_set__][__ch_icl_map__]]
+[[__icl_set__]                    [__Olgn__]    []               [__Omlgn__]     []              ]
+[[__icl_map__]                    [__Olgn__]    [__Olgn__]       [__Omlgn__]     [__Omlgn__]     ]
+]
+
+
+[table Time Complexity for inplace Subtraction on interval containers
+[[`T& operator -= (T&, const P&)`][__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
+[[interval_sets]                  [__Olgn__]    [__a_Olgn__]  []               []               [__Omlgnpm__]    []               ]
+[[interval_maps]                  [__Olgn__]    [__a_Olgn__]  [__Olgn__]       [__On__]         [__Omlgnpm__]    [__Omlgnpm__]    ]
+]
+
+[endsect][/ Inplace operators Subtraction]
+
+
+[section Infix operators][/-Subtraction]
+
+The admissible overloads for the infix 
+/subtraction/ `operator -` 
+which is a non commutative 
+operation 
+is given by the next overload table.
+
+``
+// overload tables for         -  | e b s m      -  | e i b p S M   
+T operator - (T, const P&)     ---+--------      ---+------------   
+                               s  | s   s        S  | S S     S     
+                               m  | m m m m      M  | M M M M M M   
+``
+[endsect][/- Infix operator Subtraction]
+
+
+[section Subtraction on Intervals]
+
+[table
+[[['*Subtraction*]]                                   [Types] [Description]                                        ]
+
+[[`T left_subtract(T right, const T& left_minuend)`]  [__i]   
+    [subtract `left_minuend` from the interval `right` on it's left side. 
+``
+right_over = left_subtract(right, left_minuend);
+...      d) : right
+... c)      : left_minuend
+     [c  d) : right_over
+``
+    ] ]
+[[`T right_subtract(T left, const T& right_minuend)`] [__i]   
+    [subtract `right_minuend` from the interval `left` on it's right side.
+``
+left_over = right_subtract(left, right_minuend);
+[a      ...  : left
+     [b ...  : right_minuend
+[a  b)       : left_over
+``
+    ] ]
+]
+
+[endsect][/ Subtraction on Intervals]
+
+
+['*See also . . .*]
+[table
+[]
+[[[link boost_icl.function_reference.addition ['*Addition*]]         ]]
+[[[link boost_icl.function_reference.erasure  ['*Erasure*]]          ]]
+]
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]]    ]]
+[[[link boost_icl.interface ['*Interface*]]                ]]
+]
+
+[endsect][/ Subtraction]
+

Added: trunk/libs/icl/doc/functions_symmetric_difference.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/functions_symmetric_difference.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,163 @@
+[/
+    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)
+]
+
+
+[/ //= Symmetric Difference ===================================================]
+[section Symmetric Difference]
+
+[section Synopsis][/ Symmetric difference]
+
+[table
+[[Symmetric difference]         [__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__] ]
+
+[[`T& T::flip(const P&)`]                      [__ei]     [__bp]   [ ]     [__b]     ]
+[[`T& flip(T&, const P&)`]                     [__ei]     [__bp]   [__e]   [__b]     ]
+[[`T& operator ^=(T&, const P&)`]              [__eiS]    [__bpM]  [__es]  [__bm]    ]
+[[`T  operator ^ (T, const P&)`\n
+  `T  operator ^ (const P&, T)`]               [__eiS]    [__bpM]  [__es]  [__bm]    ]
+
+]
+
+Functions and operators that implement ['*symmetric difference*] on *icl* objects
+are given in the table above.
+
+[table
+[[]      [Description of symmetric difference]]
+[[`Sets`][`operator ^` implements ['*set symmetric difference*]]]
+[[`Maps`][`operator ^` implements a ['*map symmetric difference*] 
+          function similar to /set symmetric difference/.
+          All pairs that are common to both arguments are removed. All others unified.
+         ]]
+]
+
+
+[endsect][/ Synopsis Symmetric difference]
+
+[section Functions][/ Symmetric difference]
+
+/Symmetric difference/ is implemented on interval containers
+by the function `T& flip(T&, const P& operand)`.
+
+``
+flip(y,x)
+`` 
+
+deletes every element of `y`, 
+if it is contained in `x`. Elements of
+`x` not contained in `y` are added.
+For icl containers flip is also availabel as memeber function
+`T& T::flip(const P& operand)`.
+
+[/ paratract, surtract, symetract, topple, symmetric_subtract]
+
+The admissible combinations of types for member function 
+`T& T::flip(const P&)` can be summarized in the 
+['*overload table*] below:
+
+``
+/* overload table for */           T\P| e i b p  
+T& T::flip(const P&)               ---+--------
+T& flip(T&, const P&)               s | s
+                                    m |     m
+                                    S | S S     
+                                    M |     M M
+``
+
+The next table contains complexity characteristics for functions `flip`.
+
+[table Time Complexity for member functions flip on icl containers
+[[`T& T::flip(const P&)`\n
+  `T& flip(T&, const P&)`]     [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
+[[__icl_set__]                 [__Olgn__] []          []        []          ]
+[[__icl_map__]                 []         []          [__Olgn__][]          ]
+[[__itv_set__\n__sep_itv_set__][__Olgn__] [__On__]    []        []          ]
+[[__spl_itv_set__]             [__Olgn__] [__On__]    []        []          ]
+[[__itv_map__\n__spl_itv_map__][]         []          [__Olgn__][__On__]    ]
+]
+
+[endsect][/ Member functions Symmetric difference]
+
+
+[section Inplace operators][/ Symmetric Difference]
+
+The overload tables below are giving admissible
+type combinations for `operator ^=`
+that implements ['*symmetric difference*].
+
+``
+// overload tables for             element containers:     interval containers:
+T& operator ^= (T&, const P&)      ^= | e b s m            ^= | e i b p S M    
+                                   ---+--------            ---+------------    
+                                   s  | s   s              S  | S S     S      
+                                   m  |   m   m            M  |     M M   M    
+``
+Complexity characteristics for inplace operators
+that implement ['*symmetric difference*]
+are given by the next tables where 
+``
+n = iterative_size(y);
+m = iterative_size(x); //if P is a container
+``
+
+[table Time Complexity for inplace symmetric difference on element containers
+[[`T& operator &= (T& y, const P& x)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_set__][__ch_icl_map__]]
+[[__icl_set__]                    [__Olgn__]    []               [__Omlgn__]     []              ]
+[[__icl_map__]                    [__Olgn__]    [__Olgn__]       [__Omlgn__]     [__Omlgn__]     ]
+]
+
+[table Time Complexity for inplace symmetric difference on interval containers
+[[`T& operator &= (T&, const P&)`][__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
+[[interval_sets]                  [__Olgn__]    [__On__]      []               []               [__Omlgnpm__]    []               ]
+[[interval_maps]                  [__Olgn__]    [__On__]      [__Olgn__]       [__On__]         [__Omlgnpm__]    [__Omlgnpm__]    ]
+]
+
+[endsect][/ Inplace operators Symmetric Difference]
+
+[section Infix operators][/ Symmetric Difference]
+
+For the infix version of symmetric difference the
+following overloads are available:
+
+``
+// overload tables for             element containers:     interval containers:
+T operator ^ (T, const P&)         ^  | e b s m            ^  | e  i  b  p  S1 S2 S3 M1 M3
+T operator ^ (const P&, T)         ---+--------            ---+---------------------------
+                                   e  |     s              e  |             S1 S2 S3
+                                   b  |       m            i  |             S1 S2 S3
+                                   s  | s   s              b  |                      M1 M3
+                                   m  |   m   m            p  |                      M1 M3
+                                                           S1 | S1 S1       S1 S2 S3
+                                                           S2 | S2 S2       S2 S2 S3
+                                                           S3 | S3 S3       S3 S3 S3
+                                                           M1 |       M1 M1          M1 M3
+                                                           M3 |       M3 M3          M3 M3
+``
+
+To resolve ambiguities among interval containers
+the ['*finer*] container type is chosen as result type.
+
+[endsect][/ Infix operators Symmetric Difference]
+
+
+['*See also . . .*]
+[table
+[]
+[[[link boost_icl.function_reference.intersection ['*Intersection*]] ]]
+[[[link boost_icl.function_reference.subtraction  ['*Subtraction*]]  ]]
+[[[link boost_icl.function_reference.addition     ['*Addition*]]     ]]
+]
+['*Back to section . . .*]
+[table
+[]
+[[[link function_synopsis_table ['*Function Synopsis*]]    ]]
+[[[link boost_icl.interface ['*Interface*]]                ]]
+]
+
+[endsect][/ Symmetric Difference]
+
+

Added: trunk/libs/icl/doc/icl.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/icl.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,251 @@
+[library Boost.Icl
+    [quickbook 1.4]
+    [authors [Faulhaber, Joachim]]
+    [copyright 2007-2010 Joachim Faulhaber]
+    [copyright 1999-2006 Cortex Software GmbH]
+    [category container]
+    [id optional]
+    [dirname optional]
+    [purpose
+        Implements sets and maps as sets and maps of intervals
+    ]
+    [source-mode c++]
+    [license
+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])
+    ]
+]
+
+
+[/ Macros will be used for links so we have a central place to change them ]
+[def __itv__          [classref boost::icl::interval interval]]
+[def __Itv__          [classref boost::icl::interval Interval]]
+
+[def __itv_tr__       [classref boost::icl::interval_traits interval_traits]]
+[def __Itv_tr__       [classref boost::icl::interval_traits Interval_traits]]
+
+[def __ro_itv__       [classref boost::icl::right_open_interval right_open_interval]]
+[def __lo_itv__       [classref boost::icl::right_open_interval left_open_interval]]
+[def __op_itv__       [classref boost::icl::open_interval       open_interval]]
+[def __cl_itv__       [classref boost::icl::closed_interval     closed_interval]]
+
+[def __dc_itv__       [classref boost::icl::discrete_interval   discrete_interval]]
+[def __ct_itv__       [classref boost::icl::continuous_interval continuous_interval]]
+
+
+[def __itvs__         [classref boost::icl::interval intervals]]
+[def __icl_itvs__     [classref boost::icl::interval icl::intervals]]
+[def __Itvs__         [classref boost::icl::interval Intervals]]
+[def __itv_set__      [classref boost::icl::interval_set interval_set]]
+[def __itv_sets__     [classref boost::icl::interval_set interval_sets]]
+[def __itv_bset__     [classref boost::icl::interval_base_set interval_set]]
+[def __Itv_bset__     [classref boost::icl::interval_base_set Interval_set]]
+[def __itv_bsets__    [classref boost::icl::interval_base_set interval_sets]]
+[def __itv_bset_s__   [classref boost::icl::interval_base_set interval_set's]]
+[def __Itv_bsets__    [classref boost::icl::interval_base_set Interval_sets]]
+
+[def __ele_set__      [@http://www.cplusplus.com/reference/stl/set/ `std::set` ]]
+[def __ele_sets__     [@http://www.cplusplus.com/reference/stl/set/ `std::sets`]]
+[def __icl_set__      [@http://www.cplusplus.com/reference/stl/set/ `std::set` ]]
+[def __icl_sets__     [@http://www.cplusplus.com/reference/stl/set/ `std::sets`]]
+[def __std_set__      [@http://www.cplusplus.com/reference/stl/set/ `std::set` ]]
+[def __std_sets__     [@http://www.cplusplus.com/reference/stl/set/ `std::sets`]]
+[def __std_map__      [@http://www.cplusplus.com/reference/stl/set/ `std::map` ]]
+[def __std_maps__     [@http://www.cplusplus.com/reference/stl/set/ `std::maps`]]
+
+[def __Itv_set__      [classref boost::icl::interval_set Interval_set]]
+[def __Itv_sets__     [classref boost::icl::interval_set Interval_sets]]
+[def __spl_itv_set__  [classref boost::icl::split_interval_set split_interval_set]]
+[def __spl_itv_sets__ [classref boost::icl::split_interval_set split_interval_sets]]
+[def __spl_itv_set_s__ [classref boost::icl::split_interval_set split_interval_set's]]
+[def __Spl_itv_set__  [classref boost::icl::split_interval_set Split_interval_set]]
+[def __sep_itv_set__  [classref boost::icl::separate_interval_set separate_interval_set]]
+[def __sep_itv_sets__ [classref boost::icl::separate_interval_set separate_interval_sets]]
+[def __Sep_itv_set__  [classref boost::icl::separate_interval_set Separate_interval_set]]
+[def __itv_map__      [classref boost::icl::interval_map interval_map]]
+[def __itv_maps__     [classref boost::icl::interval_map interval_maps]]
+[def __itv_map_s__    [classref boost::icl::interval_map interval_map's]]
+[def __itv_bmap__     [classref boost::icl::interval_base_map interval_map]]
+[def __Itv_bmap__     [classref boost::icl::interval_base_map Interval_map]]
+[def __itv_bmaps__    [classref boost::icl::interval_base_map interval_maps]]
+[def __Itv_bmaps__    [classref boost::icl::interval_base_map Interval_maps]]
+[def __itv_bmap_s__   [classref boost::icl::interval_base_map interval_map's]]
+[def __Itv_map__      [classref boost::icl::interval_map Interval_map]]
+[def __spl_itv_map__  [classref boost::icl::split_interval_map split_interval_map]]
+[def __Spl_itv_map__  [classref boost::icl::split_interval_map Split_interval_map]]
+[def __spl_itv_maps__ [classref boost::icl::split_interval_map split_interval_maps]]
+
+[def __inverse__      [classref boost::icl::inverse inverse]]
+[def __ip_cross__     [classref boost::icl::inplace_cross    inplace_cross]]
+[def __ip_dash__      [classref boost::icl::inplace_dash     inplace_dash]]
+[def __ip_plus__      [classref boost::icl::inplace_plus     inplace_plus]]
+[def __ip_minus__     [classref boost::icl::inplace_minus    inplace_minus]]
+[def __ip_star__      [classref boost::icl::inplace_star     inplace_star]]
+[def __ip_slash__     [classref boost::icl::inplace_slash    inplace_slash]]
+[def __ip_times__     [classref boost::icl::inplace_times    inplace_times]]
+[def __ip_divide__    [classref boost::icl::inplace_divide   inplace_divide]]
+[def __ip_pipe__      [classref boost::icl::inplace_pipe     inplace_pipe]]
+[def __ip_et__        [classref boost::icl::inplace_et       inplace_et]]
+[def __ip_caret__     [classref boost::icl::inplace_caret    inplace_caret]]
+[def __ip_min__       [classref boost::icl::inplace_min      inplace_min]]
+[def __ip_max__       [classref boost::icl::inplace_max      inplace_max]]
+[def __ip_identity__  [classref boost::icl::inplace_identity inplace_identity]]
+[def __ip_erasure__   [classref boost::icl::inplace_erasure  inplace_erasure]]
+[def __ip_bitset_union__      [classref boost::icl::inplace_bitset_union      inplace_bitset_union]]
+[def __ip_bitset_difference__ [classref boost::icl::inplace_bitset_difference inplace_bitset_difference]]
+
+[def __itv_bmap_add__ [memberref boost::icl::interval_base_map::add add]]
+
+
+[def __ele_map__      [classref boost::icl::map map]]
+[def __ele_maps__     [classref boost::icl::map maps]]
+[def __icl_map__      [classref boost::icl::map icl::map]]
+[def __icl_maps__     [classref boost::icl::map icl::maps]]
+[def __icl_map_s__    [classref boost::icl::map icl::map's]]
+
+[def __pabsorber__     [classref boost::icl::partial_absorber partial_absorber]]
+[def __penricher__     [classref boost::icl::partial_enricher partial_enricher]]
+[def __penrichers__    [classref boost::icl::partial_enricher partial_enrichers]]
+[def __tabsorber__     [classref boost::icl::total_absorber  total_absorber]]
+[def __tenricher__     [classref boost::icl::total_absorber  total_enricher]]
+
+[def __itv_bse_set__  [classref boost::icl::interval_base_set interval_base_set]]
+[def __e              [link element_type *e*]]
+[def __i              [link interval_type *i*]]
+[def __s              [link itl_set_type *s*]]
+[def __S              [link interval_set_types *S*]]
+[def __b              [link element_mapping_type *b*]]
+[def __p              [link interval_mapping_type *p*]]
+[def __m              [link itl_map_type *m*]]
+[def __M              [link interval_map_types *M*]]
+[def __d              [link discrete_types *d*]]
+[def __c              [link continuous_types *c*]]
+
+[def __ei             [link element_type *e*] [link interval_type *i*]]
+[def __bp             [link element_mapping_type *b*] [link interval_mapping_type *p*]]
+[def __eS             [link element_type *e*] [link interval_set_types *S*]]
+[def __es             [link element_type *e*] [link itl_set_type *s*]]
+[def __bM             [link element_mapping_type *b*] [link interval_map_types *M*]]
+[def __bm             [link element_mapping_type *b*] [link itl_map_type *m*]]
+[def __ebm            [link element_type *e*] [link element_mapping_type *b*] [link itl_map_type *m*]]
+[def __eiS            [link element_type *e*] [link interval_type *i*] [link interval_set_types *S*]]
+[def __bpM            [link element_mapping_type *b*] [link interval_mapping_type *p*] [link interval_map_types *M*]]
+[def __dc             [link discrete_types *d*] [link continuous_types *c*]]
+
+[def __S1             [link ph_def_S1 *S1*]]
+[def __S2             [link ph_def_S2 *S2*]]
+[def __S3             [link ph_def_S3 *S3*]]
+
+[def __M1             [link ph_def_M1 *M1*]]
+[def __M3             [link ph_def_M3 *M3*]]
+
+[def __eiS_phs__      [link element_type placeholders]]
+[def __eiS_Phs__      [link element_type Placeholders]]
+
+[def __eibpsSmM__     [link element_type *e*] [link interval_type *i*] 
+                      [link element_mapping_type *b*] [link interval_mapping_type *p*]
+                      [link itl_set_type *s*] [link interval_set_types *S*]
+                      [link itl_map_type *m*] [link interval_map_types *M*]]
+
+[def __biLConsCopyDest__ [link boost_icl.function_reference.construct__copy__destruct ['*Construct, copy, destruct*]]]
+[def __biLContainedness__  [link boost_icl.function_reference.containedness ['*Containedness*]]]
+[def __biLcontainedness__  [link boost_icl.function_reference.containedness ['*containedness*]]]
+[def __biLEquivsOrderings__   [link boost_icl.function_reference.equivalences_and_orderings ['*Equivalences and Orderings*]]]
+[def __biLSize__         [link boost_icl.function_reference.size ['*Size*]]]
+[def __biLRange__        [link boost_icl.function_reference.range ['*Range*]]]
+[def __biLHull__         [link boost_icl.function_reference.range ['*Hull*]]]
+[def __biLSelection__    [link boost_icl.function_reference.selection ['*Selection*]]]
+[def __biLAddition__     [link boost_icl.function_reference.addition ['*Addition*]]]
+[def __biLadd__          [link boost_icl.function_reference.addition ['*add*]]]
+[def __biLSubtraction__  [link boost_icl.function_reference.subtraction ['*Subtraction*]]]
+[def __biLsubtraction__  [link boost_icl.function_reference.subtraction ['*subtraction*]]]
+[def __biLInsertion__    [link boost_icl.function_reference.insertion ['*Insertion*]]]
+[def __biLErasure__      [link boost_icl.function_reference.erasure ['*Erasure*]]]
+[def __biLerasure__      [link boost_icl.function_reference.erasure ['*erasure*]]]
+[def __biLIntersection__ [link boost_icl.function_reference.intersection ['*Intersection*]]]
+[def __biLintersection__ [link boost_icl.function_reference.intersection ['*intersection*]]]
+[def __biLSymmetricDifference__ [link boost_icl.function_reference.symmetric_difference ['*Symmetric difference*]]]
+[def __biLIteratorRelated__ [link boost_icl.function_reference.iterator_related ['*Iteration*]]]
+[def __biLElementIteration__ [link boost_icl.function_reference.element_iteration ['*Element iteration*]]]
+[def __biLStreaming__    [link boost_icl.function_reference.streaming__conversion ['*Streaming, conversion*]]]
+
+[def __biLIntervalConstruct__  [link boost_icl.function_reference.interval_construction ['*Construction*]]]
+[def __biLIntervalOrderings__  [link boost_icl.function_reference.additional_interval_orderings ['*Orderings*]]]
+[def __biLIntervalMiscellaneous__  [link boost_icl.function_reference.miscellaneous_interval_functions ['*Miscellaneous*]]]
+
+[/ column headers]
+[def __ch_itvs__       intervals]
+
+[def __ch_dom_t__      domain\ntype]
+[def __ch_itv_t__      interval\ntype]
+[def __ch_dom_mp_t__   domain\nmapping\ntype]
+[def __ch_itv_mp_t__   interval\nmapping\ntype]
+
+[def __ch_itv_sets__   interval\nsets]
+[def __ch_itv_maps__   interval\nmaps]
+[def __ch_itl_set__    std::set]
+[def __ch_itl_map__    icl::map]
+[def __ch_icl_set__    std::set]
+[def __ch_icl_map__    icl::map]
+
+[def __ch_ele_sets__   element\nsets]
+[def __ch_ele_maps__   element\nmaps]
+[def __ch_ele_set__    element\nset]
+[def __ch_ele_map__    element\nmap]
+
+[def __ch_dsc_itv__    discrete\n_interval]
+[def __ch_cnt_itv__    continuous\n_interval]
+[def __ch_ro_itv__     right_open\n_interval]
+[def __ch_lo_itv__     left_open\n_interval]
+[def __ch_cl_itv__     closed\n_interval]
+[def __ch_op_itv__     open\n_interval]
+
+[def __bi_conceptual__ ['*fundamental*]]
+[def __conceptual__    fundamental]
+[def __Conceptual__    Fundamental]
+
+[def __bi_iterative__  ['*segmental*]]
+[def __iterative__     segmental]
+[def __Iterative__     Segmental]
+
+[def __O1__            ['O(1)]]
+[def __aO1__           ['amortized O(1)]]
+[def __On__            ['O(n)]]
+[def __Om__            ['O(m)]]
+[def __Ok__            ['O(k)]]
+[def __Onpm__          ['O(n+m)]]
+[def __Olgn__          ['O(log n)]]
+[def __a_Olgn__        ['amortized\nO(log n)]]
+[def __Onlgn__         ['O(n log n)]]
+[def __Omlgn__         ['O(m log n)]]
+[def __Omlgnpm__       ['O(m log(n+m))]]
+
+[def __inpops__        `+= -= &= ^=`]
+[def __ainpop__        `o=`]
+
+
+[/ Cited Boost resources ]
+
+[/ Other web resources ]
+
+[/ Icons ]
+
+[def __SPACE__ [$images/space.png]]
+[def __GO_TO__ [$images/callouts/R.png]]
+
+
+[include introduction.qbk]
+[include examples.qbk]
+[include projects.qbk]
+[include concepts.qbk]
+[include semantics.qbk]
+[include interface.qbk]
+[include customization.qbk]
+[include implementation.qbk]
+[include functions.qbk]
+[include acknowledgments.qbk]
+[xinclude icldoc.xml]
+
+
+14:46 15.10.2010
\ No newline at end of file

Added: trunk/libs/icl/doc/implementation.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/implementation.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,221 @@
+[/
+    Copyright (c) 2008-2009 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 Implementation]
+
+The [link boost_icl.interface previous section] gave an overview over the interface
+of the *icl* outlining 
+[link boost_icl.interface.class_templates class templates], 
+[link boost_icl.interface.associated_types associated types]
+and polymorphic 
+[link boost_icl.interface.function_synopsis functions and operators]. 
+In preparation to the 
+[link boost_icl.function_reference next section], 
+that describes the *icl's* polymorphic functions in
+more detail together with ['*complexity characteristics*], 
+this section summarizes some general information on
+implementation and performance.
+
+[h5 STL based implementation]
+
+The *implementation* of the *icl's* containers is based on 
+[*std::set] and [*std::map]. So the underlying data structure of
+interval containers is a red black tree of intervals or
+interval value pairs. 
+The element containers __icl_set__ and __icl_map__ are wrapper
+classes of `std::set` and `std::map`.
+Interval containers are then using __icl_sets__ of intervals
+or __icl_maps__ of interval value pairs as implementing
+containers.
+So all the ['*complexity characteristics*] of icl containers
+are based on and limited by the ['*red-black tree implementation*]
+of the underlying std::AssociativeContainers.
+
+
+[section Iterative size]
+
+Throughout the documentation on complexity, 
+big /O/ expressions like __On__ or __Omlgn__ refer to container sizes
+/n/ and /m/. In this documentation these sizes ['*do not*] denote 
+to the familiar `size` function that returns
+the ['*number of elements*] of a container. Because for an interval container
+``
+interval_set<int> mono;
+mono += interval<int>::closed(1,5); // {[1 ... 5]}
+mono.size()           == 5;         // true, 5 elements
+mono.interval_count() == 1;         // true, only one interval
+``
+
+it's size and the number of contained intervals is usually different.
+To refer uniformly to a /size/ that matters for iteration, which is
+the decisive kind of size concerning algorithmic behavior there is a function
+``
+bool T::iterative_size()const; // Number of entities that can be iterated over.
+``
+for all element and interval containers of the icl. So for
+complexity statements throughout the icl's documentation 
+the sizes will be `iterative_sizes` and big /O/ expressions like
+__Omlgn__ will refer to sizes
+``
+n = y.iterative_size();
+m = x.iterative_size();
+``
+for containers `y` and `x`. 
+Note that ``iterative_size`` refers to the primary entities,
+that we can iterate over. For interval containers these
+are intervals or segments. ``Itervative_size`` never refers
+to element iteration for interval containers. 
+
+[endsect][/ Iterative size]
+
+
+[section Complexity]
+
+[h4 Complexity of element containers]
+
+Since ['element containers] __icl_set__ and __icl_map__ are only extensions of
+stl::set and stl::map, their complexity characteristics are
+accordingly. So their major operations insertion (addition),
+deletion and search are all using logarithmic time. 
+
+[h4 Complexity of interval containers]
+
+The operations on ['interval containers] behave differently
+due to the fact that intervals unlike elements can overlap
+any number of other intervals in a container. As long as
+intervals are relatively small or just singleton, interval
+containers behave like containers of elements.
+For large intervals however time consumption of operations
+on interval containers may be worse, because most or all
+intervals of a container may have to be visited.
+As an example, time complexity of __biLAddition__ on
+interval containers is briefly discussed.
+
+More information on ['*complexity characteristics*] 
+of *icl's* functions is contained in section 
+[link boost_icl.function_reference Function Reference]
+
+
+[h5 Time Complexity of Addition]
+
+The next table
+gives the time complexities for the overloaded 
+`operator +=` on interval containers.
+The instance types of `T` are given as column headers.
+Instances of type parameter `P` are denoted in
+the second column.
+The third column contains the specific kind of complexity statement. 
+If column three is empty ['*worst case*] complexity is given
+in the related row. 
+
+
+[table Time Complexity of Addition:
+[[]                                             [`P`]               [][interval\nset][separate\ninterval\nset][split\ninterval\nset][interval\nmap][split\ninterval\nmap]]
+[/ 1operation                                   2granul.            3case        4itvset       5se_itvset    6sp_itvset    7itv_map      8sp_itvmap]
+[[`T& operator +=(T& object, const P& addend)`] [`T::element_type`] []           [__Olgn__]    [__Olgn__]    [__Olgn__]    [__Olgn__]    [__Olgn__]    ]
+[[]                                             [`T::segment_type`] [best case]  [__Olgn__]    [__Olgn__]    [__Olgn__]    [__Olgn__]    [__Olgn__]    ]
+[[]                                             []                  [worst case] [__On__]      [__On__]      [__On__]      [__On__]      [__On__]      ]
+[[]                                             []                  [amortized]  [__Olgn__]    [__Olgn__]    []            []            []            ]
+[[]                                             [`interval_sets`]   []           [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] [           ] [           ] ]
+[[]                                             [`interval_maps`]   []           [           ] [           ] [           ] [__Omlgnpm__] [__Omlgnpm__] ]
+]
+
+Adding an /element/ or 
+/element value pair/ is always done in /logarithmic time/,
+where /n/ is the number of intervals in the interval container.
+The same row of complexities applies to the insertion
+of a /segment/ (an interval or an interval value pair)
+in the ['*best case*], where the inserted segment does overlap
+with only a ['*small*] number of intervals in the container.
+
+In the ['*worst case*], where the inserted segment overlaps with 
+all intervals in the container, the algorithms
+iterate over all the overlapped segments.
+Using inplace manipulations of segments and
+hinted inserts, it is possible to perform 
+all necessary operations on each iteration step
+in /constant time/. 
+This results in ['*linear worst case time*] complexity for 
+segment addition for all interval containers.
+
+After performing
+a worst case addition  
+for an __itv_set__ or a __sep_itv_sets__ 
+adding an interval that overlaps /n/ 
+intervals, we
+need /n/ non overlapping additions of
+/logarithmic time/ before we can launch 
+another __On__ worst case addition. 
+So we have only a ['*logarithmic amortized
+time*] for the addition of an interval or interval value pair.
+
+For the addition of ['*interval containers*] complexity is __Omlgnpm__.
+So for the ['*worst case*], where the container sizes /n/ and /m/ 
+are equal and both containers cover the same ranges, 
+the complexity of container addition is ['*loglinear*].
+For other cases, that occur frequently in real world applications
+performance can be much better.
+If the added container `operand` is much smaller than 
+`object` and the intervals in `operand` are relatively
+small, performance can be /logarithmic/.
+If /m/ is small compared with /n/ and intervals in `operand`
+are large, performance tends to be /linear/.
+
+[endsect][/ Complexity]
+
+[section Inplace and infix operators]
+
+For the major operations /addition, subtraction, intersection/
+of *icl* containers and for /symmetric difference/
+inplace `operator`s `+= |=, -=, &=` and `^=` 
+are provided.
+
+For every ['*inplace*] operator
+``
+T& operator o= (T& object, const P& operand)
+``
+the *icl* provides corresponding ['*infix*] operators.
+``
+T operator o (T object, const P& operand){ return object o= operand; }
+T operator o (const P& operand, T object){ return object o= operand; }
+``
+
+From this implementation of the infix `operator o` 
+the compiler will hopefully use return value optimization 
+[@http://en.wikipedia.org/wiki/Return_value_optimization (RVO)]
+creating no temporary object and performing one copy of 
+the first argument `object`.
+
+[caution
+Compared to the /inplace/ `operator o=` every use of an 
+/infix/ `operator o` requires ['*one extra copy*] 
+of the first argument `object` that passes a container.]
+
+Use infix operators only, if
+
+* efficiency is not crucial, e.g. the containers copied are small.
+* a concise and short notation is more important than efficiency in your context.
+* you need the result of operator `o=` as a copy anyway.
+
+[h5 Time Complexity of infix `operators o`]
+
+The time complexity of all infix operators of the *icl*
+is biased by the extra copy of the `object` argument.
+So all infix `operators o` are at least 
+/linear/ in `n = object.iterative_size()`.
+Taking this into account, the complexities of all 
+infix operators can be determined
+from the corresponding inplace `operators o=` they depend
+on.
+
+[endsect][/ Inplace and infix operators]
+
+
+
+[endsect][/ Implementation]
+

Added: trunk/libs/icl/doc/interface.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/interface.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,747 @@
+[/
+    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 Interface]
+
+Section *Interface* outlines types and functions
+of the *Icl*. Synoptical tables allow to review the overall structure of
+the libraries design and to focus on structural equalities and differences
+with the corresponding containers of the standard template library.
+
+
+[section Class templates]
+
+[section Intervals]
+
+In the *icl* we have two groups of interval types. There are ['*statically bounded*] intervals, 
+__ro_itv__,
+__lo_itv__,
+__cl_itv__,
+__op_itv__,
+that always have the the same kind of interval borders and ['*dynamically bounded*] intervals,
+__dc_itv__,
+__ct_itv__
+which can have one of the four possible bound types at runtime.
+
+
+[table Interval class templates
+[[group]              [form]      [template]          [instance parameters]]
+[[statically bounded] [asymmetric][__ro_itv__]        [`<class DomainT, template<class>class Compare>`]]
+[[ ]                  []          [__lo_itv__]        [`<...same for all interval class templates...>`]]
+[[ ]                  [symmetric] [__cl_itv__]        []]
+[[ ]                  []          [__op_itv__]        []]
+[[dynamically bounded][]          [__dc_itv__]        []]
+[[ ]                  []          [__ct_itv__]        []]
+]
+
+Not every class template works with all domain types. Use interval class templates
+according the next table.
+
+[table Usability of interval class templates for discrete or continuous domain types
+[[group]              [form]      [template]          [discrete]    [continuous] ]
+[[statically bounded] [asymmetric][__ro_itv__]        [yes]         [yes]        ]
+[[ ]                  []          [__lo_itv__]        [yes]         [yes]        ]
+[[ ]                  [symmetric] [__cl_itv__]        [yes]         [ ]          ]
+[[ ]                  []          [__op_itv__]        [yes]         [ ]          ]
+[[dynamically bounded][]          [__dc_itv__]        [yes]         [ ]          ]
+[[ ]                  []          [__ct_itv__]        []            [yes]        ]
+]
+
+From a pragmatical point of view, the most important interval class template
+of the /statically bounded/ group is __ro_itv__. For discrete domain types
+also closed intervals might be convenient. Asymmetric intervals can be used
+with continuous domain types but __ct_itv__ is the only class template that
+allows to represent a singleton interval that contains only one element.
+
+Use __ct_itv__, if you work with interval containers of countinuous domain types
+and you want to be able to handle single values:
+
+``
+typedef interval_set<std::string, std::less, continuous_interval<std::string> > IdentifiersT;
+IdentifiersT identifiers, excluded;
+identifiers += continuous_interval<std::string>::right_open("a", "c");
+
+// special identifiers shall be excluded
+identifiers -= std::string("boost");
+cout << "identifiers: " << identifiers << endl;
+
+excluded = IdentifiersT(icl::hull(identifiers)) - identifiers;
+cout << "excluded   : " << excluded << endl;
+
+//------ Program output: --------
+identifiers: {[a,boost)(boost,c)}
+excluded   : {[boost,boost]}
+`` 
+
+[h4 Library defaults and class template `interval`]
+
+As shown in the example above, you can choose an interval type
+by instantiating the interval container template with the desired type.
+
+``
+typedef interval_set<std::string, std::less, continuous_interval<std::string> > IdentifiersT;
+``
+
+But you can work with the library default for interval template parameters as well, 
+which is `interval<DomainT,Compare>::type`.
+
+[table
+[[]                                               [interval bounds][domain_type][interval_default]]
+[[`#ifdef` BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS][static]         [ ]          [__ro_itv__]      ]
+[[`#else`]                                        [dynamic]        [discrete]   [__dc_itv__]      ]
+[[ ]                                              [ ]              [continuous] [__ct_itv__]      ]
+]
+
+So, if you are always happy with the library default for the interval type, just use
+``
+icl::interval<MyDomainT>::type myInterval;
+``
+as you standard way of declaring intervals and default parameters for interval containers:
+``
+typedef interval_set<std::string> IdentifiersT;
+IdentifiersT identifiers, excluded;
+identifiers += interval<std::string>::right_open("a", "c");
+. . .
+``
+
+So class template __itv__ provides a standard way to work with the library default
+for intervals. Via `interval<D,C>::type` you can declare a default interval. 
+In addition four static functions
+``
+T interval<D,C>::right_open(const D&, const D&);
+T interval<D,C>::left_open(const D&, const D&);
+T interval<D,C>::closed(const D&, const D&);
+T interval<D,C>::open(const D&, const D&);
+``
+allow to construct intervals of the library default `T = interval<D,C>::type`.
+
+If you 
+``
+#define BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS
+`` 
+the library uses only statically bounded __ro_itv__ as default interval type.
+In this case, the four static functions above are also available,
+but they only move interval borders consistently, if
+their domain type is discrete, and create an appropriate __ro_itv__ finally:
+``
+interval<D,C>::right_open(a,b) == [a, b)  ->  [a  , b  )
+interval<D,C>:: left_open(a,b) == (a, b]  ->  [a++, b++)
+interval<D,C>::    closed(a,b) == [a, b]  ->  [a  , b++)
+interval<D,C>::      open(a,b) == (a, b)  ->  [a++, b  )
+``
+
+For continuous domain types only the first of the four functions is applicable
+that matches the library default for statically bounded intervals: __ro_itv__.
+The other three functions can not perform an appropriate tranformation and
+will not compile.
+
+[endsect][/ Intervals]
+
+[section Sets]
+
+The next two tables give an overview over ['*set class templates*] of
+the icl. 
+
+[/          interval_set]
+[/ separate_interval_set]
+[/    split_interval_set]
+[/              icl::set]
+
+[table Set class templates
+[[group]        [template]       [instance parameters]]
+[/ CL [__itv__]      [__itv__]        [`<DomainT,Compare>`]]
+[[__itv_bsets__][__itv_set__]    [`<DomainT,Compare,IntervalT,Alloc>`]]
+[[]             [__sep_itv_set__][`<DomainT,Compare,IntervalT,Alloc>`]]
+[[]             [__spl_itv_set__][`<DomainT,Compare,IntervalT,Alloc>`]]
+[/ [__std_set__]  [`std::set`]     [`<_Key,  _Compare,        _Alloc>`]]
+]
+
+Templates and template parameters, given in the preceding table are 
+described in detail below.
+__Itv_bsets__ represent three
+class templates __itv_set__, __sep_itv_set__ and __spl_itv_set__
+that all have equal template parameters. 
+
+[table Parameters of set class templates
+[[]                   [type of elements][order of elements]    [type of intervals]          [memory allocation]]
+[[template parameter] [`class`]  [`template <class>class`]     [`class`]                    [`template <class>class`]]    
+[[__itv__]            [`DomainT`][`Compare = std::less`]       []                           []]
+[[__itv_bsets__]      [`DomainT`][`Compare = std::less`]       [`IntervalT = interval<DomainT,Compare>::type`] [`Alloc = std::alloc`]]
+
+[/ [__icl_set__]        [`DomainT`][`Compare = std::less`]       []                           [`Alloc = std::alloc`]]
+[/ [template parameter] [`class`]  [`class`]                     [`class`]                    [class]]
+[/ [__std_set__]        [`_Key`]   [`_Compare = std::less<_Key>`][]                           [`Alloc = std::alloc<_Key>`]]
+]
+
+[endsect][/ Sets]
+
+[section Maps]
+
+The next two tables give an overview over ['*map class templates*] of the icl. 
+
+[/       interval_map]
+[/ split_interval_map]
+[/           icl::map]
+
+[table map class templates
+[[group]        [template]       [instance parameters]]
+[[__itv_bmaps__][__itv_map__]    [`<DomainT,CodomainT,Traits,Compare,Combine,Section,IntervalT,Alloc>`]]
+[[]             [__spl_itv_map__][`<DomainT,CodomainT,Traits,Compare,Combine,Section,IntervalT,Alloc>`]]
+[[__icl_map__]  [__icl_map__]    [`<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>`]]
+[/ [__std_map__]  [__std_map__]    [`<_Key,   _Data,          _Compare,               _Alloc>`]]
+]
+
+
+Templates and template parameters, given in the preceding table are 
+described in detail below.
+__Itv_bmaps__ represent two
+class templates __itv_map__ and __spl_itv_map__
+that all have equal template parameters.
+
+[table Parameters of map class templates
+[[]                   [elements][mapped values][traits]                      [order of elements]           [aggregation propagation]  [intersection propagation]     [type of intervals]                             [memory allocation]]
+[[template parameter] [`class`]  [`class`]     [`class`]                     [`template <class>class`]     [`template <class>class`]  [`template <class>class`]      [`class`]                                       [`template <class>class`]]    
+[[__itv_bmaps__]      [`DomainT`][`CodomainT`] [`Traits = identity_absorber`] [`Compare = std::less`]       [`Combine = inplace_plus`] [`Section = icl::inplace_et`]  [`IntervalT = interval<DomainT,Compare>::type`][`Alloc = std::alloc`]]
+[[__icl_map__]        [`DomainT`][`CodomainT`] [`Traits = identity_absorber`] [`Compare = std::less`]       [`Combine = inplace_plus`] [`Section = icl::inplace_et`]  [`Alloc = std::alloc`]]
+[/ [template parameter] [`class`]  [`class`]     []                            [`class`]                     []                         []                             []                                              [`class`]]
+[/ [__std_map__]        [`_Key`]   [`_Data`]     []                            [`_Compare = std::less<_Key>`][]                         []                             []                                              [`Alloc = std::alloc<_Key>`]]
+]
+
+Using the following placeholders,
+
+``
+D  := class DomainT,
+C  := class CodomainT,
+T  := class Traits,
+cp := template<class D>class Compare = std::less,
+cb := template<class C>class Combine = icl::inplace_plus,
+s  := template<class C>class Section = icl::inplace_et,
+I  := class IntervalT = icl::interval<D,cp>::type
+a  := template<class>class Alloc = std::allocator
+``
+
+we arrive at a final synoptical matrix of class templates and their parameters.
+
+[pre
+interval     <D,       cp,             >
+interval_sets<D,       cp,        I, a >
+interval_maps<D, C, T, cp, cb, s, I, a >
+icl::map     <D, C, T, cp, cb, s,    a >
+]
+
+The choice of parameters and their positions follow the std::containers
+as close a possible, so that usage of interval sets and maps does only
+require minimal additional knowledge.
+
+Additional knowledge is required when instantiating a comparison parameter
+`Compare` or an allocation parameter `Alloc`. In contrast to std::containers
+these have to be instantiated as templates, like e.g.
+``
+interval_set<string, german_compare>      sections; // 2nd parameter is a template
+std::set<string, german_compare<string> > words;    // 2nd parameter is a type
+``
+
+[endsect][/ Maps]
+[endsect][/ Class templates]
+
+[section Required Concepts]
+
+There are uniform requirements for the template parameters 
+across *icl's* class templates. The template parameters can
+be grouped with respect to those requirements.
+
+[table 
+[[]                    [used in]             [Kind]        [Parameter]   [Instance]                     [Description] ]
+[[Domain order]        [`Intervals, Sets, Maps`][`typename`][`DomainT`]  []                             [For the type `DomainT` of key elements `...`]]
+[[]                    []                    [`template`]  [`Compare`]   [`Compare<DomainT>`]           [`...` there is an order `Compare`] ]
+[[Interval type]       [`interval_sets/maps`][`typename`]  [`IntervalT`] []                             [`...` the `IntervalT` parameter has to use the same element type and order. ] ]
+[[Codomain aggregation][`Maps`]              [`typename`]  [`CodomainT`] []                             [For the type `CodomainT` of associated values `...`]]
+[[]                    []                    [`template`]  [`Combine`]   [`Combine<CodomainT>`]         [`...` there is a binary functor `Combine<CodomainT>()` to combine them ] ]
+[[]                    []                    []            []            [`Inverse<Combine<CodomainT>>`][`...` and implicitly an `Inverse` functor to inversely combine them.  ] ]
+[[]                    []                    [`template`]  [`Section`]   [`Section<CodomainT>`]         [Intersection is propagated to CodomainT values via functor `Section<CodomainT>()`] ]
+[[Memory allocation]   [`Sets, Maps`]        [`template`]  [`Alloc`]     [`Alloc<`/various/`>`]         [An allocator can be chosen for memory allocation.]]
+]
+
+[/ table 
+[[Kind]      [Parameter]  [Condition]                              [Requirement]                                             ]
+[[`typename`][`DomainT`]  []                                       [`Regular<DomainT> && LessThanComparable<DomainT,Compare>` 
+                                                                    `&& (IsIncrementable<DomainT>||HasUnitElement<DomainT>)`] ]
+[[][]                     [`IsIntegral<DomainT>`]                  [`IsIncrementable<DomainT> && IsDecrementable<DomainT>`] ] 
+[[`typename`][`CodomainT`][`Combine` and `Inverse<Combine>` unused]         []]
+[[][]                     [only `Combine` used ]                   [`EqualityComparable<CodomainT> && Addable<CodomainT,Combine>`] ] 
+[[][]                     [also `Inverse<Combine>` used]           [`&& Subtractable<CodomainT,Inverse<Combine> >`] ] 
+[[`template`][`Compare`]  []                                       [`LessThanComparable<DomainT,Compare>`]                     ]
+[[`template`][`Combine`]  [only `Combine` used]                    [`Addable<CodomainT,Combine>`]] 
+[[][]                     [and `Inverse<Combine>` used]            [`&& Subtractable<CodomainT,Inverse<Combine> >`] ] 
+[[][]                     [`Section` used and `CodomainT` is a set][`Intersectable<CodomainT,Section>`] ] 
+]
+
+[h4 Requirements on DomainT]
+
+The next table gives an overview over the requirements for
+template parameter `DomainT`. Some requirements are dependent
+on /conditions/. Column /operators/ shows the operators and
+functions that are expected for `DomainT`, if the default order
+`Compare = std::less` is used.
+
+[table 
+[[Parameter]  [Condition]            [Operators]                     [Requirement]                                              ]
+[[`DomainT`]  []                     [`DomainT(), <`]                [`Regular<DomainT> && StrictWeakOrdering<DomainT,Compare>`]] 
+[[]           []                     [`++, unit_element<CodomainT>::value()`][`&& (IsIncrementable<DomainT>||HasUnitElement<DomainT>)`]        ]
+[[]           [`IsIntegral<DomainT>`][`++, --`]                      [`IsIncrementable<DomainT> && IsDecrementable<DomainT>`]   ] 
+]
+
+A domain type `DomainT` for intervals and interval containers
+has to satisfy the requirements of concept  
+[@http://www.generic-programming.org/languages/conceptcpp/issues/concepts-closed.html `Regular`]
+which
+implies among other properties the existence of a copy and
+a default constructor. In addition `IsIncrementable`
+*or* `HasUnitElement` is required for `DomainT`.
+In the *icl* we represent an empty closed interval as
+interval `[b,a]` where `a < b` (here `<` represents `Compare<DomainT>()`). 
+To construct one of these empty intervals as default constructor
+for any type `DomainT` we choose `[1,0]`, where `0` is a null-value or `identity_element`
+and `1` is a one-value or `unit_element`:
+`` 
+interval() := [unit_element<DomainT>::value(), identity_element<DomainT>::value()] //pseudocode
+``
+`Identity_elements` are implemented via call of the default constructor of
+`DomainT`. A `unit_element<T>::value()` is implemented 
+[classref boost::icl::unit_element by default] as a `identity_element`, 
+that is incremented once. 
+``
+template <class Type> 
+inline Type unit_element<Type>::value(){ return succ(identity_element<Type>::value()); };
+``
+So a type `DomainT` that is `incrementable` will
+also have an `unit_element`. If it does not, a `unit_element` can be provided.
+An `unit_element` can be any value, that is greater as the `neutron` value
+in the `Compare` order given.
+An example of a type, that has a `neutron` but no increment is
+`string`. So for `std::string` a unit_element is implemented like this:
+``
+// Smallest 'visible' string that is greater than the empty string.
+template <>    
+inline std::string unit_element<std::string>::value(){ return std::string(" "); };
+``
+
+Just as for the key type of std::sets and maps 
+template parameter `Compare`  is required to be a 
+[@http://en.wikipedia.org/wiki/Strict_weak_ordering strict weak ordering] on `DomainT`.
+
+Finally, if `DomainT` is an integral type, `DomainT` needs to
+be `incrementable` and `decrementable`. This [''bicrementability']
+needs to be implemented on the smallest possible unit of the
+integral type. This seems like being trivial but there are types like e.g.
+`boost::date_time::ptime`, that are integral in nature but do
+not provide the required in- and decrementation on the least incrementable unit.
+For __icl_itvs__ incementation and decementation is used
+for computations between open to closed interval borders like e.g.
+`[2,43) == [2,42]`. Such computations always need only
+one in- or decrementation, if `DomainT` is an integral type. 
+
+[h5 Requirements on IntervalT]
+
+Requirements on the `IntervalT` parameter are closely related to the 
+`DomainT` parameter. `IntervalT` has two associated types
+itself for an element type and a compare order that have
+to be consistent with the element and order parameters of
+their interval containers. 
+`IntervalT` then has to implement an order called
+`exclusive_less`. Two intervals `x, y` are exclusive_less 
+``icl::exclusive_less(x, y)``
+if all `DomainT` elements of `x` are less than elements of `y` in the
+`Compare` order. 
+ 
+[table 
+[[Parameter]   [Operators]        [Requirement]                                             ]
+[[`IntervalT`] [`exclusive_less`] [`IsExclusiveLessComparable<Interval<DomainT,Compare> >`] ] 
+]
+
+[h4 Requirements on CodomainT]
+
+Summarized in the next table are requirements for template parameter
+`CodomainT` of associated values for `Maps`. Again there are
+/conditions/ for some of the requirements. Column /operators/
+contains the operators and functions required for `CodomainT`, if we are
+using the default combiner `Combine = icl::inplace_plus`.
+
+[table 
+[[Parameter]  [Condition]                              [Operators]        [Requirement]                                 ]
+[[`CodomainT`][`add`, `subtract`, `intersect` unused]  [`CodomainT(), ==`][`Regular<CodomainT>` which implies]          ]
+[[]           []                                       []                 [`DefaultConstructible<CodomainT> && EqualityComparable<CodomainT>`]          ] 
+[[]           [only `add` used ]                       [`+=`]             [`&& Combinable<CodomainT,Combine>`]          ] 
+[[]           [... and also `subtract` used]           [`-=`]             [`&& Combinable<CodomainT,Inverse<Combine> >`]] 
+[[]           [`Section` used and `CodomainT` is a set][`&=`]             [`&& Intersectable<CodomainT,Section>`] ] 
+]
+
+The requirements on the type `CodomainT` of associated values for a __icl_map__ or __itv_map__
+depend on the usage of their aggregation functionality. If aggregation on overlap
+is never used, that is to say that none of the addition, subtraction and intersection
+operations (`+, +=, add`, `-, -=, subtract`, &, &=, add_intersection) are used on the 
+__itv_map__, then `CodomainT` only needs to be 
+[@http://www.generic-programming.org/languages/conceptcpp/issues/concepts-closed.html Regular].
+['*Regular*]
+object semantics implies `DefaultConstructible` and
+`EqualityComparable` which means it has 
+a default ctor `CodomainT()` and an `operator ==`.
+
+Use __itv_maps__ ['*without aggregation*], if the associated values are not 
+addable but still
+are attached to intervals so you want to use __itv_maps__ to handle them.
+As long as those values are added with `insert` and deleted with `erase` 
+__itv_maps__ will work fine with such values.
+
+If ['*only addition*] is used via __itv_map_s__ `+, +=` or `add` but no subtraction, 
+then `CodomainT` need to be `Combinable` for functor template `Combine`. That
+means in most cases when the default implementation `inplace_plus` for
+`Combine` is used, that `CodomainT` has to implement `operator +=`. 
+
+For associated value types, that are addable but not subtractable like 
+e.g. `std::string` it usually makes sense to use addition to combine values
+but the inverse combination is not desired.
+``
+interval_map<int,std::string> cat_map;
+cat_map += make_pair(interval<int>::rightopen(1,5),std::string("Hello"));
+cat_map += make_pair(interval<int>::rightopen(3,7),std::string(" world"));
+cout << "cat_map: " << cat_map << endl;
+//cat_map: {([1,3)->Hello)([3,5)->Hello world)([5,7)-> world)}
+``
+
+For ['complete aggregation functionality] an inverse aggregation functor on 
+a `Map`'s `CodomainT` is needed. The icl provides a 
+metafunction [classref boost::icl::inverse inverse] 
+for that purpose. Using the default
+`Combine = inplace_plus` that relies on the existence of `operator +=`
+on type `CodomainT` 
+metafunction [classref boost::icl::inverse inverse] 
+will infer [classref boost::icl::inplace_minus inplace_minus]
+as inverse functor, that requires `operator -=` on type `CodomainT`.
+
+In the icl's design we make the assumption,
+in particular for the default setting of parameters
+`Combine = `[classref boost::icl::inplace_minus inplace_plus],
+that type `CodomainT` has a neutral element or `neutron` 
+with respect to the `Combine` functor.
+
+
+[endsect][/ Required Concepts]
+
+
+[section Associated Types]
+
+In order to give an overview over ['*associated types*] the *icl* works
+with, we will apply abbreviations again that were introduced in the
+presentaiton of icl class templates,
+
+[pre
+interval     <D,       cp,             >
+interval_sets<D,       cp,        I, a >
+interval_maps<D, C, T, cp, cb, s, I, a >
+icl::map     <D, C, T, cp, cb, s,    a >
+]
+
+where these placeholders were used:
+
+``
+D  := class DomainT,
+C  := class CodomainT,
+T  := class Traits,
+cp := template<class D>class Compare = std::less,
+cb := template<class C>class Combine = icl::inplace_plus,
+s  := template<class C>class Section = icl::inplace_et,
+I  := class Interval = icl::interval<D,cp>::type
+a  := template<class>class Alloc = std::allocator
+``
+With some additions,
+``
+sz := template<class D>class size
+df := template<class D>class difference
+Xl := class ExclusiveLess = exclusive_less<Interval<DomainT,Compare> >
+inv:= template<class Combiner>class inverse
+(T,U) := std::pair<T,U> for typnames T,U
+``
+
+we can summarize the associated types as follows. 
+Again two additional columns for easy comparison with stl
+sets and maps are provided. 
+
+[table Icl Associated types
+[[Purpose]          [Aspect]         [Type][__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]                                                                                         
+[/[ ]               [ ]              [ ]                   [ ]      [ ]      [ ]       [ ]      [ ]      ]
+[/                                                       interval  itvset   itvmap  icl:set  icl:map   ]
+[[['*Data*]]        [__conceptual__] [`domain_type`]       [`D`]    [`D`]    [`D`]     [`D`]    [`D`]    ]
+[[         ]        [              ] [`codomain_type`]     [`D`]    [`D`]    [`C`]     [`D`]    [`C`]    ]
+[[         ]        [              ] [`element_type`]      [`D`]    [`D`]  [`(D,C)`]   [`D`]  [`(D,C)`]  ]
+[[         ]        [              ] [`segment_type`][`i<D,cp>`][`i<D,cp>`][`(i<D,cp>,C)`][ ]   [ ]      ]
+[[         ]        [['size]       ] [`size_type`]       [`sz<D>`][`sz<D>`][`sz<D>`] [`sz<D>`]  [`sz<D>`]  ]
+[[         ]        [              ] [`difference_type`] [`df<D>`][`df<D>`][`df<D>`] [`sz<D>`]  [`sz<D>`]  ]
+[[         ]        [             ]  [][__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]                                                                                         
+[[['*Data*]]        [__iterative__ ] [`key_type`]          [`D`][`i<D,cp>`][`i<D,cp>`] [`D`]    [`D`]   ]
+[[         ]        [              ] [`data_type`]         [`D`][`i<D,cp>`]   [`C`]    [`D`]    [`C`]   ]
+[[         ]        [              ] [`value_type`]        [`D`][`i<D,cp>`][`(i<D,cp>,C)`][`D`][`(D,C)`]]
+[[         ]        [              ] [`interval_type`] [`i<D,cp>`][`i<D,cp>`][`i<D,cp>`] [ ]     [ ]     ]
+[[         ]        [['allocation]]  [`allocator_type`] [ ][`a<i<D,cp>>`][`a<(i<D,cp>, C)>`][`a<D>`][`a<(D,C)>`]]
+[[         ]        [             ]  [][__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]                                                                                         
+[[['*Ordering*]]    [__conceptual__] [`domain_compare`]  [`cp<D>`][`cp<D>`][`cp<D>`][`cp<D>`][`cp<D>`]    ]
+[[         ]        [__iterative__ ] [`key_compare`]     [`cp<D>`]   [`Xl`]  [`Xl`] [`cp<D>`] [`cp<D>`] ]
+[[         ]        [              ] [`interval_compare`]   [ ]      [`Xl`]  [`Xl`]     [ ]      [ ]      ]
+[[['*Aggregation*]] [__conceptual__] [`codomain_combine`] [ ]      [ ]    [`cb<C>`]   [ ]   [`cb<C>`]   ]
+[[         ]        [        ]       [`inverse_codomain_combine`] [ ]      [ ][`inv<cb<C>>`] [ ][`inv<cb<C>>`]  ]
+[[         ]        [        ]       [`codomain_intersect`] [ ]      [ ]     [`s<C>`]   [ ]    [`s<C>`]   ]
+[[         ]        [      ]         [`inverse_codomain_intersect`] [ ]      [ ] [`inv<s<C>>`]  [ ][`inv<s<C>>`]  ]
+]
+
+
+[endsect][/ Associated Types]
+
+[section Function Synopsis]
+
+In this section a single ['*matrix*] is given, that shows all ['*functions*]
+with shared names and identical or analogous semantics and their 
+polymorphical overloads across the class templates of the *icl*.
+Associated are the corresponding functions of the *stl* for easy
+comparison. In order to achieve a concise representation, a series
+of ['*placeholders*] are used throughout the function matrix.
+
+The ['*placeholder's*] purpose is to express the polymorphic
+usage of the functions. The ['*first column*] of the function matrix
+contains the signatures of the functions. Within these
+signatures `T` denotes a container type and `J` and `P`
+polymorphic argument and result types.
+
+Within the body of the matrix, sets of *boldface* placeholders denote
+the sets of possible instantiations for a polymorphic
+placeholder `P`. For instance __eiS denotes that for the
+argument type `P`, an element __e, an interval __i or an interval_set __S
+can be instantiated. 
+
+If the polymorphism can not be described in this way, only the ['*number*] of
+overloaded implementations for the function of that row is shown.
+
+[table 
+[[Placeholder]                  [Argument types]          [Description]]
+[[`T`                         ] []                        [a container or interval type]]             
+[[`P`                         ] []                        [polymorphical container argument type]]             
+[[`J`                         ] []                        [polymorphical iterator type]]
+[[`K`                         ] []                        [polymorphical element_iterator type for interval containers]]
+[[`V`                         ] []                        [various types `V`, that do dot fall in the categories above]]             
+[[1,2,...                     ] []                        [number of implementations for this function]]             
+[[A                           ] []                        [implementation generated by compilers]]             
+[[[#element_type]         [*e]] [T::element_type]         [the element type of __itv_sets__ or __icl_sets__]]
+[[[#interval_type]        [*i]] [T::segment_type]         [the segment type of of __itv_sets__]]
+[[[#itl_set_type]         [*s]] [element sets]            [__std_set__ or other models of the icl's set concept]]
+[[[#interval_set_types]   [*S]] [interval_sets]           [one of the interval set types]]
+[[[#element_mapping_type] [*b]] [T::element_type]         [type of __itv_map_s__ or __icl_map_s__ element value pairs]]
+[[[#interval_mapping_type][*p]] [T::segment_type]         [type of __itv_map_s__ interval value pairs]]
+[[[#itl_map_type]         [*m]] [element maps]            [__icl_map__ icl's map type]]
+[[[#interval_map_types]   [*M]] [interval_maps]           [one of the interval map types]]
+[[[#discrete_types]       [*d]] [discrete types]          [types with a least steppable discrete unit: Integral types, date/time types etc.]]
+[[[#continuous_types]     [*c]] [continuous types]        [types with (theoretically) infinitely many elements beween two values.]]
+]
+
+[/ memberref boost::icl::set::iterative_size `iterative_size`]
+
+[table Synopsis Functions and Overloads
+[[T]                      [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]                                                                                         
+[/                                           interval  itvset   itvmap  icl:set  icl:map    ]
+[[__biLConsCopyDest__ [#function_synopsis_table]] [ ]     [ ]      [ ]     [ ]      [ ]     ]
+[[`T::T()`]                                       [1]       [1]      [1]     [1]      [1]   ]
+[[`T::T(const P&)`]                               [A]   [__eiS]  [__bpM]     [1]      [1]   ]
+[/ FYI [`T::T(...)`]                              [3]       [ ]      [ ]     [3]      [3]   ]
+[[`T& T::operator=(const P&)`]                    [A]     [__S]    [__M]     [1]      [1]   ]
+[[`void T::swap(T&)`]                             [ ]       [1]      [1]     [1]      [1]   ]
+
+[[__biLContainedness__ ][__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
+[[`bool T::empty()const`]                         [ ]       [1]      [1]     [1]      [1]   ]
+[[`bool is_empty(const T&)`]                      [1]       [1]      [1]     [1]      [1]   ]
+[[`bool contains(const T&, const P&)`\n
+  `bool within(const P&, const T&)`]            [__ei]  [__eiS][__eiS __bpM][__es]   [__bm] ]
+
+[[__biLEquivsOrderings__ ][__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
+[[`bool operator == (const T&, const T&)`]        [1]       [1]      [1]     [1]      [1]   ]
+[[`bool operator != (const T&, const T&)`]        [1]       [1]      [1]     [1]      [1]   ]
+[[`bool operator <  (const T&, const T&)`]        [1]       [1]      [1]     [1]      [1]   ]
+[[`bool operator >  (const T&, const T&)`]        [1]       [1]      [1]     [1]      [1]   ]
+[[`bool operator <= (const T&, const T&)`]        [1]       [1]      [1]     [1]      [1]   ]
+[[`bool operator >= (const T&, const T&)`]        [1]       [1]      [1]     [1]      [1]   ]
+[[`bool is_element_equal(const T&, const P&)`]    [ ]     [__S]    [__M]     [1]      [1]   ]
+[[`bool is_element_less(const T&, const P&)`]     [ ]     [__S]    [__M]     [1]      [1]   ]
+[[`bool is_element_greater(const T&, const P&)`]  [ ]     [__S]    [__M]     [1]      [1]   ]
+[[`bool is_distinct_equal(const T&, const P&)`]   [ ]       [ ]    [__M]     [ ]      [1]   ]
+
+[[__biLSize__ ] [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
+[[`size_type T::size()const`]                     [ ]       [1]      [1]     [1]      [1]   ]
+[[`size_type size(const T&)`]                     [1]       [1]      [1]     [1]      [1]   ]
+[[`size_type cardinality(const T&)`]              [1]       [1]      [1]     [1]      [1]   ]
+[[`difference_type length(const T&)`]             [1]       [1]      [1]     [ ]      [ ]   ]
+[[`size_type iterative_size(const T&)`]           [ ]       [1]      [1]     [1]      [1]   ]
+[[`size_type interval_count(const T&)`]           [ ]       [1]      [1]     [ ]      [ ]   ]
+                                                
+[[__biLSelection__ ]                              [ ]       [ ]      [ ]     [ ]      [ ]   ]
+[[`J T::find(const domain_type&)`]                [ ]       [1]      [1]     [2]      [2]   ]
+[[`codomain_type& operator[] (const domain_type&)`][ ]      [ ]      [ ]     [ ]      [1]   ]
+[[`codomain_type operator() (const domain_type&)const`][ ]  [ ]      [1]     [ ]      [1]   ]
+
+[[__biLRange__]                                   [ ]       [ ]      [ ]     [ ]      [ ]   ]
+[[`interval_type hull(const T&)`]                 [ ]       [1]      [1]     [ ]      [ ]   ]
+[[`T hull(const T&, const T&)`]                   [1]       [ ]      [ ]     [ ]      [ ]   ]
+[[`domain_type lower(const T&)`]                  [1]       [1]      [1]     [ ]      [ ]   ]
+[[`domain_type upper(const T&)`]                  [1]       [1]      [1]     [ ]      [ ]   ]
+[[`domain_type first(const T&)`]                  [1]       [1]      [1]     [ ]      [ ]   ]
+[[`domain_type last(const T&)`]                   [1]       [1]      [1]     [ ]      [ ]   ]
+
+[[__biLAddition__]                [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
+[[`T& T::add(const P&)`]                          [ ]     [__ei]    [__bp]   [ ]     [__b]  ]
+[[`T& add(T&, const P&)`]                         [ ]     [__ei]    [__bp]   [__e]   [__b]  ]
+[[`T& T::add(J pos, const P&)`]                   [ ]     [__i]     [__p]    [ ]     [__b]  ]
+[[`T& add(T&, J pos, const P&)`]                  [ ]     [__i]     [__p]    [__e]   [__b]  ]
+
+[[`T& operator +=(T&, const P&)`]                 [ ]     [__eiS]   [__bpM]  [__es]  [__bm] ]
+[[`T operator + (T, const P&)`\n
+  `T operator + (const P&, T)`]
+                                                  [ ]     [__eiS]   [__bpM]  [__es]  [__bm] ]
+[[`T& operator |=(      T&, const P&)`]           [ ]     [__eiS]   [__bpM]  [__es]  [__bm] ]
+[[`T operator | (T, const P&)`\n
+  `T operator | (const P&, T)`]
+                                                  [ ]     [__eiS]   [__bpM]  [__es]  [__bm] ]
+[[__biLSubtraction__]                             [ ]       [ ]      [ ]     [ ]      [ ]   ]
+[[`T& T::subtract(const P&)`]                     [ ]     [__ei]    [__bp]   [ ]     [__b]  ]
+[[`T& subtract(T&, const P&)`]                    [ ]     [__ei]    [__bp]   [__e]   [__b]  ]
+
+[[`T& operator -=(T&, const P&)`]                 [ ]    [__eiS][__eiS __bpM][__es]  [__bm] ]
+[[`T  operator - (T, const P&)`]                  [ ]    [__eiS][__eiS __bpM][__es]  [__bm] ]
+
+[[`T left_subtract(T, const T&)`]                 [1]       [ ]      [ ]     [ ]      [ ]   ]
+[[`T right_subtract(T, const T&)`]                [1]       [ ]      [ ]     [ ]      [ ]   ]
+
+[[__biLInsertion__]      [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
+[[`V T::insert(const P&)`]                        [ ]     [__ei]    [__bp]   [__e]    [__b]  ]
+[[`V insert(T&, const P&)`]                       [ ]     [__ei]    [__bp]   [__e]    [__b]  ]
+[[`V T::insert(J pos, const P&)`]                 [ ]     [__i]     [__p]    [__e]    [__b]  ]
+[[`V insert(T&, J pos, const P&)`]                [ ]     [__i]     [__p]    [__e]    [__b]  ]
+[[`T& insert(T&, const P&)`]                      [ ]    [__eiS]   [__bpM]   [__es]   [__bm] ]
+[[`T& T::set(const P&)`]                          [ ]       [ ]     [__bp]   [ ]      [1]    ]
+[[`T& set_at(T&, const P&)`]                      [ ]       [ ]     [__bp]   [ ]      [1]    ]
+
+[[__biLErasure__]                                 [ ]       [ ]      [ ]     [ ]      [ ]    ]
+[[`void T::clear()`]                              [ ]       [1]      [1]     [1]      [1]    ]
+[[`void clear(const T&)`]                         [ ]       [1]      [1]     [1]      [1]    ]
+[[`T& T::erase(const P&)`]                        [ ]    [__ei ] [__ei __bp] [__e]    [__bp] ]
+[[`T& erase(T&, const P&)`]                       [ ]    [__eiS][__eiS __bpM][__es]   [__bm] ]
+[[`void T::erase(iterator)`]                      [ ]       [1]      [1]     [1]      [1]    ]
+[[`void T::erase(iterator,iterator)`]             [ ]       [1]      [1]     [1]      [1]    ]
+
+[[__biLIntersection__]  [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
+[[`void add_intersection(T&, const T&, const P&)`][ ]   [__eiS][__eiS __bpM][ ]     [ ]       ]
+[[`T& operator &=(T&, const P&)`]                 [ ]   [__eiS][__eiS __bpM][__es]  [__bm]    ]
+[[`T  operator & (T, const P&)`\n
+  `T  operator & (const P&, T)`]                 [__i]  [__eiS][__eiS __bpM][__es]  [__bm]    ]
+[[`bool intersects(const T&, const P&)`\n
+  `bool disjoint(const T&, const P&)`]           [__i]  [__eiS][__eiS __bpM][__es]  [__bm]    ]
+                                               
+[[__biLSymmetricDifference__]                  [ ]       [ ]      [ ]     [ ]      [ ]      ]
+[[`T& T::flip(const P&)`]                      [ ]     [__ei]    [__bp]   [ ]      [__b]     ]
+[[`T& flip(T&, const P&)`]                     [ ]     [__ei]    [__bp]   [__e]    [__b]     ]
+[[`T& operator ^=(T&, const P&)`]              [ ]    [__eiS]    [__bpM]  [__es]  [__bm]    ]
+[[`T  operator ^ (T, const P&)`\n
+  `T  operator ^ (const P&, T)`]               [ ]    [__eiS]    [__bpM]  [__es]  [__bm]    ]
+  
+[[__biLIteratorRelated__] [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
+[[`J T::begin()`]                              [ ]       [2]      [2]     [2]      [2]      ]
+[[`J T::end()`]                                [ ]       [2]      [2]     [2]      [2]      ]
+[[`J T::rbegin()`]                             [ ]       [2]      [2]     [2]      [2]      ]
+[[`J T::rend()`]                               [ ]       [2]      [2]     [2]      [2]      ]
+[[`J T::lower_bound(const key_type&)`]         [ ]       [2]      [2]     [2]      [2]      ]
+[[`J T::upper_bound(const key_type&)`]         [ ]       [2]      [2]     [2]      [2]      ]
+[[`pair<J,J> T::equal_range(const key_type&)`] [ ]       [2]      [2]     [2]      [2]      ]
+
+[[__biLElementIteration__] [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
+[[`K elements_begin(T&)`]                      [ ]       [2]      [2]     [ ]      [ ]      ]
+[[`K elements_end(T&)`]                        [ ]       [2]      [2]     [ ]      [ ]      ]
+[[`K elements_rbegin(T&)`]                     [ ]       [2]      [2]     [ ]      [ ]      ]
+[[`K elements_rend(T&)`]                       [ ]       [2]      [2]     [ ]      [ ]      ]
+
+[[__biLStreaming__ ]      [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
+[[`std::basic_ostream operator << (basic_ostream&, const T&)`]      
+                                               [1]       [1]      [1]     [1]      [1]      ]
+]
+
+Many but not all functions of *icl* intervals are listed in the table above. 
+Some specific functions are summarized in the next table. For the group of
+the constructing functions, placeholders __d denote discrete domain types and
+__c denote continuous domain types `T::domain_type` for an interval_type `T` and an
+argument types `P`.
+ 
+[table Additional interval functions  
+[[T]                                       [__ch_dsc_itv__] [__ch_cnt_itv__] [__ch_ro_itv__] [__ch_lo_itv__]  [__ch_cl_itv__] [__ch_op_itv__]      ]
+[[Interval bounds]                                     [dynamic]  [dynamic]    [static]     [static]     [static]    [static]    ]
+[[Form]                                                [ ]        [ ]          [asymmetric] [asymmetric] [symmetric] [symmetric] ]
+[[__biLIntervalConstruct__ [#additional_interval_functions]] 
+                                                       [ ]        [ ]          [ ]          [ ]          [ ]         [ ]         ]
+[[`T singleton(const P&)`]                             [__d]      [__c]        [__d]        [__d]        [__d]       [__d]       ]
+[[`T construct(const P&, const P&)`]                   [__d]      [__c]        [__dc]       [__dc]       [__d]       [__d]       ]
+[[`T construct(const P&, const P&, interval_bounds)`]  [__d]      [__c]        [ ]          [ ]          [ ]         [ ]         ]
+[[`T hull(const P&, const P&)`]                        [__d]      [__c]        [__dc]       [__dc]       [__d]       [__d]       ]
+[[`T span(const P&, const P&)`]                        [__d]      [__c]        [__dc]       [__dc]       [__d]       [__d]       ]
+[[`static T right_open(const P&, const P&)`]           [__d]      [__c]        [ ]          [ ]          [ ]         [ ]         ]
+[[`static T left_open(const P&, const P&)`]            [__d]      [__c]        [ ]          [ ]          [ ]         [ ]         ]
+[[`static T closed(const P&, const P&)`]               [__d]      [__c]        [ ]          [ ]          [ ]         [ ]         ]
+[[`static T open(const P&, const P&)`]                 [__d]      [__c]        [ ]          [ ]          [ ]         [ ]         ]
+[[__biLIntervalOrderings__]                            [ ]        [ ]          [ ]          [ ]          [ ]         [ ]         ]
+[[`bool exclusive_less(const T&, const T&)`]           [1]        [1]          [1]          [1]          [1]         [1]         ]
+[[`bool lower_less(const T&, const T&)`\n                
+  `bool lower_equal(const T&, const T&)`\n               
+  `bool lower_less_equal(const T&, const T&)`]         [1]        [1]          [1]          [1]          [1]         [1]         ]
+[[`bool upper_less(const T&, const T&)`\n                
+  `bool upper_equal(const T&, const T&)`\n               
+  `bool upper_less_equal(const T&, const T&)`]         [1]        [1]          [1]          [1]          [1]         [1]         ]
+[[__biLIntervalMiscellaneous__]                        [ ]        [ ]          [ ]          [ ]          [ ]         [ ]         ]
+[[`bool touches(const T&, const T&)`]                  [1]        [1]          [1]          [1]          [1]         [1]         ]
+[[`T inner_complement(const T&, const T&)`]            [1]        [1]          [1]          [1]          [1]         [1]         ]
+[[`difference_type distance(const T&, const T&)`]      [1]        [1]          [1]          [1]          [1]         [1]         ]
+]
+
+[h4 Element iterators for interval containers]
+
+Iterators on [*interval conainers] that are refered to in section /Iteration/ 
+of the function synopsis table are
+['*segment iterators*]. They reveal the more implementation specific
+aspect, that the __conceptual__ aspect abstracts from.[/ NOTE Identical to function_element_iteration.qbk from here]
+Iteration over segments is fast, compared to an iteration over elements,
+particularly if intervals are large. 
+But if we want to view our interval containers as containers
+of elements that are usable with std::algoritms, we need to
+iterate over elements. 
+
+Iteration over elements . . .
+
+* is possible only for integral or discrete `domain_types`
+* can be very ['*slow*] if the intervals are very large.
+* and is therefore ['*depreciated*]
+
+On the other hand, sometimes iteration over interval containers
+on the element level might be desired, if you have some 
+interface that works for `std::SortedAssociativeContainers` of 
+elements and you need to quickly use it with an interval container.
+Accepting the poorer performance might be less bothersome at times
+than adjusting your whole interface for segment iteration.
+
+[caution So we advice you to choose element iteration over
+interval containers ['*judiciously*]. Do not use element iteration
+['*by default or habitual*]. Always try to achieve results using
+namespace global functions or operators 
+(preferably inplace versions)
+or iteration over segments first.]
+
+[endsect][/ Function Synopsis]
+
+
+[endsect][/ Interface]
+

Added: trunk/libs/icl/doc/introduction.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/introduction.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,309 @@
+[/
+    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 Introduction]
+
+[/ note [* The Interval Container Library is accepted into Boost]
+
+The [*Interval Container Library] (formerly /Interval Template Library/) underwent 
+a formal review on the boost developer's list
+from February 18, 2010 to March 08, 2010 and has been accepted 
+by declaration of review manager Hartmut Kaiser
+into the boost library collection on April 18, 2010.
+
+
+The library has been refactored for the suggestions and requests
+that came up during the review. The current version is now
+ready for inclusion into the next boost release.
+The name ['*Interval Template Library (ITL)*] 
+has been changed to ['*Interval Container Library (ICL)*].
+
+If you find bugs in the library or typos or other shortcomings in
+the documentation please send reports to the boost developers list
+boost_at_[hidden]
+the boost users list or
+boost-users_at_[hidden]
+to `[afojgo<AT>gmail dot com]`.
+
+]
+
+["A bug crawls across the boost docs on my laptop screen.
+Let him be! We need all the readers we can get.] -- 
+Freely adapted from [@http://en.wikipedia.org/wiki/Jack_Kornfield Jack Kornfield]
+
+Intervals are almost ubiquitous in software development. Yet they are
+very easily coded into user defined classes by a pair of numbers
+so they are only /implicitly/ used most of the time. The meaning of
+an interval is simple. They represent all the elements between their 
+lower and upper bound and thus a set. But unlike sets, intervals
+usually can not be added to a single new interval.
+If you want to add intervals to a collection of
+intervals that does still represent a /set/,
+you arrive at the idea of /interval_sets/ provided by this library. 
+
+Interval containers of the *ICL* have been developed initially at 
+[@http://www.cortex-software.de/desktopdefault.aspx Cortex Software GmbH]
+to solve problems related to date and time interval
+computations in the context of a Hospital Information System.
+Time intervals with associated values like ['amount of invoice]
+or ['set of therapies] had to be manipulated in statistics,
+billing programs and therapy scheduling programs. 
+So the *ICL* emerged out of those industrial use cases.
+It extracts generic code that helps to solve common
+problems from the date and time problem domain and can be
+beneficial in other fields as well.
+
+One of the most advantageous aspects of interval containers is
+their very compact representation of sets and maps. Working with
+sets and maps /of elements/ can be very inefficient, if in a given
+problem domain, elements are typically occurring in contiguous
+chunks. 
+Besides a compact representation of associative containers, that
+can reduce the cost of space and time drastically, the ICL
+comes with a universal mechanism of aggregation, that allows
+to combine associated values in meaningful ways when intervals
+overlap on insertion.
+
+For a condensed introduction and overview you may want to look at the
+[@http://www.herold-faulhaber.de/boost_icl/doc/libs/icl/doc/boostcon09/intro_to_itl.pdf 
+presentation material on the *ICL* from ['*BoostCon2009*]].
+
+
+[section Definition and Basic Example]
+
+The [*Interval Container Library (ICL)] provides __itvs__ and two kinds of 
+interval containers: __itv_sets__ and __itv_maps__.
+
+* An __itv_bset__ is a *set* that is implemented as a set of intervals.
+* An __itv_bmap__ is a *map* that is implemented as a map of interval value pairs.
+
+[h4 Two Aspects]
+
+__Itv_bsets__ and __itv_bmaps__ expose two different aspects in
+their interfaces: (1) The functionality of a set or a map, which is the more 
+['*abstract aspect*]. And (2) the functionality of a container of intervals which
+is the more specific and ['*implementation related aspect*]. In practice both 
+aspects are useful and are therefore supported. 
+
+The first aspect, that will be called __bi_conceptual__ ['*aspect*], is the more important one.
+It means that we can use an __itv_set__ or __itv_map__ like a 
+set or map ['*of elements*]. It exposes the same functions.
+``
+interval_set<int> mySet;
+mySet.insert(42);
+bool has_answer = contains(mySet, 42);
+``
+
+
+The second aspect, that will be called __bi_iterative__ ['*aspect*], allows to exploit the
+fact, that the elements of __itv_sets__ and __itv_maps__ are clustered in
+['*intervals*] or ['*segments*] that we can iterate over.
+
+``
+// Switch on my favorite telecasts using an interval_set
+interval<seconds>::type news(make_seconds("20:00:00"), make_seconds("20:15:00"));
+interval<seconds>::type talk_show(make_seconds("22:45:30"), make_seconds("23:30:50"));
+interval_set<seconds> myTvProgram;
+myTvProgram.add(news).add(talk_show);
+
+// Iterating over elements (seconds) would be silly ...
+for(interval_set<seconds>::iterator telecast = myTvProgram.begin(); 
+    telecast != myTvProgram.end(); ++telecast)
+    //...so this iterates over intervals
+   TV.switch_on(*telecast);
+``
+
+Working with __itv_bsets__ and __itv_bmaps__ can be 
+beneficial whenever the elements of 
+sets appear in contiguous chunks: __itvs__. This is obviously the 
+case in many problem domains, particularly in fields that deal with 
+computations related to date and time.
+
+[h4 Addabitlity and Subtractability]
+
+Unlike `std::sets` and `maps`, __itv_bsets__ and __itv_bmaps__ implement
+concept `Addable` and `Subtractable`. So __itv_bsets__ define an 
+`operator +=` that is naturally implemented as ['*set union*] and an
+`operator -=` that is consequently implemented as ['*set difference*].
+In the *Icl* __itv_bmaps__ are addable and subtractable as well. 
+It turned out to be a very fruitful concept to propagate the
+addition or subtraction to the __itv_bmap_s__ associated values
+in cases where the insertion of an interval value pair into an
+__itv_map__ resulted in a collision of the inserted interval
+value pair with interval value pairs, that are already in the 
+__itv_map__. This operation propagation is called ['*aggregate on overlap*].
+
+  
+[h4 Aggregate on Overlap]
+
+This is a first motivating example of a very small party, demonstrating the 
+['*aggregate on overlap*] principle ['*(aggrovering)*] on __itv_maps__:
+
+In the example Mary enters the party first. She attends during the 
+time interval `[20:00,22:00)`. Harry enters later. He stays within `[21:00,23:00)`.
+``
+typedef std::set<string> guests;
+interval_map<time, guests> party; 
+party += make_pair(interval<time>::right_open(time("20:00"), time("22:00")), guests("Mary"));
+party += make_pair(interval<time>::right_open(time("21:00"), time("23:00")), guests("Harry")); 
+// party now contains
+[20:00, 21:00)->{"Mary"} 
+[21:00, 22:00)->{"Harry","Mary"} //guest sets aggregated on overlap
+[22:00, 23:00)->{"Harry"}
+``
+['*On overlap of intervals*], the corresponding name sets are ['*accumulated*]. At
+the ['*points of overlap*] the intervals are ['*split*]. The accumulation of content on
+overlap of intervals is done via an `operator +=` that has to be implemented
+for the associated values of the __itv_map__. In the example
+the associated values are `guest sets`. Thus a `guest set` has to implement
+`operator +=` as set union. 
+
+As can be seen from the example an __itv_map__ has both 
+a ['*decompositional behavior*] (on the time dimension) as well as 
+an ['*accumulative one*] (on the associated values). 
+
+Addability and aggregate on overlap are useful features on 
+__itv_maps__ implemented via function `add` and `operator +=`. 
+But you can also use them with the ['traditional] 
+[link boost_icl.function_reference.insertion insert semantics] 
+that behaves like `std::map::insert` generalized for 
+interval insertion.
+
+[endsect]
+
+[section Icl's class templates]
+
+In addition to interval containers the *icl* provides element containers
+__icl_set__ and __icl_map__. 
+
+* An __icl_set__ is behavioral equal to __itv_bsets__ on the __bi_conceptual__ aspect.
+
+* An __icl_map__ is behavioral equal to __itv_bmaps__ on the __bi_conceptual__  aspect. 
+  Specifically an __icl_map__
+  implements ['*aggregate on overlap*], which is
+  named ['*aggregate on collision*] for an element container.
+
+The following table gives an overview over the main
+class templates provided by the *icl*.  
+
+[table Synopsis over the icl's class templates
+[[granularity][style]     [sets]           [maps]           ]
+[[interval]   []          [__itv__]        []               ]            
+[[]           [joining]   [__itv_set__]    [__itv_map__]    ]
+[[]           [separating][__sep_itv_set__][]               ]
+[[]           [splitting] [__spl_itv_set__][__spl_itv_map__]]
+[[element]    []          [__ele_set__]    [__ele_map__]    ]
+]                                   
+
+__Itv__ is placed deliberately in column *sets* because an
+interval is a set as well. Column ['*style*] refers to
+the different ways in which interval containers combine added
+intervals. These ['*combining styles*] are described in the next
+section.
+
+[endsect]
+
+[section Interval Combining Styles]
+
+When we add intervals or interval value pairs to interval containers,
+the intervals can be added in different ways: Intervals can be
+joined or split or kept separate. The different interval combining
+styles are shown by example in the tables below.
+
+[table Interval container's ways to combine intervals 
+    [[]         [joining]       [separating]            [splitting]]
+    [[set]      [[classref boost::icl::interval_set          interval_set]]  
+                [[classref boost::icl::separate_interval_set separate_interval_set]] 
+                [[classref boost::icl::split_interval_set    split_interval_set]]]
+    [[map]      [[classref boost::icl::interval_map          interval_map]]      
+                []   
+                [[classref boost::icl::split_interval_map    split_interval_map]]]
+    [[]         [Intervals are joined on overlap or touch\n(if associated values are equal).]
+                [Intervals are joined on overlap, not on touch.]
+                [Intervals are split on overlap.\nAll interval borders are preserved.]]
+]
+
+[table Interval combining styles by example
+    [[]         [joining]       [separating]            [splitting]]
+    [[set]      [[classref boost::icl::interval_set          interval_set] /A/]  
+                [[classref boost::icl::separate_interval_set separate_interval_set] /B/] 
+                [[classref boost::icl::split_interval_set    split_interval_set] /C/]]
+[[]            
+[``
+  {[1      3)          }
++       [2      4)
++                 [4 5)
+= {[1                5)}``]
+[``
+  {[1      3)}         }
++       [2      4)
++                 [4 5)
+= {[1           4)[4 5)}``]
+[``
+  {[1      3)          }
++       [2      4)
++                 [4 5)
+= {[1 2)[2 3)[3 4)[4 5)}``]
+]
+
+    [[map]      [[classref boost::icl::interval_map          interval_map] /D/]      
+                []   
+                [[classref boost::icl::split_interval_map    split_interval_map] /E/]]
+
+[[]            
+[``
+  {[1      3)->1          }
++       [2      4)->1
++                 [4 5)->1
+= {[1 2)[2 3)[3      5)   }
+  | ->1  ->2     ->1      |``]
+[]
+[``
+  {[1      3)->1          }
++       [2      4)->1
++                 [4 5)->1
+= {[1 2)[2 3)[3 4)[4 5)   }
+  | ->1  ->2  ->1  ->1    |``]
+]
+]
+
+Note that =interval_sets= /A/, /B/ and /C/ represent the same set of elements ={1,2,3,4}= 
+and =interval_maps= /D/ and /E/ represent the same map of elements [^{1->1, 2->2, 3->1, 4->1}].
+See example program [link boost_icl.examples.interval_container Interval container]
+for an additional demo.
+
+[h4 Joining interval containers]
+
+__Itv_set__ and __itv_map__ are always 
+in a ['*minimal representation*]. This is useful in many cases, where the 
+points of insertion or intersection of intervals are not relevant. So in most 
+instances __itv_set__ and 
+__itv_map__ will be the first choice 
+for an interval container.
+
+[h4 Splitting interval containers]
+
+__Spl_itv_set__ and __spl_itv_map__ on the contrary 
+have an ['*insertion memory*]. They do accumulate interval borders both 
+from additions and intersections. This is specifically useful, if we want
+to enrich an interval container with certain time grids, like e.g. months 
+or calendar weeks or both. See example [link boost_icl.examples.month_and_week_grid time grids for months and weeks].
+
+[h4 Separating interval containers]
+
+__Sep_itv_set__ implements the separating style.
+This style preserves borders, that are never passed by an overlapping
+interval. So if all intervals that are inserted into a __sep_itv_set__ 
+are generated form a certain grid that never pass say month borders, then
+these borders are preserved in the __sep_itv_set__.
+ 
+[endsect]
+
+[endsect][/ Introduction]
+
+

Added: trunk/libs/icl/doc/projects.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/projects.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,503 @@
+[/
+    Copyright (c) 2009-2009 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 Projects]
+
+['*Projects*] are examples on the usage of interval containers
+that go beyond small toy snippets of code. The code presented
+here addresses more serious applications that approach the
+quality of real world programming. At the same time it aims to
+guide the reader more deeply into various aspects of 
+the library. In order not to overburden the reader with implementation
+details, the code in ['*projects*] tries to be ['*minimal*]. It has a focus on
+the main aspects of the projects and is not intended to be complete 
+and mature like the library code itself. Cause it's minimal,
+project code lives in `namespace mini`.
+
+[/ 
+[section Overview]
+
+[table Overview over Icl Examples
+    [[level]   [example] [classes] [features]]
+    [[basic]   [[link boost_icl.examples.large_bitset Large Bitset]]
+        [__itv_map__][The most simple application of an interval map: 
+                      Counting the overlaps of added intervals.]]
+]
+
+[endsect][/ Overview IN Projects]
+]
+
+[section Large Bitset][/ IN Projects]
+
+Bitsets are just sets. Sets of unsigned integrals, 
+to be more precise. 
+The prefix ['*bit*] usually only indicates,
+that the representation of those sets is organized in a compressed
+form that exploits the fact, that we can switch on an off single
+bits in machine words. Bitsets are therefore known to be very small
+and thus efficient.
+The efficiency of bitsets is usually coupled to the 
+precondition that the range of values of elements  
+is relatively small, like [0..32) or [0..64), values that can
+be typically represented in single or a small number of
+machine words. If we wanted to represent a set containing
+two values {1, 1000000}, we would be much better off using
+other sets like e.g. an `std::set`.
+
+Bitsets compress well, if elements spread over narrow ranges
+only. Interval sets compress well, if many elements are clustered
+over intervals. They can span large sets very efficiently then.
+In project ['*Large Bitset*] we want to ['*combine the bit compression
+and the interval compression*] to achieve a set implementation, 
+that is capable of spanning large chunks of contiguous elements 
+using intervals and also to represent more narrow ['nests] of varying 
+bit sequences using bitset compression.
+As we will see, this can be achieved using only a small
+amount of code because most of the properties we need
+are provided by an __itv_map__ of `bitsets`:
+
+``
+typedef interval_map<IntegralT, SomeBitSet<N>, partial_absorber,
+                     std::less, inplace_bit_add, inplace_bit_and> IntervalBitmap;
+``
+
+Such an `IntervalBitmap` represents `k*N` bits for every segment. 
+``
+[a, a+k)->'1111....1111' // N bits associated: Represents a total of k*N bits.  
+``
+
+For the interval `[a, a+k)` above all bits are set.
+But we can also have individual ['nests] or ['clusters]
+of bitsequences.
+
+``
+[b,  b+1)->'01001011...1'
+[b+1,b+2)->'11010001...0'
+. . .
+``
+
+and we can span intervals of equal bit sequences that represent
+periodic patterns.
+
+``
+[c,d)->'010101....01'  // Every second bit is set              in range [c,d)
+[d,e)->'001100..0011'  // Every two bits alterate              in range [d,e)
+[e,f)->'bit-sequence'  // 'bit-sequence' reoccurs every N bits in range [e,f)
+``
+
+An `IntervalBitmap` can represent
+`N*(2^M)` elements, if `M` is the number of bits of the 
+integral type `IntegralT`. Unlike bitsets, that usually
+represent ['*unsigned*] integral numbers, large_bitset may 
+range over negative numbers as well.
+There are fields where such large
+bitsets implementations are needed. E.g. for the compact
+representation of large file allocation tables.
+What remains to be done for project *Large Bitset* is
+to code a wrapper `class large_bitset` around `IntervalBitmap`
+so that `large_bitset` looks and feels like a usual
+set class.
+
+[section Using large_bitset]
+
+To quicken your appetite for a look at the implementation
+here are a few use cases first. Within the examples that follow,
+we will use `nat`[^['k]] for unsigned integrals 
+and `bits`[^['k]] for bitsets containing [^['k]] bits.
+
+Let's start large.
+In the first example . . . 
+
+[import ../example/large_bitset_/large_bitset.cpp]
+[large_bitset_test_large_set_all]
+
+. . . we are testing the limits. First we set all bits and
+then we switch off the very last bit.
+
+[large_bitset_test_large_erase_last]
+
+Program output (/a little beautified/):
+``
+----- Test function test_large() -----------------------------------------------
+We have just turned on the awesome amount of 18,446,744,073,709,551,616 bits ;-)
+[                 0, 288230376151711744) -> 1111111111111111111111111111111111111111111111111111111111111111
+---- Let's swich off the very last bit -----------------------------------------
+[                 0, 288230376151711743) -> 1111111111111111111111111111111111111111111111111111111111111111
+[288230376151711743, 288230376151711744) -> 1111111111111111111111111111111111111111111111111111111111111110
+---- Venti is plenty ... let's do something small: A tall ----------------------
+``
+
+More readable is a smaller version of `large_bitset`.
+In function `test_small()` we apply a few more operations . . .
+
+[large_bitset_test_small]
+
+. . . producing this output:
+``
+----- Test function test_small() -----------
+-- Switch on all bits in range [0,64] ------
+[0,8)->11111111
+[8,9)->10000000
+--------------------------------------------
+-- Turn off bits: 25,27,28 -----------------
+[0,3)->11111111
+[3,4)->10100111
+[4,8)->11111111
+[8,9)->10000000
+--------------------------------------------
+-- Flip bits in range [24,30) --------------
+[0,3)->11111111
+[3,4)->01011011
+[4,8)->11111111
+[8,9)->10000000
+--------------------------------------------
+-- Remove the first 10 bits ----------------
+[1,2)->00111111
+[2,3)->11111111
+[3,4)->01011011
+[4,8)->11111111
+[8,9)->10000000
+-- Remove even bits in range [0,72) --------
+[1,2)->00010101
+[2,3)->01010101
+[3,4)->01010001
+[4,8)->01010101
+--    Set odd  bits in range [0,72) --------
+[0,9)->01010101
+--------------------------------------------
+``
+
+Finally, we present a little /picturesque/ example, 
+that demonstrates that `large_bitset` can also serve
+as a self compressing bitmap, that we can 'paint' with.
+
+[large_bitset_test_picturesque]
+
+Note that we have two `large_bitsets` for the /outline/ 
+and the /interior/. Both parts are compressed but we can
+compose both by `operator +`, because the right /positions/
+are provided. This is the program output:
+
+``
+----- Test function test_picturesque() -----
+-------- empty face:       3 intervals -----
+********
+*      *
+*      *
+*      *
+*      *
+ ******
+-------- compressed smile: 2 intervals -----
+  *  *
+  ****
+-------- staring bitset:   6 intervals -----
+********
+*      *
+* *  * *
+*      *
+* **** *
+ ******
+--------------------------------------------
+``
+
+So, may be you are curious how this class template
+is coded on top of __itv_map__ using only about 250 lines 
+of code. This is shown in the sections that follow.
+
+[endsect][/ Usage of a large_bitset]
+
+[section The interval_bitmap]
+
+To begin, let's look at the basic data type again, that
+will be providing the major functionality:
+
+``
+typedef interval_map<DomainT, BitSetT, partial_absorber,
+                     std::less, inplace_bit_add, inplace_bit_and> IntervalBitmap;
+``
+
+`DomainT` is supposed to be an integral
+type, the bitset type `BitSetT` will be a wrapper class around an
+unsigned integral type. `BitSetT` has to implement bitwise operators
+that will be called by the functors `inplace_bit_add<BitSetT>` 
+and `inplace_bit_and<BitSetT>`.
+The type trait of interval_map is `partial_absorber`, which means
+that it is /partial/ and that empty `BitSetTs` are not stored in
+the map. This is desired and keeps the `interval_map` minimal, storing
+only bitsets, that contain at least one bit switched on. 
+Functor template `inplace_bit_add` for parameter `Combine` indicates that we
+do not expect `operator +=` as addition but the bitwise operator
+`|=`. For template parameter `Section` which is instaniated by 
+`inplace_bit_and` we expect the bitwise `&=` operator.
+
+[endsect][/ section The interval_bitmap]
+
+[section A class implementation for the bitset type]
+
+The code of the project is enclosed in a `namespace mini`.
+The name indicates, that the implementation is a /minimal/
+example implementation. The name of the bitset class will
+be `bits` or `mini::bits` if qualified.
+
+To be used as a codomain parameter of class template __itv_map__,
+`mini::bits` has to implement all the functions that are required
+for a codomain_type in general, which are the default constructor `bits()`
+and an equality `operator==`. Moreover `mini::bits` has to implement operators
+required by the instantiations for parameter `Combine` and `Section`
+which are `inplace_bit_add` and `inplace_bit_and`. From functors
+`inplace_bit_add` and `inplace_bit_and` there are inverse functors
+`inplace_bit_subtract` and `inplace_bit_xor`. Those functors 
+use operators `|= &= ^=` and `~`. Finally if we want to apply
+lexicographical and subset comparison on large_bitset, we also
+need an `operator <`. All the operators that we need can be implemented
+for `mini::bits` on a few lines:
+
+[import ../example/large_bitset_/bits.hpp]
+[mini_bits_class_bits]
+
+Finally there is one important piece of meta information, we have 
+to provide: `mini::bits` has to be recognized as a `Set` by the
+icl code. Otherwise we can not exploit the fact that a map of
+sets is model of `Set` and the resulting large_bitset would not
+behave like a set. So we have to say that `mini::bits` shall be sets:
+
+[mini_bits_is_set]
+
+This is done by adding a partial template specialization to
+the type trait template `icl::is_set`.
+For the extension of this type trait template and the result
+values of inclusion_compare we need these `#includes` for the
+implementation of `mini::bits`:
+ 
+[mini_bits_includes]
+ 
+[endsect][/ A class implementation for the bitset type]
+
+[section Implementation of a large bitset]
+
+Having finished our `mini::bits` implementation, we can start to
+code the wrapper class that hides the efficient interval map of mini::bits
+and exposes a simple and convenient set behavior to the world of users.
+
+Let's start with the required `#include`s this time:
+
+[import ../example/large_bitset_/large_bitset.hpp]
+[large_bitset_includes]
+
+Besides `boost/icl/interval_map.hpp` and `bits.hpp` the most important
+include here is `boost/operators.hpp`. We use this library in order
+to further minimize the code and to provide pretty extensive operator
+functionality using very little code.
+
+For a short and concise naming of the most important unsigned integer
+types and the corresponding `mini::bits` we define this:
+
+[large_bitset_natural_typedefs]
+
+[section large_bitset: Public interface][/ ------------------------------------]
+
+And now let's code `large_bitset`. 
+
+[large_bitset_class_template_header]
+
+The first template parameter `DomainT` will be instantiated with
+an integral type that defines the kind of numbers that can
+be elements of the set. Since we want to go for a large set we
+use `nat64` as default which is a 64 bit unsigned integer ranging
+from `0` to `2^64-1`. As bitset parameter we also choose a 64-bit
+default. Parameters `Combine` and `Interval` are necessary to
+be passed to dependent type expressions. An allocator can be
+chosen, if desired.
+
+The nested list of private inheritance contains groups of template
+instantiations from 
+[@http://www.boost.org/doc/libs/1_39_0/libs/utility/operators.htm Boost.Operator], 
+that provides derivable operators from more fundamental once.
+Implementing the fundamental operators, we get the derivable ones
+/for free/. Below is a short overview of what we get using Boost.Operator,
+where __S stands for `large_bitset`, __i for it's `interval_type` 
+and __e for it's `domain_type` or `element_type`.
+
+[table
+[[Group                    ][fundamental]      [derivable     ]]
+[[Equality, ordering       ][`==`]             [`!=`          ]]
+[[                         ][`<` ]             [`> <= >=`     ]]
+[[Set operators (__S x __S)][`+= |= -= &= ^=` ][`+ | - & ^`   ]]
+[[Set operators (__S x __e)][`+= |= -= &= ^=` ][`+ | - & ^`   ]]
+[[Set operators (__S x __i)][`+= |= -= &= ^=` ][`+ | - & ^`   ]]
+]
+
+There is a number of associated types
+
+[large_bitset_associated_types]
+
+most importantly the implementing `interval_bitmap_type` that is used
+for the implementing container.
+
+[large_bitmap_impl_map]
+
+In order to use
+[@http://www.boost.org/doc/libs/1_39_0/libs/utility/operators.htm Boost.Operator]
+we have to implement the fundamental operators as class members. This can be
+done quite schematically.
+
+[large_bitset_operators]
+
+As we can see, the seven most important operators that work on the
+class type `large_bitset` can be directly implemented by propagating
+the operation to the implementing `_map`
+of type `interval_bitmap_type`. For the operators that work on segment and
+element types, we use member functions `add`, `subtract`, `intersect` and
+`flip`. As we will see only a small amount of adaper code is needed
+to couple those functions with the functionality of the implementing
+container.
+
+Member functions `add`, `subtract`, `intersect` and `flip`, 
+that allow to combine ['*intervals*] to `large_bitsets` can
+be uniformly implemented using a private function
+`segment_apply` that applies /addition/, /subtraction/,
+/intersection/ or /symmetric difference/, after having
+translated the interval's borders into the right bitset
+positions.  
+
+[large_bitset_fundamental_functions]
+
+In the sample programs, that we will present to demonstrate
+the capabilities of `large_bitset` we will need a few additional
+functions specifically output functions in two different
+flavors.
+
+[large_bitset_demo_functions]
+
+* The first one, `show_segments()` shows the container 
+content as it is implemented, in the compressed form.
+
+* The second function `show_matrix` shows the complete
+matrix of bits that is represented by the container.
+
+[endsect][/ large_bitset: Public interface] 
+[section large_bitset: Private implementation]  [/ -------------------------------------]
+
+In order to implement operations like the addition of 
+an element say `42` to
+the large bitset, we need to translate the /value/ to the
+/position/ of the associated *bit* representing `42` in the
+interval container of bitsets. As an example, suppose we
+use a
+``
+large_bitset<nat, mini::bits8> lbs;
+``
+that carries small bitsets of 8 bits only. 
+The first four interval of `lbs` are assumed to
+be associated with some bitsets. Now we want to add the interval
+`[a,b]==[5,27]`. This will result in the following situation:
+``
+   [0,1)->   [1,2)->   [2,3)->   [3,4)->   
+   [00101100][11001011][11101001][11100000]
++       [111  11111111  11111111  1111]      [5,27] as bitset
+         a                           b
+         
+=> [0,1)->   [1,3)->   [3,4)->
+   [00101111][11111111][11110000]
+``
+So we have to convert values 5 and 27 into a part that
+points to the interval and a part that refers to the
+position within the interval, which is done by a
+/division/ and a /modulo/ computation. (In order to have a
+consistent representation of the bitsequences across the containers,
+within this project, bitsets are denoted with the
+['*least significant bit on the left!*])
+
+``
+A = a/8 =  5/8 = 0 // refers to interval 
+B = b/8 = 27/8 = 3
+R = a%8 =  5%8 = 5 // refers to the position in the associated bitset.
+S = b%8 = 27%8 = 3
+``
+
+All /division/ and /modulo operations/ needed here are always done
+using a divisor `d` that is a power of `2`: `d = 2^x`. Therefore
+division and modulo can be expressed by bitset operations.
+The constants needed for those bitset computations are defined here:
+ 
+[large_bitset_impl_constants]
+
+Looking at the example again, we can see that we have to identify the
+positions of the beginning and ending of the interval [5,27] that is
+to insert, and then ['*subdivide*] that range of bitsets into three partitions.
+
+# The bitset where the interval starts.
+# the bitset where the interval ends
+# The bitsets that are completely overlapped by the interval
+
+``
+combine interval [5,27] to large_bitset lbs w.r.t. some operation o
+
+   [0,1)->   [1,2)->   [2,3)->   [3,4)->   
+   [00101100][11001011][11101001][11100000]
+o       [111  11111111  11111111  1111]
+         a                           b
+subdivide:
+   [first!  ][mid_1] . . .[mid_n][   !last]
+   [00000111][1...1] . . .[1...1][11110000]
+``
+
+After subdividing, we perform the operation `o` as follows:
+
+# For the first bitset: Set all bits from ther starting bit (`!`)
+  to the end of the bitset to `1`. All other bits are `0`. Then
+  perform operation `o`: `_map o= ([0,1)->00000111)`
+  
+# For the last bitset: Set all bits from the beginning of the bitset
+  to the ending bit (`!`) to `1`. All other bits are `0`. Then
+  perform operation `o`: `_map o= ([3,4)->11110000)`
+  
+# For the range of bitsets in between the staring and ending one,
+  perform operation `o`: `_map o= ([1,3)->11111111)`
+
+The algorithm, that has been outlined and illustrated by the 
+example, is implemented by the private member function
+`segment_apply`. To make the combiner operation a variable
+in this algorithm, we use a /pointer to member function type/
+
+[large_bitset_segment_combiner]
+
+as first function argument. We will pass member functions `combine_` here, 
+``
+combine_(first_of_interval, end_of_interval, some_bitset);
+``
+that take the beginning and ending of an interval and a bitset and combine
+them to the implementing `interval_bitmap_type _map`. Here are these functions:
+
+[large_bitmap_combiners]
+
+Finally we can code function `segment_apply`, that does the partitioning
+and subsequent combining:
+
+[large_bitset_segment_apply]
+
+The functions that help filling bitsets to and from a given bit are 
+implemented here:
+[large_bitset_bitset_filler]
+
+This completes the implementation of class template `large_bitset`.
+Using only a small amount of mostly schematic code,
+we have been able to provide a pretty powerful, self compressing
+and generally usable set type for all integral domain types. 
+
+[endsect][/ large_bitset: Private implementation]
+
+[endsect][/ Implementation of a large bitset]
+
+[endsect][/ Large Bitsets IN Projects]
+
+
+[endsect][/ Projects]
+
+
+

Added: trunk/libs/icl/doc/semantics.qbk
==============================================================================
--- (empty file)
+++ trunk/libs/icl/doc/semantics.qbk	2010-11-07 12:38:20 EST (Sun, 07 Nov 2010)
@@ -0,0 +1,760 @@
+[/
+    Copyright (c) 2008-2009 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 Semantics]
+
+["Beauty is the ultimate defense against complexity] -- [/David Gelernter]
+[@http://en.wikipedia.org/wiki/David_Gelernter David Gelernter]
+
+In the *icl* we follow the notion, that the semantics of a ['*concept*] or
+['*abstract data type*] can be expressed by ['*laws*]. We formulate
+laws over interval containers that can be evaluated for a given
+instantiation of the variables contained in the law. The following
+pseudocode gives a shorthand notation of such a law.
+``
+Commutativity<T,+>:
+T a, b; a + b == b + a;
+``
+This can of course be coded as a proper c++ class template which has 
+been done for the validation of the *icl*. For sake of simplicity 
+we will use pseudocode here.
+
+The laws that describe the semantics of the *icl's* class templates
+were validated using the Law based Test Automaton ['*LaBatea*],
+a tool that generates instances for the law's variables and then
+tests it's validity.  
+Since the *icl* deals with sets, maps and relations, that are
+well known objects from mathematics, the laws that we are
+using are mostly /recycled/ ones. Also some of those laws are grouped
+in notions like e.g. /orderings/ or /algebras/.
+
+[section Orderings and Equivalences]
+
+[h4 Lexicographical Ordering and Equality]
+
+On all set and map containers of the icl, there is an `operator <`
+that implements a
+[@http://www.sgi.com/tech/stl/StrictWeakOrdering.html strict weak ordering].
+[/ (see also [@http://en.wikipedia.org/wiki/Strict_weak_ordering here]).]
+The semantics of `operator <` is the same as for an stl's
+[@http://www.sgi.com/tech/stl/SortedAssociativeContainer.html SortedAssociativeContainer], 
+specifically
+[@http://www.sgi.com/tech/stl/set.html stl::set] 
+and 
+[@http://www.sgi.com/tech/stl/map.html stl::map]:
+``
+Irreflexivity<T,< > : T a;     !(a<a)
+Asymmetry<T,< >     : T a,b;   a<b implies !(b<a)
+Transitivity<T,< >  : T a,b,c; a<b && b<c implies a<c
+``
+
+`Operator <` depends on the icl::container's template parameter
+`Compare` that implements a ['strict weak ordering] for the container's
+`domain_type`.
+For a given `Compare` ordering, `operator <` implements a 
+lexicographical comparison on icl::containers, that uses the 
+`Compare` order to establish a unique sequence of values in 
+the container. 
+
+The induced equivalence of `operator <` is 
+lexicographical equality 
+which is implemented as `operator ==`. 
+``
+//equivalence induced by strict weak ordering <
+!(a<b) && !(b<a) implies a == b;
+``
+Again this
+follows the semantics of the *stl*.
+Lexicographical equality is stronger than the equality
+of elements. Two containers that contain the same elements
+can be lexicographically unequal, if their elements are
+differently sorted. Lexicographical comparison belongs to 
+the __bi_iterative__ aspect. Of all the different sequences that are valid 
+for unordered sets and maps, one such sequence is
+selected by the `Compare` order of elements. Based on
+this selection a unique iteration is possible.
+
+[h4 Subset Ordering and Element Equality]
+
+On the __conceptual__ aspect only membership of elements
+matters, not their sequence. So there are functions
+`contained_in` and `element_equal` that implement
+the subset relation and the equality on elements.
+Yet, `contained_in` and `is_element_equal` functions are not
+really working on the level of elements. They also
+work on the basis of the containers templates
+`Compare` parameter. In practical terms we need to
+distinguish between lexicographical equality 
+`operator ==` and equality of elements `is_element_equal`,
+if we work with interval splitting interval containers:
+``
+split_interval_set<time> w1, w2; //Pseudocode
+w1 = {[Mon       ..       Sun)}; //split_interval_set containing a week
+w2 = {[Mon .. Fri)[Sat .. Sun)}; //Same week split in work and week end parts.
+w1 == w2;                        //false: Different segmentation
+is_element_equal(w1,w2);         //true:  Same elements contained  
+``   
+
+For a constant `Compare` order on key elements,
+member function `contained_in` that is defined for all 
+icl::containers implements a
+[@http://en.wikipedia.org/wiki/Partially_ordered_set partial order]
+on icl::containers.
+
+``
+with <= for contained_in,
+    =e= for is_element_equal:
+Reflexivity<T,<= >     : T a;     a <= a
+Antisymmetry<T,<=,=e=> : T a,b;   a <= b && b <= a implies a =e= b 
+Transitivity<T,<= >    : T a,b,c; a <= b && b <= c implies a <= c
+``
+
+The induced equivalence is the equality of elements that
+is implemented via function `is_element_equal`.
+``
+//equivalence induced by the partial ordering contained_in on icl::container a,b
+a.contained_in(b) && b.contained_in(a) implies is_element_equal(a, b);
+``
+
+[endsect][/ Orderings and Equivalences]
+
+[section Sets]
+
+For all set types `S` that are models concept `Set`  
+(__icl_set__, __itv_set__, __sep_itv_set__ and __spl_itv_set__)
+most of the well known mathematical 
+[@http://en.wikipedia.org/wiki/Algebra_of_sets laws on sets]
+were successfully checked via LaBatea. The next tables 
+are giving an overview over the checked laws ordered by
+operations. If possible, the laws are formulated with
+the stronger lexicographical equality (`operator ==`)
+which implies the law's validity for the weaker
+element equality `is_element_equal`. Throughout this
+chapter we will denote element equality as `=e=` instead
+of `is_element_equal` where a short notation is advantageous.
+
+[h5 Laws on set union]
+
+For the operation ['*set union*] available as 
+`operator +, +=, |, |=` and the neutral element
+`neutron<S>::value()` which is the empty set `S()`
+these laws hold:
+``
+Associativity<S,+,== >: S a,b,c; a+(b+c) == (a+b)+c
+Neutrality<S,+,== >   : S a;       a+S() == a
+Commutativity<S,+,== >: S a,b;       a+b == b+a
+``
+
+[h5 Laws on set intersection]
+
+For the operation ['*set intersection*] available as 
+`operator &, &=` these laws were validated:
+
+``
+Associativity<S,&,== >: S a,b,c; a&(b&c) == (a&b)&c
+Commutativity<S,&,== >: S a,b;       a&b == b&a
+``
+
+[/ FYI
+Neutrality has *not* been validated to avoid 
+additional requirements on the sets template
+parameters.] 
+
+[h5 Laws on set difference]
+
+For set difference there are only these laws. It is
+not associative and not commutative. It's neutrality
+is non symmetrical.
+
+``
+RightNeutrality<S,-,== > : S a;   a-S() == a
+Inversion<S,-,== >:        S a;   a - a == S()
+``
+
+Summarized in the next table are laws that use `+`, `&` and `-`
+as a single operation. For all validated laws,
+the left and right hand sides of the equations
+are lexicographically equal, as denoted by `==` in the cells
+of the table.
+
+``
+                 +    &   -
+Associativity    ==   == 
+Neutrality       ==       ==
+Commutativity    ==   ==
+Inversion                 ==
+``
+
+[h5 Distributivity Laws]
+
+Laws, like distributivity, that use more than one operation can
+sometimes be instantiated for different sequences of operators
+as can be seen below. In the two instantiations of the distributivity
+laws operators `+` and `&` are swapped. So we can have small operator
+signatures like `+,&` and `&,+` to describe such instantiations,
+which will be used below.
+Not all instances of distributivity laws hold for lexicographical equality.
+Therefore they are denoted using a /variable/ equality `=v=` below.
+
+``
+     Distributivity<S,+,&,=v= > : S a,b,c; a + (b & c) =v= (a + b) & (a + c)
+     Distributivity<S,&,+,=v= > : S a,b,c; a & (b + c) =v= (a & b) + (a & c)
+RightDistributivity<S,+,-,=v= > : S a,b,c; (a + b) - c =v= (a - c) + (b - c)
+RightDistributivity<S,&,-,=v= > : S a,b,c; (a & b) - c =v= (a - c) & (b - c)
+``
+
+The next table shows the relationship between 
+law instances, 
+[link boost_icl.introduction.interval_combining_styles interval combining style]
+and the 
+used equality relation.
+
+``
+                                  +,&    &,+
+     Distributivity  joining      ==     ==
+                     separating   ==     ==
+                     splitting    =e=    =e=
+                     
+                                  +,-    &,-
+RightDistributivity  joining      ==     ==
+                     separating   ==     ==
+                     splitting    =e=    ==
+``
+
+The table gives an overview over 12 instantiations of
+the four distributivity laws and shows the equalities 
+which the instantiations holds for. For instance
+`RightDistributivity` with operator signature `+,-`
+instantiated for __spl_itv_sets__ holds only for
+element equality (denoted as `=e=`):
+``
+RightDistributivity<S,+,-,=e= > : S a,b,c; (a + b) - c =e= (a - c) + (b - c)
+``
+The remaining five instantiations of `RightDistributivity`
+are valid for lexicographical equality (demoted as `==`) as well.
+
+[link boost_icl.introduction.interval_combining_styles Interval combining styles]
+correspond to containers according to
+``
+style       set
+joining     interval_set
+separating  separate_interval_set
+splitting   split_interval_set
+``
+
+
+Finally there are two laws that combine all three major set operations:
+De Mogans Law and Symmetric Difference.
+
+[h5 DeMorgan's Law]
+
+De Morgans Law is better known in an incarnation where the unary
+complement operation `~` is used. `~(a+b) == ~a * ~b`. The version
+below is an adaption for the binary set difference `-`, which is 
+also called ['*relative complement*].
+``
+DeMorgan<S,+,&,=v= > : S a,b,c; a - (b + c) =v= (a - b) & (a - c)
+DeMorgan<S,&,+,=v= > : S a,b,c; a - (b & c) =v= (a - b) + (a - c)
+``
+
+``
+                         +,&     &,+
+DeMorgan  joining        ==      ==
+          separating     ==      =e=
+          splitting      ==      =e=
+``
+
+Again not all law instances are valid for lexicographical equality.
+The second instantiations only holds for element equality, if
+the interval sets are non joining.
+
+[h5 Symmetric Difference]
+
+``
+SymmetricDifference<S,== > : S a,b,c; (a + b) - (a & b) == (a - b) + (b - a)
+``
+
+Finally Symmetric Difference holds for all of icl set types and
+lexicographical equality.
+
+[/ pushout laws]
+
+[endsect][/ Sets]
+
+[section Maps]
+
+By definition a map is set of pairs. So we would expect maps to
+obey the same laws that are valid for sets. Yet
+the semantics of the *icl's* maps may be a different one, because
+of it's aggregating facilities, where the aggregating combiner
+operations are passed to combine the map's associated values.
+It turns out, that the aggregation on overlap principle
+induces semantic properties to icl maps in such a way,
+that the set of equations that are valid will depend on
+the semantics of the type `CodomainT` of the map's associated
+values.
+
+This is less magical as it might seem at first glance.
+If, for instance, we instantiate an __itv_map__ to 
+collect and concatenate
+`std::strings` associated to intervals,
+
+``    
+interval_map<int,std::string> cat_map;
+cat_map += make_pair(interval<int>::rightopen(1,5),std::string("Hello"));
+cat_map += make_pair(interval<int>::rightopen(3,7),std::string(" World"));
+cout << "cat_map: " << cat_map << endl;
+``
+
+we won't be able to apply `operator -=` 
+``
+// This will not compile because string::operator -= is missing.
+cat_map -= make_pair(interval<int>::rightopen(3,7),std::string(" World"));
+``
+because, as std::sting does not implement `-=` itself, this won't compile.
+So all *laws*, that rely on `operator -=` or `-` not only will not be valid they 
+can not even be stated.
+This reduces the set of laws that can be valid for a richer `CodomainT`
+type to a smaller set of laws and thus to a less restricted semantics. 
+
+Currently we have investigated and validated two major instantiations 
+of icl::Maps,
+
+* ['*Maps of Sets*] that will be called ['*Collectors*]  and
+* ['*Maps of Numbers*] which will be called ['*Quantifiers*]
+
+both of which seem to have many interesting use cases for practical
+applications. The semantics associated with the term /Numbers/ 
+is a 
+[@http://en.wikipedia.org/wiki/Monoid commutative monoid] 
+for unsigned numbers
+and a 
+[@http://en.wikipedia.org/wiki/Abelian_group commutative or abelian group]
+for signed numbers.
+From a practical point of view we can think
+of numbers as counting or quantifying the key values 
+of the map.
+
+Icl ['*Maps of Sets*] or ['*Collectors*]
+are models of concept `Set`. This implies that all laws that have been
+stated as a semantics for `icl::Sets` in the previous chapter also hold for
+`Maps of Sets`.
+Icl ['*Maps of Numbers*] or ['*Quantifiers*] on the contrary are not models 
+of concept `Set`.
+But there is a substantial intersection of laws that apply both for
+`Collectors` and `Quantifiers`.
+
+[table
+[[Kind of Map]    [Alias]     [Behavior]                             ]
+[[Maps of Sets]   [Collector] [Collects items *for* key values]      ]
+[[Maps of Numbers][Quantifier][Counts or quantifies *the* key values]]
+]
+
+In the next two sections the law based semantics of ['*Collectors*]
+and ['*Quantifiers*] will be described in more detail.
+
+[endsect][/ Maps]
+
+[section Collectors: Maps of Sets]
+
+Icl `Collectors`, behave like `Sets`. 
+This can be understood easily, if we consider, that
+every map of sets can be transformed to an equivalent
+set of pairs.
+For instance in the pseudocode below map `m`
+``
+icl::map<int,set<int> >  m = {(1->{1,2}), (2->{1})}; 
+``
+is equivalent to set `s`
+``
+icl::set<pair<int,int> > s = {(1,1),(1,2),   //representing 1->{1,2}
+                              (2,1)       }; //representing 2->{1}
+`` 
+
+Also the results of add, subtract and other operations on `map m` and `set s`
+preserves the equivalence of the containers ['*almost*] perfectly:
+``
+m += (1,3); 
+m == {(1->{1,2,3}), (2->{1})}; //aggregated on collision of key value 1
+s += (1,3);
+s == {(1,1),(1,2),(1,3),   //representing 1->{1,2,3}
+      (2,1)             }; //representing 2->{1}
+``
+
+The equivalence of `m` and `s` is only violated if an 
+empty set occurres in `m` by subtraction of a value pair:
+``
+m -= (2,1); 
+m == {(1->{1,2,3}), (2->{})}; //aggregated on collision of key value 2
+s -= (2,1);
+s == {(1,1),(1,2),(1,3)   //representing 1->{1,2,3}
+                       }; //2->{} is not represented in s
+``
+
+This problem can be dealt with in two ways. 
+
+# Deleting value pairs form the Collector, if it's associated value 
+  becomes a neutral value or `neutron`.
+# Using a different equality, called protonic equality in the laws
+  to validate. Protonic equality only 
+  accounts for value pairs that that carry values unequal to the `neutron` value. 
+
+Solution (1) led to the introduction of map traits, particularly trait
+['*partial_absorber*], which is the default setting in all icl's map
+templates.
+
+Solution (2), is applied to check the semantics of icl::Maps for the
+partial_enricher trait that does not delete value pairs that carry
+neutrons. Protonic equality is implemented by a non member function
+called `is_protonic_equal`. Throughout this chapter
+protonic equality in pseudocode and law denotations is denoted
+as `=p=` operator.
+
+The validity of the sets of laws that make up `Set` semantics
+should now be quite evident. So the following text shows the
+laws that are validated for all `Collector` types `C`. Which are
+__icl_map__`<D,S,T>`, __itv_map__`<D,S,T>` and __spl_itv_map__`<D,S,T>`
+where `CodomainT` type `S` is a model of `Set` and `Trait` type `T` is either 
+__pabsorber__ or __penricher__.
+
+
+[h5 Laws on set union, set intersection and set difference]
+
+``
+Associativity<C,+,== >: C a,b,c; a+(b+c) == (a+b)+c
+Neutrality<C,+,== >   : C a;       a+C() == a
+Commutativity<C,+,== >: C a,b;       a+b == b+a
+
+Associativity<C,&,== >: C a,b,c; a&(b&c) ==(a&b)&c
+Commutativity<C,&,== >: C a,b;       a&b == b&a
+
+RightNeutrality<C,-,== >: C a;   a-C() ==  a
+Inversion<C,-,=v= >     : C a;   a - a =v= C()
+``
+
+All the fundamental laws could be validated for all 
+icl Maps in their instantiation as Maps of Sets or Collectors.
+As expected Inversion only holds for protonic equality,
+if the map is not a `partial_absorber`.
+
+``
+                             +    &    -
+Associativity                ==   == 
+Neutrality                   ==        ==
+Commutativity                ==   ==
+Inversion partial_absorber             ==
+          partial_enricher             =p=
+``
+
+[h5 Distributivity Laws]
+
+``
+     Distributivity<C,+,&,=v= > : C a,b,c; a + (b & c) =v= (a + b) & (a + c)
+     Distributivity<C,&,+,=v= > : C a,b,c; a & (b + c) =v= (a & b) + (a & c)
+RightDistributivity<C,+,-,=v= > : C a,b,c; (a + b) - c =v= (a - c) + (b - c)
+RightDistributivity<C,&,-,=v= > : C a,b,c; (a & b) - c =v= (a - c) & (b - c)
+``
+
+Results for the distributivity laws are almost identical to 
+the validation of sets except that
+for a `partial_enricher map` the law `(a & b) - c == (a - c) & (b - c)`
+holds for lexicographical equality.
+
+``
+                                                   +,&    &,+
+     Distributivity  joining                       ==     ==
+                     splitting   partial_absorber  =e=    =e=
+                                 partial_enricher  =e=    ==                     
+                     
+                                                   +,-    &,-
+RightDistributivity  joining                       ==     ==
+                     splitting                     =e=    ==
+``
+
+[h5 DeMorgan's Law and Symmetric Difference]
+
+``
+DeMorgan<C,+,&,=v= > : C a,b,c; a - (b + c) =v= (a - b) & (a - c)
+DeMorgan<C,&,+,=v= > : C a,b,c; a - (b & c) =v= (a - b) + (a - c)
+``
+
+``
+                         +,&     &,+
+DeMorgan  joining        ==      ==
+          splitting      ==      =e=
+``
+
+``
+SymmetricDifference<C,== > : C a,b,c; (a + b) - (a * b) == (a - b) + (b - a)
+``
+
+Reviewing the validity tables above shows, that the sets of valid laws for
+`icl Sets` and `icl Maps of Sets` that are /neutron absorbing/ are exactly the same.
+As expected, only for Maps of Sets that represent empty sets as associated values,
+called /neutron enrichers/, there are marginal semantic differences.
+
+[endsect][/ Collectors]
+
+[section Quantifiers: Maps of Numbers]
+
+[h5 Subtraction on Quantifiers]
+
+With `Sets` and `Collectors` the semantics of  
+`operator -` is
+that of /set difference/ which means, that you can
+only subtract what has been put into the container before.
+With `Quantifiers` that ['*count*] or ['*quantify*]
+their key values in some way, 
+the semantics of `operator -` may be different.
+
+The question is how subtraction should be defined here?
+``
+//Pseudocode:
+icl::map<int,some_number> q = {(1->1)};
+q -= (2->1);
+`` 
+If type `some_number` is `unsigned` a /set difference/ kind of
+subtraction make sense 
+``
+icl::map<int,some_number> q = {(1->1)};
+q -= (2->1);   // key 2 is not in the map so  
+q == {(1->1)}; // q is unchanged by 'aggregate on collision'
+`` 
+If `some_number` is a `signed` numerical type
+the result can also be this
+``
+icl::map<int,some_number> q = {(1->1)};
+q -= (2->1);             // subtracting works like  
+q == {(1->1), (2-> -1)}; // adding the inverse element
+`` 
+As commented in the example, subtraction of a key value
+pair `(k,v)` can obviously be defined as adding the ['*inverse element*]
+for that key `(k,-v)`, if the key is not yet stored in the map.
+
+[h4 Partial and Total Quantifiers and Infinite Vectors]
+
+Another concept, that we can think of, is that in a `Quantifier` 
+every `key_value` is initially quantified `0`-times, where `0` stands
+for the neutral element of the numeric `CodomainT` type.
+Such a `Quantifier` would be totally defined on all values of
+it's `DomainT` type and can be
+conceived as an `InfiniteVector`. 
+
+To create an infinite vector
+that is totally defined on it's domain we can set
+the map's `Trait` parameter to the value __tabsorber__.
+The __tabsorber__ trait fits specifically well with
+a `Quantifier` if it's `CodomainT` has an inverse 
+element, like all signed numerical type have.
+As we can see later in this section this kind of 
+a total `Quantifier` has the basic properties that
+elements of a 
+[@http://en.wikipedia.org/wiki/Vector_space vector space] 
+do provide.
+
+
+[h5 Intersection on Quantifiers]
+
+Another difference between `Collectors` and `Quantifiers`
+is the semantics of `operator &`, that has the meaning of
+set intersection for `Collectors`.
+
+For the /aggregate on overlap principle/ the operation `&`
+has to be passed to combine associated values on overlap
+of intervals or collision of keys. This can not be done
+for `Quantifiers`, since numeric types do not implement
+intersection.
+
+For `CodomainT` types that are not models of `Sets` 
+`operator & ` is defined as ['aggregation on the intersection
+of the domains]. Instead of the `codomain_intersect` functor
+`codomain_combine` is used as aggregation operation: 
+``
+//Pseudocode example for partial Quantifiers p, q:
+interval_map<int,int> p, q;
+p     = {[1     3)->1   };
+q     = {   ([2    4)->1};
+p & q =={    [2 3)->2   };
+``
+So an addition or aggregation of associated values is
+done like for `operator +` but value pairs that have
+no common keys are not added to the result.
+
+For a `Quantifier` that is a model of an `InfiniteVector`
+and which is therefore defined for every key value of
+the `DomainT` type, this definition of `operator &`
+degenerates to the same sematics that `operaotor +`
+implements:
+``
+//Pseudocode example for total Quantifiers p, q:
+interval_map<int,int> p, q;
+p   = {[min   1)[1      3)[3         max]};
+          ->0      ->1         ->0
+q   = {[min        2)[2      4)[4    max]};
+            ->0         ->1       ->0
+p&q =={[min   1)[1  2)[2 3)[3 4)[4   max]};
+          ->0    ->1   ->2  ->1    ->0
+``
+
+[h4 Laws for Quantifiers of unsigned Numbers]
+
+The semantics of icl Maps of Numbers is different
+for unsigned or signed numbers. So the sets of
+laws that are valid for Quantifiers will be different
+depending on the instantiation of an unsigned or
+a signed number type as `CodomainT` parameter.
+
+Again, we are presenting the investigated sets of laws, this time for
+`Quantifier` types `Q` which are
+__icl_map__`<D,N,T>`, __itv_map__`<D,N,T>` and __spl_itv_map__`<D,N,T>`
+where `CodomainT` type `N` is a `Number` and `Trait` type `T` is one of
+the icl's map traits. 
+
+``
+Associativity<Q,+,== >: Q a,b,c; a+(b+c) == (a+b)+c
+Neutrality<Q,+,== >   : Q a;       a+Q() == a
+Commutativity<Q,+,== >: Q a,b;       a+b == b+a
+
+Associativity<Q,&,== >: Q a,b,c; a&(b&c) ==(a&b)&c
+Commutativity<Q,&,== >: Q a,b;       a&b == b&a
+
+RightNeutrality<Q,-,== >: Q a;   a-Q() ==  a
+Inversion<Q,-,=v= >     : Q a;   a - a =v= Q()
+``
+
+For an `unsigned Quantifier`, an icl Map of `unsigned numbers`,
+the same basic laws apply that are
+valid for `Collectors`:
+
+``
+                             +    &    -
+Associativity                ==   == 
+Neutrality                   ==        ==
+Commutativity                ==   ==
+Inversion absorbs_neutrons             ==
+          enriches_neutrons            =p=
+``
+
+The subset of laws, that relates to `operator +` and the neutral
+element `Q()` is that of a commutative monoid. This is the same
+concept, that applies for the `CodomainT` type. This gives 
+rise to the assumption that an icl `Map` over a `CommutativeModoid`
+is again a `CommutativeModoid`.
+
+Other laws that were valid for `Collectors` are not valid
+for an `unsigned Quantifier`. 
+
+ 
+[h4 Laws for Quantifiers of signed Numbers]
+
+For `Quantifiers` of signed numbers, or 
+`signed Quantifiers`, the pattern of valid
+laws is somewhat different:
+``
+                             +    &    -
+Associativity                =v=  =v=  
+Neutrality                   ==        ==
+Commutativity                ==   ==
+Inversion absorbs_neutrons             ==
+          enriches_neutrons            =p=
+``
+
+The differences are tagged as `=v=` indicating, that
+the associativity law is not uniquely valid for a single
+equality relation `==` as this was the case for
+`Collector` and `unsigned Quntifier` maps.
+
+The differences are these:
+``
+                                   +  
+Associativity         icl::map     ==   
+                  interval_map     ==
+            split_interval_map     =e=
+``
+For `operator +` the associativity on __spl_itv_maps__ is only valid
+with element equality `=e=`, which is not a big constrained, because
+only element equality is required.
+
+For `operator &` the associativity is broken for all maps
+that are partial absorbers. For total absorbers associativity
+is valid for element equality. All maps having the neutron enricher
+Trait are associative wrt. lexicographical equality `==`.
+``                               
+Associativity                      &
+   absorbs_neutrons && !is_total   false
+   absorbs_neutrons &&  is_total   =e=
+   enriches_neutrons               ==                  
+``
+
+Note, that all laws that establish a commutative
+monoid for `operator +` and neutron `Q()` are valid
+for `signed Quantifiers`.
+In addition symmetric difference that does not
+hold for `unsigned Qunatifiers` is valid
+for `signed Qunatifiers`.
+
+``
+SymmetricDifference<Q,== > : Q a,b,c; (a + b) - (a & b) == (a - b) + (b - a)
+``
+For a `signed TotalQuantifier` `Qt` symmetrical difference degenerates to 
+a trivial form since `operator &` and `operator +` become identical
+``
+SymmetricDifference<Qt,== > : Qt a,b,c; (a + b) - (a + b) == (a - b) + (b - a) == Qt()
+``
+
+[h5 Existence of an Inverse]
+
+By now `signed Quantifiers` `Q` are 
+commutative monoids 
+with respect to the
+`operator +` and the neutral element `Q()`. 
+If the Quantifier's `CodomainT` type has an /inverse element/ 
+like e.g. `signed numbers` do,
+the `CodomainT` type is a 
+['*commutative*] or ['*abelian group*].
+In this case a `signed Quantifier` that is also ['*total*] 
+has an ['*inverse*] and the following law holds:
+
+``
+InverseElement<Qt,== > : Qt a; (0 - a) + a == 0
+``
+
+Which means that each `TotalQuantifier` over an
+abelian group is an 
+abelian group 
+itself.
+
+This also implies that a `Quantifier` of `Quantifiers` 
+is again a `Quantifiers` and a
+`TotalQuantifier` of `TotalQuantifiers`
+is also a `TotalQuantifier`. 
+
+`TotalQuantifiers` resemble the notion of a
+vector space partially.
+The concept could be completed to a vector space, 
+if a scalar multiplication was added. 
+[endsect][/ Quantifiers]
+
+
+[section Concept Induction]
+
+Obviously we can observe the induction of semantics
+from the `CodomainT` parameter into the instantiations
+of icl maps.
+
+[table
+[[]                          [is model of]        [if]                       [example]]
+[[`Map<D,Monoid>`]           [`Modoid`]           []                         [`interval_map<int,string>`]]
+[[`Map<D,Set,Trait>`]        [`Set`]              [`Trait::absorbs_neutrons`][`interval_map<int,std::set<int> >`]]
+[[`Map<D,CommutativeMonoid>`][`CommutativeMonoid`][]                         [`interval_map<int,unsigned int>`]]
+[[`Map<D,CommutativeGroup>`] [`CommutativeGroup`] [`Trait::is_total`]  [`interval_map<int,int,total_absorber>`]]
+]
+
+[endsect][/ Concept Induction]
+
+[endsect][/ Semantics]