]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |