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