Creating a Priority Queue: An Adventure
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:
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
}
I must be doing something really stupid here, but I have no clue
what it is. Anyone know?
Re: Creating a Priority Queue: An Adventure
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!
Re: Creating a Priority Queue: An Adventure
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.
Re: Creating a Priority Queue: An Adventure
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 1 elements just to use
x.take(6)
Yeah, that's it exactly!
Re: Creating a Priority Queue: An Adventure
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
Re: Dynamic array and foreach loop
On Saturday, 8 August 2015 at 15:57:15 UTC, Binarydepth wrote:
Here's what happens :
How many elements need to be used? 5
Input the element : 1 1
Input the element : 1 2
Input the element : 1 3
Input the element : 1 4
Input the element : 1 5
How many positions do you wish to rotate ? 3
The original patter is : 5 0 0 0 0
The final is : 0 0 0 5 0
Do you want to rotate again ? y/n y
How many positions do you wish to rotate ? 2
The original patter is : 0 0 0 5 0
The final is : 5 0 0 0 0
Do you want to rotate again ? y/n n
Do you want to make an adicional sequence ? a/A a
How many elements need to be used? 4
Input the element : 1 1
Input the element : 1 2
Input the element : 1 3
core.exception.RangeError@gen014.d(31): Range violation
0x4077ef _Dmain
???:0
0x41684e void rt.dmain2._d_run_main(int, char**, extern (C) int
function(char[][])*).runAll().void __lambda1()
../../../../src/libphobos/libdruntime/rt/dmain2.d:408
0x416abe void rt.dmain2._d_run_main(int, char**, extern (C) int
function(char[][])*).tryExec(scope void delegate())
../../../../src/libphobos/libdruntime/rt/dmain2.d:383
0x416d18 void rt.dmain2._d_run_main(int, char**, extern (C) int
function(char[][])*).runAll()
../../../../src/libphobos/libdruntime/rt/dmain2.d:408
0x416abe void rt.dmain2._d_run_main(int, char**, extern (C) int
function(char[][])*).tryExec(scope void delegate())
../../../../src/libphobos/libdruntime/rt/dmain2.d:383
0x416c45 _d_run_main
../../../../src/libphobos/libdruntime/rt/dmain2.d:416
0x7f8c84eeda3f __libc_start_main
???:0
0x406058 _start
???:0
0x ???
???:0
This is happening because 'num' is reading the value of each
element in the array; it's not a count. Once it reads the 5 in
element, it attempts to put the next number into element 5, which
of course doesn't exist.
This is also why the first time through there is only one value
in the array that isn't 0: 'num' the first time through is always
zero because the values of the dynamic array are .init-ed to zero.
You can fix it like the following:
foreach(num, element; liaOrig) {//Data input loop
writefln("num: %s current element: %s liaOrig.length: %s",
num, element, liaOrig.length);
write("Input the element : ", num+1, " ");
readf(" %d", &liaOrig[num]);
}
Now 'num' is just an iterative number starting from 0 (the .init
value of an int), while the actual element value is stored in
'element'. I added the writefln() statement to make it a bit more
clear during runtime.
As an addenum, you don't need the liaOrig[0 .. $] in the foreach
statement; just the name of the array variable is required to
walk the entire array.
Hope this helps!
Derelict, SDL, and OpenGL3: Triangle Tribulations
So I decided to try some OGL3 stuff in D utilizing the Derelict
bindings and SDL. Creating an SDL-OGL window worked fine, but I'm
having trouble with doing the most basic thing of rendering a
triangle. I get the window just fine and the screen is being
properly cleared and buffered, but no triangle.
Code:
GLuint initVAO () {
// An array of 3 vectors which represents 3 vertices
static const GLfloat g_vertex_buffer_data[] = [
-1.0f, -1.0f, 0.0f,
1.0f, -1.0f, 0.0f,
0.0f, 1.0f, 0.0f,
];
// This will identify our vertex buffer
GLuint vertexbuffer;
// Generate 1 buffer, put the resulting identifier in
vertexbuffer
glGenBuffers(1, &vertexbuffer);
// The following commands will talk about our 'vertexbuffer'
buffer
glBindBuffer(GL_ARRAY_BUFFER, vertexbuffer);
// Give our vertices to OpenGL.
glBufferData(GL_ARRAY_BUFFER, g_vertex_buffer_data.length *
GL_FLOAT.sizeof, g_vertex_buffer_data.ptr, GL_STATIC_DRAW);
glEnableVertexAttribArray(0);
glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, 0, null);
glBindBuffer(GL_ARRAY_BUFFER, 0);
return vertexbuffer;
}
void main() {
string title = "Hello, world! With SDL2 OpenGL3.3!";
writefln(title);
// Create a new OGL Window
Window win = new SDL_OGL_Window(title);
GLuint vertexbuffer = initVAO();
// Main loop flag
bool quit = false;
//Event handler
SDL_Event e;
glClearColor(0,0,0.4,0);
do {
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
glBindVertexArray(vertexbuffer);
// Draw the triangle
glDrawArrays(GL_TRIANGLES, 0, 3);
glDisableVertexAttribArray(vertexbuffer);
glBindVertexArray(0);
SDL_GL_SwapWindow(win.window);
// Handle events on queue
while( SDL_PollEvent( &e ) != 0 ) {
//User requests quit
if( e.type == SDL_QUIT ) {
quit = true;
}
}
const Uint8* currentKeyStates = SDL_GetKeyboardState( null );
// Escape to quit as well.
if( currentKeyStates[ SDL_SCANCODE_ESCAPE ] ) {
quit = true;;
}
} while ( !quit );
glDeleteBuffers(1, &vertexbuffer);
}
The SDL_OGL_Window is an object that creates an SDL window and
binds a OpenGL context to it; I don't think it's relevant for
what's going on, but if anyone thinks it might be the culprit,
I'll post it.
So, any ideas what I'm doing wrong?
Re: Derelict, SDL, and OpenGL3: Triangle Tribulations
On Wednesday, 12 August 2015 at 05:26:33 UTC, JN wrote: You need a vertex and a fragment shader. You can't render anything in OGL3 without shaders. I thought that was the case, but the tutorial I was looking at didn't have any shaders at that point. I added a shader program. Also, you seem to be confusing Vertex Array Objects and Vertex Buffer Objects. You are creating a VBO and try to bind it as a VAO. You should put a glGenVertexArrays somewhere there. Aha! Yes, that's it, thanks! Once I understood the difference between VAO and VBOs, it was easy to fix. Thanks! On Wednesday, 12 August 2015 at 05:35:30 UTC, Mike Parker wrote: On Wednesday, 12 August 2015 at 03:32:47 UTC, DarthCthulhu wrote: So, any ideas what I'm doing wrong? Too much to list. I suggest you get going with a good tutorial. One of the best I've seen is by Anton Gerdelan [1]. The four basic tutorials he has on his site will be enough to get you up and running. He used to have a lot more there, but he's published them all in a book. Even though there are numerous free resources online, I think Anton's ebook is well worth the ~$9.00 you pay for it. His tutorials are quite detailed and do a lot more than showing you a bunch of code to copy and paste. Work your way through that book and you'll know your way around well enough to do what you need to do for any basic OpenGL renderer. On Wednesday, 12 August 2015 at 05:54:13 UTC, Mike Parker wrote: On Wednesday, 12 August 2015 at 05:35:30 UTC, Mike Parker wrote: One of the best I've seen is by Anton Gerdelan [1]. The four [1] http://antongerdelan.net/opengl/index.html Thanks very much for the resource! I had already looked at about a dozen different OGL3.x tutorials online, but this was the one which clicked for me. I'll definitely look into getting his book. Thanks again!
Theoretical Best Practices
This is more a theoretical exercise than specific code nitty
gritty, but...
Let's say I have some code like this:
class World {
// Bunch of members and other functions
void happyDay () {
if (bCthulhuRises) {
debug(logging) {
logger.writeLog(this); // uses the class toString to give a
dump of interesting parts of the object
}
throw new Exception("We're doomed! Run you fools!");
}
}
}
I only want to access the logger object when the program is
compiled with the -debug option, so I don't want to pass it along
to the object constructor or set a member as a reference to it
(which is both tedious and pointless if not in -debug mode). The
simple solution is to make the Logger class a singleton (can D do
singletons? I presume it's possible, but I haven't really looked
into it), but is there a means in D that is considered a better
way to do this?
Re: Theoretical Best Practices
On Friday, 14 August 2015 at 12:40:08 UTC, Steven Schveighoffer
wrote:
I would do it this way:
// at module level
debug(logging) {
Logger logger;
static this() { logger = new Logger;}
}
If you want to have the logger be global, add 'shared' to both
the logger and the static this.
This initializes the data before main() is run, so there is no
need for singletons.
The added bonus here is that you can't accidentally log stuff
when debug(logging) isn't enabled, as the variable will not
exist.
-Steve
Ahh, that is a much cleaner way to do it rather than using a
singleton.
By 'module level', I assume you mean in the module that defines
the Logger class? An 'import debug.logger' or somesuch would then
give all relevant modules access, correct?
Is the compiler smart enough to compile out all the symbols
associated with the logger if it is never instantiated?
Re: Theoretical Best Practices
On Friday, 14 August 2015 at 23:17:44 UTC, Tofu Ninja wrote: On Friday, 14 August 2015 at 22:25:15 UTC, DarthCthulhu wrote: Ahh, that is a much cleaner way to do it rather than using a singleton. By 'module level', I assume you mean in the module that defines the Logger class? An 'import debug.logger' or somesuch would then give all relevant modules access, correct? Is the compiler smart enough to compile out all the symbols associated with the logger if it is never instantiated? If you want to make 100% sure that the Logger code does not end up in the release version, you can just put the Logger class definition in that debug block as well. Well, it doesn't really matter much as a logger class wouldn't have very much in it anyway. But I am imagining some kind of uber-huge class might be used for some reason in other ways and it would be interesting to know if it would be cut out completely by the compiler or not. Also, am I the only one who is imagining that you are really the dog in your avatar. I am just imagining that there is a dog somewhere trying to learn D. WHO TOLD YOU!? Er, I mean, gee-whilikers, why would you think that? I am a perfectly normal human. Yessiree, human hands an evryting. no annoyingly fat paws that make it hard to type. Now if you'll excuse me, I have to go walkies.
Template Collections of Different Types
Say I want to do something like:
Propertery!int pi = 42;
PropertyCollection pc;
pc.attach("Life_and_Everything", pi);
assert(pc.Life_and_Everything == 42);
Property!string ps = "Hello World";
pc.attach("text", ps);
assert(pc.text == "Hello World");
How would one store the Property objects in the
PropertyCollection? You can't use something like an array because
the two Properties are of different types. Do you really need to
do something like make a member of PropertyCollection for every
type of Property you are interested in storing and using static
ifs to determine which variable it goes into?
I feel like there is an obvious solution here that I'm missing.
Re: Template Collections of Different Types
On Sunday, 16 August 2015 at 01:51:36 UTC, Adam D. Ruppe wrote: On Sunday, 16 August 2015 at 01:39:54 UTC, DarthCthulhu wrote: How would one store the Property objects in the PropertyCollection? You don't, not like that anyway. The attach call is the ruin of it. If it was all one definition, you could use something like std.typecons.Tuple, but multiple calls to attach need to be a runtime function, which means what you attach will lose the compile time type when you get it. I see. Yeah, I thought that might be the case. Nice to know I wasn't just being ignorant. That would work. You could write a plain struct definition and then the attach could be implemented as a allMembers/getMember assignment loop, similarly to this: http://stackoverflow.com/questions/31993705/d-call-a-function-using-a-string-variable-with-its-name/31996526#31996526 but looking at data member assignments instead of method calls. Oh, neat! Thanks! Incidentally, I watched your dconf2015 talk "Dynamic Types in D". That (along with Andrei's "Generic Programming Must Go") actually inspired me to think about this particular problem. It's very appropriate that you would have the solution, then!
Template Parameters in Struct Member Functions
I'm having difficulty understanding how templates operate as
function parameters.
Say I have this:
struct ArrayTest {
void arrayTest(T) (T arrayT) {
writeln(arrayT);
}
}
unittest {
ArrayTest test;
float farray[] = [
0.5f, 0.5f, 0.0f,
0.5f, -0.5f, 0.0f,
-0.5f, -0.5f, 0.0f,
-0.5f, 0.5f, 0.0f
];
test.arrayTest(farray);
}
Everything works peachy as expected. But as soon as I add another
parameter to the arrayTest function like so (and changing the
unit test to match):
void arrayTest(T, int passing) (T arrayT) { ... }
I get 'cannot deduce function from argument types' errors.
Specifically stating the type of the function doesn't seem to
help:
test.arrayTest(float [])(farray, 1);
There must be a way to mix template and non-template parameters,
right? What am I missing here?
In addition, as I understand it, one can restrict the type of
parameter a template can use. So if I only wanted arrays as the
function name indicates, I should be able to do this:
void arrayTest(T : T[]) (T arrayT) { ... }
But that also doesn't seem to work.
