Re: [boost] [google summer of code] student

Subject: Re: [boost] [google summer of code] student
From: Cezary Bartoszuk (cbart_at_[hidden])
Date: 2010-04-05 04:30:53

Hi,

I looked at APIs at https://svn.boost.org/svn/boost/sandbox/libs/pri_queue/
The interfaces are quite well designed, but I don't understand one point:
Why are there function templates used in methods providing mutability
(for example change_top, change, decrease, increase for the lazy
Fibonacci heap:
https://svn.boost.org/svn/boost/sandbox/libs/pri_queue/l_heap.html)? I
think K stands there for "key", but there's already comparison functor
(which defaults to std::less) provided, so we don't store key-value
pairs (with key being the priority), do we?
Why then K is used?

The second key point I would like to ask about is the implementation.
Are there any priority queues already implemented in BGL? If so, it
would be nice for us to stay compatible with interfaces implemented
already.

Besides few doubts listed above I would like to propose implementing
at least pri queues listed in
https://svn.boost.org/svn/boost/sandbox/libs/pri_queue/, so:

* D-ary Heap (with standard - binary - heap as a special case)
* Fibonacci Heap (btw, I thought, the Fibonacci heap is already lazy -
maybe there's an discrepancy in the names)
* Pairing Heap (didn't ever hear about them, but there are lots of
references in the net)
* Splay Heap (think it's a gret idea - simple implementaion and quite
nice performance)
* Radix Heap (also didn't hear about them, but the intuition is,
that's a dara structure implementing radix-sort?)

Speaking about stable priority queues (FIFO- or LIFO- stable) i have
no fresh ideas for now, but I think it's quite useful, and would be
happy to implement it.

I have read that there are lots of people submitting proposals for the
project; could any partition of work or time estimation be a part of
the proposal (because there will surely be at least few of us working
on the Heaps & Queues)?

Best regards,
Cezary Bartoszuk

2010/3/30 Cezary Bartoszuk <cbart_at_[hidden]>:
> Thanks, I surely will.
>
> Cezary Bartoszuk
>
> 2010/3/30 Andrew Sutton <andrew.n.sutton_at_[hidden]>:
>>> I am a CS student and I would like to patricipate in developing Heaps
>>> & Queues in Boost during Google Summer Of Code '10.
>>> Where, besides the source code, should I search for information
>>> about what's already in Boost (in the meaning of heaps/queues)?
>>> Who should I talk to about participating in Boost?
>>>
>>
>> Hi Cezary,
>>
>> You would probably ask me since I posted the idea. If you search the
>> dev-list archives you'll find lots of discussion on this topic.
>>
>> Andrew Sutton
>> andrew.n.sutton_at_[hidden]
>> _______________________________________________
>> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>>
>