www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Growable BinaryHeap: use w/Array?

reply Magnus Lie Hetland <magnus hetland.org> writes:
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
Mar 06 2011
parent reply Magnus Lie Hetland <magnus hetland.org> writes:
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
Mar 06 2011
next sibling parent reply David Nadlinger <see klickverbot.at> writes:
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
Mar 06 2011
parent Magnus Lie Hetland <magnus hetland.org> writes:
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
Mar 06 2011
prev sibling parent Magnus Lie Hetland <magnus hetland.org> writes:
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
Mar 07 2011