BinaryHeap is a range so it goes in std.range. Agree?

[Andrei Alexandrescu]

On 06/08/2010 04:41 PM, Simen kjaeraas wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:
>
>> On 06/08/2010 10:53 AM, Simen kjaeraas wrote:
>>> Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:
>
>>>> But where should I put it then? I thought it would be even more
>>>> confusing if I put something in std.container that wait a minute, is
>>>> not a container.
>>>
>>> How is it not a container? Because it uses a different container as a
>>> back-end?
>>
>> It does not implement the container primitives and is not a reference
>> type.
>
> So it is not a container because you chose not to make it a container.

Instead of assuming that I'm simultaneously retard(ed) and stubborn, it 
would be more productive to ask more about my reasons. I'll assume you 
did so.

I wrote BinaryHeap out of necessity. The necessity was to solve the 
selection problem (see topN, topNIndex in std.algorithm) and to 
implement n-way merge (see std.algorithm.nWayUnion, I think I'll rename 
it to nWayMerge).

In all these cases, there was no necessity for defining a heap as a 
container; instead, using it as a means to add structure over an 
existing range were sufficient.

If I defined the heap as a container, there would be need for one extra 
allocation and also extra indirections to ensure reference semantics. I 
wanted to avoid all that.

>> There are already rules that disambiguate range operations from
>> similar container operations. For example a range defines popFront()
>> whereas a container defines removeFront().
>
> And my point is that removeFront() is popFront() with a different name,
> so many containers could be considered ranges with mutated member
> functions. :p But we're arguing semantics.

It's a good point. I agree it would make sense to define a binary heap 
container in addition to a binary heap range. I'm only weary that they 
don't have very clean means to reuse code, so we'll end up with some 
unpleasant implementation internals. I guess I'll just have to do that.

>> I agree that a BinaryHeap built on top of a container may ultimately
>> affect the topology of the container, which makes it unlike e.g. Take
>> or Chain. I could choose to disallow that and simply require that
>> BinaryHeap always works on top of a range, not a container. But I
>> think it's useful to have the growing functionality, and I don't think
>> that makes BinaryHeap hopelessly confusing.
>
> To me, this makes it a container.
>
> Now, my favorite way of dealing with this: Where would I look for a
> binary heap if I wanted one? I would think of it as a container, and thus
> check std.container. If it was not there, I would use the search function
> to find it. I can invent reasons, but it's mostly grounded in learned
> names and categories.

I think that's sensible.


Andrei