The formal review of Tim Blechmann's Heap library has concluded. Only four votes were cast, although more people commented on issues either on the mailing list or though the Code Collaborator tool. However, from the comments received, the review identified no fundamental problems in the design or implementation of the library that would entail rejection. A such, the Boost.Heap library is ACCEPTED into Boost Votes for the library were cast by: Phil Endecott Daniel Russel Votes against: Thomas Klimpel (provisionally) Andrew Sutton Other comments received during the course of the review were generally positive, with a number of technical issues identified that need to to be addressed. The final version of the library can be fully accepted once Tim has addressed the technical issues identified during the review. Below is a summary of technical concerns. - The pairing heap has a known issue, regarding stack overflows, making it potentially unusable for production code. If the recursion issue can't be adequately solved, then the data structure should carry a much stronger warning label (i.e., put it in an experimental directory). - The performance of b_heap vs. d_ary_heap vs. priority_queue needs to be better characterized. Under what circumstances does one outperform the other. If no convincing scenario can be found where b_heap outperforms the others, then it should also be placed in an experimental directory. - The heap concepts need to be revisited as per comments on the review tool. The concepts should also describe semantics of the operations, not just the interfaces. - There were several comments on the implementation of heap stability. Three alternatives were identified: “naturally stable” heaps (of which no examples were given), the current counter based approach, and a chaining approach. No consensus on the best implementation strategy. Although the counter-based approach is probably adequate for most applications, it is not universally desirable. A more thorough investigation of alternative strategies is encouraged. It would be acceptable to document the investigation in a “Future Work” section of the library documentations (with any experiments also housed in the library). - The notion of Mergeable heaps needs to be better addressed, at least to differentiate between heaps that merge in O(n) or slower time and those that can merge in O(lg n) time. The proposed solution is to write merge as a general heap algorithm and specialize it for Mergeable heaps by calling the member function merge. Also, merge should be destructive, so merge and clear should not be needed. - The documentation must be substantially improved with respect to the overall design of heap data structures (i.e., concepts), especially mutable heaps and best practices. It also needs to provide both theoretical and performance comparisons for the different heaps. - Include documentation of the benchmarking tool in the documentation. It could be instructive for users to evaluate different heap implementations on their host or target architectures. - Document the complexity of == and < for heaps. - Address the comments and issues in the Review Tool. There were other recommendations that should be considered in the long term for the library. - Thorsten Ottosen suggest making b_heap and d_ary_heap container adaptors along the lines of std::stack, std::queue, and std::priority_queue, allowing parameterization over (e.g., stack-based container). Subsequent discussion indicates that there are some impracticalities in doing so, namely that it could invalidate other policies (e.g., stability). - Phil Endecott suggested rewriting some heaps (b_heap and d_ary_heap) in terms of more general algorithms operating on a (Random Access) Range in order to support the formulation of heap structures on other memory structures. Doing this would also help support the definition of heaps that satisfied Thorsten's request. I strongly recommend investigating Phil's suggestion, but this is not a barrier to acceptance. This feature could be added in future revisions of the library. I'd like to thank the community members who took the time to review Tim's work and especially those that submitted formal reviews. I'd also like to thank Tim (again) for his contributions and patiently answering our questions and addressing our comments. Andrew _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost