Okay, so, I decided to scrap the BinaryHeap version of the
priority queue, going back to basics and utilizing a simple
array. It works, huzzah!
Code:
module data_structures.priority_queue;
import std.array;
import std.range: assumeSorted;
import std.typecons: Tuple;
/*
Templated Priority Queue
Usage: PriorityQueue!(PRIORITY_TYPE, VALUE_TYPE,
OPTIONAL_PREDICATE)
*/
struct PriorityQueue(P, V, alias predicate = "a < b") {
// To make the code a bit more readable
alias Tuple!(P, V) PV;
PV _q[];
// Forward most function calls to the underlying array.
PV[]* opDot() {
return &_q;
}
// Determine if the queue is empty
@property bool empty () {
return (_q.length == 0);
}
// Needed so foreach can work
@property PV front() {
return _q.front;
}
// Chop off the front of the array
@property void popFront() {
_q = _q[1 .. $];
}
// Insert a record via a template tuple
void insert(ref PV rec) {
// Empty queue?
if (_q.length == 0 ) {
// just put the record into the queue
_q ~= rec;
return;
}
// Assume the queue is already sorted according to PREDICATE
auto a = assumeSorted!(predicate)(_q);
// Find a slice containing records with priorities less than
the insertion rec
auto p = a.lowerBound(rec);
int location = p.length;
// Insert the record
_q.insertInPlace(location, rec);
}
void insert(PV rec) {
insert(rec);
}
// Insert a record via decomposed priority and value
void insert(P priority, V value) {
PV rec = PV(priority, value);
// Insert the record
insert(rec);
}
// Merge two Priority Queues, returning the merge.
// The two queues must obviously be of the same type in Priority
and Value, and predicate;
ref PriorityQueue!(P, V, predicate) merge(ref PriorityQueue!(P,
V, predicate) qmerge) {
// Make a copy of this PriorityQueue
PriorityQueue!(P, V, predicate)* qreturn = new
PriorityQueue!(P, V, predicate);
qreturn._q = _q.dup;
// Add in all the elements of the merging queue
foreach(rec; qmerge) {
qreturn.insert(rec);
}
// Return the resulting merged queue
return *qreturn;
}
}
unittest {
alias P = int;
alias V = string;
alias PV = Tuple!(P, V);
alias PQ = PriorityQueue!(P, V, "a < b");
PQ pq, pq2, pq3;
import std.typecons: tuple;
// Test basic insertion
pq.insert(10, "HELLO10");
pq.insert(11, "HELLO11");
pq.insert(3, "HELLO3");
pq.insert(31, "HELLO31");
pq.insert(5, "HELLO5");
pq.insert(10, "HELLO10-2");
assert(pq.length == 6);
foreach (const e; pq) {} // iteration
assert(!pq.empty); // shouldn't consume queue
// Copy by value
pq2 = pq;
foreach (priority, value; pq) {
pq.popFront();
}
// pq and pq2 should be independent
assert( !pq2.empty);
assert( pq.empty );
// Test merging
pq3.insert(tuple(12, "HELLO12"));
pq3.insert(Tuple!(int, string)(17, "HELLO17"));
pq3.insert(tuple(7, "HELLO7"));
pq = pq2.merge(pq3);
assert ( !pq.empty);
assert(pq.front == tuple(3, "HELLO3"));
pq.popFront;
assert(pq.front == tuple(5, "HELLO5"));
pq.popFront;
assert(pq.front == tuple(7, "HELLO7"));
pq.popFront;
assert( pq.length == 6 );
}
And a little driver main() to illustrate the queue a bit better:
main() {
PriorityQueue!(int, string) pq, pq2, pq3;
pq.insert(10, "HELLO10");
pq.insert(11, "HELLO11");
pq.insert(Tuple!(int, string)(3, "HELLO3"));
pq.insert(5, "HELLO5");
pq.insert(Tuple!(int, string)(12, "HELLO12"));
pq.insert(Tuple!(int, string)(17, "HELLO17"));
pq2.insert(Tuple!(int, string)(15, "HELLO15"));
pq2.insert(Tuple!(int, string)(21, "HELLO21"));
writefln("\tPQ: %s \n\tPQ2: %s \n\tPQ3: %s", pq, pq2,
pq3);
pq3 = pq.merge(pq2);
foreach(priority, value; pq3) {
writefln("Priority: %s \tValue: %s \tLength: %s", priority,
value, pq3.length);
pq3.popFront();
}
}
I think I like this version better than the BinaryHeap one. It's
a bit simpler and can be extended easier. For instance, I think
it would be pretty easy to use mixins to make a seperate
PriorityQueueChangable version which allows the alteration of
priorities. It's also pretty easy to search for priorities or
values of certain requirements.
I don't know enough about D to really say if its performant in
any way, but it does do the job. It took about a week to get to
this final form, coming from someone familiar with programming
but not D.
A quick review of this project from my perspective:
The first day was mostly taken up with reading about D, then
doing an abortive attempt with associative arrays until I
realized that associative arrays are not and can not be sorted.
The next day involved finding BinaryHeap and puzzling out how to
use it. I think I got really hung up on the template syntax for a
bit. It took a little to get used to. I also over engineered the
thing with a separate helper struct until I embarrassingly
discovered tuples would do the job easier.
The third day had me hitting a wall with not thinking that the
BinaryHeap eats its elements on traversal. Coming here was a
great help.
The fourth day was mostly cleaning up the BinaryHeap version and
becoming increasingly dissatisfied with it.
And now here we are today, with a new version written with just
standard arrays. The big problems I had were screwing up the
sorting predicate (I couldn't figure out why everything would
work correctly in one direction, but not the other until I
realized that assumeSorted needed to be told which predicate to
use). The predicate was also needed for the merge portion
otherwise changing the direction of the queue would cause a type
mismatch.
Those two problems plus a few other minor ones later, and the
queue is complete. I have to say, I really like D a lot!
Thanks to you all for the assistance!
