ceph/src/boost/libs/icl/doc/introduction.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 [section Introduction]
  10
  11 [/ note [* The Interval Container Library is accepted into Boost]
  12
  13 The [*Interval Container Library] (formerly /Interval Template Library/) underwent
  14 a formal review on the boost developer's list
  15 from February 18, 2010 to March 08, 2010 and has been accepted
  16 by declaration of review manager Hartmut Kaiser
  17 into the boost library collection on April 18, 2010.
  18
  19
  20 The library has been refactored for the suggestions and requests
  21 that came up during the review. The current version is now
  22 ready for inclusion into the next boost release.
  23 The name ['*Interval Template Library (ITL)*]
  24 has been changed to ['*Interval Container Library (ICL)*].
  25
  26 If you find bugs in the library or typos or other shortcomings in
  27 the documentation please send reports to the boost developers list
  28 boost@lists.boost.org
  29 the boost users list or
  30 boost-users@lists.boost.org
  31 to `[afojgo<AT>gmail dot com]`.
  32
  33 ]
  34
  35 ["A bug crawls across the boost docs on my laptop screen.
  36 Let him be! We need all the readers we can get.] --
  37 Freely adapted from [@http://en.wikipedia.org/wiki/Jack_Kornfield Jack Kornfield]
  38
  39 Intervals are almost ubiquitous in software development. Yet they are
  40 very easily coded into user defined classes by a pair of numbers
  41 so they are only /implicitly/ used most of the time. The meaning of
  42 an interval is simple. They represent all the elements between their
  43 lower and upper bound and thus a set. But unlike sets, intervals
  44 usually can not be added to a single new interval.
  45 If you want to add intervals to a collection of
  46 intervals that does still represent a /set/,
  47 you arrive at the idea of /interval_sets/ provided by this library.
  48
  49 Interval containers of the *ICL* have been developed initially at
  50 [@http://www.cortex-software.de/desktopdefault.aspx Cortex Software GmbH]
  51 to solve problems related to date and time interval
  52 computations in the context of a Hospital Information System.
  53 Time intervals with associated values like ['amount of invoice]
  54 or ['set of therapies] had to be manipulated in statistics,
  55 billing programs and therapy scheduling programs.
  56 So the *ICL* emerged out of those industrial use cases.
  57 It extracts generic code that helps to solve common
  58 problems from the date and time problem domain and can be
  59 beneficial in other fields as well.
  60
  61 One of the most advantageous aspects of interval containers is
  62 their very compact representation of sets and maps. Working with
  63 sets and maps /of elements/ can be very inefficient, if in a given
  64 problem domain, elements are typically occurring in contiguous
  65 chunks.
  66 Besides a compact representation of associative containers, that
  67 can reduce the cost of space and time drastically, the ICL
  68 comes with a universal mechanism of aggregation, that allows
  69 to combine associated values in meaningful ways when intervals
  70 overlap on insertion.
  71
  72 For a condensed introduction and overview you may want to look at the
  73 [@http://www.herold-faulhaber.de/boost_icl/doc/libs/icl/doc/boostcon09/intro_to_itl.pdf
  74 presentation material on the *ICL* from ['*BoostCon2009*]].
  75
  76
  77 [section Definition and Basic Example]
  78
  79 The [*Interval Container Library (ICL)] provides __itvs__ and two kinds of
  80 interval containers: __itv_sets__ and __itv_maps__.
  81
  82 * An __itv_bset__ is a *set* that is implemented as a set of intervals.
  83 * An __itv_bmap__ is a *map* that is implemented as a map of interval value pairs.
  84
  85 [h4 Two Aspects]
  86
  87 __Itv_bsets__ and __itv_bmaps__ expose two different aspects in
  88 their interfaces: (1) The functionality of a set or a map, which is the more
  89 ['*abstract aspect*]. And (2) the functionality of a container of intervals which
  90 is the more specific and ['*implementation related aspect*]. In practice both
  91 aspects are useful and are therefore supported.
  92
  93 The first aspect, that will be called __bi_conceptual__ ['*aspect*], is the more important one.
  94 It means that we can use an __itv_set__ or __itv_map__ like a
  95 set or map ['*of elements*]. It exposes the same functions.
  96 ``
  97 interval_set<int> mySet;
  98 mySet.insert(42);
  99 bool has_answer = contains(mySet, 42);
 100 ``
 101
 102
 103 The second aspect, that will be called __bi_iterative__ ['*aspect*], allows to exploit the
 104 fact, that the elements of __itv_sets__ and __itv_maps__ are clustered in
 105 ['*intervals*] or ['*segments*] that we can iterate over.
 106
 107 ``
 108 // Switch on my favorite telecasts using an interval_set
 109 interval<seconds>::type news(make_seconds("20:00:00"), make_seconds("20:15:00"));
 110 interval<seconds>::type talk_show(make_seconds("22:45:30"), make_seconds("23:30:50"));
 111 interval_set<seconds> myTvProgram;
 112 myTvProgram.add(news).add(talk_show);
 113
 114 // Iterating over elements (seconds) would be silly ...
 115 for(interval_set<seconds>::iterator telecast = myTvProgram.begin();
 116     telecast != myTvProgram.end(); ++telecast)
 117     //...so this iterates over intervals
 118    TV.switch_on(*telecast);
 119 ``
 120
 121 Working with __itv_bsets__ and __itv_bmaps__ can be
 122 beneficial whenever the elements of
 123 sets appear in contiguous chunks: __itvs__. This is obviously the
 124 case in many problem domains, particularly in fields that deal with
 125 computations related to date and time.
 126
 127 [h4 Addabitlity and Subtractability]
 128
 129 Unlike `std::sets` and `maps`, __itv_bsets__ and __itv_bmaps__ implement
 130 concept `Addable` and `Subtractable`. So __itv_bsets__ define an
 131 `operator +=` that is naturally implemented as ['*set union*] and an
 132 `operator -=` that is consequently implemented as ['*set difference*].
 133 In the *Icl* __itv_bmaps__ are addable and subtractable as well.
 134 It turned out to be a very fruitful concept to propagate the
 135 addition or subtraction to the __itv_bmap_s__ associated values
 136 in cases where the insertion of an interval value pair into an
 137 __itv_map__ resulted in a collision of the inserted interval
 138 value pair with interval value pairs, that are already in the
 139 __itv_map__. This operation propagation is called ['*aggregate on overlap*].
 140
 141
 142 [h4 Aggregate on Overlap]
 143
 144 This is a first motivating example of a very small party, demonstrating the
 145 ['*aggregate on overlap*] principle on __itv_maps__:
 146
 147 In the example Mary enters the party first. She attends during the
 148 time interval `[20:00,22:00)`. Harry enters later. He stays within `[21:00,23:00)`.
 149 ``
 150 typedef std::set<string> guests;
 151 interval_map<time, guests> party;
 152 party += make_pair(interval<time>::right_open(time("20:00"), time("22:00")), guests("Mary"));
 153 party += make_pair(interval<time>::right_open(time("21:00"), time("23:00")), guests("Harry"));
 154 // party now contains
 155 [20:00, 21:00)->{"Mary"}
 156 [21:00, 22:00)->{"Harry","Mary"} //guest sets aggregated on overlap
 157 [22:00, 23:00)->{"Harry"}
 158 ``
 159 ['*On overlap of intervals*], the corresponding name sets are ['*accumulated*]. At
 160 the ['*points of overlap*] the intervals are ['*split*]. The accumulation of content on
 161 overlap of intervals is done via an `operator +=` that has to be implemented
 162 for the associated values of the __itv_map__. In the example
 163 the associated values are `guest sets`. Thus a `guest set` has to implement
 164 `operator +=` as set union.
 165
 166 As can be seen from the example an __itv_map__ has both
 167 a ['*decompositional behavior*] (on the time dimension) as well as
 168 an ['*accumulative one*] (on the associated values).
 169
 170 Addability and aggregate on overlap are useful features on
 171 __itv_maps__ implemented via function `add` and `operator +=`.
 172 But you can also use them with the ['traditional]
 173 [link boost_icl.function_reference.insertion insert semantics]
 174 that behaves like `std::map::insert` generalized for
 175 interval insertion.
 176
 177 [endsect]
 178
 179 [section Icl's class templates]
 180
 181 In addition to interval containers we can work with
 182 containers of elements that are ['*behavioral equal*]
 183 to the interval containers: On the fundamental aspect
 184 they have exactly the same functionality.
 185 An __std_set__ of the STL is such an equivalent set implementation.
 186 Due to the aggregation facilities of the icl's interval maps
 187 __std_map__ is fundamentally not completely equivalent to an __itv_map__.
 188 Therefore there is an extra __icl_map__ class template for maps of
 189 elements in the icl.
 190
 191
 192 * The __std_set__ is behavioral equal to __itv_bsets__ on the __bi_conceptual__ aspect.
 193
 194 * An __icl_map__ is behavioral equal to __itv_bmaps__ on the __bi_conceptual__  aspect.
 195   Specifically an __icl_map__
 196   implements ['*aggregate on overlap*], which is
 197   named ['*aggregate on collision*] for an element container.
 198
 199 The following tables give an overview over the main
 200 class templates provided by the *icl*.
 201
 202 [table Interval class templates
 203 [[group]              [form]      [template]          ]
 204 [[statically bounded] [asymmetric][__ro_itv__]        ]
 205 [[ ]                  []          [__lo_itv__]        ]
 206 [[ ]                  [symmetric] [__cl_itv__]        ]
 207 [[ ]                  []          [__op_itv__]        ]
 208 [[dynamically bounded][]          [__dc_itv__]        ]
 209 [[ ]                  []          [__ct_itv__]        ]
 210 ]
 211
 212 Statically bounded intervals always have the same kind of interval borders,
 213 e.g. right open borders`[a..b)` for __ro_itv__. Dynamically bounded intervals
 214 can have different borders. Refer to the chapter about
 215 [link boost_icl.interface.class_templates.intervals ['*intervals*]]
 216 for details.
 217
 218 [table Container class templates
 219 [[granularity][style]     [sets]           [maps]           ]
 220 [[interval]   [joining]   [__itv_set__]    [__itv_map__]    ]
 221 [[]           [separating][__sep_itv_set__][]               ]
 222 [[]           [splitting] [__spl_itv_set__][__spl_itv_map__]]
 223 [[element]    []          [(__ele_set__)]  [__ele_map__]    ]
 224 ]
 225
 226 __Std_set__ is placed in paretheses, because it is not a class template
 227 of the *ICL*. It can be used as element container though that is
 228 behavioral equal to the ICL's interval sets on their fundamental aspect.
 229 Column ['*style*] refers to
 230 the different ways in which interval containers combine added
 231 intervals. These ['*combining styles*] are described in the next
 232 section.
 233
 234
 235 [endsect]
 236
 237 [section Interval Combining Styles]
 238
 239 When we add intervals or interval value pairs to interval containers,
 240 the intervals can be added in different ways: Intervals can be
 241 joined or split or kept separate. The different interval combining
 242 styles are shown by example in the tables below.
 243
 244 [table Interval container's ways to combine intervals
 245     [[]         [joining]       [separating]            [splitting]]
 246     [[set]      [[classref boost::icl::interval_set          interval_set]]
 247                 [[classref boost::icl::separate_interval_set separate_interval_set]]
 248                 [[classref boost::icl::split_interval_set    split_interval_set]]]
 249     [[map]      [[classref boost::icl::interval_map          interval_map]]
 250                 []
 251                 [[classref boost::icl::split_interval_map    split_interval_map]]]
 252     [[]         [Intervals are joined on overlap or touch\n(if associated values are equal).]
 253                 [Intervals are joined on overlap, not on touch.]
 254                 [Intervals are split on overlap.\nAll interval borders are preserved.]]
 255 ]
 256
 257 [table Interval combining styles by example
 258     [[]         [joining]       [separating]            [splitting]]
 259     [[set]      [[classref boost::icl::interval_set          interval_set] /A/]
 260                 [[classref boost::icl::separate_interval_set separate_interval_set] /B/]
 261                 [[classref boost::icl::split_interval_set    split_interval_set] /C/]]
 262 [[]
 263 [``
 264   {[1      3)          }
 265 +       [2      4)
 266 +                 [4 5)
 267 = {[1                5)}``]
 268 [``
 269   {[1      3)}         }
 270 +       [2      4)
 271 +                 [4 5)
 272 = {[1           4)[4 5)}``]
 273 [``
 274   {[1      3)          }
 275 +       [2      4)
 276 +                 [4 5)
 277 = {[1 2)[2 3)[3 4)[4 5)}``]
 278 ]
 279
 280     [[map]      [[classref boost::icl::interval_map          interval_map] /D/]
 281                 []
 282                 [[classref boost::icl::split_interval_map    split_interval_map] /E/]]
 283
 284 [[]
 285 [``
 286   {[1      3)->1          }
 287 +       [2      4)->1
 288 +                 [4 5)->1
 289 = {[1 2)[2 3)[3      5)   }
 290   | ->1  ->2     ->1      |``]
 291 []
 292 [``
 293   {[1      3)->1          }
 294 +       [2      4)->1
 295 +                 [4 5)->1
 296 = {[1 2)[2 3)[3 4)[4 5)   }
 297   | ->1  ->2  ->1  ->1    |``]
 298 ]
 299 ]
 300
 301 Note that =interval_sets= /A/, /B/ and /C/ represent the same set of elements ={1,2,3,4}=
 302 and =interval_maps= /D/ and /E/ represent the same map of elements [^{1->1, 2->2, 3->1, 4->1}].
 303 See example program [link boost_icl.examples.interval_container Interval container]
 304 for an additional demo.
 305
 306 [h4 Joining interval containers]
 307
 308 __Itv_set__ and __itv_map__ are always
 309 in a ['*minimal representation*]. This is useful in many cases, where the
 310 points of insertion or intersection of intervals are not relevant. So in most
 311 instances __itv_set__ and
 312 __itv_map__ will be the first choice
 313 for an interval container.
 314
 315 [h4 Splitting interval containers]
 316
 317 __Spl_itv_set__ and __spl_itv_map__ on the contrary
 318 have an ['*insertion memory*]. They do accumulate interval borders both
 319 from additions and intersections. This is specifically useful, if we want
 320 to enrich an interval container with certain time grids, like e.g. months
 321 or calendar weeks or both. See example [link boost_icl.examples.time_grids time grids for months and weeks].
 322
 323 [h4 Separating interval containers]
 324
 325 __Sep_itv_set__ implements the separating style.
 326 This style preserves borders, that are never passed by an overlapping
 327 interval. So if all intervals that are inserted into a __sep_itv_set__
 328 are generated form a certain grid that never pass say month borders, then
 329 these borders are preserved in the __sep_itv_set__.
 330
 331 [endsect]
 332
 333 [endsect][/ Introduction]
 334
 335