EQ2EMu/EQ2/source/depends/boost_1_72_0/libs/icl/doc/interface.qbk

[/
    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.informit.com/guides/content.aspx?g=cplusplus&seqNum=314 `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.
A `unit_element` can be any value, that is greater as the `identity_element` 
in the `Compare` order given.
An example of a type, that has an `identity_element` but no increment operation 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.informit.com/guides/content.aspx?g=cplusplus&seqNum=314 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 `identity_element` 
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 
polymorphic overloads across the class templates of the *icl*.
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`                         ] []                        [polymorphic container argument type]]             
[[`J`                         ] []                        [polymorphic iterator type]]
[[`K`                         ] []                        [polymorphic 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 P&)`]                          [ ]    [__ei]   [__ei]     [2]      [2]   ]
[[`J find(T&, const P&)`]                         [ ]    [__ei]   [__ei]     [ ]      [ ]   ]
[[`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]  ]
[[`J T::add(J pos, const P&)`]                    [ ]     [__i]     [__p]    [ ]     [__b]  ]
[[`J 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]  ]
[[`J T::insert(J pos, const P&)`]                 [ ]     [__i]     [__p]    [__e]    [__b]  ]
[[`J 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]