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 749