Creating a Priority Queue: An Adventure
DarthCthulhu via Digitalmars-d-learn
digitalmars-d-learn at puremagic.com
Wed Aug 5 13:41:39 PDT 2015
On Wednesday, 5 August 2015 at 09:04:54 UTC, Nordlöw wrote:
> On Wednesday, 5 August 2015 at 01:02:56 UTC, DarthCthulhu wrote:
>> I must be doing something really stupid here, but I have no
>> clue what it is. Anyone know?
>
>
> For functional behaviour I prefer a postblit that duplicates
> the underlying BinaryHeap.
>
> https://github.com/nordlow/justd/blob/master/priority_queue.d
>
> Now the foreach won't consume the queue.
Oh, neat! I stumbled on the same thing (making a .dup of the
BinaryHeap), but didn't know about the postblit. That makes
things simplier.
>
> This will however duplicate the underlying array aswell, which
> is probably not what we want. How do we avoid this?
I was wondering that, myself, when I stumbled on the .dup
solution. My first thought was to instantiate a templated Array!
first, then use BinaryHeap.assume or .acquire to make it a
BinaryHeap while also keeping a reference to the underlining
array. Then one could just return the array reference in a
separate function rather than destructively iterating through the
BinaryHeap.
My experiments didn't bear this out, however. Maybe I'm
misunderstanding what the .assume and .acquire functions do?
Incidentally, I also discovered the wonderful opDot function
which allows the PriorityQueue to shunt most of the work down to
the BinaryHeap directly.
// Forward most function calls to the underlying queue.
BinaryHeap!(Array!(PV), predicate)* opDot() {
return &_q;
}
> Yeah, I think there is no way to "traverse" a binary heap in
> order without manipulating it. However, you can print the
> underlying storage.
There's a way to get at the underlining store? I couldn't find
any means to do so in the BinaryHeap documentation.
>in my vision, either x.popFront would also create a copy or you
>would have to go "auto y = x.nonModifyingView" or similar. What
>I don't want is something that copies 10000 elements just to use
>x.take(6)
Yeah, that's it exactly!
More information about the Digitalmars-d-learn
mailing list