
Boost : 
From: vicente.botet (vicente.botet_at_[hidden])
Date: 20080516 13:04:05
 Original Message 
From: "Joachim Faulhaber" <afojgo_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, May 12, 2008 5:35 PM
Subject: [boost] proposal: interval containers
> Dear boost developers,
>
> I would like to contribute some library code that covers the field of
> interval containers, specifically interval_set and interval_map.
>
> My design of interval sets is based on the fact that an
> interval<T> is a set<T>, which implies that a set<T> t can be
> represented as a set<interval<T>> s, where t is the union over
> all intervals contained in s.
>
> The implementation of a set<T> as a set<interval<T>> can be
> beneficial whenever in a given problem domain the elements of
> sets appear in contiguous chunks: intervals. This is obviously the
> case in many problem domains, namely in fields that deal with problems
> related to date and time.
Hello,
I'm mainly interested in an implementation of set<T> using set<interval<T>
and on how it comapres to the stl::set in space and time, when the set are
dense or scattered.
I have just take a look to the documentation and the implementation, and I
have some questions?
* Why not follow the STL set and map interfaces as far as possible?
* Why do you use virtual functions? Are the classes sets, and
interval_base_set public? I think this can and should be avoided.
* Does it works with boost::interval?
> The benefits of interval sets and maps are
> 1. The implementation of sets/maps via interval_set/map is very
> space and also time efficient.
Have you done some messures, in space and time? In the worst case {1, 11,
21...}?
> 2. All problems concerning overlaps of intervals and their
> handling can be encapsulated in the implementation and thus ...
> 3. A higher abstraction level dealing with interval and specifically
> time interval related problems can be obtained.
> I wrote a library that provides generic classes for interval_sets
> and interval_maps and a few more things called "Interval
> Template Library (itl)". I'd like to give a very brief
> description of the library in this post. For more detailed
> information and the current source code you might want to download
> the itl from http://sourceforge.net/projects/itl.
>
> The code contained in the library was originally developed
> at Cortex Software GmbH Berlin (Clinic Information Systems), where
> interval containers already proved to be very useful for
> quite some years in almost all of our applications. In 2006
> Cortex Software GmbH allowed the code to be released
> as open source and I provided a preliminary version at sourceforge.
>
> Meanwhile I have refactored the code to enhance it's fitness
> for generic designs, portable usage and a possible integration
> in the boost libraries. Since I have not (yet;) found
> the functionality of the 'itl' in the boost libraries nor
> a discussion about the rejection of such topics in the
> boost archives I would like to offer parts of the library here.
Do you plan to boostify your code?
> interval_set:
> itl::interval_set implements all functionality of std::set as a set
> of intervals and in addition +=, = and *= for set union, difference
> and intersection. On insertion of neighbouring or overlapping
> intervals inserted intervals are joined.
I'm no sure interval_set is a model of Unique Associative Container.
Given the following :
interval_set<interval<int>> is;
is.insert([1,3));
is.insert([3,5));
What is the result of
assert(find([1,3))!= end);
And of
assert(find([1,5))== end);
Which operator would you use for set_symmetric_difference? This is a detail
but it will be better to provided the function version of this operators as
well.
> split_interval_set:
> split_interval_set works like interval_set but borders of the
> inserted intervals are preserved, so it can be used as time grid.
> Using itl::split_interval_set you can partition other interval
> containers using the *= operator to perform intersections.
Which are the difference between split_interval_set <interval<T> > and
set<interval<T> >?
> split_interval_map:
> A split_interval_map implements a map as a map of intervals
> and associated values. For dealing with the insertion
> of overlapping intervals the principle of "aggregation on
> overlap" has proved to be very useful: It is shown by example:
>
> typedef set<string> guests;
> split_interval_map<time, guests> party;
> guests mary; mary.insert("Mary");
> guests harry; harry.insert("Harry");
> party.insert(make_pair(rightopen_interval(20:00, 22:00), mary));
> party.insert(make_pair(rightopen_interval(21:00, 23:00), 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"}
>
> As can be seen from the example a split_interval_map has both
> a decompositional behavior (on the time dimension) as well as
> a accumulative one (on the associated values).
Quite interesting!
> Quality, validation, portability:
>
> The library code of the itl has been validated with a law based
> test automaton (LaBatea;) which is included in
> the current release. It includes a testcase generator and law tester
> that checks laws like e.g. commutativity<interval_set<double>, +=>:
> the commutativity of interval_set<double> w.r.t. the operation +=.
>
> The code has been compiled and tested with three compilers
> (gcc 3.4.4, conceptgccboostcon, msvc 8.0 sp1) and with three
> implementations of the stl (linux/gnu, stlport, msvc8) under
> suse linux 10.1. and mswindows xp.
> I'd be happy if you found interval conainers as presented in this
> post an interesting contribution to look at.
I'm sure that this library will be a good candidate to boost.
> If so, I am looking forward to an inspiring discussion.
Best regards
Vicente Botet
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk