Re: [boost] proposal: interval containers

From: vicente.botet (vicente.botet_at_[hidden])
Date: 2008-05-16 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, conceptgcc-boostcon, msvc 8.0 sp1) and with three
> implementations of the stl (linux/gnu, stlport, msvc8) under
> suse linux 10.1. and ms-windows 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