Re: [boost] GSoC 2010: Heaps and Queues

Subject: Re: [boost] GSoC 2010: Heaps and Queues
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2010-04-09 00:31:20

AMDG

Dan Larkin wrote:
> Steven Watanabe wrote:
>> Maybe I missed something but why pure virtual functions?
>
> Heap is simply a concept, and should be treated as an abstract base 
> class, I believe, and should never be instantiated.  Individual models 
> should take up all the slack of actually implementing these methods.  
> Do I have the wrong understanding?

I'm confused about whether this is a real class and what it's
actually doing.  Is it actually going to be the base class for the
different heap implementations?  In my experience, templates
and virtual functions are not usually combined in this way.
The normal way to specify the concept requirements is
something like
http://www.boost.org/doc/html/Assignable.html

>>>       virtual iterator& findMin() = 0;
>>>       virtual void removeMin() = 0;
>>
>> top and pop would be more consistent with
>> std::priority_queue.
>
> findMin and removeMin (or even moreso deleteMin) are more consistent 
> with standard heap terminology.  It's a well-known group of data 
> structures taught in curricula all over and studied since who knows 
> when.  Why conform to the terminology of a specific implementation in 
> a programming language that's not nearly as old or well-established?

Because it's the language that you're implementing it in.  Consistent
naming makes it easier to plug in different types (for instance, what if
I wanted to write a function that could take either your heap or a
standard priority_queue).  findMin is also inconsistent with standard
and Boost naming conventions, which use lowercase_and_underscores
for everything except Concepts and MACROS.

>   I'm providing the PriorityQueue class as essentially a wrapper with 
> the potentially more appealing push/pop terminology for this reason.  
> Sorry if that sounded overly aggressive, it wasn't my intent.

If the different names are the only reason to separate PriorityQueue and
Heap classes, then I'm strongly against it.

In Christ,
Steven Watanabe