Re: [boost] Interval Trees & ICL

Subject: Re: [boost] Interval Trees & ICL
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-12-16 06:20:36

2010/12/16 Dave Abrahams <dave_at_[hidden]>:
> At Thu, 16 Dec 2010 00:25:37 +0100,
> Joachim Faulhaber wrote:
>>
>> 2010/12/15 Dave Abrahams <dave_at_[hidden]>:
>> > At Wed, 15 Dec 2010 21:34:44 +0100,
>> > Joachim Faulhaber wrote:
>> >>
>> > Not too hairy; an interval tree I made by modifying my STL's rbtree
>> > implementation worked just fine.
>>
>> so why not add your interval tree implementation to Interval
>> Containers, if it is readily available?
>
> That code was written before Boost even existed, I think, and is owned
> by my employer-at-the-time.

:(

So, what would be a good way of doing this?
Instead of implementing a specific augmentation modifying an existing
rbtree, I think it'd be more fun, to write an augmented_rbtree on the
basis of a good rbtree implementation, and then write the
interval_tree as an instance of augmented_rbtree.

The augmented_rbtree would have a template parameter typename A, for
the sythesized attribute, the augmentation and a functor F to compute
the augmented node attribute a = F()(left, x, right). This way it
might be possible to write a template for a class of augmented trees,
that contains the interval_tree as a special case but can be used for
other problems as well.

Joachim

-- 
Interval Container Library [Boost.Icl]
http://www.joachim-faulhaber.de