]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/libs/icl/doc/interface.qbk
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
bump version to 12.2.2-pve1
[ceph.git] / ceph / src / boost / libs / icl / doc / interface.qbk
CommitLineData
7c673cae
FG		 1[/
2 Copyright (c) 2008-2010 Joachim Faulhaber
3
4 Distributed under the Boost Software License, Version 1.0.
5 (See accompanying file LICENSE_1_0.txt or copy at
6 http://www.boost.org/LICENSE_1_0.txt)
7]
8
9[section Interface]
10
11Section *Interface* outlines types and functions
12of the *Icl*. Synoptical tables allow to review the overall structure of
13the libraries design and to focus on structural equalities and differences
14with the corresponding containers of the standard template library.
15
16
17[section Class templates]
18
19[section Intervals]
20
21In the *icl* we have two groups of interval types. There are ['*statically bounded*] intervals,
22__ro_itv__,
23__lo_itv__,
24__cl_itv__,
25__op_itv__,
26that always have the the same kind of interval borders and ['*dynamically bounded*] intervals,
27__dc_itv__,
28__ct_itv__
29which can have one of the four possible bound types at runtime.
30
31
32[table Interval class templates
33[[group] [form] [template] [instance parameters]]
34[[statically bounded] [asymmetric][__ro_itv__] [`<class DomainT, template<class>class Compare>`]]
35[[ ] [] [__lo_itv__] [`<...same for all interval class templates...>`]]
36[[ ] [symmetric] [__cl_itv__] []]
37[[ ] [] [__op_itv__] []]
38[[dynamically bounded][] [__dc_itv__] []]
39[[ ] [] [__ct_itv__] []]
40]
41
42Not every class template works with all domain types. Use interval class templates
43according the next table.
44
45[table Usability of interval class templates for discrete or continuous domain types
46[[group] [form] [template] [discrete] [continuous] ]
47[[statically bounded] [asymmetric][__ro_itv__] [yes] [yes] ]
48[[ ] [] [__lo_itv__] [yes] [yes] ]
49[[ ] [symmetric] [__cl_itv__] [yes] [ ] ]
50[[ ] [] [__op_itv__] [yes] [ ] ]
51[[dynamically bounded][] [__dc_itv__] [yes] [ ] ]
52[[ ] [] [__ct_itv__] [] [yes] ]
53]
54
55From a pragmatical point of view, the most important interval class template
56of the /statically bounded/ group is __ro_itv__. For discrete domain types
57also closed intervals might be convenient. Asymmetric intervals can be used
58with continuous domain types but __ct_itv__ is the only class template that
59allows to represent a singleton interval that contains only one element.
60
61Use __ct_itv__, if you work with interval containers of countinuous domain types
62and you want to be able to handle single values:
63
64``
65typedef interval_set<std::string, std::less, continuous_interval<std::string> > IdentifiersT;
66IdentifiersT identifiers, excluded;
67identifiers += continuous_interval<std::string>::right_open("a", "c");
68
69// special identifiers shall be excluded
70identifiers -= std::string("boost");
71cout << "identifiers: " << identifiers << endl;
72
73excluded = IdentifiersT(icl::hull(identifiers)) - identifiers;
74cout << "excluded : " << excluded << endl;
75
76//------ Program output: --------
77identifiers: {[a,boost)(boost,c)}
78excluded : {[boost,boost]}
79``
80
81[h4 Library defaults and class template `interval`]
82
83As shown in the example above, you can choose an interval type
84by instantiating the interval container template with the desired type.
85
86``
87typedef interval_set<std::string, std::less, continuous_interval<std::string> > IdentifiersT;
88``
89
90But you can work with the library default for interval template parameters as well,
91which is `interval<DomainT,Compare>::type`.
92
93[table
94[[] [interval bounds][domain_type][interval_default]]
95[[`#ifdef` BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS][static] [ ] [__ro_itv__] ]
96[[`#else`] [dynamic] [discrete] [__dc_itv__] ]
97[[ ] [ ] [continuous] [__ct_itv__] ]
98]
99
100So, if you are always happy with the library default for the interval type, just use
101``
102icl::interval<MyDomainT>::type myInterval;
103``
104as you standard way of declaring intervals and default parameters for interval containers:
105``
106typedef interval_set<std::string> IdentifiersT;
107IdentifiersT identifiers, excluded;
108identifiers += interval<std::string>::right_open("a", "c");
109. . .
110``
111
112So class template __itv__ provides a standard way to work with the library default
113for intervals. Via `interval<D,C>::type` you can declare a default interval.
114In addition four static functions
115``
116T interval<D,C>::right_open(const D&, const D&);
117T interval<D,C>::left_open(const D&, const D&);
118T interval<D,C>::closed(const D&, const D&);
119T interval<D,C>::open(const D&, const D&);
120``
121allow to construct intervals of the library default `T = interval<D,C>::type`.
122
123If you
124``
125#define BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS
126``
127the library uses only statically bounded __ro_itv__ as default interval type.
128In this case, the four static functions above are also available,
129but they only move interval borders consistently, if
130their domain type is discrete, and create an appropriate __ro_itv__ finally:
131``
132interval<D,C>::right_open(a,b) == [a, b) -> [a , b )
133interval<D,C>:: left_open(a,b) == (a, b] -> [a++, b++)
134interval<D,C>:: closed(a,b) == [a, b] -> [a , b++)
135interval<D,C>:: open(a,b) == (a, b) -> [a++, b )
136``
137
138For continuous domain types only the first of the four functions is applicable
139that matches the library default for statically bounded intervals: __ro_itv__.
140The other three functions can not perform an appropriate tranformation and
141will not compile.
142
143[endsect][/ Intervals]
144
145[section Sets]
146
147The next two tables give an overview over ['*set class templates*] of
148the icl.
149
150[/ interval_set]
151[/ separate_interval_set]
152[/ split_interval_set]
153[/ icl::set]
154
155[table Set class templates
156[[group] [template] [instance parameters]]
157[/ CL [__itv__] [__itv__] [`<DomainT,Compare>`]]
158[[__itv_bsets__][__itv_set__] [`<DomainT,Compare,IntervalT,Alloc>`]]
159[[] [__sep_itv_set__][`<DomainT,Compare,IntervalT,Alloc>`]]
160[[] [__spl_itv_set__][`<DomainT,Compare,IntervalT,Alloc>`]]
161[/ [__std_set__] [`std::set`] [`<_Key, _Compare, _Alloc>`]]
162]
163
164Templates and template parameters, given in the preceding table are
165described in detail below.
166__Itv_bsets__ represent three
167class templates __itv_set__, __sep_itv_set__ and __spl_itv_set__
168that all have equal template parameters.
169
170[table Parameters of set class templates
171[[] [type of elements][order of elements] [type of intervals] [memory allocation]]
172[[template parameter] [`class`] [`template <class>class`] [`class`] [`template <class>class`]]
173[[__itv__] [`DomainT`][`Compare = std::less`] [] []]
174[[__itv_bsets__] [`DomainT`][`Compare = std::less`] [`IntervalT = interval<DomainT,Compare>::type`] [`Alloc = std::alloc`]]
175
176[/ [__icl_set__] [`DomainT`][`Compare = std::less`] [] [`Alloc = std::alloc`]]
177[/ [template parameter] [`class`] [`class`] [`class`] [class]]
178[/ [__std_set__] [`_Key`] [`_Compare = std::less<_Key>`][] [`Alloc = std::alloc<_Key>`]]
179]
180
181[endsect][/ Sets]
182
183[section Maps]
184
185The next two tables give an overview over ['*map class templates*] of the icl.
186
187[/ interval_map]
188[/ split_interval_map]
189[/ icl::map]
190
191[table map class templates
192[[group] [template] [instance parameters]]
193[[__itv_bmaps__][__itv_map__] [`<DomainT,CodomainT,Traits,Compare,Combine,Section,IntervalT,Alloc>`]]
194[[] [__spl_itv_map__][`<DomainT,CodomainT,Traits,Compare,Combine,Section,IntervalT,Alloc>`]]
195[[__icl_map__] [__icl_map__] [`<DomainT,CodomainT,Traits,Compare,Combine,Section,Alloc>`]]
196[/ [__std_map__] [__std_map__] [`<_Key, _Data, _Compare, _Alloc>`]]
197]
198
199
200Templates and template parameters, given in the preceding table are
201described in detail below.
202__Itv_bmaps__ represent two
203class templates __itv_map__ and __spl_itv_map__
204that all have equal template parameters.
205
206[table Parameters of map class templates
207[[] [elements][mapped values][traits] [order of elements] [aggregation propagation] [intersection propagation] [type of intervals] [memory allocation]]
208[[template parameter] [`class`] [`class`] [`class`] [`template <class>class`] [`template <class>class`] [`template <class>class`] [`class`] [`template <class>class`]]
209[[__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`]]
210[[__icl_map__] [`DomainT`][`CodomainT`] [`Traits = identity_absorber`] [`Compare = std::less`] [`Combine = inplace_plus`] [`Section = icl::inplace_et`] [`Alloc = std::alloc`]]
211[/ [template parameter] [`class`] [`class`] [] [`class`] [] [] [] [`class`]]
212[/ [__std_map__] [`_Key`] [`_Data`] [] [`_Compare = std::less<_Key>`][] [] [] [`Alloc = std::alloc<_Key>`]]
213]
214
215Using the following placeholders,
216
217``
218D := class DomainT,
219C := class CodomainT,
220T := class Traits,
221cp := template<class D>class Compare = std::less,
222cb := template<class C>class Combine = icl::inplace_plus,
223s := template<class C>class Section = icl::inplace_et,
224I := class IntervalT = icl::interval<D,cp>::type
225a := template<class>class Alloc = std::allocator
226``
227
228we arrive at a final synoptical matrix of class templates and their parameters.
229
230[pre
231interval <D, cp, >
232interval_sets<D, cp, I, a >
233interval_maps<D, C, T, cp, cb, s, I, a >
234icl::map <D, C, T, cp, cb, s, a >
235]
236
237The choice of parameters and their positions follow the std::containers
238as close a possible, so that usage of interval sets and maps does only
239require minimal additional knowledge.
240
241Additional knowledge is required when instantiating a comparison parameter
242`Compare` or an allocation parameter `Alloc`. In contrast to std::containers
243these have to be instantiated as templates, like e.g.
244``
245interval_set<string, german_compare> sections; // 2nd parameter is a template
246std::set<string, german_compare<string> > words; // 2nd parameter is a type
247``
248
249[endsect][/ Maps]
250[endsect][/ Class templates]
251
252[section Required Concepts]
253
254There are uniform requirements for the template parameters
255across *icl's* class templates. The template parameters can
256be grouped with respect to those requirements.
257
258[table
259[[] [used in] [Kind] [Parameter] [Instance] [Description] ]
260[[Domain order] [`Intervals, Sets, Maps`][`typename`][`DomainT`] [] [For the type `DomainT` of key elements `...`]]
261[[] [] [`template`] [`Compare`] [`Compare<DomainT>`] [`...` there is an order `Compare`] ]
262[[Interval type] [`interval_sets/maps`][`typename`] [`IntervalT`] [] [`...` the `IntervalT` parameter has to use the same element type and order. ] ]
263[[Codomain aggregation][`Maps`] [`typename`] [`CodomainT`] [] [For the type `CodomainT` of associated values `...`]]
264[[] [] [`template`] [`Combine`] [`Combine<CodomainT>`] [`...` there is a binary functor `Combine<CodomainT>()` to combine them ] ]
265[[] [] [] [] [`Inverse<Combine<CodomainT>>`][`...` and implicitly an `Inverse` functor to inversely combine them. ] ]
266[[] [] [`template`] [`Section`] [`Section<CodomainT>`] [Intersection is propagated to CodomainT values via functor `Section<CodomainT>()`] ]
267[[Memory allocation] [`Sets, Maps`] [`template`] [`Alloc`] [`Alloc<`/various/`>`] [An allocator can be chosen for memory allocation.]]
268]
269
270[/ table
271[[Kind] [Parameter] [Condition] [Requirement] ]
272[[`typename`][`DomainT`] [] [`Regular<DomainT> && LessThanComparable<DomainT,Compare>`
273 `&& (IsIncrementable<DomainT>||HasUnitElement<DomainT>)`] ]
274[[][] [`IsIntegral<DomainT>`] [`IsIncrementable<DomainT> && IsDecrementable<DomainT>`] ]
275[[`typename`][`CodomainT`][`Combine` and `Inverse<Combine>` unused] []]
276[[][] [only `Combine` used ] [`EqualityComparable<CodomainT> && Addable<CodomainT,Combine>`] ]
277[[][] [also `Inverse<Combine>` used] [`&& Subtractable<CodomainT,Inverse<Combine> >`] ]
278[[`template`][`Compare`] [] [`LessThanComparable<DomainT,Compare>`] ]
279[[`template`][`Combine`] [only `Combine` used] [`Addable<CodomainT,Combine>`]]
280[[][] [and `Inverse<Combine>` used] [`&& Subtractable<CodomainT,Inverse<Combine> >`] ]
281[[][] [`Section` used and `CodomainT` is a set][`Intersectable<CodomainT,Section>`] ]
282]
283
284[h4 Requirements on DomainT]
285
286The next table gives an overview over the requirements for
287template parameter `DomainT`. Some requirements are dependent
288on /conditions/. Column /operators/ shows the operators and
289functions that are expected for `DomainT`, if the default order
290`Compare = std::less` is used.
291
292[table
293[[Parameter] [Condition] [Operators] [Requirement] ]
294[[`DomainT`] [] [`DomainT(), <`] [`Regular<DomainT> && StrictWeakOrdering<DomainT,Compare>`]]
295[[] [] [`++, unit_element<CodomainT>::value()`][`&& (IsIncrementable<DomainT>||HasUnitElement<DomainT>)`] ]
296[[] [`IsIntegral<DomainT>`][`++, --`] [`IsIncrementable<DomainT> && IsDecrementable<DomainT>`] ]
297]
298
299A domain type `DomainT` for intervals and interval containers
300has to satisfy the requirements of concept
301[@http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=314 `Regular`]
302which
303implies among other properties the existence of a copy and
304a default constructor. In addition `IsIncrementable`
305*or* `HasUnitElement` is required for `DomainT`.
306In the *icl* we represent an empty closed interval as
307interval `[b,a]` where `a < b` (here `<` represents `Compare<DomainT>()`).
308To construct one of these empty intervals as default constructor
309for any type `DomainT` we choose `[1,0]`, where `0` is a null-value or `identity_element`
310and `1` is a one-value or `unit_element`:
311``
312interval() := [unit_element<DomainT>::value(), identity_element<DomainT>::value()] //pseudocode
313``
314`Identity_elements` are implemented via call of the default constructor of
315`DomainT`. A `unit_element<T>::value()` is implemented
316[classref boost::icl::unit_element by default] as a `identity_element`,
317that is incremented once.
318``
319template <class Type>
320inline Type unit_element<Type>::value(){ return succ(identity_element<Type>::value()); };
321``
322So a type `DomainT` that is `incrementable` will
323also have an `unit_element`. If it does not, a `unit_element` can be provided.
324A `unit_element` can be any value, that is greater as the `identity_element`
325in the `Compare` order given.
326An example of a type, that has an `identity_element` but no increment operation is
327`string`. So for `std::string` a unit_element is implemented like this:
328``
329// Smallest 'visible' string that is greater than the empty string.
330template <>
331inline std::string unit_element<std::string>::value(){ return std::string(" "); };
332``
333
334Just as for the key type of std::sets and maps
335template parameter `Compare` is required to be a
336[@http://en.wikipedia.org/wiki/Strict_weak_ordering strict weak ordering] on `DomainT`.
337
338Finally, if `DomainT` is an integral type, `DomainT` needs to
339be `incrementable` and `decrementable`. This [''bicrementability']
340needs to be implemented on the smallest possible unit of the
341integral type. This seems like being trivial but there are types like e.g.
342`boost::date_time::ptime`, that are integral in nature but do
343not provide the required in- and decrementation on the least incrementable unit.
344For __icl_itvs__ incementation and decementation is used
345for computations between open to closed interval borders like e.g.
346`[2,43) == [2,42]`. Such computations always need only
347one in- or decrementation, if `DomainT` is an integral type.
348
349[h5 Requirements on IntervalT]
350
351Requirements on the `IntervalT` parameter are closely related to the
352`DomainT` parameter. `IntervalT` has two associated types
353itself for an element type and a compare order that have
354to be consistent with the element and order parameters of
355their interval containers.
356`IntervalT` then has to implement an order called
357`exclusive_less`. Two intervals `x, y` are exclusive_less
358``icl::exclusive_less(x, y)``
359if all `DomainT` elements of `x` are less than elements of `y` in the
360`Compare` order.
361
362[table
363[[Parameter] [Operators] [Requirement] ]
364[[`IntervalT`] [`exclusive_less`] [`IsExclusiveLessComparable<Interval<DomainT,Compare> >`] ]
365]
366
367[h4 Requirements on CodomainT]
368
369Summarized in the next table are requirements for template parameter
370`CodomainT` of associated values for `Maps`. Again there are
371/conditions/ for some of the requirements. Column /operators/
372contains the operators and functions required for `CodomainT`, if we are
373using the default combiner `Combine = icl::inplace_plus`.
374
375[table
376[[Parameter] [Condition] [Operators] [Requirement] ]
377[[`CodomainT`][`add`, `subtract`, `intersect` unused] [`CodomainT(), ==`][`Regular<CodomainT>` which implies] ]
378[[] [] [] [`DefaultConstructible<CodomainT> && EqualityComparable<CodomainT>`] ]
379[[] [only `add` used ] [`+=`] [`&& Combinable<CodomainT,Combine>`] ]
380[[] [... and also `subtract` used] [`-=`] [`&& Combinable<CodomainT,Inverse<Combine> >`]]
381[[] [`Section` used and `CodomainT` is a set][`&=`] [`&& Intersectable<CodomainT,Section>`] ]
382]
383
384The requirements on the type `CodomainT` of associated values for a __icl_map__ or __itv_map__
385depend on the usage of their aggregation functionality. If aggregation on overlap
386is never used, that is to say that none of the addition, subtraction and intersection
387operations (`+, +=, add`, `-, -=, subtract`, &, &=, add_intersection) are used on the
388__itv_map__, then `CodomainT` only needs to be
389[@http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=314 Regular].
390
391['*Regular*]
392object semantics implies `DefaultConstructible` and
393`EqualityComparable` which means it has
394a default ctor `CodomainT()` and an `operator ==`.
395
396Use __itv_maps__ ['*without aggregation*], if the associated values are not
397addable but still
398are attached to intervals so you want to use __itv_maps__ to handle them.
399As long as those values are added with `insert` and deleted with `erase`
400__itv_maps__ will work fine with such values.
401
402If ['*only addition*] is used via __itv_map_s__ `+, +=` or `add` but no subtraction,
403then `CodomainT` need to be `Combinable` for functor template `Combine`. That
404means in most cases when the default implementation `inplace_plus` for
405`Combine` is used, that `CodomainT` has to implement `operator +=`.
406
407For associated value types, that are addable but not subtractable like
408e.g. `std::string` it usually makes sense to use addition to combine values
409but the inverse combination is not desired.
410``
411interval_map<int,std::string> cat_map;
412cat_map += make_pair(interval<int>::rightopen(1,5),std::string("Hello"));
413cat_map += make_pair(interval<int>::rightopen(3,7),std::string(" world"));
414cout << "cat_map: " << cat_map << endl;
415//cat_map: {([1,3)->Hello)([3,5)->Hello world)([5,7)-> world)}
416``
417
418For ['complete aggregation functionality] an inverse aggregation functor on
419a `Map`'s `CodomainT` is needed. The icl provides a
420metafunction [classref boost::icl::inverse inverse]
421for that purpose. Using the default
422`Combine = inplace_plus` that relies on the existence of `operator +=`
423on type `CodomainT`
424metafunction [classref boost::icl::inverse inverse]
425will infer [classref boost::icl::inplace_minus inplace_minus]
426as inverse functor, that requires `operator -=` on type `CodomainT`.
427
428In the icl's design we make the assumption,
429in particular for the default setting of parameters
430`Combine = `[classref boost::icl::inplace_minus inplace_plus],
431that type `CodomainT` has a neutral element or `identity_element`
432with respect to the `Combine` functor.
433
434
435[endsect][/ Required Concepts]
436
437
438[section Associated Types]
439
440In order to give an overview over ['*associated types*] the *icl* works
441with, we will apply abbreviations again that were introduced in the
442presentaiton of icl class templates,
443
444[pre
445interval <D, cp, >
446interval_sets<D, cp, I, a >
447interval_maps<D, C, T, cp, cb, s, I, a >
448icl::map <D, C, T, cp, cb, s, a >
449]
450
451where these placeholders were used:
452
453``
454D := class DomainT,
455C := class CodomainT,
456T := class Traits,
457cp := template<class D>class Compare = std::less,
458cb := template<class C>class Combine = icl::inplace_plus,
459s := template<class C>class Section = icl::inplace_et,
460I := class Interval = icl::interval<D,cp>::type
461a := template<class>class Alloc = std::allocator
462``
463With some additions,
464``
465sz := template<class D>class size
466df := template<class D>class difference
467Xl := class ExclusiveLess = exclusive_less<Interval<DomainT,Compare> >
468inv:= template<class Combiner>class inverse
469(T,U) := std::pair<T,U> for typnames T,U
470``
471
472we can summarize the associated types as follows.
473Again two additional columns for easy comparison with stl
474sets and maps are provided.
475
476[table Icl Associated types
477[[Purpose] [Aspect] [Type][__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
478[/[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] ]
479[/ interval itvset itvmap icl:set icl:map ]
480[[['*Data*]] [__conceptual__] [`domain_type`] [`D`] [`D`] [`D`] [`D`] [`D`] ]
481[[ ] [ ] [`codomain_type`] [`D`] [`D`] [`C`] [`D`] [`C`] ]
482[[ ] [ ] [`element_type`] [`D`] [`D`] [`(D,C)`] [`D`] [`(D,C)`] ]
483[[ ] [ ] [`segment_type`][`i<D,cp>`][`i<D,cp>`][`(i<D,cp>,C)`][ ] [ ] ]
484[[ ] [['size] ] [`size_type`] [`sz<D>`][`sz<D>`][`sz<D>`] [`sz<D>`] [`sz<D>`] ]
485[[ ] [ ] [`difference_type`] [`df<D>`][`df<D>`][`df<D>`] [`sz<D>`] [`sz<D>`] ]
486[[ ] [ ] [][__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
487[[['*Data*]] [__iterative__ ] [`key_type`] [`D`][`i<D,cp>`][`i<D,cp>`] [`D`] [`D`] ]
488[[ ] [ ] [`data_type`] [`D`][`i<D,cp>`] [`C`] [`D`] [`C`] ]
489[[ ] [ ] [`value_type`] [`D`][`i<D,cp>`][`(i<D,cp>,C)`][`D`][`(D,C)`]]
490[[ ] [ ] [`interval_type`] [`i<D,cp>`][`i<D,cp>`][`i<D,cp>`] [ ] [ ] ]
491[[ ] [['allocation]] [`allocator_type`] [ ][`a<i<D,cp>>`][`a<(i<D,cp>, C)>`][`a<D>`][`a<(D,C)>`]]
492[[ ] [ ] [][__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
493[[['*Ordering*]] [__conceptual__] [`domain_compare`] [`cp<D>`][`cp<D>`][`cp<D>`][`cp<D>`][`cp<D>`] ]
494[[ ] [__iterative__ ] [`key_compare`] [`cp<D>`] [`Xl`] [`Xl`] [`cp<D>`] [`cp<D>`] ]
495[[ ] [ ] [`interval_compare`] [ ] [`Xl`] [`Xl`] [ ] [ ] ]
496[[['*Aggregation*]] [__conceptual__] [`codomain_combine`] [ ] [ ] [`cb<C>`] [ ] [`cb<C>`] ]
497[[ ] [ ] [`inverse_codomain_combine`] [ ] [ ][`inv<cb<C>>`] [ ][`inv<cb<C>>`] ]
498[[ ] [ ] [`codomain_intersect`] [ ] [ ] [`s<C>`] [ ] [`s<C>`] ]
499[[ ] [ ] [`inverse_codomain_intersect`] [ ] [ ] [`inv<s<C>>`] [ ][`inv<s<C>>`] ]
500]
501
502
503[endsect][/ Associated Types]
504
505[section Function Synopsis]
506
507In this section a single ['*matrix*] is given, that shows all ['*functions*]
508with shared names and identical or analogous semantics and their
509polymorphic overloads across the class templates of the *icl*.
510In order to achieve a concise representation, a series
511of ['*placeholders*] are used throughout the function matrix.
512
513The ['*placeholder's*] purpose is to express the polymorphic
514usage of the functions. The ['*first column*] of the function matrix
515contains the signatures of the functions. Within these
516signatures `T` denotes a container type and `J` and `P`
517polymorphic argument and result types.
518
519Within the body of the matrix, sets of *boldface* placeholders denote
520the sets of possible instantiations for a polymorphic
521placeholder `P`. For instance __eiS denotes that for the
522argument type `P`, an element __e, an interval __i or an interval_set __S
523can be instantiated.
524
525If the polymorphism can not be described in this way, only the ['*number*] of
526overloaded implementations for the function of that row is shown.
527
528[table
529[[Placeholder] [Argument types] [Description]]
530[[`T` ] [] [a container or interval type]]
531[[`P` ] [] [polymorphic container argument type]]
532[[`J` ] [] [polymorphic iterator type]]
533[[`K` ] [] [polymorphic element_iterator type for interval containers]]
534[[`V` ] [] [various types `V`, that do dot fall in the categories above]]
535[[1,2,... ] [] [number of implementations for this function]]
536[[A ] [] [implementation generated by compilers]]
537[[[#element_type] [*e]] [T::element_type] [the element type of __itv_sets__ or __icl_sets__]]
538[[[#interval_type] [*i]] [T::segment_type] [the segment type of of __itv_sets__]]
539[[[#itl_set_type] [*s]] [element sets] [__std_set__ or other models of the icl's set concept]]
540[[[#interval_set_types] [*S]] [interval_sets] [one of the interval set types]]
541[[[#element_mapping_type] [*b]] [T::element_type] [type of __itv_map_s__ or __icl_map_s__ element value pairs]]
542[[[#interval_mapping_type][*p]] [T::segment_type] [type of __itv_map_s__ interval value pairs]]
543[[[#itl_map_type] [*m]] [element maps] [__icl_map__ icl's map type]]
544[[[#interval_map_types] [*M]] [interval_maps] [one of the interval map types]]
545[[[#discrete_types] [*d]] [discrete types] [types with a least steppable discrete unit: Integral types, date/time types etc.]]
546[[[#continuous_types] [*c]] [continuous types] [types with (theoretically) infinitely many elements beween two values.]]
547]
548
549[/ memberref boost::icl::set::iterative_size `iterative_size`]
550
551[table Synopsis Functions and Overloads
552[[T] [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
553[/ interval itvset itvmap icl:set icl:map ]
554[[__biLConsCopyDest__ [#function_synopsis_table]] [ ] [ ] [ ] [ ] [ ] ]
555[[`T::T()`] [1] [1] [1] [1] [1] ]
556[[`T::T(const P&)`] [A] [__eiS] [__bpM] [1] [1] ]
557[/ FYI [`T::T(...)`] [3] [ ] [ ] [3] [3] ]
558[[`T& T::operator=(const P&)`] [A] [__S] [__M] [1] [1] ]
559[[`void T::swap(T&)`] [ ] [1] [1] [1] [1] ]
560
561[[__biLContainedness__ ][__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
562[[`bool T::empty()const`] [ ] [1] [1] [1] [1] ]
563[[`bool is_empty(const T&)`] [1] [1] [1] [1] [1] ]
564[[`bool contains(const T&, const P&)`\n
565 `bool within(const P&, const T&)`] [__ei] [__eiS][__eiS __bpM][__es] [__bm] ]
566
567[[__biLEquivsOrderings__ ][__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
568[[`bool operator == (const T&, const T&)`] [1] [1] [1] [1] [1] ]
569[[`bool operator != (const T&, const T&)`] [1] [1] [1] [1] [1] ]
570[[`bool operator < (const T&, const T&)`] [1] [1] [1] [1] [1] ]
571[[`bool operator > (const T&, const T&)`] [1] [1] [1] [1] [1] ]
572[[`bool operator <= (const T&, const T&)`] [1] [1] [1] [1] [1] ]
573[[`bool operator >= (const T&, const T&)`] [1] [1] [1] [1] [1] ]
574[[`bool is_element_equal(const T&, const P&)`] [ ] [__S] [__M] [1] [1] ]
575[[`bool is_element_less(const T&, const P&)`] [ ] [__S] [__M] [1] [1] ]
576[[`bool is_element_greater(const T&, const P&)`] [ ] [__S] [__M] [1] [1] ]
577[[`bool is_distinct_equal(const T&, const P&)`] [ ] [ ] [__M] [ ] [1] ]
578
579[[__biLSize__ ] [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
580[[`size_type T::size()const`] [ ] [1] [1] [1] [1] ]
581[[`size_type size(const T&)`] [1] [1] [1] [1] [1] ]
582[[`size_type cardinality(const T&)`] [1] [1] [1] [1] [1] ]
583[[`difference_type length(const T&)`] [1] [1] [1] [ ] [ ] ]
584[[`size_type iterative_size(const T&)`] [ ] [1] [1] [1] [1] ]
585[[`size_type interval_count(const T&)`] [ ] [1] [1] [ ] [ ] ]
586
587[[__biLSelection__ ] [ ] [ ] [ ] [ ] [ ] ]
588[[`J T::find(const P&)`] [ ] [__ei] [__ei] [2] [2] ]
589[[`J find(T&, const P&)`] [ ] [__ei] [__ei] [ ] [ ] ]
590[[`codomain_type& operator[] (const domain_type&)`][ ] [ ] [ ] [ ] [1] ]
591[[`codomain_type operator() (const domain_type&)const`][ ] [ ] [1] [ ] [1] ]
592
593[[__biLRange__] [ ] [ ] [ ] [ ] [ ] ]
594[[`interval_type hull(const T&)`] [ ] [1] [1] [ ] [ ] ]
595[[`T hull(const T&, const T&)`] [1] [ ] [ ] [ ] [ ] ]
596[[`domain_type lower(const T&)`] [1] [1] [1] [ ] [ ] ]
597[[`domain_type upper(const T&)`] [1] [1] [1] [ ] [ ] ]
598[[`domain_type first(const T&)`] [1] [1] [1] [ ] [ ] ]
599[[`domain_type last(const T&)`] [1] [1] [1] [ ] [ ] ]
600
601[[__biLAddition__] [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
602[[`T& T::add(const P&)`] [ ] [__ei] [__bp] [ ] [__b] ]
603[[`T& add(T&, const P&)`] [ ] [__ei] [__bp] [__e] [__b] ]
604[[`J T::add(J pos, const P&)`] [ ] [__i] [__p] [ ] [__b] ]
605[[`J add(T&, J pos, const P&)`] [ ] [__i] [__p] [__e] [__b] ]
606
607[[`T& operator +=(T&, const P&)`] [ ] [__eiS] [__bpM] [__es] [__bm] ]
608[[`T operator + (T, const P&)`\n
609 `T operator + (const P&, T)`]
610 [ ] [__eiS] [__bpM] [__es] [__bm] ]
611[[`T& operator |=( T&, const P&)`] [ ] [__eiS] [__bpM] [__es] [__bm] ]
612[[`T operator | (T, const P&)`\n
613 `T operator | (const P&, T)`]
614 [ ] [__eiS] [__bpM] [__es] [__bm] ]
615[[__biLSubtraction__] [ ] [ ] [ ] [ ] [ ] ]
616[[`T& T::subtract(const P&)`] [ ] [__ei] [__bp] [ ] [__b] ]
617[[`T& subtract(T&, const P&)`] [ ] [__ei] [__bp] [__e] [__b] ]
618
619[[`T& operator -=(T&, const P&)`] [ ] [__eiS][__eiS __bpM][__es] [__bm] ]
620[[`T operator - (T, const P&)`] [ ] [__eiS][__eiS __bpM][__es] [__bm] ]
621
622[[`T left_subtract(T, const T&)`] [1] [ ] [ ] [ ] [ ] ]
623[[`T right_subtract(T, const T&)`] [1] [ ] [ ] [ ] [ ] ]
624
625[[__biLInsertion__] [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
626[[`V T::insert(const P&)`] [ ] [__ei] [__bp] [__e] [__b] ]
627[[`V insert(T&, const P&)`] [ ] [__ei] [__bp] [__e] [__b] ]
628[[`J T::insert(J pos, const P&)`] [ ] [__i] [__p] [__e] [__b] ]
629[[`J insert(T&, J pos, const P&)`] [ ] [__i] [__p] [__e] [__b] ]
630[[`T& insert(T&, const P&)`] [ ] [__eiS] [__bpM] [__es] [__bm] ]
631[[`T& T::set(const P&)`] [ ] [ ] [__bp] [ ] [1] ]
632[[`T& set_at(T&, const P&)`] [ ] [ ] [__bp] [ ] [1] ]
633
634[[__biLErasure__] [ ] [ ] [ ] [ ] [ ] ]
635[[`void T::clear()`] [ ] [1] [1] [1] [1] ]
636[[`void clear(const T&)`] [ ] [1] [1] [1] [1] ]
637[[`T& T::erase(const P&)`] [ ] [__ei ] [__ei __bp] [__e] [__bp] ]
638[[`T& erase(T&, const P&)`] [ ] [__eiS][__eiS __bpM][__es] [__bm] ]
639[[`void T::erase(iterator)`] [ ] [1] [1] [1] [1] ]
640[[`void T::erase(iterator,iterator)`] [ ] [1] [1] [1] [1] ]
641
642[[__biLIntersection__] [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
643[[`void add_intersection(T&, const T&, const P&)`][ ] [__eiS][__eiS __bpM][ ] [ ] ]
644[[`T& operator &=(T&, const P&)`] [ ] [__eiS][__eiS __bpM][__es] [__bm] ]
645[[`T operator & (T, const P&)`\n
646 `T operator & (const P&, T)`] [__i] [__eiS][__eiS __bpM][__es] [__bm] ]
647[[`bool intersects(const T&, const P&)`\n
648 `bool disjoint(const T&, const P&)`] [__i] [__eiS][__eiS __bpM][__es] [__bm] ]
649
650[[__biLSymmetricDifference__] [ ] [ ] [ ] [ ] [ ] ]
651[[`T& T::flip(const P&)`] [ ] [__ei] [__bp] [ ] [__b] ]
652[[`T& flip(T&, const P&)`] [ ] [__ei] [__bp] [__e] [__b] ]
653[[`T& operator ^=(T&, const P&)`] [ ] [__eiS] [__bpM] [__es] [__bm] ]
654[[`T operator ^ (T, const P&)`\n
655 `T operator ^ (const P&, T)`] [ ] [__eiS] [__bpM] [__es] [__bm] ]
656
657[[__biLIteratorRelated__] [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
658[[`J T::begin()`] [ ] [2] [2] [2] [2] ]
659[[`J T::end()`] [ ] [2] [2] [2] [2] ]
660[[`J T::rbegin()`] [ ] [2] [2] [2] [2] ]
661[[`J T::rend()`] [ ] [2] [2] [2] [2] ]
662[[`J T::lower_bound(const key_type&)`] [ ] [2] [2] [2] [2] ]
663[[`J T::upper_bound(const key_type&)`] [ ] [2] [2] [2] [2] ]
664[[`pair<J,J> T::equal_range(const key_type&)`] [ ] [2] [2] [2] [2] ]
665
666[[__biLElementIteration__] [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
667[[`K elements_begin(T&)`] [ ] [2] [2] [ ] [ ] ]
668[[`K elements_end(T&)`] [ ] [2] [2] [ ] [ ] ]
669[[`K elements_rbegin(T&)`] [ ] [2] [2] [ ] [ ] ]
670[[`K elements_rend(T&)`] [ ] [2] [2] [ ] [ ] ]
671
672[[__biLStreaming__ ] [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
673[[`std::basic_ostream operator << (basic_ostream&, const T&)`]
674 [1] [1] [1] [1] [1] ]
675]
676
677Many but not all functions of *icl* intervals are listed in the table above.
678Some specific functions are summarized in the next table. For the group of
679the constructing functions, placeholders __d denote discrete domain types and
680__c denote continuous domain types `T::domain_type` for an interval_type `T` and an
681argument types `P`.
682
683[table Additional interval functions
684[[T] [__ch_dsc_itv__] [__ch_cnt_itv__] [__ch_ro_itv__] [__ch_lo_itv__] [__ch_cl_itv__] [__ch_op_itv__] ]
685[[Interval bounds] [dynamic] [dynamic] [static] [static] [static] [static] ]
686[[Form] [ ] [ ] [asymmetric] [asymmetric] [symmetric] [symmetric] ]
687[[__biLIntervalConstruct__ [#additional_interval_functions]]
688 [ ] [ ] [ ] [ ] [ ] [ ] ]
689[[`T singleton(const P&)`] [__d] [__c] [__d] [__d] [__d] [__d] ]
690[[`T construct(const P&, const P&)`] [__d] [__c] [__dc] [__dc] [__d] [__d] ]
691[[`T construct(const P&, const P&, interval_bounds)`] [__d] [__c] [ ] [ ] [ ] [ ] ]
692[[`T hull(const P&, const P&)`] [__d] [__c] [__dc] [__dc] [__d] [__d] ]
693[[`T span(const P&, const P&)`] [__d] [__c] [__dc] [__dc] [__d] [__d] ]
694[[`static T right_open(const P&, const P&)`] [__d] [__c] [ ] [ ] [ ] [ ] ]
695[[`static T left_open(const P&, const P&)`] [__d] [__c] [ ] [ ] [ ] [ ] ]
696[[`static T closed(const P&, const P&)`] [__d] [__c] [ ] [ ] [ ] [ ] ]
697[[`static T open(const P&, const P&)`] [__d] [__c] [ ] [ ] [ ] [ ] ]
698[[__biLIntervalOrderings__] [ ] [ ] [ ] [ ] [ ] [ ] ]
699[[`bool exclusive_less(const T&, const T&)`] [1] [1] [1] [1] [1] [1] ]
700[[`bool lower_less(const T&, const T&)`\n
701 `bool lower_equal(const T&, const T&)`\n
702 `bool lower_less_equal(const T&, const T&)`] [1] [1] [1] [1] [1] [1] ]
703[[`bool upper_less(const T&, const T&)`\n
704 `bool upper_equal(const T&, const T&)`\n
705 `bool upper_less_equal(const T&, const T&)`] [1] [1] [1] [1] [1] [1] ]
706[[__biLIntervalMiscellaneous__] [ ] [ ] [ ] [ ] [ ] [ ] ]
707[[`bool touches(const T&, const T&)`] [1] [1] [1] [1] [1] [1] ]
708[[`T inner_complement(const T&, const T&)`] [1] [1] [1] [1] [1] [1] ]
709[[`difference_type distance(const T&, const T&)`] [1] [1] [1] [1] [1] [1] ]
710]
711
712[h4 Element iterators for interval containers]
713
714Iterators on [*interval conainers] that are refered to in section /Iteration/
715of the function synopsis table are
716['*segment iterators*]. They reveal the more implementation specific
717aspect, that the __conceptual__ aspect abstracts from.[/ NOTE Identical to function_element_iteration.qbk from here]
718Iteration over segments is fast, compared to an iteration over elements,
719particularly if intervals are large.
720But if we want to view our interval containers as containers
721of elements that are usable with std::algoritms, we need to
722iterate over elements.
723
724Iteration over elements . . .
725
726* is possible only for integral or discrete `domain_types`
727* can be very ['*slow*] if the intervals are very large.
728* and is therefore ['*depreciated*]
729
730On the other hand, sometimes iteration over interval containers
731on the element level might be desired, if you have some
732interface that works for `std::SortedAssociativeContainers` of
733elements and you need to quickly use it with an interval container.
734Accepting the poorer performance might be less bothersome at times
735than adjusting your whole interface for segment iteration.
736
737[caution So we advice you to choose element iteration over
738interval containers ['*judiciously*]. Do not use element iteration
739['*by default or habitual*]. Always try to achieve results using
740namespace global functions or operators
741(preferably inplace versions)
742or iteration over segments first.]
743
744[endsect][/ Function Synopsis]
745
746
747[endsect][/ Interface]
748
Ceph