----- Original Message ----- From: "Joachim Faulhaber" <afojgo@googlemail.com> To: <boost@lists.boost.org> 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