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?
