PrioritizedQueue class

gistfile1.hx

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;
	}

}