Re: [boost] [gsoc] boost.heap update

Subject: Re: [boost] [gsoc] boost.heap update
From: Tim Blechmann (tim_at_[hidden])
Date: 2010-07-29 08:50:28

>> i am a bit afraid to show a piece of incorrect code. in the
>> documentation. but is is probably clearer than just describing it with
>> words ...
> 
> If you have some comment like // DON'T DO THIS AT HOME
> no harm would come from showing incorrect code, I guess.

well, people may think, that you may use it, if you are supersmart ;)

> BTW: Wouldn't it be possible to check whether or not increase/decrease
> are used correctly (and throw an exception otherwise)?

no. there is no way to detect, whether some data has been modified. stl 
containers like map/set don't allow you to modify the key elements in 
general, boost.intrusive lets you modify the nodes, but assumes that you are 
careful enough not to modify the key ...

>>> * Data structure comparisons: The information seems rather incomplete.
>>> For instance, "In contrast to d-ary heaps, binomial heaps can also be
>>> merged in O(log n)." OK, now I know, that binomial heaps can be merged
>>> in O(log n), and d-ary can't. But I don't know the complexity for
>>> merging d-ary nor any other heap.
>>> Maybe it would be easier to use one or more tables to compare the
>>> features/complexities?
>> 
>> well, i have been thinking about it ... however i am not sure, what to
>> compare (amortized or worst-case complexity). also the analysis of
>> pairing heaps is not solved, yet ...
> 
> One idea would be to have a table for complexities for each pair of type
> and action (i.e. push, top, pop, merge, ...). If you have different
> values (e.g. optimal, average, worst-case), name them all. Maybe also
> describe what optimal/worst-case look like.

i will see, what i can do.

> One more thing: Even if boost heaps are probably quite easy to use, I'd
> add a small tutorial/examples section that shows some working code using
> heaps and their features.

well, in the concepts section, i am trying to explain the concepts and give 
some example code. not sure, if it is better to separate concepts and 
examples or to combine them ...

tim

-- 
tim_at_[hidden]
http://tim.klingt.org
All we composers really have to work with is time and sound - and
sometimes I'm not even sure about sound.
  Morton Feldman