ZSNES board

May as well throw out some data structure prOn for everyone. This paper was published in 2005.

Ladder Queues

Also, blargg's code had a nice optimization that replaced swaps in the enqueue() and deqeue() methods with a single assignment. This would cut the number of memory accesses in half. I don't see how that's possible, but I only had a cursory glance. I'll go look again. I have some comments in the cod...

Bah, screw that. I'll just use a normalize function instead. Call it once a second or so. void normalize() { for(unsigned i = 0; i < heapsize; i++) heap[i].counter -= counter; counter = 0; } Wait, do not be so unidealistic! That normalizing is just plainly ugly. Why not inline the function blargg p...

Here's a version using an array-based heap, absolute times, and no need to periodically adjust them, as overflow doesn't cause any problems. Full code + exerciser: Delta_Queue_2.cpp I threw together a C implementation of the linked-list and heap-based versions. The heap does not coalesce events by ...

sinamas, if you keep track of the absolute time of the last event, inserting an event past all the others can done in constant time. True, but we still get linear complexity on average if the common case position is before the end and has a mean proportional to N. I have to agree with sinamas here....

lscharen, thank you very much for the example code. Not following what you mean by "amortization pool credits", but I get the general idea of your code. The part I missed was that you don't have to recompute all elements after your insertion part, just one. Yes, I was trying to get across...

Background info: There's probably no more than ~10 events: DRAM refresh, DMA trigger, HDMA trigger, HDMA init trigger, NMI trigger, IRQ trigger, ALU step, Joypad poll step, etc. They don't stack, so we can make our queue a fixed size, no need for a resizable vector. The only way I can think to impl...