ceph/src/boost/libs/icl/doc/functions.qbk

   1 [/
   2     Copyright (c) 2008-2009 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
  10 [section Function Reference]
  11
  12 Section [link boost_icl.interface.function_synopsis Function Synopsis]
  13 above gave an overview of the polymorphic functions of the icl.
  14 This is what you will need to find the desired possibilities to combine icl
  15 functions and objects most of the time.
  16 The functions and overloads that you intuitively expect
  17 should be provided, so you won't need to refer to the documentation very often.
  18
  19 If you are interested
  20
  21 * in the ['*specific design of the function overloads*],
  22 * in ['*complexity characteristics*] for certain overloads
  23 * or if the compiler ['*refuses to resolve*] specific function application you want to use,
  24
  25 refer to this section that describes the polymorphic function families of the icl
  26 in detail.
  27
  28 [h5 Placeholders]
  29
  30 For a concise representation the same __eiS_phs__ will be used that have been
  31 introduced in section [link boost_icl.interface.function_synopsis Function Synopsis].
  32
  33 [h5 More specific function documentation]
  34
  35 This section covers the most important polymorphic and namespace global
  36 functions of the *icl*. More specific functions can be looked up
  37 in the doxygen generated
  38 [link interval_container_library_reference reference documentation].
  39
  40 [section Overload tables]
  41
  42 Many of the *icl's* functions are overloaded for
  43 elements, segments, element and interval containers.
  44 But not all type combinations are provided. Also
  45 the admissible type combinations are different for
  46 different functions and operations.
  47 To concisely represent the overloads that can be
  48 used we use synoptical tables that contain
  49 possible type combinations for an operation.
  50 These are called ['*overload tables*]. As an example
  51 the overload tables for the inplace intersection
  52 `operator &=` are given:
  53
  54 ``
  55 // overload tables for
  56 T& operator &= (T&, const P&)
  57
  58 element containers:     interval containers:
  59 &= | e b s m            &= | e i b p S M
  60 ---+--------            ---+------------
  61 s  | s   s              S  | S S     S
  62 m  | m m m m            M  | M M M M M M
  63 ``
  64
  65 For the binary `T& operator &= (T&, const P&)` there are two
  66 different tables for the overloads of element and interval containers.
  67 The first argument type `T` is displayed as row headers
  68 of the tables.
  69 The second argument type `P` is displayed as column headers
  70 of the tables.
  71 If a combination of `T` and `P` is admissible the related
  72 cell of the table is non empty.
  73 It displays the result type of the operation. In this example
  74 the result type is always equal to the first argument.
  75
  76 The possible types that can be instantiated for `T` and `P`
  77 are element, interval and container types abbreviated by
  78 placeholders that are defined
  79 [link boost_icl.interface.function_synopsis here]
  80 and can be summarized as
  81
  82 __s : element set, __S : interval sets, __e : elements, __i : intervals\n
  83 __m:element map,   __M:interval maps,   __b:element-value pairs, __p:interval-value pairs
  84
  85
  86 [endsect][/ Overload tables]
  87
  88 [section Segmentational Fineness]
  89
  90 For overloading tables on infix operators, we need to
  91 break down __itv_sets__ and __itv_maps__ to the
  92 specific class templates
  93
  94 [table
  95 [[][] [][] [][]]
  96 [[[#ph_def_S1][*S1]][__itv_set__][[#ph_def_S2][*S2]][__sep_itv_set__][[#ph_def_S3][*S3]][__spl_itv_set__]]
  97 [[[#ph_def_M1][*M1]][__itv_map__][][]                                [[#ph_def_M3][*M3]][__spl_itv_map__]]
  98 ]
  99
 100
 101 choosing *Si* and *Mi* as placeholders.
 102
 103 The indices *i* of *Si* and *Mi* represent a property
 104 called ['*segmentational fineness*] or short ['*fineness*],
 105 which is a ['*type trait*] on interval containers.
 106
 107 [table
 108 [[]]
 109 [[`segmentational_fineness<`[*Si]`>::value` == *i*]]
 110 [[`segmentational_fineness<`[*Mi]`>::value` == *i*]]
 111 ]
 112
 113
 114 Segmentational fineness represents the fact,
 115 that for interval containers holding the same elements, a
 116 splitting interval container may contain more segments as
 117 a separating container which in turn may contain more
 118 segments than a joining one. So for an
 119 ``
 120 operator >
 121 ``
 122 where
 123 ``
 124 x > y   // means that
 125 x is_finer_than y
 126
 127 // we have
 128
 129 finer                                             coarser
 130 split_interval_set                           interval_set
 131                    > separate_interval_set >
 132 split_interval_map                           interval_map
 133 ``
 134
 135 This relation is needed to resolve the instantiation of
 136 infix operators e.g. `T operator + (P, Q)` for two interval container types
 137 `P` and `Q`. If both `P` and `Q` are candidates for the result
 138 type `T`, one of them must be chosen by the compiler.
 139 We choose the type that is segmentational finer as
 140 result type `T`. This way we do not loose the ['*segment information*]
 141 that is stored in the ['*finer*] one of the container types `P` and `Q`.
 142
 143 ``
 144 // overload tables for
 145 T operator + (T, const P&)
 146 T operator + (const P&, T)
 147
 148 element containers:     interval containers:
 149 +  | e b s m            +  | e  i  b  p  S1 S2 S3 M1 M3
 150 ---+--------            ---+---------------------------
 151 e  |     s              e  |             S1 S2 S3
 152 b  |       m            i  |             S1 S2 S3
 153 s  | s   s              b  |                      M1 M3
 154 m  |   m   m            p  |                      M1 M3
 155                         S1 | S1 S1       S1 S2 S3
 156                         S2 | S2 S2       S2 S2 S3
 157                         S3 | S3 S3       S3 S3 S3
 158                         M1 |       M1 M1          M1 M3
 159                         M3 |       M3 M3          M3 M3
 160 ``
 161
 162
 163 So looking up a type combination for e.g.
 164 `T operator + (interval_map, split_interval_map)`
 165 which is equivalent to
 166 `T operator + (M1, M3)`
 167 we find for row type `M1` and column type `M3`
 168 that `M3`
 169 will be assigned as result type, because `M3`
 170 is finer than `M1`.
 171 So this type combination will result in
 172 choosing this
 173 ``
 174 split_interval_map operator + (const interval_map&, split_interval_map)
 175 ``
 176 implementation by the compiler.
 177
 178 [endsect][/ Segmentational Fineness]
 179
 180 [section Key Types]
 181
 182 In an *stl* map `map<K,D>` the first parameter type of the map
 183 template `K` is called `key_type`. It allows to select key-value pairs
 184 pairs via `find(const K&)`
 185 and to remove key-value pairs using `erase(const K&)`.
 186 For icl Maps we have generalized key types to a larger
 187 set of types. Not only the `key_type` (`domain_type`)
 188 but also an interval type and a set type can be ['*key types*],
 189 that allow for ['*selection*] and ['*removal*] of map elements
 190 segments and submaps.
 191
 192 [table Selection of elements, segments and sub maps using key types
 193 [[                     ][  __M: __itv_maps__    ][  __m: icl_map        ]]
 194 [[__e: `domain_type`   ][  key value pair       ][   key value pair ]]
 195 [[__i: `interval_type` ][  interval value pair  ][                     ]]
 196 [[__S: __itv_sets__    ][  interval map            ][                     ]]
 197 [[__s: __icl_set__     ][                       ][   interval map     ]]
 198 ]
 199
 200 __biLSubtraction__, __biLerasure__, __biLintersection__
 201 [/ , which is a generalized find ]
 202 and __biLcontainedness__ predicates
 203 can be used with those kinds of key types.
 204 For instance, the overload table for intersection
 205
 206 ``
 207 // overload tables for
 208 T& operator &= (T&, const P&)
 209
 210 element containers:     interval containers:
 211 &= | e b s m            &= | e i b p S M
 212 ---+--------            ---+------------
 213 s  | s   s              S  | S S     S
 214 m  | m m m m            M  | M M M M M M
 215 ``
 216
 217 has a part that that allows for selection by key objects
 218
 219 ``
 220 element containers:     interval containers:
 221 &= | e b s m            &= | e i b p S M
 222 ---+--------            ---+------------
 223 s  | s   s              S  | S S     S
 224 m  | m   m              M  | M M     M
 225 ``
 226
 227 and another part that provides overloads for
 228 generalized intersection:
 229
 230 ``
 231 element containers:     interval containers:
 232 &= | e b s m            &= | e i b p S M
 233 ---+--------            ---+------------
 234 s  | s   s              S  | S S     S
 235 m  |   m   m            M  |     M M   M
 236 ``
 237
 238 For `Sets`, the ['*key types*] defined for maps
 239 are identical with the set types themselves.
 240 So the distinction between the function groups
 241 ['*selection by key*] and ['*generalized intersection*]
 242 fall together in the well known ['*set intersection*].
 243
 244 [endsect][/ Key Types]
 245
 246 [include functions_cons_copy_dest.qbk]
 247 [include functions_containedness.qbk]
 248 [include functions_equivs_orderings.qbk]
 249 [include functions_size.qbk]
 250 [include functions_range.qbk]
 251 [include functions_selection.qbk]
 252 [include functions_addition.qbk]
 253 [include functions_subtraction.qbk]
 254 [include functions_insertion.qbk]
 255 [include functions_erasure.qbk]
 256 [include functions_intersection.qbk]
 257 [include functions_symmetric_difference.qbk]
 258 [include functions_iterator_related.qbk]
 259 [include functions_element_iteration.qbk]
 260 [include functions_streaming.qbk]
 261
 262 [include functions_interval_construct.qbk]
 263 [include functions_interval_orderings.qbk]
 264 [include functions_interval_misc.qbk]
 265
 266
 267 [endsect][/ Function Reference]
 268
 269