I'm another potential student throwing my hat in the ring for the heap project.
Hi Dan, Sorry I've been slow responding. I'm having trouble keeping track of which GSoC email I've responded to :)
The way I see it, the current heap implementations in boost/pending are rather fractured. They just have simple push/pop interfaces with no mutability (well, there's mutable_heap.hpp, but that's separate and not fleshed out).
That's a fairly accurate description of the state of things. You should also look at the C++ Standard heap algorithms and priority queue. You might want to consider what how you might change those to support mutability in standard heaps. I know that a stable priority queue was mentioned in earlier discussion, but
I'm not sure what to do about that just yet.
In general a priority queue can essentially be thought of as a queue adaptor for an (partially?) ordered data structure. Stability is a property of the ordering of elements in the underlying data structure. Such that two equivalent objects in the queue will be popped in the reverse order of their insertion. Or was it the same order? You could probably make arguments for either or as long as its deterministic. I guess that's basically how I see the problem so far. Please let me know
what you think, or what other sort of information/planning/etc. you would like to hear from me prior to my proposal/draft.
Draft proposals are welcome. It's easier to give feedback than to suggest ideas :) Andrew Sutton andrew.n.sutton@gmail.com