ceph/src/boost/libs/icl/doc/implementation.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 [section Implementation]
  10
  11 The [link boost_icl.interface previous section] gave an overview over the interface
  12 of the *icl* outlining
  13 [link boost_icl.interface.class_templates class templates],
  14 [link boost_icl.interface.associated_types associated types]
  15 and polymorphic
  16 [link boost_icl.interface.function_synopsis functions and operators].
  17 In preparation to the
  18 [link boost_icl.function_reference next section],
  19 that describes the *icl's* polymorphic functions in
  20 more detail together with ['*complexity characteristics*],
  21 this section summarizes some general information on
  22 implementation and performance.
  23
  24 [h5 STL based implementation]
  25
  26 The *implementation* of the *icl's* containers is based on
  27 [*std::set] and [*std::map]. So the underlying data structure of
  28 interval containers is a red black tree of intervals or
  29 interval value pairs.
  30 The element containers __icl_set__ and __icl_map__ are wrapper
  31 classes of `std::set` and `std::map`.
  32 Interval containers are then using __icl_sets__ of intervals
  33 or __icl_maps__ of interval value pairs as implementing
  34 containers.
  35 So all the ['*complexity characteristics*] of icl containers
  36 are based on and limited by the ['*red-black tree implementation*]
  37 of the underlying std::AssociativeContainers.
  38
  39
  40 [section Iterative size]
  41
  42 Throughout the documentation on complexity,
  43 big /O/ expressions like __On__ or __Omlgn__ refer to container sizes
  44 /n/ and /m/. In this documentation these sizes ['*do not*] denote
  45 to the familiar `size` function that returns
  46 the ['*number of elements*] of a container. Because for an interval container
  47 ``
  48 interval_set<int> mono;
  49 mono += interval<int>::closed(1,5); // {[1 ... 5]}
  50 mono.size()           == 5;         // true, 5 elements
  51 mono.interval_count() == 1;         // true, only one interval
  52 ``
  53
  54 it's size and the number of contained intervals is usually different.
  55 To refer uniformly to a /size/ that matters for iteration, which is
  56 the decisive kind of size concerning algorithmic behavior there is a function
  57 ``
  58 bool T::iterative_size()const; // Number of entities that can be iterated over.
  59 ``
  60 for all element and interval containers of the icl. So for
  61 complexity statements throughout the icl's documentation
  62 the sizes will be `iterative_sizes` and big /O/ expressions like
  63 __Omlgn__ will refer to sizes
  64 ``
  65 n = y.iterative_size();
  66 m = x.iterative_size();
  67 ``
  68 for containers `y` and `x`.
  69 Note that ``iterative_size`` refers to the primary entities,
  70 that we can iterate over. For interval containers these
  71 are intervals or segments. ``Itervative_size`` never refers
  72 to element iteration for interval containers.
  73
  74 [endsect][/ Iterative size]
  75
  76
  77 [section Complexity]
  78
  79 [h4 Complexity of element containers]
  80
  81 Since ['element containers] __icl_set__ and __icl_map__ are only extensions of
  82 stl::set and stl::map, their complexity characteristics are
  83 accordingly. So their major operations insertion (addition),
  84 deletion and search are all using logarithmic time.
  85
  86 [h4 Complexity of interval containers]
  87
  88 The operations on ['interval containers] behave differently
  89 due to the fact that intervals unlike elements can overlap
  90 any number of other intervals in a container. As long as
  91 intervals are relatively small or just singleton, interval
  92 containers behave like containers of elements.
  93 For large intervals however time consumption of operations
  94 on interval containers may be worse, because most or all
  95 intervals of a container may have to be visited.
  96 As an example, time complexity of __biLAddition__ on
  97 interval containers is briefly discussed.
  98
  99 More information on ['*complexity characteristics*]
 100 of *icl's* functions is contained in section
 101 [link boost_icl.function_reference Function Reference]
 102
 103
 104 [h5 Time Complexity of Addition]
 105
 106 The next table
 107 gives the time complexities for the overloaded
 108 `operator +=` on interval containers.
 109 The instance types of `T` are given as column headers.
 110 Instances of type parameter `P` are denoted in
 111 the second column.
 112 The third column contains the specific kind of complexity statement.
 113 If column three is empty ['*worst case*] complexity is given
 114 in the related row.
 115
 116
 117 [table Time Complexity of Addition:
 118 [[]                                             [`P`]               [][interval\nset][separate\ninterval\nset][split\ninterval\nset][interval\nmap][split\ninterval\nmap]]
 119 [/ 1operation                                   2granul.            3case        4itvset       5se_itvset    6sp_itvset    7itv_map      8sp_itvmap]
 120 [[`T& operator +=(T& object, const P& addend)`] [`T::element_type`] []           [__Olgn__]    [__Olgn__]    [__Olgn__]    [__Olgn__]    [__Olgn__]    ]
 121 [[]                                             [`T::segment_type`] [best case]  [__Olgn__]    [__Olgn__]    [__Olgn__]    [__Olgn__]    [__Olgn__]    ]
 122 [[]                                             []                  [worst case] [__On__]      [__On__]      [__On__]      [__On__]      [__On__]      ]
 123 [[]                                             []                  [amortized]  [__Olgn__]    [__Olgn__]    []            []            []            ]
 124 [[]                                             [`interval_sets`]   []           [__Omlgnpm__] [__Omlgnpm__] [__Omlgnpm__] [           ] [           ] ]
 125 [[]                                             [`interval_maps`]   []           [           ] [           ] [           ] [__Omlgnpm__] [__Omlgnpm__] ]
 126 ]
 127
 128 Adding an /element/ or
 129 /element value pair/ is always done in /logarithmic time/,
 130 where /n/ is the number of intervals in the interval container.
 131 The same row of complexities applies to the insertion
 132 of a /segment/ (an interval or an interval value pair)
 133 in the ['*best case*], where the inserted segment does overlap
 134 with only a ['*small*] number of intervals in the container.
 135
 136 In the ['*worst case*], where the inserted segment overlaps with
 137 all intervals in the container, the algorithms
 138 iterate over all the overlapped segments.
 139 Using inplace manipulations of segments and
 140 hinted inserts, it is possible to perform
 141 all necessary operations on each iteration step
 142 in /constant time/.
 143 This results in ['*linear worst case time*] complexity for
 144 segment addition for all interval containers.
 145
 146 After performing
 147 a worst case addition
 148 for an __itv_set__ or a __sep_itv_sets__
 149 adding an interval that overlaps /n/
 150 intervals, we
 151 need /n/ non overlapping additions of
 152 /logarithmic time/ before we can launch
 153 another __On__ worst case addition.
 154 So we have only a ['*logarithmic amortized
 155 time*] for the addition of an interval or interval value pair.
 156
 157 For the addition of ['*interval containers*] complexity is __Omlgnpm__.
 158 So for the ['*worst case*], where the container sizes /n/ and /m/
 159 are equal and both containers cover the same ranges,
 160 the complexity of container addition is ['*loglinear*].
 161 For other cases, that occur frequently in real world applications
 162 performance can be much better.
 163 If the added container `operand` is much smaller than
 164 `object` and the intervals in `operand` are relatively
 165 small, performance can be /logarithmic/.
 166 If /m/ is small compared with /n/ and intervals in `operand`
 167 are large, performance tends to be /linear/.
 168
 169 [endsect][/ Complexity]
 170
 171 [section Inplace and infix operators]
 172
 173 For the major operations /addition, subtraction, intersection/
 174 of *icl* containers and for /symmetric difference/
 175 inplace `operator`s `+= |=, -=, &=` and `^=`
 176 are provided.
 177
 178 For every ['*inplace*] operator
 179 ``
 180 T& operator o= (T& object, const P& operand)
 181 ``
 182 the *icl* provides corresponding ['*infix*] operators.
 183 ``
 184 T operator o (T object, const P& operand){ return object o= operand; }
 185 T operator o (const P& operand, T object){ return object o= operand; }
 186 ``
 187
 188 From this implementation of the infix `operator o`
 189 the compiler will hopefully use return value optimization
 190 [@http://en.wikipedia.org/wiki/Return_value_optimization (RVO)]
 191 creating no temporary object and performing one copy of
 192 the first argument `object`.
 193
 194 [caution
 195 Compared to the /inplace/ `operator o=` every use of an
 196 /infix/ `operator o` requires ['*one extra copy*]
 197 of the first argument `object` that passes a container.]
 198
 199 Use infix operators only, if
 200
 201 * efficiency is not crucial, e.g. the containers copied are small.
 202 * a concise and short notation is more important than efficiency in your context.
 203 * you need the result of operator `o=` as a copy anyway.
 204
 205 [h5 Time Complexity of infix `operators o`]
 206
 207 The time complexity of all infix operators of the *icl*
 208 is biased by the extra copy of the `object` argument.
 209 So all infix `operators o` are at least
 210 /linear/ in `n = object.iterative_size()`.
 211 Taking this into account, the complexities of all
 212 infix operators can be determined
 213 from the corresponding inplace `operators o=` they depend
 214 on.
 215
 216 [endsect][/ Inplace and infix operators]
 217
 218
 219
 220 [endsect][/ Implementation]
 221