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.