[boost] [gsoc] heaps & queues

Subject: [boost] [gsoc] heaps & queues
From: Tim Blechmann (tim_at_[hidden])
Date: 2010-04-28 14:55:30

hi all,

i'm the student, working on the heaps&queues project during this year's 
summer of code. i have also been in touch with my mentor about this, but 
thought, it may be a good idea to hear some comments from other boost devs.

i would like to implement the priority queue data as intrusive data 
structures, which can simply be wrapped to non-intrusive ones. the main 
reason for this approach is the mutable property.

in order to provide a mutable priority queue, one would either need a handle 
to the inner node (like in dietmar kuehl's pri_queue) or provide a lookup 
table (as in boost/pending/mutable_queue). both approaches are somehow 
problematic. otoh, if i want to change the priority of a node, it would be 
natural to use an intrusive data structure for this.
the non-intrusive version would be simply a wrapped version of the intrusive 
implementation, and would simply lack the mutable property.

the question then would be, whether i should try to introduce it into 
boost.intrusive, or implement it as a library on its own. boost.intrusive 
already provides a treap, so it would be quite logical to include heap data 
structures as well. otoh, having a heap library with both intrusive and non-
intrusive data structures, one would have everything in one place. so, i see 
benefits in both approaches, but would like to hear, what other people think 
about it ...

cheers, tim

-- 
tim_at_[hidden]
http://tim.klingt.org
The first question I ask myself when something doesn't seem to be
beautiful is why do I think it's not beautiful. And very shortly you
discover that there is no reason.
  John Cage.