Re: [boost] proposal: interval containers; boost examples and more

From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2008-08-04 16:09:05

2008/7/29, David Abrahams <dave_at_[hidden]>:
>
> on Tue Jul 29 2008, "Alp Mestan" <alpmestan-AT-gmail.com> wrote:
>
> > That looks quite good.
> >
> > Internally, how do you manage errors ? Is there an exception based system ?
> > Or did you write some static-verification-system ?
> >
> > On Tue, Jul 29, 2008 at 8:51 AM, Joachim Faulhaber <afojgo_at_[hidden]>wrote:
> >
> >> Dear boost developers,
> >>
> >> after encouraging feedback by Paul A Bristow, Vicente Botet and
> >> Luke Simonson to my proposal on interval containers from end of May
> >> (http://lists.boost.org/Archives/boost/2008/05/137301.php), I started to
> >> boostify my interval template library (ITL). Even though there is a lot
> >> left
> >> to be done for the ITL to become fully boost compliant I'd like to report
> >> on
> <snip entire (long!) post>
>
> 1. Please don't overquote
>
> 2. I wrote an interval map about ten years ago now by modifying the
>   rb-tree implementation from STLPort.  This can be a really useful
>   class of data structures.  I support continued work on getting this
>   into Boost.
>
Thank you for looking at my work. I am really happy to have such an
influential boost developer supporting my project.

You mention your own implementation of an interval map using rb-trees.
As you might have noticed my library implements interval sets finally
via std::sets and interval_maps via std::maps. I am well aware that a
specifically tailored interval tree has an optimization potential over
a std::container implementation. So this is also on my todo list. Yet
I wanted to focus on design, clarity and correctness first before
improving performance using a more optimally tailored implementation.

I have been thinking about such optimized implementation a few times
and would also choose a balanced tree implementation (e.g. the newly
simplified left leaned rb trees by Robert Sedgewick
http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf) that
additionally exploits properties of the intervals.

Therefore I am interested to take a look at your implementation of an
interval map using rb-trees. This might save me some unnecessary hours
of work.

Thanks
Joachim