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

   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
  10 [/ //= Equivalences and Orderings ===================================================]
  11 [section Equivalences and Orderings]
  12
  13 [section Synopsis][/ Equivalences and Orderings]
  14
  15 [table
  16 [[['*Equivalences and Orderings*]][__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
  17 [[['Segment Ordering]]                         [ ]       [ ]      [ ]     [ ]      [ ]   ]
  18 [[`bool operator == (const T&, const T&)`]     [1]       [1]      [1]     [1]      [1]   ]
  19 [[`bool operator != (const T&, const T&)`]     [1]       [1]      [1]     [1]      [1]   ]
  20 [[`bool operator <  (const T&, const T&)`]     [1]       [1]      [1]     [1]      [1]   ]
  21 [[`bool operator >  (const T&, const T&)`]     [1]       [1]      [1]     [1]      [1]   ]
  22 [[`bool operator <= (const T&, const T&)`]     [1]       [1]      [1]     [1]      [1]   ]
  23 [[`bool operator >= (const T&, const T&)`]     [1]       [1]      [1]     [1]      [1]   ]
  24 [[['Element Ordering]]                         [ ]       [ ]      [ ]     [ ]      [ ]   ]
  25 [[`bool is_element_equal(const T&, const P&)`] [ ]     [__S]    [__M]     [1]      [1]   ]
  26 [[`bool is_element_less(const T&, const P&)`]  [ ]     [__S]    [__M]     [1]      [1]   ]
  27 [[`bool is_element_greater(const T&, const P&)`][ ]    [__S]    [__M]     [1]      [1]   ]
  28 [[['Distinct Equality]]                        [ ]       [ ]      [ ]     [ ]      [ ]   ]
  29 [[`bool is_distinct_equal(const T&, const P&)`][ ]       [ ]    [__M]     [ ]      [1]   ]
  30 ]
  31
  32
  33 [endsect][/ Synopsis Equivalences and Orderings]
  34
  35 [section Less on Intervals]
  36
  37 [table
  38 [[ ]    [Types][]]
  39 [[`x < y`]   [__i]   [`x` begins before `y` or, for equal beginnings `x` ends before `y`]]
  40 ]
  41
  42 [endsect][/ Less on Intervals]
  43
  44 [section Lexicographical Ordering][/ Equivalences and Orderings]
  45
  46 All common equality and compare operators are defined for
  47 all objects of the *icl*. For all *icl* containers
  48 equality and compare operators implement lexicographical
  49 equality and lexicographical comparison, that depends on
  50 the equality of template parameter `Compare`.
  51 This includes the less ordering on intervals, that can be
  52 perceived as the sequence of elements between their lower and upper
  53 bound. This generalized lexicogrphical comparison in intervals
  54 can also be specified this way:
  55
  56 [table
  57 []
  58 [[`x < y`]  [`:=`]  [`x` begins before `y` or, for equal beginnings `x` ends before `y`.]]
  59
  60 [[]         []      [The other operators can be deduced in the usual way]]
  61 [[`x > y`]  [`:=`]  [`y < x`] ]
  62 [[`x <= y`] [`:=`]  [`!(y < x)`] ]
  63 [[`x >= y`] [`:=`]  [`!(x < y)`] ]
  64 [[`x == y`] [`:=`]  [`!(x < y) && !(y < x)` induced equivalence] ]
  65 [[`x != y`] [`:=`]  [`!(x == y)`] ]
  66 ]
  67
  68
  69 Equality and compare operators are defined for all *icl*
  70 objects but there are no overloads between different types.
  71
  72 Containers of different segmentation are different,
  73 even if their elements are the same:
  74 ``
  75 split_interval_set<time> w1, w2; //Pseudocode
  76 w1 = {[Mon       ..       Sun)}; //split_interval_set containing a week
  77 w2 = {[Mon .. Fri)[Sat .. Sun)}; //Same week split in work and week end parts.
  78 w1 == w2;                        //false: Different segmentation
  79 is_element_equal(w1,w2);         //true:  Same elements contained
  80 ``
  81
  82 [*Complexity] is ['*linear*] in the `iterative_size` of the shorter
  83 container to compare.
  84
  85 [endsect][/ Lexicographical Ordering; Equivalences and Orderings]
  86
  87
  88 [/ ----------------------------------------------------------------------------]
  89
  90 [section Sequential Element Ordering][/ Equivalences and Orderings]
  91
  92 The ['*Sequential Element Ordering*] abstracts from the way in which
  93 elements of interval containers are clustered into intervals:
  94 it's ['*segmentation*].
  95
  96 So these equality and compare operations can be applied within
  97 interval container types. The admissible type combinations are summarized
  98 in the next overload table.
  99
 100 ``
 101 // overload tables for
 102 bool is_element_equal  (const T&, const P&)
 103 bool is_element_less   (const T&, const P&)
 104 bool is_element_greater(const T&, const P&)
 105
 106 element containers:     interval containers:
 107 T\P| s m                T\P| S1 S2 S3 M1 M3
 108 ---+----                ---+---------------
 109 s  | 1                  S1 | 1  1  1
 110 m  |   1                S2 | 1  1  1
 111                         S3 | 1  1  1
 112                         M1 |          1  1
 113                         M3 |          1  1
 114 ``
 115
 116 For element containers lexicographical equality and
 117 sequential element equality are identical.
 118
 119 The *complexity* of sequential element comparison functions
 120 is ['*linear*] in the `iterative_size` of the larger
 121 container.
 122
 123 [endsect]
 124
 125 [section Distinct Equality]
 126
 127 ['*Distinct Equality*] is an equality predicate that is available
 128 for __icl_maps__ and __itv_maps__. It yields true, if
 129 two maps are sequential element equal except for value
 130 pairs whose associated values are identity elements.
 131
 132 [*Complexity] is linear in the `iterative_size` of the
 133 larger container to compare.
 134
 135 [endsect]
 136
 137
 138 ['*See also . . .*]
 139 [table
 140 []
 141 [[[link boost_icl.semantics.orderings_and_equivalences ['*Semantics*]]]]
 142 ]
 143 ['*Back to section . . .*]
 144 [table
 145 []
 146 [[[link function_synopsis_table ['*Function Synopsis*]]]]
 147 [[[link boost_icl.interface ['*Interface*]]                          ]]
 148 ]
 149
 150 [endsect][/ Equivalences and Orderings]
 151
 152