[gsoc] boost.heap snapshot
hi all, i have uploaded a snapshot of boost.heap [1] and the initial documentation to [2]. feedback / suggestions are more than welcome! especially i would like to hear some thoughts about the interface, and if someone requests a specific heap implementation, it is also a good time to ask for it now ... cheers, tim [1] http://tim.klingt.org/code/attachments/download/28/boost_heap_110710.tar.gz [2] http://tim.klingt.org/boost_heap -- tim@klingt.org http://tim.klingt.org ... to make life worth living ... Keith Rowe on making music
On 2010-07-11, Tim Blechmann <tim@klingt.org> wrote:
hi all,
i have uploaded a snapshot of boost.heap [1] and the initial documentation to [2]. feedback / suggestions are more than welcome! especially i would like to hear some thoughts about the interface, and if someone requests a specific heap implementation, it is also a good time to ask for it now ...
cheers, tim
[1] http://tim.klingt.org/code/attachments/download/28/boost_heap_110710.tar.gz [2] http://tim.klingt.org/boost_heap
-- tim@klingt.org http://tim.klingt.org
A few points of feedback: 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. 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*`. 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 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 6. Members that take rvalue references might be good to add in anticipation of C++0x. 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. 8. In the documentation, would you outline the major differences between the different heap types? 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.
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@klingt.org http://tim.klingt.org A good composer does not imitate; he steals. Igor Stravinsky
participants (2)
-
Daniel Trebbien -
Tim Blechmann