Skip to content

Instantly share code, notes, and snippets.

@martinwells
Created July 26, 2013 18:49
Show Gist options
  • Save martinwells/6091295 to your computer and use it in GitHub Desktop.
Save martinwells/6091295 to your computer and use it in GitHub Desktop.
PrioritizedQueue class
import haxe.ds.ObjectMap;
/*
Simple prioritized queue. Throw objects at it and you'll always get back things according
to a priority you set. Priorities are retained internally, so you don't need to modify your
objects.
Usage:
// create a queue:
var q = new PrioritizedQueue();
// add three things to the queue
q.enqueue(100, 'first');
q.enqueue(-5, { test: 23 } );
q.enqueue(20, 'third');
// grab next items off the queue
assertTrue(q.dequeue() == 'first');
var obj:Dynamic = q.dequeue();
assertTrue(obj.test == 23);
assertTrue(q.dequeue() == 'third');
*/
class PrioritizedQueue
{
private var objects:Array<{}>;
// we remember priorities in a separate map for resorting
private var priorities:ObjectMap<{}, Int>;
public function new()
{
init();
}
public function init()
{
objects = new Array();
priorities = new ObjectMap<{}, Int>();
}
// Add an object onto the queue
public function enqueue(priority:Int, object:{})
{
objects.push(object);
priorities.set(object, priority);
sort();
}
// Resort the array according to the object priorities
public function sort()
{
objects.sort(function(a:{}, b:{}):Int { return priorities.get(a) - priorities.get(b); });
}
// Get the next prioritized item off the queue (removes it)
public function dequeue()
{
var first = objects.shift();
priorities.remove(first); // remove the corresponding meta data
return first;
}
public function length()
{
return objects.length;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment