123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387 |
- [/
- Copyright (c) 2008-2010 Joachim Faulhaber
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- ]
- [section Examples]
- [section Overview]
- [table Overview over Icl Examples
- [[level] [example] [classes] [features]]
- [[intro][[link boost_icl.examples.party Party]]
- [__itv_map__][Generates an attendance history of a party
- by inserting into an __itv_map__.
- Demonstrating
- ['*aggregate on overlap*].]]
- [[basic] [[link boost_icl.examples.interval Interval]]
- [__dc_itv__, __ct_itv__ ] [Intervals for discrete and continuous instance types.
- Closed and open interval borders.]]
- [[basic] [[link boost_icl.examples.dynamic_interval Dynamic intervals]]
- [__dc_itv__, __ct_itv__, __itv__ ] [Intervals with dynamic interval bounds as library default.]]
- [[basic] [[link boost_icl.examples.static_interval Static intervals]]
- [__ro_itv__, __itv__ ] [Intervals with static interval bounds and changing the library default.]]
- [[basic] [[link boost_icl.examples.interval_container Interval container]]
- [__itv_set__,\n__sep_itv_set__,\n__spl_itv_set__,\n__spl_itv_map__,\n__itv_map__]
- [Basic characteristics of interval containers.]]
- [[basic] [[link boost_icl.examples.overlap_counter Overlap counter]]
- [__itv_map__][The most simple application of an interval map:
- Counting the overlaps of added intervals.]]
- [[advanced][[link boost_icl.examples.partys_height_average Party's height average]]
- [__itv_map__][Using /aggregate on overlap/ a history of height averages of party guests is computed.
- Associated values are user defined class objects, that implement
- an appropriate `operator +=` for the aggregation.]]
- [[advanced][[link boost_icl.examples.partys_tallest_guests Party's tallest guests]]
- [__itv_map__,\n__spl_itv_map__]
- [Using /aggregate on overlap/ the heights of the party's tallest guests are computed.
- Associated values are aggregated via a maximum functor, that can
- be chosen as template parameter of an interval_map class template.]]
- [[advanced][[link boost_icl.examples.time_grids Time grids for months and weeks]]
- [__spl_itv_set__]
- [Shows how the ['*border preserving*]
- __spl_itv_set__ can be used to create time partitions where different
- periodic time intervals overlay each other.]]
- [[advanced][[link boost_icl.examples.man_power Man power]]
- [__itv_set__,\n__itv_map__]
- [Set style operations on __itv_sets__ and __itv_maps__ like union, difference
- and intersection can be used to obtain calculations in a flexible way. Example
- [*man_power] demonstrates such operations in the process of calculating the
- available man-power of a company in a given time interval.]]
- [[advanced][[link boost_icl.examples.user_groups User groups]][__itv_map__]
- [Example [*user_groups] shows how interval_maps can be unified or
- intersected to calculate desired information.]]
-
- [[and std] [[link boost_icl.examples.std_copy Std copy]]
- [__itv_map__][Fill interval containers using `std::copy`.]]
- [[and std] [[link boost_icl.examples.std_transform Std transform]]
- [__itv_map__,\n__sep_itv_set__][Fill interval containers from user defined objects using `std::transform`.]]
-
- [[customize] [[link boost_icl.examples.custom_interval Custom interval]]
- [__itv_tr__][Use interval containers with your own interval class types.]]
- ]
- [endsect]
- [section Party]
- [import ../example/boost_party_/boost_party.cpp]
- Example *party* demonstrates the possibilities of an interval map
- (__itv_map__ or __spl_itv_map__).
- An __itv_map__ maps intervals to a given content. In this case the
- content is a set of party guests represented by their name strings.
- As time goes by, groups of people join the party and leave later in the evening.
- So we add a time interval and a name set to the __itv_map__ for the attendance
- of each group of people, that come together and leave together.
- On every overlap of intervals, the corresponding name sets are accumulated. At
- the points of overlap the intervals are split. The accumulation of content
- is done via an operator += that has to be implemented
- for the content parameter of the __itv_map__.
- Finally the interval_map contains the history of attendance and all points in
- time, where the group of party guests changed.
- Party demonstrates a principle that we call
- ['*aggregate on overlap*]:
- On insertion a value associated to the interval is aggregated with those
- values in the interval_map that overlap with the inserted value.
- There are two behavioral aspects to ['*aggregate on overlap*]: a ['*decompositional
- behavior*] and an ['*accumulative behavior*].
- * The ['*decompositional behavior*] splits up intervals on the /time/ /dimension/ of the
- interval_map so that the intervals are split whenever associated values
- change.
- * The ['*accumulative behavior*] accumulates associated values on every overlap of
- an insertion for the associated values.
-
- The aggregation function is += by default. Different aggregations can
- be used, if desired.
-
- [example_boost_party]
- [caution
- We are introducing __itv_maps__ using an
- ['interval map ['*of sets of strings*]],
- because of it's didactic advantages. The party example is
- used to give an immediate access to the basic ideas of
- interval maps and /aggregate on overlap/.
- For real world applications, an interval_map of sets is
- not necessarily recommended.
- It has the same efficiency problems as
- a `std::map` of `std::sets`.
- There is a big realm though of using
- interval_maps with numerical and other
- efficient data types for the associated values.
- ]
- [endsect] [/ Party]
- [section Interval]
- Example *interval* shows some basic functionality of __itvs__.
- * Different instances of __itvs__ for integral ([^int, Time]) and
- continuous types ([^double, std::string]) are used.
- * The examples uses open and closed intervals bounds.
- * Some borderline functions calls on open interval borders are tested e.g.:
- `interval<double>::rightopen(1/sqrt(2.0), sqrt(2.0)).contains(sqrt(2.0));`
- [import ../example/interval_/interval.cpp]
- [example_interval]
- [endsect]
- [section Dynamic interval]
- [import ../example/dynamic_interval_/dynamic_interval.cpp]
- [example_dynamic_interval]
- [endsect]
- [section Static interval]
- [import ../example/static_interval_/static_interval.cpp]
- [example_static_interval]
- [endsect]
- [section Interval container]
- Example [*interval container] demonstrates the characteristic behaviors
- of different interval containers that are also summarized
- in the introductory [link boost_icl.introduction.interval_combining_styles Interval Combining Styles].
- [import ../example/interval_container_/interval_container.cpp]
- [example_interval_container]
- [endsect]
- [section Overlap counter]
- Example [*overlap counter] provides the simplest application
- of an interval_map that maps intervals to integers.
- An interval_map<int,int> serves as an overlap counter
- if we only add interval value pairs that carry 1 as
- associated value.
- Doing so, the associated values that are accumulated in
- the interval_map are just the number of overlaps of all added
- intervals.
- [import ../example/overlap_counter_/overlap_counter.cpp]
- [example_overlap_counter]
- [endsect]
- [section:partys_height_average Party's height average]
- In the example `partys_height_average.cpp` we compute yet another aggregation:
- The average height of guests. This is done by defining a `class counted_sum`
- that sums up heights and counts the number of guests
- via an `operator +=`.
- Based on the `operator +=` we can aggregate counted sums on addition
- of interval value pairs into an interval_map.
- [import ../example/partys_height_average_/partys_height_average.cpp]
- [example_partys_height_average]
- Required for `class counted_sum` is a default constructor
- `counted_sum()`and
- an `operator ==` to test equality.
- To enable additive aggregation on overlap also
- an `operator +=` is needed.
- Note that no `operator -=` for a subtraction of `counted_sum` values
- is defined. So you can only add to the
- `interval_map<ptime, counted_sum>`
- but not subtract from it.
- In many real world applications only addition is needed and user
- defined classes will work fine, if they only implement
- `operator +=`. Only if any of the `operator`s `-=` or `-`
- is called on the interval_map, the user defined class has to
- implement it's own `operator -=` to provide the subtractive
- aggregation on overlap.
- [endsect]
- [section:partys_tallest_guests Party's tallest guests]
- Defining `operator +=` (and `-=`) is probably the most important
- method to implement arbitrary kinds of user defined aggregations.
- An alternative way to choose a desired aggregation is to
- instantiate an interval_map class template with an
- appropriate ['*aggregation functor*]. For the most common
- kinds of aggregation the [*icl]
- provides such functors as shown in the example.
- Example `partys_tallest_guests.cpp` also demonstrates
- the difference between an __itv_map__
- that joins intervals for equal associated values and a
- __spl_itv_map__ that preserves all borders of inserted
- intervals.
- [import ../example/partys_tallest_guests_/partys_tallest_guests.cpp]
- [example_partys_tallest_guests]
- [endsect]
- [section:time_grids Time grids for months and weeks]
- A __spl_itv_set__ preserves all interval borders on insertion
- and intersection operations. So given a __spl_itv_set__ and an addition of an interval
- ``
- x = {[1, 3)}
- x.add( [2, 4))
- ``
- then the intervals are split at their borders
- ``
- x == {[1,2)[2,3)[3,4)}
- ``
- Using this property we can intersect __spl_itv_maps__ in
- order to iterate over intervals accounting for all occurring
- changes of interval borders.
- In this example we provide an intersection of two __spl_itv_sets__
- representing a month and week time grid.
- [import ../example/month_and_week_grid_/month_and_week_grid.cpp]
- [example_month_and_week_grid]
- [endsect]
- [section Man power]
- __Itv_sets__ and __itv_maps__ can be filled and manipulated using
- set style operations such as union `+=`, difference `-=` and
- intersection `&=`.
- In this example [*man power] a number of those operations are
- demonstrated in the process of calculation the available working
- times (man-power) of a company's employees accounting for weekends,
- holidays, sickness times and vacations.
- [import ../example/man_power_/man_power.cpp]
- [example_man_power]
- [endsect]
- [section User groups]
- Example [*user groups] shows the availability of set operations
- on __itv_maps__.
- In the example there is a user group `med_users` of a hospital staff
- that has the authorisation to handle medical data of patients.
- User group `admin_users` has access to administrative data like
- health insurance and financial data.
- The membership for each user in one of the user groups has a time
- interval of validity. The group membership begins and ends.
- * Using a union operation `+` we can have an overview over the unified
- user groups and the membership dates of employees.
- * Computing an intersection `&` shows who is member of both med_users
- and admin_users at what times.
- [import ../example/user_groups_/user_groups.cpp]
- [example_user_groups]
- [endsect]
- [section Std copy]
- The standard algorithm
- [@http://www.cplusplus.com/reference/algorithm/copy/ `std::copy`]
- can be used to fill interval containers
- from standard containers of intervals or
- interval value pairs (segments). Because intervals
- do not represent ['*elements*] but ['*sets*], that
- can be empty or contain more than one element,
- the usage of `std::copy` differs from what we
- are familiar with using ['containers of elements].
- * Use `icl::inserter` from `#include <boost/icl/iterator.hpp>`
- instead of `std::inserter` to call insertions on the target
- interval container.
-
- * As shown in the examples above and below this point, most of
- the time we will not be interested to `insert` segments
- into __itv_maps__ but to __biLadd__
- them, in order to generate the desired aggregation results.
- You can use `std::copy` with an `icl::adder` instead of an
- `icl::inserter` to achieve this.
- [import ../example/std_copy_/std_copy.cpp]
- [example_std_copy]
- [endsect][/ Std copy]
- [section Std transform]
- Instead of writing loops, the standard algorithm
- [@http://www.cplusplus.com/reference/algorithm/transform/ `std::transform`]
- can be used to fill interval containers
- from std containers of user defined objects.
- We need a function, that
- maps the ['user defined object] into the
- ['segement type] of an interval map or the
- ['interval type] of an interval set.
- Based on that we can use `std::transform`
- with an `icl::inserter` or `icl::adder`
- to transform the user objects into interval
- containers.
- [import ../example/std_transform_/std_transform.cpp]
- [example_std_transform]
- To get clear about the different behaviors of interval containers
- in the example, you may want to refer to the section about
- [link boost_icl.introduction.interval_combining_styles interval combining styles]
- that uses the same data.
- [/
- Instead of `icl::inserter` we could also use an `std::inserter`
- with algorithms `std::copy` and `std::transform`.
- This is ['*depreciated*], because `std::inserter` is designed for
- containers of elements, where ['*exacty one*] element is inserted
- via `std::inserter` if it is not already in the container.
- In contrast to that, an interval or segemnt can represent zero, one,
- or many elements of an interval container.
- You can use `std::inserter` *only*, if you actively take care of
- two preconditions:
- # None of the intervals or segements of the source containers
- must be empty.
-
- # A segment never carries a neutral element when your target
- interval map absorbs identities.
- Violating those preconditions leads to ['*undefined behavior*].
- ]
- [endsect][/ std::transform]
- [section Custom interval]
- Example *custom interval* demonstrates how to use interval
- containers with an own interval class type.
- [import ../example/custom_interval_/custom_interval.cpp]
- [example_custom_interval]
- [endsect][/ Custom interval]
- [endsect][/ examples]
|