2 Copyright (c) 2008-2010 Joachim Faulhaber
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)
11 Section *Interface* outlines types and functions
12 of the *Icl*. Synoptical tables allow to review the overall structure of
13 the libraries design and to focus on structural equalities and differences
14 with the corresponding containers of the standard template library.
17 [section Class templates]
21 In the *icl* we have two groups of interval types. There are ['*statically bounded*] intervals,
26 that always have the the same kind of interval borders and ['*dynamically bounded*] intervals,
29 which can have one of the four possible bound types at runtime.
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__] []]
42 Not every class template works with all domain types. Use interval class templates
43 according the next table.
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] ]
55 From a pragmatical point of view, the most important interval class template
56 of the /statically bounded/ group is __ro_itv__. For discrete domain types
57 also closed intervals might be convenient. Asymmetric intervals can be used
58 with continuous domain types but __ct_itv__ is the only class template that
59 allows to represent a singleton interval that contains only one element.
61 Use __ct_itv__, if you work with interval containers of countinuous domain types
62 and you want to be able to handle single values:
65 typedef interval_set<std::string, std::less, continuous_interval<std::string> > IdentifiersT;
66 IdentifiersT identifiers, excluded;
67 identifiers += continuous_interval<std::string>::right_open("a", "c");
69 // special identifiers shall be excluded
70 identifiers -= std::string("boost");
71 cout << "identifiers: " << identifiers << endl;
73 excluded = IdentifiersT(icl::hull(identifiers)) - identifiers;
74 cout << "excluded : " << excluded << endl;
76 //------ Program output: --------
77 identifiers: {[a,boost)(boost,c)}
78 excluded : {[boost,boost]}
81 [h4 Library defaults and class template `interval`]
83 As shown in the example above, you can choose an interval type
84 by instantiating the interval container template with the desired type.
87 typedef interval_set<std::string, std::less, continuous_interval<std::string> > IdentifiersT;
90 But you can work with the library default for interval template parameters as well,
91 which is `interval<DomainT,Compare>::type`.
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__] ]
100 So, if you are always happy with the library default for the interval type, just use
102 icl::interval<MyDomainT>::type myInterval;
104 as you standard way of declaring intervals and default parameters for interval containers:
106 typedef interval_set<std::string> IdentifiersT;
107 IdentifiersT identifiers, excluded;
108 identifiers += interval<std::string>::right_open("a", "c");
112 So class template __itv__ provides a standard way to work with the library default
113 for intervals. Via `interval<D,C>::type` you can declare a default interval.
114 In addition four static functions
116 T interval<D,C>::right_open(const D&, const D&);
117 T interval<D,C>::left_open(const D&, const D&);
118 T interval<D,C>::closed(const D&, const D&);
119 T interval<D,C>::open(const D&, const D&);
121 allow to construct intervals of the library default `T = interval<D,C>::type`.
125 #define BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS
127 the library uses only statically bounded __ro_itv__ as default interval type.
128 In this case, the four static functions above are also available,
129 but they only move interval borders consistently, if
130 their domain type is discrete, and create an appropriate __ro_itv__ finally:
132 interval<D,C>::right_open(a,b) == [a, b) -> [a , b )
133 interval<D,C>:: left_open(a,b) == (a, b] -> [a++, b++)
134 interval<D,C>:: closed(a,b) == [a, b] -> [a , b++)
135 interval<D,C>:: open(a,b) == (a, b) -> [a++, b )
138 For continuous domain types only the first of the four functions is applicable
139 that matches the library default for statically bounded intervals: __ro_itv__.
140 The other three functions can not perform an appropriate tranformation and
143 [endsect][/ Intervals]
147 The next two tables give an overview over ['*set class templates*] of
151 [/ separate_interval_set]
152 [/ split_interval_set]
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>`]]
164 Templates and template parameters, given in the preceding table are
165 described in detail below.
166 __Itv_bsets__ represent three
167 class templates __itv_set__, __sep_itv_set__ and __spl_itv_set__
168 that all have equal template parameters.
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`]]
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>`]]
185 The next two tables give an overview over ['*map class templates*] of the icl.
188 [/ split_interval_map]
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>`]]
200 Templates and template parameters, given in the preceding table are
201 described in detail below.
202 __Itv_bmaps__ represent two
203 class templates __itv_map__ and __spl_itv_map__
204 that all have equal template parameters.
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>`]]
215 Using the following placeholders,
219 C := class CodomainT,
221 cp := template<class D>class Compare = std::less,
222 cb := template<class C>class Combine = icl::inplace_plus,
223 s := template<class C>class Section = icl::inplace_et,
224 I := class IntervalT = icl::interval<D,cp>::type
225 a := template<class>class Alloc = std::allocator
228 we arrive at a final synoptical matrix of class templates and their parameters.
232 interval_sets<D, cp, I, a >
233 interval_maps<D, C, T, cp, cb, s, I, a >
234 icl::map <D, C, T, cp, cb, s, a >
237 The choice of parameters and their positions follow the std::containers
238 as close a possible, so that usage of interval sets and maps does only
239 require minimal additional knowledge.
241 Additional knowledge is required when instantiating a comparison parameter
242 `Compare` or an allocation parameter `Alloc`. In contrast to std::containers
243 these have to be instantiated as templates, like e.g.
245 interval_set<string, german_compare> sections; // 2nd parameter is a template
246 std::set<string, german_compare<string> > words; // 2nd parameter is a type
250 [endsect][/ Class templates]
252 [section Required Concepts]
254 There are uniform requirements for the template parameters
255 across *icl's* class templates. The template parameters can
256 be grouped with respect to those requirements.
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.]]
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>`] ]
284 [h4 Requirements on DomainT]
286 The next table gives an overview over the requirements for
287 template parameter `DomainT`. Some requirements are dependent
288 on /conditions/. Column /operators/ shows the operators and
289 functions that are expected for `DomainT`, if the default order
290 `Compare = std::less` is used.
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>`] ]
299 A domain type `DomainT` for intervals and interval containers
300 has to satisfy the requirements of concept
301 [@http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=314 `Regular`]
303 implies among other properties the existence of a copy and
304 a default constructor. In addition `IsIncrementable`
305 *or* `HasUnitElement` is required for `DomainT`.
306 In the *icl* we represent an empty closed interval as
307 interval `[b,a]` where `a < b` (here `<` represents `Compare<DomainT>()`).
308 To construct one of these empty intervals as default constructor
309 for any type `DomainT` we choose `[1,0]`, where `0` is a null-value or `identity_element`
310 and `1` is a one-value or `unit_element`:
312 interval() := [unit_element<DomainT>::value(), identity_element<DomainT>::value()] //pseudocode
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`,
317 that is incremented once.
319 template <class Type>
320 inline Type unit_element<Type>::value(){ return succ(identity_element<Type>::value()); };
322 So a type `DomainT` that is `incrementable` will
323 also have an `unit_element`. If it does not, a `unit_element` can be provided.
324 A `unit_element` can be any value, that is greater as the `identity_element`
325 in the `Compare` order given.
326 An 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:
329 // Smallest 'visible' string that is greater than the empty string.
331 inline std::string unit_element<std::string>::value(){ return std::string(" "); };
334 Just as for the key type of std::sets and maps
335 template parameter `Compare` is required to be a
336 [@http://en.wikipedia.org/wiki/Strict_weak_ordering strict weak ordering] on `DomainT`.
338 Finally, if `DomainT` is an integral type, `DomainT` needs to
339 be `incrementable` and `decrementable`. This [''bicrementability']
340 needs to be implemented on the smallest possible unit of the
341 integral 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
343 not provide the required in- and decrementation on the least incrementable unit.
344 For __icl_itvs__ incementation and decementation is used
345 for computations between open to closed interval borders like e.g.
346 `[2,43) == [2,42]`. Such computations always need only
347 one in- or decrementation, if `DomainT` is an integral type.
349 [h5 Requirements on IntervalT]
351 Requirements on the `IntervalT` parameter are closely related to the
352 `DomainT` parameter. `IntervalT` has two associated types
353 itself for an element type and a compare order that have
354 to be consistent with the element and order parameters of
355 their 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)``
359 if all `DomainT` elements of `x` are less than elements of `y` in the
363 [[Parameter] [Operators] [Requirement] ]
364 [[`IntervalT`] [`exclusive_less`] [`IsExclusiveLessComparable<Interval<DomainT,Compare> >`] ]
367 [h4 Requirements on CodomainT]
369 Summarized 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/
372 contains the operators and functions required for `CodomainT`, if we are
373 using the default combiner `Combine = icl::inplace_plus`.
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>`] ]
384 The requirements on the type `CodomainT` of associated values for a __icl_map__ or __itv_map__
385 depend on the usage of their aggregation functionality. If aggregation on overlap
386 is never used, that is to say that none of the addition, subtraction and intersection
387 operations (`+, +=, 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].
392 object semantics implies `DefaultConstructible` and
393 `EqualityComparable` which means it has
394 a default ctor `CodomainT()` and an `operator ==`.
396 Use __itv_maps__ ['*without aggregation*], if the associated values are not
398 are attached to intervals so you want to use __itv_maps__ to handle them.
399 As long as those values are added with `insert` and deleted with `erase`
400 __itv_maps__ will work fine with such values.
402 If ['*only addition*] is used via __itv_map_s__ `+, +=` or `add` but no subtraction,
403 then `CodomainT` need to be `Combinable` for functor template `Combine`. That
404 means in most cases when the default implementation `inplace_plus` for
405 `Combine` is used, that `CodomainT` has to implement `operator +=`.
407 For associated value types, that are addable but not subtractable like
408 e.g. `std::string` it usually makes sense to use addition to combine values
409 but the inverse combination is not desired.
411 interval_map<int,std::string> cat_map;
412 cat_map += make_pair(interval<int>::rightopen(1,5),std::string("Hello"));
413 cat_map += make_pair(interval<int>::rightopen(3,7),std::string(" world"));
414 cout << "cat_map: " << cat_map << endl;
415 //cat_map: {([1,3)->Hello)([3,5)->Hello world)([5,7)-> world)}
418 For ['complete aggregation functionality] an inverse aggregation functor on
419 a `Map`'s `CodomainT` is needed. The icl provides a
420 metafunction [classref boost::icl::inverse inverse]
421 for that purpose. Using the default
422 `Combine = inplace_plus` that relies on the existence of `operator +=`
424 metafunction [classref boost::icl::inverse inverse]
425 will infer [classref boost::icl::inplace_minus inplace_minus]
426 as inverse functor, that requires `operator -=` on type `CodomainT`.
428 In the icl's design we make the assumption,
429 in particular for the default setting of parameters
430 `Combine = `[classref boost::icl::inplace_minus inplace_plus],
431 that type `CodomainT` has a neutral element or `identity_element`
432 with respect to the `Combine` functor.
435 [endsect][/ Required Concepts]
438 [section Associated Types]
440 In order to give an overview over ['*associated types*] the *icl* works
441 with, we will apply abbreviations again that were introduced in the
442 presentaiton of icl class templates,
446 interval_sets<D, cp, I, a >
447 interval_maps<D, C, T, cp, cb, s, I, a >
448 icl::map <D, C, T, cp, cb, s, a >
451 where these placeholders were used:
455 C := class CodomainT,
457 cp := template<class D>class Compare = std::less,
458 cb := template<class C>class Combine = icl::inplace_plus,
459 s := template<class C>class Section = icl::inplace_et,
460 I := class Interval = icl::interval<D,cp>::type
461 a := template<class>class Alloc = std::allocator
465 sz := template<class D>class size
466 df := template<class D>class difference
467 Xl := class ExclusiveLess = exclusive_less<Interval<DomainT,Compare> >
468 inv:= template<class Combiner>class inverse
469 (T,U) := std::pair<T,U> for typnames T,U
472 we can summarize the associated types as follows.
473 Again two additional columns for easy comparison with stl
474 sets and maps are provided.
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>>`] ]
503 [endsect][/ Associated Types]
505 [section Function Synopsis]
507 In this section a single ['*matrix*] is given, that shows all ['*functions*]
508 with shared names and identical or analogous semantics and their
509 polymorphic overloads across the class templates of the *icl*.
510 In order to achieve a concise representation, a series
511 of ['*placeholders*] are used throughout the function matrix.
513 The ['*placeholder's*] purpose is to express the polymorphic
514 usage of the functions. The ['*first column*] of the function matrix
515 contains the signatures of the functions. Within these
516 signatures `T` denotes a container type and `J` and `P`
517 polymorphic argument and result types.
519 Within the body of the matrix, sets of *boldface* placeholders denote
520 the sets of possible instantiations for a polymorphic
521 placeholder `P`. For instance __eiS denotes that for the
522 argument type `P`, an element __e, an interval __i or an interval_set __S
525 If the polymorphism can not be described in this way, only the ['*number*] of
526 overloaded implementations for the function of that row is shown.
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.]]
549 [/ memberref boost::icl::set::iterative_size `iterative_size`]
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] ]
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] ]
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] ]
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] [ ] [ ] ]
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] ]
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] [ ] [ ] ]
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] ]
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] ]
619 [[`T& operator -=(T&, const P&)`] [ ] [__eiS][__eiS __bpM][__es] [__bm] ]
620 [[`T operator - (T, const P&)`] [ ] [__eiS][__eiS __bpM][__es] [__bm] ]
622 [[`T left_subtract(T, const T&)`] [1] [ ] [ ] [ ] [ ] ]
623 [[`T right_subtract(T, const T&)`] [1] [ ] [ ] [ ] [ ] ]
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] ]
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] ]
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] ]
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] ]
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] ]
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] [ ] [ ] ]
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] ]
677 Many but not all functions of *icl* intervals are listed in the table above.
678 Some specific functions are summarized in the next table. For the group of
679 the 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
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] ]
712 [h4 Element iterators for interval containers]
714 Iterators on [*interval conainers] that are refered to in section /Iteration/
715 of the function synopsis table are
716 ['*segment iterators*]. They reveal the more implementation specific
717 aspect, that the __conceptual__ aspect abstracts from.[/ NOTE Identical to function_element_iteration.qbk from here]
718 Iteration over segments is fast, compared to an iteration over elements,
719 particularly if intervals are large.
720 But if we want to view our interval containers as containers
721 of elements that are usable with std::algoritms, we need to
722 iterate over elements.
724 Iteration over elements . . .
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*]
730 On the other hand, sometimes iteration over interval containers
731 on the element level might be desired, if you have some
732 interface that works for `std::SortedAssociativeContainers` of
733 elements and you need to quickly use it with an interval container.
734 Accepting the poorer performance might be less bothersome at times
735 than adjusting your whole interface for segment iteration.
737 [caution So we advice you to choose element iteration over
738 interval containers ['*judiciously*]. Do not use element iteration
739 ['*by default or habitual*]. Always try to achieve results using
740 namespace global functions or operators
741 (preferably inplace versions)
742 or iteration over segments first.]
744 [endsect][/ Function Synopsis]
747 [endsect][/ Interface]
projects / ceph.git / blob