2010/12/16 Dave Abrahams <dave@boostpro.com>:
At Thu, 16 Dec 2010 00:25:37 +0100, Joachim Faulhaber wrote:
2010/12/15 Dave Abrahams <dave@boostpro.com>:
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