123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335 |
- [/
- 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 Introduction]
- [/ note [* The Interval Container Library is accepted into Boost]
- The [*Interval Container Library] (formerly /Interval Template Library/) underwent
- a formal review on the boost developer's list
- from February 18, 2010 to March 08, 2010 and has been accepted
- by declaration of review manager Hartmut Kaiser
- into the boost library collection on April 18, 2010.
- The library has been refactored for the suggestions and requests
- that came up during the review. The current version is now
- ready for inclusion into the next boost release.
- The name ['*Interval Template Library (ITL)*]
- has been changed to ['*Interval Container Library (ICL)*].
- If you find bugs in the library or typos or other shortcomings in
- the documentation please send reports to the boost developers list
- boost@lists.boost.org
- the boost users list or
- boost-users@lists.boost.org
- to `[afojgo<AT>gmail dot com]`.
- ]
- ["A bug crawls across the boost docs on my laptop screen.
- Let him be! We need all the readers we can get.] --
- Freely adapted from [@http://en.wikipedia.org/wiki/Jack_Kornfield Jack Kornfield]
- Intervals are almost ubiquitous in software development. Yet they are
- very easily coded into user defined classes by a pair of numbers
- so they are only /implicitly/ used most of the time. The meaning of
- an interval is simple. They represent all the elements between their
- lower and upper bound and thus a set. But unlike sets, intervals
- usually can not be added to a single new interval.
- If you want to add intervals to a collection of
- intervals that does still represent a /set/,
- you arrive at the idea of /interval_sets/ provided by this library.
- Interval containers of the *ICL* have been developed initially at
- [@http://www.cortex-software.de/desktopdefault.aspx Cortex Software GmbH]
- to solve problems related to date and time interval
- computations in the context of a Hospital Information System.
- Time intervals with associated values like ['amount of invoice]
- or ['set of therapies] had to be manipulated in statistics,
- billing programs and therapy scheduling programs.
- So the *ICL* emerged out of those industrial use cases.
- It extracts generic code that helps to solve common
- problems from the date and time problem domain and can be
- beneficial in other fields as well.
- One of the most advantageous aspects of interval containers is
- their very compact representation of sets and maps. Working with
- sets and maps /of elements/ can be very inefficient, if in a given
- problem domain, elements are typically occurring in contiguous
- chunks.
- Besides a compact representation of associative containers, that
- can reduce the cost of space and time drastically, the ICL
- comes with a universal mechanism of aggregation, that allows
- to combine associated values in meaningful ways when intervals
- overlap on insertion.
- For a condensed introduction and overview you may want to look at the
- [@http://www.herold-faulhaber.de/boost_icl/doc/libs/icl/doc/boostcon09/intro_to_itl.pdf
- presentation material on the *ICL* from ['*BoostCon2009*]].
- [section Definition and Basic Example]
- The [*Interval Container Library (ICL)] provides __itvs__ and two kinds of
- interval containers: __itv_sets__ and __itv_maps__.
- * An __itv_bset__ is a *set* that is implemented as a set of intervals.
- * An __itv_bmap__ is a *map* that is implemented as a map of interval value pairs.
- [h4 Two Aspects]
- __Itv_bsets__ and __itv_bmaps__ expose two different aspects in
- their interfaces: (1) The functionality of a set or a map, which is the more
- ['*abstract aspect*]. And (2) the functionality of a container of intervals which
- is the more specific and ['*implementation related aspect*]. In practice both
- aspects are useful and are therefore supported.
- The first aspect, that will be called __bi_conceptual__ ['*aspect*], is the more important one.
- It means that we can use an __itv_set__ or __itv_map__ like a
- set or map ['*of elements*]. It exposes the same functions.
- ``
- interval_set<int> mySet;
- mySet.insert(42);
- bool has_answer = contains(mySet, 42);
- ``
- The second aspect, that will be called __bi_iterative__ ['*aspect*], allows to exploit the
- fact, that the elements of __itv_sets__ and __itv_maps__ are clustered in
- ['*intervals*] or ['*segments*] that we can iterate over.
- ``
- // Switch on my favorite telecasts using an interval_set
- interval<seconds>::type news(make_seconds("20:00:00"), make_seconds("20:15:00"));
- interval<seconds>::type talk_show(make_seconds("22:45:30"), make_seconds("23:30:50"));
- interval_set<seconds> myTvProgram;
- myTvProgram.add(news).add(talk_show);
- // Iterating over elements (seconds) would be silly ...
- for(interval_set<seconds>::iterator telecast = myTvProgram.begin();
- telecast != myTvProgram.end(); ++telecast)
- //...so this iterates over intervals
- TV.switch_on(*telecast);
- ``
- Working with __itv_bsets__ and __itv_bmaps__ can be
- beneficial whenever the elements of
- sets appear in contiguous chunks: __itvs__. This is obviously the
- case in many problem domains, particularly in fields that deal with
- computations related to date and time.
- [h4 Addabitlity and Subtractability]
- Unlike `std::sets` and `maps`, __itv_bsets__ and __itv_bmaps__ implement
- concept `Addable` and `Subtractable`. So __itv_bsets__ define an
- `operator +=` that is naturally implemented as ['*set union*] and an
- `operator -=` that is consequently implemented as ['*set difference*].
- In the *Icl* __itv_bmaps__ are addable and subtractable as well.
- It turned out to be a very fruitful concept to propagate the
- addition or subtraction to the __itv_bmap_s__ associated values
- in cases where the insertion of an interval value pair into an
- __itv_map__ resulted in a collision of the inserted interval
- value pair with interval value pairs, that are already in the
- __itv_map__. This operation propagation is called ['*aggregate on overlap*].
-
- [h4 Aggregate on Overlap]
- This is a first motivating example of a very small party, demonstrating the
- ['*aggregate on overlap*] principle on __itv_maps__:
- In the example Mary enters the party first. She attends during the
- time interval `[20:00,22:00)`. Harry enters later. He stays within `[21:00,23:00)`.
- ``
- typedef std::set<string> guests;
- interval_map<time, guests> party;
- party += make_pair(interval<time>::right_open(time("20:00"), time("22:00")), guests("Mary"));
- party += make_pair(interval<time>::right_open(time("21:00"), time("23:00")), guests("Harry"));
- // party now contains
- [20:00, 21:00)->{"Mary"}
- [21:00, 22:00)->{"Harry","Mary"} //guest sets aggregated on overlap
- [22:00, 23:00)->{"Harry"}
- ``
- ['*On overlap of intervals*], the corresponding name sets are ['*accumulated*]. At
- the ['*points of overlap*] the intervals are ['*split*]. The accumulation of content on
- overlap of intervals is done via an `operator +=` that has to be implemented
- for the associated values of the __itv_map__. In the example
- the associated values are `guest sets`. Thus a `guest set` has to implement
- `operator +=` as set union.
- As can be seen from the example an __itv_map__ has both
- a ['*decompositional behavior*] (on the time dimension) as well as
- an ['*accumulative one*] (on the associated values).
- Addability and aggregate on overlap are useful features on
- __itv_maps__ implemented via function `add` and `operator +=`.
- But you can also use them with the ['traditional]
- [link boost_icl.function_reference.insertion insert semantics]
- that behaves like `std::map::insert` generalized for
- interval insertion.
- [endsect]
- [section Icl's class templates]
- In addition to interval containers we can work with
- containers of elements that are ['*behavioral equal*]
- to the interval containers: On the fundamental aspect
- they have exactly the same functionality.
- An __std_set__ of the STL is such an equivalent set implementation.
- Due to the aggregation facilities of the icl's interval maps
- __std_map__ is fundamentally not completely equivalent to an __itv_map__.
- Therefore there is an extra __icl_map__ class template for maps of
- elements in the icl.
- * The __std_set__ is behavioral equal to __itv_bsets__ on the __bi_conceptual__ aspect.
- * An __icl_map__ is behavioral equal to __itv_bmaps__ on the __bi_conceptual__ aspect.
- Specifically an __icl_map__
- implements ['*aggregate on overlap*], which is
- named ['*aggregate on collision*] for an element container.
- The following tables give an overview over the main
- class templates provided by the *icl*.
- [table Interval class templates
- [[group] [form] [template] ]
- [[statically bounded] [asymmetric][__ro_itv__] ]
- [[ ] [] [__lo_itv__] ]
- [[ ] [symmetric] [__cl_itv__] ]
- [[ ] [] [__op_itv__] ]
- [[dynamically bounded][] [__dc_itv__] ]
- [[ ] [] [__ct_itv__] ]
- ]
- Statically bounded intervals always have the same kind of interval borders,
- e.g. right open borders`[a..b)` for __ro_itv__. Dynamically bounded intervals
- can have different borders. Refer to the chapter about
- [link boost_icl.interface.class_templates.intervals ['*intervals*]]
- for details.
- [table Container class templates
- [[granularity][style] [sets] [maps] ]
- [[interval] [joining] [__itv_set__] [__itv_map__] ]
- [[] [separating][__sep_itv_set__][] ]
- [[] [splitting] [__spl_itv_set__][__spl_itv_map__]]
- [[element] [] [(__ele_set__)] [__ele_map__] ]
- ]
- __Std_set__ is placed in paretheses, because it is not a class template
- of the *ICL*. It can be used as element container though that is
- behavioral equal to the ICL's interval sets on their fundamental aspect.
- Column ['*style*] refers to
- the different ways in which interval containers combine added
- intervals. These ['*combining styles*] are described in the next
- section.
- [endsect]
- [section Interval Combining Styles]
- When we add intervals or interval value pairs to interval containers,
- the intervals can be added in different ways: Intervals can be
- joined or split or kept separate. The different interval combining
- styles are shown by example in the tables below.
- [table Interval container's ways to combine intervals
- [[] [joining] [separating] [splitting]]
- [[set] [[classref boost::icl::interval_set interval_set]]
- [[classref boost::icl::separate_interval_set separate_interval_set]]
- [[classref boost::icl::split_interval_set split_interval_set]]]
- [[map] [[classref boost::icl::interval_map interval_map]]
- []
- [[classref boost::icl::split_interval_map split_interval_map]]]
- [[] [Intervals are joined on overlap or touch\n(if associated values are equal).]
- [Intervals are joined on overlap, not on touch.]
- [Intervals are split on overlap.\nAll interval borders are preserved.]]
- ]
- [table Interval combining styles by example
- [[] [joining] [separating] [splitting]]
- [[set] [[classref boost::icl::interval_set interval_set] /A/]
- [[classref boost::icl::separate_interval_set separate_interval_set] /B/]
- [[classref boost::icl::split_interval_set split_interval_set] /C/]]
- [[]
- [``
- {[1 3) }
- + [2 4)
- + [4 5)
- = {[1 5)}``]
- [``
- {[1 3)} }
- + [2 4)
- + [4 5)
- = {[1 4)[4 5)}``]
- [``
- {[1 3) }
- + [2 4)
- + [4 5)
- = {[1 2)[2 3)[3 4)[4 5)}``]
- ]
- [[map] [[classref boost::icl::interval_map interval_map] /D/]
- []
- [[classref boost::icl::split_interval_map split_interval_map] /E/]]
- [[]
- [``
- {[1 3)->1 }
- + [2 4)->1
- + [4 5)->1
- = {[1 2)[2 3)[3 5) }
- | ->1 ->2 ->1 |``]
- []
- [``
- {[1 3)->1 }
- + [2 4)->1
- + [4 5)->1
- = {[1 2)[2 3)[3 4)[4 5) }
- | ->1 ->2 ->1 ->1 |``]
- ]
- ]
- Note that =interval_sets= /A/, /B/ and /C/ represent the same set of elements ={1,2,3,4}=
- and =interval_maps= /D/ and /E/ represent the same map of elements [^{1->1, 2->2, 3->1, 4->1}].
- See example program [link boost_icl.examples.interval_container Interval container]
- for an additional demo.
- [h4 Joining interval containers]
- __Itv_set__ and __itv_map__ are always
- in a ['*minimal representation*]. This is useful in many cases, where the
- points of insertion or intersection of intervals are not relevant. So in most
- instances __itv_set__ and
- __itv_map__ will be the first choice
- for an interval container.
- [h4 Splitting interval containers]
- __Spl_itv_set__ and __spl_itv_map__ on the contrary
- have an ['*insertion memory*]. They do accumulate interval borders both
- from additions and intersections. This is specifically useful, if we want
- to enrich an interval container with certain time grids, like e.g. months
- or calendar weeks or both. See example [link boost_icl.examples.time_grids time grids for months and weeks].
- [h4 Separating interval containers]
- __Sep_itv_set__ implements the separating style.
- This style preserves borders, that are never passed by an overlapping
- interval. So if all intervals that are inserted into a __sep_itv_set__
- are generated form a certain grid that never pass say month borders, then
- these borders are preserved in the __sep_itv_set__.
-
- [endsect]
- [endsect][/ Introduction]
|