]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <html> |
2 | <head> | |
3 | <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> | |
4 | <title>Chapter 1. Boost.Icl</title> | |
5 | <link rel="stylesheet" href="../../../../doc/src/boostbook.css" type="text/css"> | |
6 | <meta name="generator" content="DocBook XSL Stylesheets V1.74.0"> | |
7 | <link rel="home" href="index.html" title="Chapter 1. Boost.Icl"> | |
8 | <link rel="next" href="boost_icl/examples.html" title="Examples"> | |
9 | </head> | |
10 | <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> | |
11 | <table cellpadding="2" width="100%"><tr> | |
12 | <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../boost.png"></td> | |
13 | <td align="center"><a href="../../../../index.html">Home</a></td> | |
14 | <td align="center"><a href="../../../libraries.htm">Libraries</a></td> | |
15 | <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> | |
16 | <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> | |
17 | <td align="center"><a href="../../../../more/index.htm">More</a></td> | |
18 | </tr></table> | |
19 | <hr> | |
20 | <div class="spirit-nav"><a accesskey="n" href="boost_icl/examples.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div> | |
21 | <div class="chapter" lang="en"> | |
22 | <div class="titlepage"><div> | |
23 | <div><h2 class="title"> | |
24 | <a name="optional"></a>Chapter 1. Boost.Icl</h2></div> | |
25 | <div><div class="author"><h3 class="author"> | |
26 | <span class="firstname">Joachim</span> <span class="surname">Faulhaber</span> | |
27 | </h3></div></div> | |
28 | <div><p class="copyright">Copyright © 2007 -2010 Joachim Faulhaber</p></div> | |
29 | <div><p class="copyright">Copyright © 1999 -2006 Cortex Software GmbH</p></div> | |
30 | <div><div class="legalnotice"> | |
31 | <a name="id1009066"></a><p> | |
32 | Distributed under the Boost Software License, Version 1.0. (See accompanying | |
33 | file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) | |
34 | </p> | |
35 | </div></div> | |
36 | </div></div> | |
37 | <div class="toc"> | |
38 | <p><b>Table of Contents</b></p> | |
39 | <dl> | |
40 | <dt><span class="section"><a href="index.html#boost_icl.introduction">Introduction</a></span></dt> | |
41 | <dd><dl> | |
42 | <dt><span class="section"><a href="index.html#boost_icl.introduction.definition_and_basic_example">Definition | |
43 | and Basic Example</a></span></dt> | |
44 | <dt><span class="section"><a href="index.html#boost_icl.introduction.icl_s_class_templates">Icl's class | |
45 | templates</a></span></dt> | |
46 | <dt><span class="section"><a href="index.html#boost_icl.introduction.interval_combining_styles">Interval | |
47 | Combining Styles</a></span></dt> | |
48 | </dl></dd> | |
49 | <dt><span class="section"><a href="boost_icl/examples.html">Examples</a></span></dt> | |
50 | <dd><dl> | |
51 | <dt><span class="section"><a href="boost_icl/examples.html#boost_icl.examples.overview">Overview</a></span></dt> | |
52 | <dt><span class="section"><a href="boost_icl/examples/party.html">Party</a></span></dt> | |
53 | <dt><span class="section"><a href="boost_icl/examples/interval.html">Interval</a></span></dt> | |
54 | <dt><span class="section"><a href="boost_icl/examples/dynamic_interval.html">Dynamic interval</a></span></dt> | |
55 | <dt><span class="section"><a href="boost_icl/examples/static_interval.html">Static interval</a></span></dt> | |
56 | <dt><span class="section"><a href="boost_icl/examples/interval_container.html">Interval container</a></span></dt> | |
57 | <dt><span class="section"><a href="boost_icl/examples/overlap_counter.html">Overlap counter</a></span></dt> | |
58 | <dt><span class="section"><a href="boost_icl/examples/partys_height_average.html"> Party's height | |
59 | average</a></span></dt> | |
60 | <dt><span class="section"><a href="boost_icl/examples/partys_tallest_guests.html"> Party's tallest | |
61 | guests</a></span></dt> | |
62 | <dt><span class="section"><a href="boost_icl/examples/time_grids.html"> Time grids for months | |
63 | and weeks</a></span></dt> | |
64 | <dt><span class="section"><a href="boost_icl/examples/man_power.html">Man power</a></span></dt> | |
65 | <dt><span class="section"><a href="boost_icl/examples/user_groups.html">User groups</a></span></dt> | |
66 | <dt><span class="section"><a href="boost_icl/examples/std_copy.html">Std copy</a></span></dt> | |
67 | <dt><span class="section"><a href="boost_icl/examples/std_transform.html">Std transform</a></span></dt> | |
68 | <dt><span class="section"><a href="boost_icl/examples/custom_interval.html">Custom interval</a></span></dt> | |
69 | </dl></dd> | |
70 | <dt><span class="section"><a href="boost_icl/projects.html">Projects</a></span></dt> | |
71 | <dd><dl><dt><span class="section"><a href="boost_icl/projects.html#boost_icl.projects.large_bitset">Large Bitset</a></span></dt></dl></dd> | |
72 | <dt><span class="section"><a href="boost_icl/concepts.html">Concepts</a></span></dt> | |
73 | <dd><dl> | |
74 | <dt><span class="section"><a href="boost_icl/concepts.html#boost_icl.concepts.naming">Naming</a></span></dt> | |
75 | <dt><span class="section"><a href="boost_icl/concepts/aspects.html">Aspects</a></span></dt> | |
76 | <dt><span class="section"><a href="boost_icl/concepts/sets_and_maps.html">Sets and Maps</a></span></dt> | |
77 | <dt><span class="section"><a href="boost_icl/concepts/aggrovering.html"> Addability, Subtractability | |
78 | and Aggregate on Overlap</a></span></dt> | |
79 | <dt><span class="section"><a href="boost_icl/concepts/map_traits.html">Map Traits</a></span></dt> | |
80 | </dl></dd> | |
81 | <dt><span class="section"><a href="boost_icl/semantics.html">Semantics</a></span></dt> | |
82 | <dd><dl> | |
83 | <dt><span class="section"><a href="boost_icl/semantics.html#boost_icl.semantics.orderings_and_equivalences">Orderings | |
84 | and Equivalences</a></span></dt> | |
85 | <dt><span class="section"><a href="boost_icl/semantics/sets.html">Sets</a></span></dt> | |
86 | <dt><span class="section"><a href="boost_icl/semantics/maps.html">Maps</a></span></dt> | |
87 | <dt><span class="section"><a href="boost_icl/semantics/collectors__maps_of_sets.html">Collectors: | |
88 | Maps of Sets</a></span></dt> | |
89 | <dt><span class="section"><a href="boost_icl/semantics/quantifiers__maps_of_numbers.html">Quantifiers: | |
90 | Maps of Numbers</a></span></dt> | |
91 | <dt><span class="section"><a href="boost_icl/semantics/concept_induction.html">Concept Induction</a></span></dt> | |
92 | </dl></dd> | |
93 | <dt><span class="section"><a href="boost_icl/interface.html">Interface</a></span></dt> | |
94 | <dd><dl> | |
95 | <dt><span class="section"><a href="boost_icl/interface.html#boost_icl.interface.class_templates">Class templates</a></span></dt> | |
96 | <dt><span class="section"><a href="boost_icl/interface/required_concepts.html">Required Concepts</a></span></dt> | |
97 | <dt><span class="section"><a href="boost_icl/interface/associated_types.html">Associated Types</a></span></dt> | |
98 | <dt><span class="section"><a href="boost_icl/interface/function_synopsis.html">Function Synopsis</a></span></dt> | |
99 | </dl></dd> | |
100 | <dt><span class="section"><a href="boost_icl/customization.html">Customization</a></span></dt> | |
101 | <dd><dl><dt><span class="section"><a href="boost_icl/customization.html#boost_icl.customization.intervals">Intervals</a></span></dt></dl></dd> | |
102 | <dt><span class="section"><a href="boost_icl/implementation.html">Implementation</a></span></dt> | |
103 | <dd><dl> | |
104 | <dt><span class="section"><a href="boost_icl/implementation.html#boost_icl.implementation.iterative_size">Iterative size</a></span></dt> | |
105 | <dt><span class="section"><a href="boost_icl/implementation/complexity.html">Complexity</a></span></dt> | |
106 | <dt><span class="section"><a href="boost_icl/implementation/inplace_and_infix_operators.html">Inplace | |
107 | and infix operators</a></span></dt> | |
108 | </dl></dd> | |
109 | <dt><span class="section"><a href="boost_icl/function_reference.html">Function Reference</a></span></dt> | |
110 | <dd><dl> | |
111 | <dt><span class="section"><a href="boost_icl/function_reference.html#boost_icl.function_reference.overload_tables">Overload | |
112 | tables</a></span></dt> | |
113 | <dt><span class="section"><a href="boost_icl/function_reference/segmentational_fineness.html">Segmentational | |
114 | Fineness</a></span></dt> | |
115 | <dt><span class="section"><a href="boost_icl/function_reference/key_types.html">Key Types</a></span></dt> | |
116 | <dt><span class="section"><a href="boost_icl/function_reference/construct__copy__destruct.html">Construct, | |
117 | copy, destruct</a></span></dt> | |
118 | <dt><span class="section"><a href="boost_icl/function_reference/containedness.html">Containedness</a></span></dt> | |
119 | <dt><span class="section"><a href="boost_icl/function_reference/equivalences_and_orderings.html">Equivalences | |
120 | and Orderings</a></span></dt> | |
121 | <dt><span class="section"><a href="boost_icl/function_reference/size.html">Size</a></span></dt> | |
122 | <dt><span class="section"><a href="boost_icl/function_reference/range.html">Range</a></span></dt> | |
123 | <dt><span class="section"><a href="boost_icl/function_reference/selection.html">Selection</a></span></dt> | |
124 | <dt><span class="section"><a href="boost_icl/function_reference/addition.html">Addition</a></span></dt> | |
125 | <dt><span class="section"><a href="boost_icl/function_reference/subtraction.html">Subtraction</a></span></dt> | |
126 | <dt><span class="section"><a href="boost_icl/function_reference/insertion.html">Insertion</a></span></dt> | |
127 | <dt><span class="section"><a href="boost_icl/function_reference/erasure.html">Erasure</a></span></dt> | |
128 | <dt><span class="section"><a href="boost_icl/function_reference/intersection.html">Intersection</a></span></dt> | |
129 | <dt><span class="section"><a href="boost_icl/function_reference/symmetric_difference.html">Symmetric | |
130 | Difference</a></span></dt> | |
131 | <dt><span class="section"><a href="boost_icl/function_reference/iterator_related.html">Iterator | |
132 | related</a></span></dt> | |
133 | <dt><span class="section"><a href="boost_icl/function_reference/element_iteration.html">Element | |
134 | iteration</a></span></dt> | |
135 | <dt><span class="section"><a href="boost_icl/function_reference/streaming__conversion.html">Streaming, | |
136 | conversion</a></span></dt> | |
137 | <dt><span class="section"><a href="boost_icl/function_reference/interval_construction.html">Interval | |
138 | Construction</a></span></dt> | |
139 | <dt><span class="section"><a href="boost_icl/function_reference/additional_interval_orderings.html">Additional | |
140 | Interval Orderings</a></span></dt> | |
141 | <dt><span class="section"><a href="boost_icl/function_reference/miscellaneous_interval_functions.html">Miscellaneous | |
142 | Interval Functions</a></span></dt> | |
143 | </dl></dd> | |
144 | <dt><span class="section"><a href="boost_icl/acknowledgments.html">Acknowledgments</a></span></dt> | |
145 | <dt><span class="section"><a href="interval_container_library_reference.html">Interval Container Library Reference</a></span></dt> | |
146 | <dd><dl> | |
147 | <dt><span class="section"><a href="interval_container_library_reference.html#header.boost.icl.closed_interval_hpp">Header <boost/icl/closed_interval.hpp></a></span></dt> | |
148 | <dt><span class="section"><a href="header/boost/icl/continuous_interval_hpp.html">Header <boost/icl/continuous_interval.hpp></a></span></dt> | |
149 | <dt><span class="section"><a href="header/boost/icl/discrete_interval_hpp.html">Header <boost/icl/discrete_interval.hpp></a></span></dt> | |
150 | <dt><span class="section"><a href="header/boost/icl/dynamic_interval_traits_hpp.html">Header <boost/icl/dynamic_interval_traits.hpp></a></span></dt> | |
151 | <dt><span class="section"><a href="header/boost/icl/functors_hpp.html">Header <boost/icl/functors.hpp></a></span></dt> | |
152 | <dt><span class="section"><a href="header/boost/icl/gregorian_hpp.html">Header <boost/icl/gregorian.hpp></a></span></dt> | |
153 | <dt><span class="section"><a href="header/boost/icl/impl_config_hpp.html">Header <boost/icl/impl_config.hpp></a></span></dt> | |
154 | <dt><span class="section"><a href="header/boost/icl/interval_hpp.html">Header <boost/icl/interval.hpp></a></span></dt> | |
155 | <dt><span class="section"><a href="header/boost/icl/interval_base_map_hpp.html">Header <boost/icl/interval_base_map.hpp></a></span></dt> | |
156 | <dt><span class="section"><a href="header/boost/icl/interval_base_set_hpp.html">Header <boost/icl/interval_base_set.hpp></a></span></dt> | |
157 | <dt><span class="section"><a href="header/boost/icl/interval_bounds_hpp.html">Header <boost/icl/interval_bounds.hpp></a></span></dt> | |
158 | <dt><span class="section"><a href="header/boost/icl/interval_combining_style_hpp.html">Header <boost/icl/interval_combining_style.hpp></a></span></dt> | |
159 | <dt><span class="section"><a href="header/boost/icl/interval_map_hpp.html">Header <boost/icl/interval_map.hpp></a></span></dt> | |
160 | <dt><span class="section"><a href="header/boost/icl/interval_set_hpp.html">Header <boost/icl/interval_set.hpp></a></span></dt> | |
161 | <dt><span class="section"><a href="header/boost/icl/interval_traits_hpp.html">Header <boost/icl/interval_traits.hpp></a></span></dt> | |
162 | <dt><span class="section"><a href="header/boost/icl/iterator_hpp.html">Header <boost/icl/iterator.hpp></a></span></dt> | |
163 | <dt><span class="section"><a href="header/boost/icl/left_open_interval_hpp.html">Header <boost/icl/left_open_interval.hpp></a></span></dt> | |
164 | <dt><span class="section"><a href="header/boost/icl/map_hpp.html">Header <boost/icl/map.hpp></a></span></dt> | |
165 | <dt><span class="section"><a href="header/boost/icl/open_interval_hpp.html">Header <boost/icl/open_interval.hpp></a></span></dt> | |
166 | <dt><span class="section"><a href="header/boost/icl/ptime_hpp.html">Header <boost/icl/ptime.hpp></a></span></dt> | |
167 | <dt><span class="section"><a href="header/boost/icl/rational_hpp.html">Header <boost/icl/rational.hpp></a></span></dt> | |
168 | <dt><span class="section"><a href="header/boost/icl/right_open_interval_hpp.html">Header <boost/icl/right_open_interval.hpp></a></span></dt> | |
169 | <dt><span class="section"><a href="header/boost/icl/separate_interval_set_hpp.html">Header <boost/icl/separate_interval_set.hpp></a></span></dt> | |
170 | <dt><span class="section"><a href="header/boost/icl/split_interval_map_hpp.html">Header <boost/icl/split_interval_map.hpp></a></span></dt> | |
171 | <dt><span class="section"><a href="header/boost/icl/split_interval_set_hpp.html">Header <boost/icl/split_interval_set.hpp></a></span></dt> | |
172 | </dl></dd> | |
173 | </dl> | |
174 | </div> | |
175 | <div class="section boost_icl_introduction" lang="en"> | |
176 | <div class="titlepage"><div><div><h2 class="title" style="clear: both"> | |
177 | <a name="boost_icl.introduction"></a><a class="link" href="index.html#boost_icl.introduction" title="Introduction">Introduction</a> | |
178 | </h2></div></div></div> | |
179 | <div class="toc"><dl> | |
180 | <dt><span class="section"><a href="index.html#boost_icl.introduction.definition_and_basic_example">Definition | |
181 | and Basic Example</a></span></dt> | |
182 | <dt><span class="section"><a href="index.html#boost_icl.introduction.icl_s_class_templates">Icl's class | |
183 | templates</a></span></dt> | |
184 | <dt><span class="section"><a href="index.html#boost_icl.introduction.interval_combining_styles">Interval | |
185 | Combining Styles</a></span></dt> | |
186 | </dl></div> | |
187 | <p> | |
188 | “<span class="quote">A bug crawls across the boost docs on my laptop screen. Let him be! | |
189 | We need all the readers we can get.</span>” -- Freely adapted from <a href="http://en.wikipedia.org/wiki/Jack_Kornfield" target="_top">Jack | |
190 | Kornfield</a> | |
191 | </p> | |
192 | <p> | |
193 | Intervals are almost ubiquitous in software development. Yet they are very | |
194 | easily coded into user defined classes by a pair of numbers so they are only | |
195 | <span class="emphasis"><em>implicitly</em></span> used most of the time. The meaning of an interval | |
196 | is simple. They represent all the elements between their lower and upper bound | |
197 | and thus a set. But unlike sets, intervals usually can not be added to a single | |
198 | new interval. If you want to add intervals to a collection of intervals that | |
199 | does still represent a <span class="emphasis"><em>set</em></span>, you arrive at the idea of | |
200 | <span class="emphasis"><em>interval_sets</em></span> provided by this library. | |
201 | </p> | |
202 | <p> | |
203 | Interval containers of the <span class="bold"><strong>ICL</strong></span> have been developed | |
204 | initially at <a href="http://www.cortex-software.de/desktopdefault.aspx" target="_top">Cortex | |
205 | Software GmbH</a> to solve problems related to date and time interval computations | |
206 | in the context of a Hospital Information System. Time intervals with associated | |
207 | values like <span class="emphasis"><em>amount of invoice</em></span> or <span class="emphasis"><em>set of therapies</em></span> | |
208 | had to be manipulated in statistics, billing programs and therapy scheduling | |
209 | programs. So the <span class="bold"><strong>ICL</strong></span> emerged out of those | |
210 | industrial use cases. It extracts generic code that helps to solve common problems | |
211 | from the date and time problem domain and can be beneficial in other fields | |
212 | as well. | |
213 | </p> | |
214 | <p> | |
215 | One of the most advantageous aspects of interval containers is their very compact | |
216 | representation of sets and maps. Working with sets and maps <span class="emphasis"><em>of elements</em></span> | |
217 | can be very inefficient, if in a given problem domain, elements are typically | |
218 | occurring in contiguous chunks. Besides a compact representation of associative | |
219 | containers, that can reduce the cost of space and time drastically, the ICL | |
220 | comes with a universal mechanism of aggregation, that allows to combine associated | |
221 | values in meaningful ways when intervals overlap on insertion. | |
222 | </p> | |
223 | <p> | |
224 | For a condensed introduction and overview you may want to look at the <a href="http://www.herold-faulhaber.de/boost_icl/doc/libs/icl/doc/boostcon09/intro_to_itl.pdf" target="_top">presentation | |
225 | material on the <span class="bold"><strong>ICL</strong></span> from <span class="emphasis"><em><span class="bold"><strong>BoostCon2009</strong></span></em></span></a>. | |
226 | </p> | |
227 | <div class="section boost_icl_introduction_definition_and_basic_example" lang="en"> | |
228 | <div class="titlepage"><div><div><h3 class="title"> | |
229 | <a name="boost_icl.introduction.definition_and_basic_example"></a><a class="link" href="index.html#boost_icl.introduction.definition_and_basic_example" title="Definition and Basic Example">Definition | |
230 | and Basic Example</a> | |
231 | </h3></div></div></div> | |
232 | <p> | |
233 | The <span class="bold"><strong>Interval Container Library (ICL)</strong></span> provides | |
234 | <code class="computeroutput"><a class="link" href="boost/icl/interval.html" title="Struct template interval">intervals</a></code> and two kinds | |
235 | of interval containers: <code class="computeroutput"><a class="link" href="boost/icl/interval_set.html" title="Class template interval_set">interval_sets</a></code> | |
236 | and <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_maps</a></code>. | |
237 | </p> | |
238 | <div class="itemizedlist"><ul type="disc"> | |
239 | <li> | |
240 | An <code class="computeroutput"><a class="link" href="boost/icl/interval_base_set.html" title="Class template interval_base_set">interval_set</a></code> | |
241 | is a <span class="bold"><strong>set</strong></span> that is implemented as a set | |
242 | of intervals. | |
243 | </li> | |
244 | <li> | |
245 | An <code class="computeroutput"><a class="link" href="boost/icl/interval_base_map.html" title="Class template interval_base_map">interval_map</a></code> | |
246 | is a <span class="bold"><strong>map</strong></span> that is implemented as a map | |
247 | of interval value pairs. | |
248 | </li> | |
249 | </ul></div> | |
250 | <a name="boost_icl.introduction.definition_and_basic_example.two_aspects"></a><h5> | |
251 | <a name="id1009249"></a> | |
252 | <a class="link" href="index.html#boost_icl.introduction.definition_and_basic_example.two_aspects">Two | |
253 | Aspects</a> | |
254 | </h5> | |
255 | <p> | |
256 | <code class="computeroutput"><a class="link" href="boost/icl/interval_base_set.html" title="Class template interval_base_set">Interval_sets</a></code> | |
257 | and <code class="computeroutput"><a class="link" href="boost/icl/interval_base_map.html" title="Class template interval_base_map">interval_maps</a></code> | |
258 | expose two different aspects in their interfaces: (1) The functionality of | |
259 | a set or a map, which is the more <span class="emphasis"><em><span class="bold"><strong>abstract | |
260 | aspect</strong></span></em></span>. And (2) the functionality of a container of | |
261 | intervals which is the more specific and <span class="emphasis"><em><span class="bold"><strong>implementation | |
262 | related aspect</strong></span></em></span>. In practice both aspects are useful | |
263 | and are therefore supported. | |
264 | </p> | |
265 | <p> | |
266 | The first aspect, that will be called <span class="emphasis"><em><span class="bold"><strong>fundamental</strong></span></em></span> | |
267 | <span class="emphasis"><em><span class="bold"><strong>aspect</strong></span></em></span>, is the more | |
268 | important one. It means that we can use an <code class="computeroutput"><a class="link" href="boost/icl/interval_set.html" title="Class template interval_set">interval_set</a></code> | |
269 | or <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code> like | |
270 | a set or map <span class="emphasis"><em><span class="bold"><strong>of elements</strong></span></em></span>. | |
271 | It exposes the same functions. | |
272 | </p> | |
273 | <pre class="programlisting"><span class="identifier">interval_set</span><span class="special"><</span><span class="keyword">int</span><span class="special">></span> <span class="identifier">mySet</span><span class="special">;</span> | |
274 | <span class="identifier">mySet</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="number">42</span><span class="special">);</span> | |
275 | <span class="keyword">bool</span> <span class="identifier">has_answer</span> <span class="special">=</span> <span class="identifier">contains</span><span class="special">(</span><span class="identifier">mySet</span><span class="special">,</span> <span class="number">42</span><span class="special">);</span> | |
276 | </pre> | |
277 | <p> | |
278 | </p> | |
279 | <p> | |
280 | The second aspect, that will be called <span class="emphasis"><em><span class="bold"><strong>segmental</strong></span></em></span> | |
281 | <span class="emphasis"><em><span class="bold"><strong>aspect</strong></span></em></span>, allows to exploit | |
282 | the fact, that the elements of <code class="computeroutput"><a class="link" href="boost/icl/interval_set.html" title="Class template interval_set">interval_sets</a></code> | |
283 | and <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_maps</a></code> are | |
284 | clustered in <span class="emphasis"><em><span class="bold"><strong>intervals</strong></span></em></span> | |
285 | or <span class="emphasis"><em><span class="bold"><strong>segments</strong></span></em></span> that we | |
286 | can iterate over. | |
287 | </p> | |
288 | <p> | |
289 | ||
290 | </p> | |
291 | <pre class="programlisting"><span class="comment">// Switch on my favorite telecasts using an interval_set | |
292 | </span><span class="identifier">interval</span><span class="special"><</span><span class="identifier">seconds</span><span class="special">>::</span><span class="identifier">type</span> <span class="identifier">news</span><span class="special">(</span><span class="identifier">make_seconds</span><span class="special">(</span><span class="string">"20:00:00"</span><span class="special">),</span> <span class="identifier">make_seconds</span><span class="special">(</span><span class="string">"20:15:00"</span><span class="special">));</span> | |
293 | <span class="identifier">interval</span><span class="special"><</span><span class="identifier">seconds</span><span class="special">>::</span><span class="identifier">type</span> <span class="identifier">talk_show</span><span class="special">(</span><span class="identifier">make_seconds</span><span class="special">(</span><span class="string">"22:45:30"</span><span class="special">),</span> <span class="identifier">make_seconds</span><span class="special">(</span><span class="string">"23:30:50"</span><span class="special">));</span> | |
294 | <span class="identifier">interval_set</span><span class="special"><</span><span class="identifier">seconds</span><span class="special">></span> <span class="identifier">myTvProgram</span><span class="special">;</span> | |
295 | <span class="identifier">myTvProgram</span><span class="special">.</span><span class="identifier">add</span><span class="special">(</span><span class="identifier">news</span><span class="special">).</span><span class="identifier">add</span><span class="special">(</span><span class="identifier">talk_show</span><span class="special">);</span> | |
296 | ||
297 | <span class="comment">// Iterating over elements (seconds) would be silly ... | |
298 | </span><span class="keyword">for</span><span class="special">(</span><span class="identifier">interval_set</span><span class="special"><</span><span class="identifier">seconds</span><span class="special">>::</span><span class="identifier">iterator</span> <span class="identifier">telecast</span> <span class="special">=</span> <span class="identifier">myTvProgram</span><span class="special">.</span><span class="identifier">begin</span><span class="special">();</span> | |
299 | <span class="identifier">telecast</span> <span class="special">!=</span> <span class="identifier">myTvProgram</span><span class="special">.</span><span class="identifier">end</span><span class="special">();</span> <span class="special">++</span><span class="identifier">telecast</span><span class="special">)</span> | |
300 | <span class="comment">//...so this iterates over intervals | |
301 | </span> <span class="identifier">TV</span><span class="special">.</span><span class="identifier">switch_on</span><span class="special">(*</span><span class="identifier">telecast</span><span class="special">);</span> | |
302 | </pre> | |
303 | <p> | |
304 | </p> | |
305 | <p> | |
306 | Working with <code class="computeroutput"><a class="link" href="boost/icl/interval_base_set.html" title="Class template interval_base_set">interval_sets</a></code> | |
307 | and <code class="computeroutput"><a class="link" href="boost/icl/interval_base_map.html" title="Class template interval_base_map">interval_maps</a></code> | |
308 | can be beneficial whenever the elements of sets appear in contiguous chunks: | |
309 | <code class="computeroutput"><a class="link" href="boost/icl/interval.html" title="Struct template interval">intervals</a></code>. This is obviously | |
310 | the case in many problem domains, particularly in fields that deal with computations | |
311 | related to date and time. | |
312 | </p> | |
313 | <a name="boost_icl.introduction.definition_and_basic_example.addabitlity_and_subtractability"></a><h5> | |
314 | <a name="id1017462"></a> | |
315 | <a class="link" href="index.html#boost_icl.introduction.definition_and_basic_example.addabitlity_and_subtractability">Addabitlity | |
316 | and Subtractability</a> | |
317 | </h5> | |
318 | <p> | |
319 | Unlike <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">sets</span></code> and <code class="computeroutput"><span class="identifier">maps</span></code>, | |
320 | <code class="computeroutput"><a class="link" href="boost/icl/interval_base_set.html" title="Class template interval_base_set">interval_sets</a></code> | |
321 | and <code class="computeroutput"><a class="link" href="boost/icl/interval_base_map.html" title="Class template interval_base_map">interval_maps</a></code> | |
322 | implement concept <code class="computeroutput"><span class="identifier">Addable</span></code> | |
323 | and <code class="computeroutput"><span class="identifier">Subtractable</span></code>. So <code class="computeroutput"><a class="link" href="boost/icl/interval_base_set.html" title="Class template interval_base_set">interval_sets</a></code> define an | |
324 | <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+=</span></code> | |
325 | that is naturally implemented as <span class="emphasis"><em><span class="bold"><strong>set union</strong></span></em></span> | |
326 | and an <code class="computeroutput"><span class="keyword">operator</span> <span class="special">-=</span></code> | |
327 | that is consequently implemented as <span class="emphasis"><em><span class="bold"><strong>set difference</strong></span></em></span>. | |
328 | In the <span class="bold"><strong>Icl</strong></span> <code class="computeroutput"><a class="link" href="boost/icl/interval_base_map.html" title="Class template interval_base_map">interval_maps</a></code> | |
329 | are addable and subtractable as well. It turned out to be a very fruitful | |
330 | concept to propagate the addition or subtraction to the <code class="computeroutput"><a class="link" href="boost/icl/interval_base_map.html" title="Class template interval_base_map">interval_map's</a></code> | |
331 | associated values in cases where the insertion of an interval value pair | |
332 | into an <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code> | |
333 | resulted in a collision of the inserted interval value pair with interval | |
334 | value pairs, that are already in the <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code>. | |
335 | This operation propagation is called <span class="emphasis"><em><span class="bold"><strong>aggregate | |
336 | on overlap</strong></span></em></span>. | |
337 | </p> | |
338 | <a name="boost_icl.introduction.definition_and_basic_example.aggregate_on_overlap"></a><h5> | |
339 | <a name="id1017612"></a> | |
340 | <a class="link" href="index.html#boost_icl.introduction.definition_and_basic_example.aggregate_on_overlap">Aggregate | |
341 | on Overlap</a> | |
342 | </h5> | |
343 | <p> | |
344 | This is a first motivating example of a very small party, demonstrating the | |
345 | <span class="emphasis"><em><span class="bold"><strong>aggregate on overlap</strong></span></em></span> | |
346 | principle on <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_maps</a></code>: | |
347 | </p> | |
348 | <p> | |
349 | In the example Mary enters the party first. She attends during the time interval | |
350 | <code class="computeroutput"><span class="special">[</span><span class="number">20</span><span class="special">:</span><span class="number">00</span><span class="special">,</span><span class="number">22</span><span class="special">:</span><span class="number">00</span><span class="special">)</span></code>. Harry enters later. He stays within <code class="computeroutput"><span class="special">[</span><span class="number">21</span><span class="special">:</span><span class="number">00</span><span class="special">,</span><span class="number">23</span><span class="special">:</span><span class="number">00</span><span class="special">)</span></code>. | |
351 | ||
352 | </p> | |
353 | <pre class="programlisting"><span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special"><</span><span class="identifier">string</span><span class="special">></span> <span class="identifier">guests</span><span class="special">;</span> | |
354 | <span class="identifier">interval_map</span><span class="special"><</span><span class="identifier">time</span><span class="special">,</span> <span class="identifier">guests</span><span class="special">></span> <span class="identifier">party</span><span class="special">;</span> | |
355 | <span class="identifier">party</span> <span class="special">+=</span> <span class="identifier">make_pair</span><span class="special">(</span><span class="identifier">interval</span><span class="special"><</span><span class="identifier">time</span><span class="special">>::</span><span class="identifier">right_open</span><span class="special">(</span><span class="identifier">time</span><span class="special">(</span><span class="string">"20:00"</span><span class="special">),</span> <span class="identifier">time</span><span class="special">(</span><span class="string">"22:00"</span><span class="special">)),</span> <span class="identifier">guests</span><span class="special">(</span><span class="string">"Mary"</span><span class="special">));</span> | |
356 | <span class="identifier">party</span> <span class="special">+=</span> <span class="identifier">make_pair</span><span class="special">(</span><span class="identifier">interval</span><span class="special"><</span><span class="identifier">time</span><span class="special">>::</span><span class="identifier">right_open</span><span class="special">(</span><span class="identifier">time</span><span class="special">(</span><span class="string">"21:00"</span><span class="special">),</span> <span class="identifier">time</span><span class="special">(</span><span class="string">"23:00"</span><span class="special">)),</span> <span class="identifier">guests</span><span class="special">(</span><span class="string">"Harry"</span><span class="special">));</span> | |
357 | <span class="comment">// party now contains | |
358 | </span><span class="special">[</span><span class="number">20</span><span class="special">:</span><span class="number">00</span><span class="special">,</span> <span class="number">21</span><span class="special">:</span><span class="number">00</span><span class="special">)->{</span><span class="string">"Mary"</span><span class="special">}</span> | |
359 | <span class="special">[</span><span class="number">21</span><span class="special">:</span><span class="number">00</span><span class="special">,</span> <span class="number">22</span><span class="special">:</span><span class="number">00</span><span class="special">)->{</span><span class="string">"Harry"</span><span class="special">,</span><span class="string">"Mary"</span><span class="special">}</span> <span class="comment">//guest sets aggregated on overlap | |
360 | </span><span class="special">[</span><span class="number">22</span><span class="special">:</span><span class="number">00</span><span class="special">,</span> <span class="number">23</span><span class="special">:</span><span class="number">00</span><span class="special">)->{</span><span class="string">"Harry"</span><span class="special">}</span> | |
361 | </pre> | |
362 | <p> | |
363 | <span class="emphasis"><em><span class="bold"><strong>On overlap of intervals</strong></span></em></span>, | |
364 | the corresponding name sets are <span class="emphasis"><em><span class="bold"><strong>accumulated</strong></span></em></span>. | |
365 | At the <span class="emphasis"><em><span class="bold"><strong>points of overlap</strong></span></em></span> | |
366 | the intervals are <span class="emphasis"><em><span class="bold"><strong>split</strong></span></em></span>. | |
367 | The accumulation of content on overlap of intervals is done via an <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+=</span></code> | |
368 | that has to be implemented for the associated values of the <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code>. | |
369 | In the example the associated values are <code class="computeroutput"><span class="identifier">guest</span> | |
370 | <span class="identifier">sets</span></code>. Thus a <code class="computeroutput"><span class="identifier">guest</span> | |
371 | <span class="identifier">set</span></code> has to implement <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+=</span></code> | |
372 | as set union. | |
373 | </p> | |
374 | <p> | |
375 | As can be seen from the example an <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code> | |
376 | has both a <span class="emphasis"><em><span class="bold"><strong>decompositional behavior</strong></span></em></span> | |
377 | (on the time dimension) as well as an <span class="emphasis"><em><span class="bold"><strong>accumulative | |
378 | one</strong></span></em></span> (on the associated values). | |
379 | </p> | |
380 | <p> | |
381 | Addability and aggregate on overlap are useful features on <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_maps</a></code> | |
382 | implemented via function <code class="computeroutput"><span class="identifier">add</span></code> | |
383 | and <code class="computeroutput"><span class="keyword">operator</span> <span class="special">+=</span></code>. | |
384 | But you can also use them with the <span class="emphasis"><em>traditional</em></span> <a class="link" href="boost_icl/function_reference/insertion.html" title="Insertion">insert semantics</a> | |
385 | that behaves like <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span><span class="special">::</span><span class="identifier">insert</span></code> | |
386 | generalized for interval insertion. | |
387 | </p> | |
388 | </div> | |
389 | <div class="section boost_icl_introduction_icl_s_class_templates" lang="en"> | |
390 | <div class="titlepage"><div><div><h3 class="title"> | |
391 | <a name="boost_icl.introduction.icl_s_class_templates"></a><a class="link" href="index.html#boost_icl.introduction.icl_s_class_templates" title="Icl's class templates">Icl's class | |
392 | templates</a> | |
393 | </h3></div></div></div> | |
394 | <p> | |
395 | In addition to interval containers we can work with containers of elements | |
396 | that are <span class="emphasis"><em><span class="bold"><strong>behavioral equal</strong></span></em></span> | |
397 | to the interval containers: On the fundamental aspect they have exactly the | |
398 | same functionality. An <a href="http://www.cplusplus.com/reference/stl/set/" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span></code> | |
399 | </a> of the STL is such an equivalent set implementation. Due to the | |
400 | aggregation facilities of the icl's interval maps <a href="http://www.cplusplus.com/reference/stl/set/" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span></code> | |
401 | </a> is fundamentally not completely equivalent to an <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code>. | |
402 | Therefore there is an extra <code class="computeroutput"><a class="link" href="boost/icl/map.html" title="Class template map">icl::map</a></code> | |
403 | class template for maps of elements in the icl. | |
404 | </p> | |
405 | <div class="itemizedlist"><ul type="disc"> | |
406 | <li> | |
407 | The <a href="http://www.cplusplus.com/reference/stl/set/" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span></code> </a> is behavioral equal to | |
408 | <code class="computeroutput"><a class="link" href="boost/icl/interval_base_set.html" title="Class template interval_base_set">interval_sets</a></code> | |
409 | on the <span class="emphasis"><em><span class="bold"><strong>fundamental</strong></span></em></span> | |
410 | aspect. | |
411 | </li> | |
412 | <li> | |
413 | An <code class="computeroutput"><a class="link" href="boost/icl/map.html" title="Class template map">icl::map</a></code> is behavioral | |
414 | equal to <code class="computeroutput"><a class="link" href="boost/icl/interval_base_map.html" title="Class template interval_base_map">interval_maps</a></code> | |
415 | on the <span class="emphasis"><em><span class="bold"><strong>fundamental</strong></span></em></span> | |
416 | aspect. Specifically an <code class="computeroutput"><a class="link" href="boost/icl/map.html" title="Class template map">icl::map</a></code> | |
417 | implements <span class="emphasis"><em><span class="bold"><strong>aggregate on overlap</strong></span></em></span>, | |
418 | which is named <span class="emphasis"><em><span class="bold"><strong>aggregate on collision</strong></span></em></span> | |
419 | for an element container. | |
420 | </li> | |
421 | </ul></div> | |
422 | <p> | |
423 | The following tables give an overview over the main class templates provided | |
424 | by the <span class="bold"><strong>icl</strong></span>. | |
425 | </p> | |
426 | <div class="table"> | |
427 | <a name="id1018421"></a><p class="title"><b>Table 1.1. Interval class templates</b></p> | |
428 | <div class="table-contents"><table class="table" summary="Interval class templates"> | |
429 | <colgroup> | |
430 | <col> | |
431 | <col> | |
432 | <col> | |
433 | </colgroup> | |
434 | <thead><tr> | |
435 | <th> | |
436 | <p> | |
437 | group | |
438 | </p> | |
439 | </th> | |
440 | <th> | |
441 | <p> | |
442 | form | |
443 | </p> | |
444 | </th> | |
445 | <th> | |
446 | <p> | |
447 | template | |
448 | </p> | |
449 | </th> | |
450 | </tr></thead> | |
451 | <tbody> | |
452 | <tr> | |
453 | <td> | |
454 | <p> | |
455 | statically bounded | |
456 | </p> | |
457 | </td> | |
458 | <td> | |
459 | <p> | |
460 | asymmetric | |
461 | </p> | |
462 | </td> | |
463 | <td> | |
464 | <p> | |
465 | <code class="computeroutput"><a class="link" href="boost/icl/right_open_interval.html" title="Class template right_open_interval">right_open_interval</a></code> | |
466 | </p> | |
467 | </td> | |
468 | </tr> | |
469 | <tr> | |
470 | <td> | |
471 | <p> | |
472 | </p> | |
473 | </td> | |
474 | <td> | |
475 | <p> | |
476 | </p> | |
477 | </td> | |
478 | <td> | |
479 | <p> | |
480 | <code class="computeroutput"><a class="link" href="boost/icl/left_open_interval.html" title="Class template left_open_interval">left_open_interval</a></code> | |
481 | </p> | |
482 | </td> | |
483 | </tr> | |
484 | <tr> | |
485 | <td> | |
486 | <p> | |
487 | </p> | |
488 | </td> | |
489 | <td> | |
490 | <p> | |
491 | symmetric | |
492 | </p> | |
493 | </td> | |
494 | <td> | |
495 | <p> | |
496 | <code class="computeroutput"><a class="link" href="boost/icl/closed_interval.html" title="Class template closed_interval">closed_interval</a></code> | |
497 | </p> | |
498 | </td> | |
499 | </tr> | |
500 | <tr> | |
501 | <td> | |
502 | <p> | |
503 | </p> | |
504 | </td> | |
505 | <td> | |
506 | <p> | |
507 | </p> | |
508 | </td> | |
509 | <td> | |
510 | <p> | |
511 | <code class="computeroutput"><a class="link" href="boost/icl/open_interval.html" title="Class template open_interval">open_interval</a></code> | |
512 | </p> | |
513 | </td> | |
514 | </tr> | |
515 | <tr> | |
516 | <td> | |
517 | <p> | |
518 | dynamically bounded | |
519 | </p> | |
520 | </td> | |
521 | <td> | |
522 | <p> | |
523 | </p> | |
524 | </td> | |
525 | <td> | |
526 | <p> | |
527 | <code class="computeroutput"><a class="link" href="boost/icl/discrete_interval.html" title="Class template discrete_interval">discrete_interval</a></code> | |
528 | </p> | |
529 | </td> | |
530 | </tr> | |
531 | <tr> | |
532 | <td> | |
533 | <p> | |
534 | </p> | |
535 | </td> | |
536 | <td> | |
537 | <p> | |
538 | </p> | |
539 | </td> | |
540 | <td> | |
541 | <p> | |
542 | <code class="computeroutput"><a class="link" href="boost/icl/continuous_interval.html" title="Class template continuous_interval">continuous_interval</a></code> | |
543 | </p> | |
544 | </td> | |
545 | </tr> | |
546 | </tbody> | |
547 | </table></div> | |
548 | </div> | |
549 | <br class="table-break"><p> | |
550 | Statically bounded intervals always have the same kind of interval borders, | |
551 | e.g. right open borders<code class="computeroutput"><span class="special">[</span><span class="identifier">a</span><span class="special">..</span><span class="identifier">b</span><span class="special">)</span></code> | |
552 | for <code class="computeroutput"><a class="link" href="boost/icl/right_open_interval.html" title="Class template right_open_interval">right_open_interval</a></code>. | |
553 | Dynamically bounded intervals can have different borders. Refer to the chapter | |
554 | about <a class="link" href="boost_icl/interface.html#boost_icl.interface.class_templates.intervals" title="Intervals"><span class="emphasis"><em><span class="bold"><strong>intervals</strong></span></em></span></a> for details. | |
555 | </p> | |
556 | <div class="table"> | |
557 | <a name="id1018685"></a><p class="title"><b>Table 1.2. Container class templates</b></p> | |
558 | <div class="table-contents"><table class="table" summary="Container class templates"> | |
559 | <colgroup> | |
560 | <col> | |
561 | <col> | |
562 | <col> | |
563 | <col> | |
564 | </colgroup> | |
565 | <thead><tr> | |
566 | <th> | |
567 | <p> | |
568 | granularity | |
569 | </p> | |
570 | </th> | |
571 | <th> | |
572 | <p> | |
573 | style | |
574 | </p> | |
575 | </th> | |
576 | <th> | |
577 | <p> | |
578 | sets | |
579 | </p> | |
580 | </th> | |
581 | <th> | |
582 | <p> | |
583 | maps | |
584 | </p> | |
585 | </th> | |
586 | </tr></thead> | |
587 | <tbody> | |
588 | <tr> | |
589 | <td> | |
590 | <p> | |
591 | interval | |
592 | </p> | |
593 | </td> | |
594 | <td> | |
595 | <p> | |
596 | joining | |
597 | </p> | |
598 | </td> | |
599 | <td> | |
600 | <p> | |
601 | <code class="computeroutput"><a class="link" href="boost/icl/interval_set.html" title="Class template interval_set">interval_set</a></code> | |
602 | </p> | |
603 | </td> | |
604 | <td> | |
605 | <p> | |
606 | <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code> | |
607 | </p> | |
608 | </td> | |
609 | </tr> | |
610 | <tr> | |
611 | <td> | |
612 | <p> | |
613 | </p> | |
614 | </td> | |
615 | <td> | |
616 | <p> | |
617 | separating | |
618 | </p> | |
619 | </td> | |
620 | <td> | |
621 | <p> | |
622 | <code class="computeroutput"><a class="link" href="boost/icl/separate_interval_set.html" title="Class template separate_interval_set">separate_interval_set</a></code> | |
623 | </p> | |
624 | </td> | |
625 | <td> | |
626 | <p> | |
627 | </p> | |
628 | </td> | |
629 | </tr> | |
630 | <tr> | |
631 | <td> | |
632 | <p> | |
633 | </p> | |
634 | </td> | |
635 | <td> | |
636 | <p> | |
637 | splitting | |
638 | </p> | |
639 | </td> | |
640 | <td> | |
641 | <p> | |
642 | <code class="computeroutput"><a class="link" href="boost/icl/split_interval_set.html" title="Class template split_interval_set">split_interval_set</a></code> | |
643 | </p> | |
644 | </td> | |
645 | <td> | |
646 | <p> | |
647 | <code class="computeroutput"><a class="link" href="boost/icl/split_interval_map.html" title="Class template split_interval_map">split_interval_map</a></code> | |
648 | </p> | |
649 | </td> | |
650 | </tr> | |
651 | <tr> | |
652 | <td> | |
653 | <p> | |
654 | element | |
655 | </p> | |
656 | </td> | |
657 | <td> | |
658 | <p> | |
659 | </p> | |
660 | </td> | |
661 | <td> | |
662 | <p> | |
663 | (<a href="http://www.cplusplus.com/reference/stl/set/" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span></code> </a>) | |
664 | </p> | |
665 | </td> | |
666 | <td> | |
667 | <p> | |
668 | <code class="computeroutput"><a class="link" href="boost/icl/map.html" title="Class template map">map</a></code> | |
669 | </p> | |
670 | </td> | |
671 | </tr> | |
672 | </tbody> | |
673 | </table></div> | |
674 | </div> | |
675 | <br class="table-break"><p> | |
676 | <a href="http://www.cplusplus.com/reference/stl/set/" target="_top"><code class="computeroutput"><span class="identifier">Std</span><span class="special">::</span><span class="identifier">set</span></code> | |
677 | </a> is placed in paretheses, because it is not a class template of the | |
678 | <span class="bold"><strong>ICL</strong></span>. It can be used as element container | |
679 | though that is behavioral equal to the ICL's interval sets on their fundamental | |
680 | aspect. Column <span class="emphasis"><em><span class="bold"><strong>style</strong></span></em></span> | |
681 | refers to the different ways in which interval containers combine added intervals. | |
682 | These <span class="emphasis"><em><span class="bold"><strong>combining styles</strong></span></em></span> | |
683 | are described in the next section. | |
684 | </p> | |
685 | </div> | |
686 | <div class="section boost_icl_introduction_interval_combining_styles" lang="en"> | |
687 | <div class="titlepage"><div><div><h3 class="title"> | |
688 | <a name="boost_icl.introduction.interval_combining_styles"></a><a class="link" href="index.html#boost_icl.introduction.interval_combining_styles" title="Interval Combining Styles">Interval | |
689 | Combining Styles</a> | |
690 | </h3></div></div></div> | |
691 | <p> | |
692 | When we add intervals or interval value pairs to interval containers, the | |
693 | intervals can be added in different ways: Intervals can be joined or split | |
694 | or kept separate. The different interval combining styles are shown by example | |
695 | in the tables below. | |
696 | </p> | |
697 | <div class="table"> | |
698 | <a name="id1018963"></a><p class="title"><b>Table 1.3. Interval container's ways to combine intervals</b></p> | |
699 | <div class="table-contents"><table class="table" summary="Interval container's ways to combine intervals"> | |
700 | <colgroup> | |
701 | <col> | |
702 | <col> | |
703 | <col> | |
704 | <col> | |
705 | </colgroup> | |
706 | <thead><tr> | |
707 | <th> | |
708 | <p> | |
709 | </p> | |
710 | </th> | |
711 | <th> | |
712 | <p> | |
713 | joining | |
714 | </p> | |
715 | </th> | |
716 | <th> | |
717 | <p> | |
718 | separating | |
719 | </p> | |
720 | </th> | |
721 | <th> | |
722 | <p> | |
723 | splitting | |
724 | </p> | |
725 | </th> | |
726 | </tr></thead> | |
727 | <tbody> | |
728 | <tr> | |
729 | <td> | |
730 | <p> | |
731 | set | |
732 | </p> | |
733 | </td> | |
734 | <td> | |
735 | <p> | |
736 | <code class="computeroutput"><a class="link" href="boost/icl/interval_set.html" title="Class template interval_set">interval_set</a></code> | |
737 | </p> | |
738 | </td> | |
739 | <td> | |
740 | <p> | |
741 | <code class="computeroutput"><a class="link" href="boost/icl/separate_interval_set.html" title="Class template separate_interval_set">separate_interval_set</a></code> | |
742 | </p> | |
743 | </td> | |
744 | <td> | |
745 | <p> | |
746 | <code class="computeroutput"><a class="link" href="boost/icl/split_interval_set.html" title="Class template split_interval_set">split_interval_set</a></code> | |
747 | </p> | |
748 | </td> | |
749 | </tr> | |
750 | <tr> | |
751 | <td> | |
752 | <p> | |
753 | map | |
754 | </p> | |
755 | </td> | |
756 | <td> | |
757 | <p> | |
758 | <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code> | |
759 | </p> | |
760 | </td> | |
761 | <td> | |
762 | <p> | |
763 | </p> | |
764 | </td> | |
765 | <td> | |
766 | <p> | |
767 | <code class="computeroutput"><a class="link" href="boost/icl/split_interval_map.html" title="Class template split_interval_map">split_interval_map</a></code> | |
768 | </p> | |
769 | </td> | |
770 | </tr> | |
771 | <tr> | |
772 | <td> | |
773 | <p> | |
774 | </p> | |
775 | </td> | |
776 | <td> | |
777 | <p> | |
778 | Intervals are joined on overlap or touch<br> (if associated values | |
779 | are equal). | |
780 | </p> | |
781 | </td> | |
782 | <td> | |
783 | <p> | |
784 | Intervals are joined on overlap, not on touch. | |
785 | </p> | |
786 | </td> | |
787 | <td> | |
788 | <p> | |
789 | Intervals are split on overlap.<br> All interval borders are preserved. | |
790 | </p> | |
791 | </td> | |
792 | </tr> | |
793 | </tbody> | |
794 | </table></div> | |
795 | </div> | |
796 | <br class="table-break"><div class="table"> | |
797 | <a name="id1019141"></a><p class="title"><b>Table 1.4. Interval combining styles by example</b></p> | |
798 | <div class="table-contents"><table class="table" summary="Interval combining styles by example"> | |
799 | <colgroup> | |
800 | <col> | |
801 | <col> | |
802 | <col> | |
803 | <col> | |
804 | </colgroup> | |
805 | <thead><tr> | |
806 | <th> | |
807 | <p> | |
808 | </p> | |
809 | </th> | |
810 | <th> | |
811 | <p> | |
812 | joining | |
813 | </p> | |
814 | </th> | |
815 | <th> | |
816 | <p> | |
817 | separating | |
818 | </p> | |
819 | </th> | |
820 | <th> | |
821 | <p> | |
822 | splitting | |
823 | </p> | |
824 | </th> | |
825 | </tr></thead> | |
826 | <tbody> | |
827 | <tr> | |
828 | <td> | |
829 | <p> | |
830 | set | |
831 | </p> | |
832 | </td> | |
833 | <td> | |
834 | <p> | |
835 | <code class="computeroutput"><a class="link" href="boost/icl/interval_set.html" title="Class template interval_set">interval_set</a></code> | |
836 | <span class="emphasis"><em>A</em></span> | |
837 | </p> | |
838 | </td> | |
839 | <td> | |
840 | <p> | |
841 | <code class="computeroutput"><a class="link" href="boost/icl/separate_interval_set.html" title="Class template separate_interval_set">separate_interval_set</a></code> | |
842 | <span class="emphasis"><em>B</em></span> | |
843 | </p> | |
844 | </td> | |
845 | <td> | |
846 | <p> | |
847 | <code class="computeroutput"><a class="link" href="boost/icl/split_interval_set.html" title="Class template split_interval_set">split_interval_set</a></code> | |
848 | <span class="emphasis"><em>C</em></span> | |
849 | </p> | |
850 | </td> | |
851 | </tr> | |
852 | <tr> | |
853 | <td> | |
854 | <p> | |
855 | </p> | |
856 | </td> | |
857 | <td> | |
858 | <p> | |
859 | ||
860 | </p> | |
861 | <pre class="programlisting"> <span class="special">{[</span><span class="number">1</span> <span class="number">3</span><span class="special">)</span> <span class="special">}</span> | |
862 | <span class="special">+</span> <span class="special">[</span><span class="number">2</span> <span class="number">4</span><span class="special">)</span> | |
863 | <span class="special">+</span> <span class="special">[</span><span class="number">4</span> <span class="number">5</span><span class="special">)</span> | |
864 | <span class="special">=</span> <span class="special">{[</span><span class="number">1</span> <span class="number">5</span><span class="special">)}</span></pre> | |
865 | <p> | |
866 | </p> | |
867 | </td> | |
868 | <td> | |
869 | <p> | |
870 | ||
871 | </p> | |
872 | <pre class="programlisting"> <span class="special">{[</span><span class="number">1</span> <span class="number">3</span><span class="special">)}</span> <span class="special">}</span> | |
873 | <span class="special">+</span> <span class="special">[</span><span class="number">2</span> <span class="number">4</span><span class="special">)</span> | |
874 | <span class="special">+</span> <span class="special">[</span><span class="number">4</span> <span class="number">5</span><span class="special">)</span> | |
875 | <span class="special">=</span> <span class="special">{[</span><span class="number">1</span> <span class="number">4</span><span class="special">)[</span><span class="number">4</span> <span class="number">5</span><span class="special">)}</span></pre> | |
876 | <p> | |
877 | </p> | |
878 | </td> | |
879 | <td> | |
880 | <p> | |
881 | ||
882 | </p> | |
883 | <pre class="programlisting"> <span class="special">{[</span><span class="number">1</span> <span class="number">3</span><span class="special">)</span> <span class="special">}</span> | |
884 | <span class="special">+</span> <span class="special">[</span><span class="number">2</span> <span class="number">4</span><span class="special">)</span> | |
885 | <span class="special">+</span> <span class="special">[</span><span class="number">4</span> <span class="number">5</span><span class="special">)</span> | |
886 | <span class="special">=</span> <span class="special">{[</span><span class="number">1</span> <span class="number">2</span><span class="special">)[</span><span class="number">2</span> <span class="number">3</span><span class="special">)[</span><span class="number">3</span> <span class="number">4</span><span class="special">)[</span><span class="number">4</span> <span class="number">5</span><span class="special">)}</span></pre> | |
887 | <p> | |
888 | </p> | |
889 | </td> | |
890 | </tr> | |
891 | <tr> | |
892 | <td> | |
893 | <p> | |
894 | map | |
895 | </p> | |
896 | </td> | |
897 | <td> | |
898 | <p> | |
899 | <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code> | |
900 | <span class="emphasis"><em>D</em></span> | |
901 | </p> | |
902 | </td> | |
903 | <td> | |
904 | <p> | |
905 | </p> | |
906 | </td> | |
907 | <td> | |
908 | <p> | |
909 | <code class="computeroutput"><a class="link" href="boost/icl/split_interval_map.html" title="Class template split_interval_map">split_interval_map</a></code> | |
910 | <span class="emphasis"><em>E</em></span> | |
911 | </p> | |
912 | </td> | |
913 | </tr> | |
914 | <tr> | |
915 | <td> | |
916 | <p> | |
917 | </p> | |
918 | </td> | |
919 | <td> | |
920 | <p> | |
921 | ||
922 | </p> | |
923 | <pre class="programlisting"> <span class="special">{[</span><span class="number">1</span> <span class="number">3</span><span class="special">)-></span><span class="number">1</span> <span class="special">}</span> | |
924 | <span class="special">+</span> <span class="special">[</span><span class="number">2</span> <span class="number">4</span><span class="special">)-></span><span class="number">1</span> | |
925 | <span class="special">+</span> <span class="special">[</span><span class="number">4</span> <span class="number">5</span><span class="special">)-></span><span class="number">1</span> | |
926 | <span class="special">=</span> <span class="special">{[</span><span class="number">1</span> <span class="number">2</span><span class="special">)[</span><span class="number">2</span> <span class="number">3</span><span class="special">)[</span><span class="number">3</span> <span class="number">5</span><span class="special">)</span> <span class="special">}</span> | |
927 | <span class="special">|</span> <span class="special">-></span><span class="number">1</span> <span class="special">-></span><span class="number">2</span> <span class="special">-></span><span class="number">1</span> <span class="special">|</span></pre> | |
928 | <p> | |
929 | </p> | |
930 | </td> | |
931 | <td> | |
932 | <p> | |
933 | </p> | |
934 | </td> | |
935 | <td> | |
936 | <p> | |
937 | ||
938 | </p> | |
939 | <pre class="programlisting"> <span class="special">{[</span><span class="number">1</span> <span class="number">3</span><span class="special">)-></span><span class="number">1</span> <span class="special">}</span> | |
940 | <span class="special">+</span> <span class="special">[</span><span class="number">2</span> <span class="number">4</span><span class="special">)-></span><span class="number">1</span> | |
941 | <span class="special">+</span> <span class="special">[</span><span class="number">4</span> <span class="number">5</span><span class="special">)-></span><span class="number">1</span> | |
942 | <span class="special">=</span> <span class="special">{[</span><span class="number">1</span> <span class="number">2</span><span class="special">)[</span><span class="number">2</span> <span class="number">3</span><span class="special">)[</span><span class="number">3</span> <span class="number">4</span><span class="special">)[</span><span class="number">4</span> <span class="number">5</span><span class="special">)</span> <span class="special">}</span> | |
943 | <span class="special">|</span> <span class="special">-></span><span class="number">1</span> <span class="special">-></span><span class="number">2</span> <span class="special">-></span><span class="number">1</span> <span class="special">-></span><span class="number">1</span> <span class="special">|</span></pre> | |
944 | <p> | |
945 | </p> | |
946 | </td> | |
947 | </tr> | |
948 | </tbody> | |
949 | </table></div> | |
950 | </div> | |
951 | <br class="table-break"><p> | |
952 | Note that <code class="literal">interval_sets</code> <span class="emphasis"><em>A</em></span>, <span class="emphasis"><em>B</em></span> | |
953 | and <span class="emphasis"><em>C</em></span> represent the same set of elements <code class="literal">{1,2,3,4}</code> | |
954 | and <code class="literal">interval_maps</code> <span class="emphasis"><em>D</em></span> and <span class="emphasis"><em>E</em></span> | |
955 | represent the same map of elements <code class="literal">{1->1, 2->2, 3->1, 4->1}</code>. | |
956 | See example program <a class="link" href="boost_icl/examples/interval_container.html" title="Interval container">Interval | |
957 | container</a> for an additional demo. | |
958 | </p> | |
959 | <a name="boost_icl.introduction.interval_combining_styles.joining_interval_containers"></a><h5> | |
960 | <a name="id1021715"></a> | |
961 | <a class="link" href="index.html#boost_icl.introduction.interval_combining_styles.joining_interval_containers">Joining | |
962 | interval containers</a> | |
963 | </h5> | |
964 | <p> | |
965 | <code class="computeroutput"><a class="link" href="boost/icl/interval_set.html" title="Class template interval_set">Interval_set</a></code> and <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code> are always in a | |
966 | <span class="emphasis"><em><span class="bold"><strong>minimal representation</strong></span></em></span>. | |
967 | This is useful in many cases, where the points of insertion or intersection | |
968 | of intervals are not relevant. So in most instances <code class="computeroutput"><a class="link" href="boost/icl/interval_set.html" title="Class template interval_set">interval_set</a></code> | |
969 | and <code class="computeroutput"><a class="link" href="boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code> will | |
970 | be the first choice for an interval container. | |
971 | </p> | |
972 | <a name="boost_icl.introduction.interval_combining_styles.splitting_interval_containers"></a><h5> | |
973 | <a name="id1021766"></a> | |
974 | <a class="link" href="index.html#boost_icl.introduction.interval_combining_styles.splitting_interval_containers">Splitting | |
975 | interval containers</a> | |
976 | </h5> | |
977 | <p> | |
978 | <code class="computeroutput"><a class="link" href="boost/icl/split_interval_set.html" title="Class template split_interval_set">Split_interval_set</a></code> | |
979 | and <code class="computeroutput"><a class="link" href="boost/icl/split_interval_map.html" title="Class template split_interval_map">split_interval_map</a></code> | |
980 | on the contrary have an <span class="emphasis"><em><span class="bold"><strong>insertion memory</strong></span></em></span>. | |
981 | They do accumulate interval borders both from additions and intersections. | |
982 | This is specifically useful, if we want to enrich an interval container with | |
983 | certain time grids, like e.g. months or calendar weeks or both. See example | |
984 | <a class="link" href="boost_icl/examples/time_grids.html" title="Time grids for months and weeks">time grids for months and weeks</a>. | |
985 | </p> | |
986 | <a name="boost_icl.introduction.interval_combining_styles.separating_interval_containers"></a><h5> | |
987 | <a name="id1021808"></a> | |
988 | <a class="link" href="index.html#boost_icl.introduction.interval_combining_styles.separating_interval_containers">Separating | |
989 | interval containers</a> | |
990 | </h5> | |
991 | <p> | |
992 | <code class="computeroutput"><a class="link" href="boost/icl/separate_interval_set.html" title="Class template separate_interval_set">Separate_interval_set</a></code> | |
993 | implements the separating style. This style preserves borders, that are never | |
994 | passed by an overlapping interval. So if all intervals that are inserted | |
995 | into a <code class="computeroutput"><a class="link" href="boost/icl/separate_interval_set.html" title="Class template separate_interval_set">separate_interval_set</a></code> | |
996 | are generated form a certain grid that never pass say month borders, then | |
997 | these borders are preserved in the <code class="computeroutput"><a class="link" href="boost/icl/separate_interval_set.html" title="Class template separate_interval_set">separate_interval_set</a></code>. | |
998 | </p> | |
999 | </div> | |
1000 | </div> | |
1001 | <p> | |
1002 | 14:46 15.10.2010 | |
1003 | </p> | |
1004 | </div> | |
1005 | <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> | |
1006 | <td align="left"><p><small>Last revised: February 17, 2013 at 16:00:17 GMT</small></p></td> | |
1007 | <td align="right"><div class="copyright-footer"></div></td> | |
1008 | </tr></table> | |
1009 | <hr> | |
1010 | <div class="spirit-nav"><a accesskey="n" href="boost_icl/examples.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div> | |
1011 | </body> | |
1012 | </html> |