Steven Schveighoffer wrote:
> On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> 
> 
>> The heap is a tad difficult to tackle. Most of the time you don't want to create a heap, but instead to organize an existing range as a heap. As such, the heap is not always obvious to think of as a container. I'm undecided on how to approach this.
> 
> It's easier to think of a heap as a single entity with operations on it.  At least for me anyway.
> 
> Most of the time, once you make a range a heap, you want to continue to use it as a heap.  Restricting operations on that range by defining a heap type around it can do this.  Otherwise, you could accidentally do something foolish like sort the range.
> 
> -Steve

But for several graph algorithms, (eg, A* pathfinding), you have {key1, key2} pairs, forming a heap based on key1, but you also need to able to search for key2.
The container is a hybrid, consisting of heap on {key1} + AA on {key2}.
It uses the heap operations, but it's not exactly a heap.

Incidentally this requires the adjust_heap() operation, which was dropped from the STL for political reasons, but should be provided in D.

On 06/01/2010 07:57 AM, Steven Schveighoffer wrote:
> On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>
>
>> The heap is a tad difficult to tackle. Most of the time you don't want
>> to create a heap, but instead to organize an existing range as a heap.
>> As such, the heap is not always obvious to think of as a container.
>> I'm undecided on how to approach this.
>
> It's easier to think of a heap as a single entity with operations on it.
> At least for me anyway.
>
> Most of the time, once you make a range a heap, you want to continue to
> use it as a heap. Restricting operations on that range by defining a
> heap type around it can do this. Otherwise, you could accidentally do
> something foolish like sort the range.

The problem is the original range is still around.

void fun(Range)(Range r) if (isRandomAccessRange!Range)
{
    auto heap = BinaryHeap!Range(r);
    ... use heap, but r is still there ...
}

This is not memory-unsafe, but may mess up the working of the heap. If the heap takes a copy of the range, that would most often be wasteful.


Andrei

On Tue, 01 Jun 2010 09:17:15 -0400, Don <nospam@nospam.com> wrote:

> Steven Schveighoffer wrote:
>> On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>>
>>> The heap is a tad difficult to tackle. Most of the time you don't want to create a heap, but instead to organize an existing range as a heap. As such, the heap is not always obvious to think of as a container. I'm undecided on how to approach this.
>>  It's easier to think of a heap as a single entity with operations on it.  At least for me anyway.
>>  Most of the time, once you make a range a heap, you want to continue to use it as a heap.  Restricting operations on that range by defining a heap type around it can do this.  Otherwise, you could accidentally do something foolish like sort the range.
>>  -Steve
>
> But for several graph algorithms, (eg, A* pathfinding), you have {key1, key2} pairs, forming a heap based on key1, but you also need to able to search for key2.
> The container is a hybrid, consisting of heap on {key1} + AA on {key2}.
> It uses the heap operations, but it's not exactly a heap.

And such a container would be not a heap.  I don't think it should be impossible to define such a construct if a vanilla heap type is also defined.

My recommendation: keep the heap functions in std.algorithm and create a std.container based off them.

-Steve

On Tue, 01 Jun 2010 09:28:28 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> On 06/01/2010 07:57 AM, Steven Schveighoffer wrote:
>> On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu
>> <SeeWebsiteForEmail@erdani.org> wrote:
>>
>>
>>> The heap is a tad difficult to tackle. Most of the time you don't want
>>> to create a heap, but instead to organize an existing range as a heap.
>>> As such, the heap is not always obvious to think of as a container.
>>> I'm undecided on how to approach this.
>>
>> It's easier to think of a heap as a single entity with operations on it.
>> At least for me anyway.
>>
>> Most of the time, once you make a range a heap, you want to continue to
>> use it as a heap. Restricting operations on that range by defining a
>> heap type around it can do this. Otherwise, you could accidentally do
>> something foolish like sort the range.
>
> The problem is the original range is still around.
>
> void fun(Range)(Range r) if (isRandomAccessRange!Range)
> {
>      auto heap = BinaryHeap!Range(r);
>      ... use heap, but r is still there ...
> }
>
> This is not memory-unsafe, but may mess up the working of the heap. If the heap takes a copy of the range, that would most often be wasteful.

You can go through lengths to make sure r isn't accessible outside it's heap interface, for example, by splitting fun into two functions:

void fun(Range)(Range r) if (isRandomAccessRange!Range)
{
    auto heap = BinaryHeap!Range(r);
    fun2(heap);  // in this function, r is not accessible.
}

And even without this, I can stop using r after the first line.  I have a better chance of not using r in a non-heap way in that case.

A heap type also may want to make a copy of the input, most other containers do.  This allows it to own the storage for the data.

-Steve

On Tue, 01 Jun 2010 09:43:55 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:


> And even without this, I can stop using r after the first line.  I have a better chance of not using r in a non-heap way in that case.

Note, this is similar to how immutable data must be created mutable, cast to immutable, and then you must forget the original mutable reference.

-Steve

On 06/01/2010 08:43 AM, Steven Schveighoffer wrote:
> On Tue, 01 Jun 2010 09:28:28 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>
>> On 06/01/2010 07:57 AM, Steven Schveighoffer wrote:
>>> On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu
>>> <SeeWebsiteForEmail@erdani.org> wrote:
>>>
>>>
>>>> The heap is a tad difficult to tackle. Most of the time you don't want
>>>> to create a heap, but instead to organize an existing range as a heap.
>>>> As such, the heap is not always obvious to think of as a container.
>>>> I'm undecided on how to approach this.
>>>
>>> It's easier to think of a heap as a single entity with operations on it.
>>> At least for me anyway.
>>>
>>> Most of the time, once you make a range a heap, you want to continue to
>>> use it as a heap. Restricting operations on that range by defining a
>>> heap type around it can do this. Otherwise, you could accidentally do
>>> something foolish like sort the range.
>>
>> The problem is the original range is still around.
>>
>> void fun(Range)(Range r) if (isRandomAccessRange!Range)
>> {
>> auto heap = BinaryHeap!Range(r);
>> ... use heap, but r is still there ...
>> }
>>
>> This is not memory-unsafe, but may mess up the working of the heap. If
>> the heap takes a copy of the range, that would most often be wasteful.
>
> You can go through lengths to make sure r isn't accessible outside it's
> heap interface, for example, by splitting fun into two functions:
>
> void fun(Range)(Range r) if (isRandomAccessRange!Range)
> {
> auto heap = BinaryHeap!Range(r);
> fun2(heap); // in this function, r is not accessible.
> }
>
> And even without this, I can stop using r after the first line. I have a
> better chance of not using r in a non-heap way in that case.
>
> A heap type also may want to make a copy of the input, most other
> containers do. This allows it to own the storage for the data.

Good points. Let me just mention that I wrote BinaryHeap for a number of practical necessities. Without exception, _all_ would be killed if copying would be required. IMHO requiring copying is out of the question.

I see two possibilities:

(a) Move BinaryHeap as it is to std.container. That means you can build a heap around any given random-access range, but it also means that the heap can't grow beyond the original range's size. Incidentally this is often the case, but I'm sure not always.

(b) Have BinaryHeap require a container, then define a method Array!(T).acquire(T[]) that assumes ownership of a given buffer. In such cases, you can define a growable BinaryHeap on top of an array that has just acquired a given range. Other random-access ranges, however, would not be supported.

Not sure what to do.


Andrei

Steven Schveighoffer wrote:
> On Tue, 01 Jun 2010 09:17:15 -0400, Don <nospam@nospam.com> wrote:
> 
>> Steven Schveighoffer wrote:
>>> On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>>>
>>>> The heap is a tad difficult to tackle. Most of the time you don't want to create a heap, but instead to organize an existing range as a heap. As such, the heap is not always obvious to think of as a container. I'm undecided on how to approach this.
>>>  It's easier to think of a heap as a single entity with operations on it.  At least for me anyway.
>>>  Most of the time, once you make a range a heap, you want to continue to use it as a heap.  Restricting operations on that range by defining a heap type around it can do this.  Otherwise, you could accidentally do something foolish like sort the range.
>>>  -Steve
>>
>> But for several graph algorithms, (eg, A* pathfinding), you have {key1, key2} pairs, forming a heap based on key1, but you also need to able to search for key2.
>> The container is a hybrid, consisting of heap on {key1} + AA on {key2}.
>> It uses the heap operations, but it's not exactly a heap.
> 
> And such a container would be not a heap.  I don't think it should be impossible to define such a construct if a vanilla heap type is also defined.
> 
> My recommendation: keep the heap functions in std.algorithm and create a std.container based off them.

That's what I think, too.