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

Subject: Re: [boost] [gsoc] boost.heap snapshot
From: Tim Blechmann (tim_at_[hidden])
Date: 2010-07-12 03:07:43

hi daniel,

> 1. Would it make sense to overload some operators to merge heaps?
> Perhaps `|` and `|=` to mirror Boost Dynamic Bitset and the suggestion
> for `interval_set` of Boost Interval Container Library.

hm ... i am not sure about this ... i like the expressive power of `merge' 
and `merge_and_clear', especially, since some non-destructive merges are 
rather expensive ... i would prefer if the API reflects this difference ...

> 2. The `pointer`, `const_pointer`, `reference`, and `const_reference`
> typedefs should come from the `Alloc` template parameter.
> 
> 3. The `pointer` and `const_pointer` types from `Alloc::template
> rebind<node>::other` should be used instead of `node*` and `const
> node*`.

good point!

> 4. It might be nice to implement a B-heap. Poul-Henning Kamp wrote an
> article for ACM Queue that was published just a month ago. In it, Kamp
> argues for B-heaps instead of binary heaps:
> http://queue.acm.org/detail.cfm?id=1814327

interesting, especially, since it seems that b-heaps can easily be 
implemented as container adapters ... i will try to implement it as well ...

> 5. A soft heap implementation might be nice, too, depending on time.
> Of course, this could be a future extension:
> http://en.wikipedia.org/wiki/Soft_heap

i have considered adding soft heaps and some relaxed heaps (violation heaps 
look interesting) ... if i have some spare time at the end of the gsoc, i 
will work on them ...

> 6. Members that take rvalue references might be good to add in
> anticipation of C++0x.

true ...

> 7. I saw in the documentation that you were defining the interfaces of
> heaps and mutable heaps. This is really good because it helps to
> standardize things. It would be nice to also have concept checking
> classes so that programs can use `BOOST_CONCEPT_ASSERT`. See
> <boost/graph/graph_concepts.hpp>
> (http://www.boost.org/doc/libs/1_43_0/boost/graph/graph_concepts.hpp)
> for some examples of creating concepts.

i am actually not completely sure, how to document concepts correctly. 
currently the concept checking classes are located in 
heap/test/common_heap_tests.hpp.

> 8. In the documentation, would you outline the major differences
> between the different heap types?

yes, i will need to give an overview

> 9. Do your implementations accept equivalent values (equivalent in the
> equivalence relation induced by the compare object)? I assume so,
> because you discuss "stable" heaps. A point about accepting
> "duplicates" would be good to add to the documentation, though.

yes. duplicate values are fine, but unless the heap is configured to be 
stable, the order of duplicates is undefined.

thanks for your comments, i will try to address them ..

cheers, tim

-- 
tim_at_[hidden]
http://tim.klingt.org
A good composer does not imitate; he steals.
  Igor Stravinsky