Just wondering: If I want a growable binary heap (I'd be open to other priority queue structures, for that matter ;), is the standard way in D (w/Phobos) to combine std.container.BinaryHeap with std.container.Array? Any reason why BinaryHeap can't deal with ordinary dynamic array appending, or appender instances, for that matter? Or, to put the questions a bit differently: Is there a reason why std.array doesn't have an insertBack method (that BinaryHeap can use) either defined for dynamic arrays or for std.array.Appender?

Just trying to figure out what's what here :)

-- 
Magnus Lie Hetland
http://hetland.org

On 2011-03-06 14:37:19 +0100, Magnus Lie Hetland said:

> Just wondering: If I want a growable binary heap (I'd be open to other priority queue structures, for that matter ;), is the standard way in D (w/Phobos) to combine std.container.BinaryHeap with std.container.Array?

Another thing ... when I use priority queues, I'm usually not interested in just having a set of priorities -- the payload data is what it's all about. So I thought I'd just use an Array of Tuples, managed by BinaryHeap (possibly with a custom comparison, to avoid comparing the payloads). But perhaps that's not a good idea?

When I try

   alias Tuple!(real,int) Entry;
   Array!Entry Q;

that works just fine. However, if I try

   alias Tuple!(real,int) Entry;
   Array!Entry Q;

then I get the following errors:

container.d(1549): Error: this for _data needs to be type Array not type Payload
container.d(1550): Error: this for _data needs to be type Array not type Payload
container.d(1551): Error: this for _data needs to be type Array not type Payload

It seems the lines that are being referred to are

   GC.removeRange(_data._payload.ptr);
   free(_data._payload.ptr);
   _data._payload = newPayload;

though I may be wrong about that.

Is this a bug in Array? Am I using it wrong? And what would be the recommended "best practice" for a priority queue with payload data in D (using Phobos)? (I could just write one myself, but that seems sort of wasteful ;)

-- 
Magnus Lie Hetland
http://hetland.org

On 3/6/11 2:58 PM, Magnus Lie Hetland wrote:
> alias Tuple!(real,int) Entry;
> Array!Entry Q;
> […]
> alias Tuple!(real,int) Entry;
> Array!Entry Q;

Is it just me, or is there really no difference between the two snippets? ;)

David

On 2011-03-06 15:00:29 +0100, David Nadlinger said:

> On 3/6/11 2:58 PM, Magnus Lie Hetland wrote:
>> alias Tuple!(real,int) Entry;
>> Array!Entry Q;
>> [...]
>> alias Tuple!(real,int) Entry;
>> Array!Entry Q;
> 
> Is it just me, or is there really no difference between the two snippets? ;)

$(WITTY_REPLY) ;-)

The one that fails should have string (or some other reference type, perhaps) rather than int. Copy/paste fail :D

-- 
Magnus Lie Hetland
http://hetland.org

On 2011-03-06 14:58:10 +0100, Magnus Lie Hetland said:

[corrected the example below, replacing int with string]
> that works just fine. However, if I try
> 
>     alias Tuple!(real,string) Entry;
>     Array!Entry Q;
> 
> then I get the following errors:
> 
> container.d(1549): Error: this for _data needs to be type Array not type Payload
> container.d(1550): Error: this for _data needs to be type Array not type Payload
> container.d(1551): Error: this for _data needs to be type Array not type Payload

Actually, now, running the same program, I get a *different* error message:

container.d(1502): Error: template instance template 'hasElaborateDestructor' is not defined
container.d(1502): Error: hasElaborateDestructor!(Tuple!(real,string)) is not an expression

As far as I know, I haven't changed anything in the ecosystem, and the code is the same (which seems a bit magical...).

Anyway: this doesn't seem right ... should I file a bug?

-- 
Magnus Lie Hetland
http://hetland.org