So I've just gotten into D and decided to have a go at creating something relatively simple to get my feet wet: a priority queue. Seemed like a simple enough thing, right? It's a pretty basic data structure, it can't possibly be THAT difficult, right?

First, I tried using associative arrays only to discover that associative arrays are not and can not be sorted, nor is the order of elements guaranteed via insertion. Doh! Back to the drawing board.

Next, I discovered the BinaryHeap. Aha! This does exactly what I want! This should be easy! Just a thin little wrapper around it and I should be golden.

I created a small helper struct to encapsulate the priority and values... and then I discovered Tuple, which does that pretty much already. Feeling pretty stupid for missing tuples before, I rewrote the PriorityQueue to use tuples.

And now (two days later) things seem to work... except for one big thing.

The BinaryHeap always has a length of zero. This is especially confusing as I can verify that new elements are being inserted, the BinaryHeap just keeps its length at zero. I figure I must be doing something wrong, but I haven't the faintest clue what it could be.

Here's some code:

<code>

struct PriorityQueue(P, V, alias predicate = "a > b") {

	// Templated queue
	alias Tuple!(P, V) PV;
	BinaryHeap!(Array!(PV), predicate) queue;

	@property bool empty()
    	{
		return queue.empty;
    	}

	@property PV front()
    	{

		return queue.front;

    	}

	@property int length() {
		return queue.length;
	}

	void insert(P priority, V value) {

		// Insert the new element into the queue
		queue.insert( PV(priority, value) );

	}
	
	void insert(PV ins) {
		queue.insert(ins);
	}

	void popFront()
    	{
		// Remove the first key
		queue.popFront();
    	}

}

void main() {

	PriorityQueue!(int, string) pq;
	
	pq.insert(10, "HELLO10");
	pq.insert(11, "HELLO11");
	pq.insert(Tuple!(int, string)(3, "HELLO3"));

	writefln("PQ: %s", pq.queue); <- prints PQ: [Tuple!(int, string)(3, "HELLO3"), Tuple!(int, string)(10, "HELLO10"), Tuple!(int, string)(11, "HELLO11")]

	writefln("PQ length: %s", pq.queue.length); <- prints PQ length: 0

	assert( !pq.empty ); <- Assert fails
}

</code>

I must be doing something really stupid here, but I have no clue what it is. Anyone know?

On 8/4/15 9:02 PM, DarthCthulhu wrote:

>      writefln("PQ: %s", pq.queue); <- prints PQ: [Tuple!(int, string)(3,
> "HELLO3"), Tuple!(int, string)(10, "HELLO10"), Tuple!(int, string)(11,
> "HELLO11")]

This is probably consuming your queue, popping all the data off as it prints. If you print the length before hand, I'll bet it's not zero.

I don't know how to print the elements without removing them, as binary heap doesn't have a range type, it seems to be the range itself (an odd situation). Perhaps print the underlying storage?

-Steve

On Wednesday, 5 August 2015 at 01:27:53 UTC, Steven Schveighoffer wrote:
> On 8/4/15 9:02 PM, DarthCthulhu wrote:
>
>>      writefln("PQ: %s", pq.queue); <- prints PQ: [Tuple!(int, string)(3,
>> "HELLO3"), Tuple!(int, string)(10, "HELLO10"), Tuple!(int, string)(11,
>> "HELLO11")]
>
> This is probably consuming your queue, popping all the data off as it prints. If you print the length before hand, I'll bet it's not zero.
>

Aha! Yes, you are correct. I didn't know writefln was popping elements off the heap. I thought it would've just walked down the heap without altering it at all. Interesting. Now I feel kinda silly.

> I don't know how to print the elements without removing them, as binary heap doesn't have a range type, it seems to be the range itself (an odd situation). Perhaps print the underlying storage?
>
> -Steve

Yeah, I think the thing to do would be to make a helper function that would return the Array!(Tuple!) that the heap contains. Maybe as a const reference to make sure a user doesn't accidentally alter the array?

Thanks for your help!

On Wednesday, 5 August 2015 at 01:27:53 UTC, Steven Schveighoffer wrote:
> On 8/4/15 9:02 PM, DarthCthulhu wrote:
>
>>      writefln("PQ: %s", pq.queue); <- prints PQ: [Tuple!(int, string)(3,
>> "HELLO3"), Tuple!(int, string)(10, "HELLO10"), Tuple!(int, string)(11,
>> "HELLO11")]
>
> This is probably consuming your queue, popping all the data off as it prints. If you print the length before hand, I'll bet it's not zero.
>
> I don't know how to print the elements without removing them, as binary heap doesn't have a range type, it seems to be the range itself (an odd situation). Perhaps print the underlying storage?
>
> -Steve

It looks like there was a breaking change made to BinaryHeap somewhere between 2.065 and the present. The code compiles fine on 2.065.

http://dpaste.dzfl.pl/65ba735d69e7

On Wednesday, 5 August 2015 at 02:26:48 UTC, Meta wrote:
> On Wednesday, 5 August 2015 at 01:27:53 UTC, Steven Schveighoffer wrote:
>> On 8/4/15 9:02 PM, DarthCthulhu wrote:
>>
>>>      writefln("PQ: %s", pq.queue); <- prints PQ: [Tuple!(int, string)(3,
>>> "HELLO3"), Tuple!(int, string)(10, "HELLO10"), Tuple!(int, string)(11,
>>> "HELLO11")]
>>
>> This is probably consuming your queue, popping all the data off as it prints. If you print the length before hand, I'll bet it's not zero.
>>
>> I don't know how to print the elements without removing them, as binary heap doesn't have a range type, it seems to be the range itself (an odd situation). Perhaps print the underlying storage?
>>
>> -Steve
>
> It looks like there was a breaking change made to BinaryHeap somewhere between 2.065 and the present. The code compiles fine on 2.065.
>
> http://dpaste.dzfl.pl/65ba735d69e7

Interesting.

I notice that the output of the 'writefln("PQ: %s", pq.queue);' line is different in 2.065 as well. Presumably the change was made because if one is printing out a BinaryHeap, one is more likely interested in the contents of the heap rather than its signature?

I'm using 2.067.1.

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.

This will however duplicate the underlying array aswell, which is probably not what we want. How do we avoid this?

On Wednesday, 5 August 2015 at 02:26:48 UTC, Meta wrote:
> It looks like there was a breaking change made to BinaryHeap somewhere between 2.065 and the present. The code compiles fine on 2.065.
>
> http://dpaste.dzfl.pl/65ba735d69e7

It was this PR that changed the behaviour:
https://github.com/D-Programming-Language/phobos/pull/1989

On Wednesday, 5 August 2015 at 09:04:54 UTC, Nordlöw wrote:
> For functional behaviour I prefer a postblit that duplicates the underlying BinaryHeap.

The postblit is the

    this(this) { ... }

On Wednesday, 5 August 2015 at 09:04:54 UTC, Nordlöw wrote:
> This will however duplicate the underlying array aswell, which is probably not what we want. How do we avoid this?

Correction: the underlying storage array *must* be duplicated whenever we want to iterate over it without side effects in the original instance. That's just the way binary heaps work.

On 8/5/15 7:09 AM, "Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow@gmail.com>" wrote:
> On Wednesday, 5 August 2015 at 09:04:54 UTC, Nordlöw wrote:
>> This will however duplicate the underlying array aswell, which is
>> probably not what we want. How do we avoid this?
>
> Correction: the underlying storage array *must* be duplicated whenever
> we want to iterate over it without side effects in the original
> instance. That's just the way binary heaps work.

Yeah, I think there is no way to "traverse" a binary heap in order without manipulating it. However, you can print the underlying storage.

-Steve