Using the FastPriorityQueue

FastPriorityQueue is designed to be as fast as possible, especially for pathfinding, at the cost of convenience and safety.

• If you're just looking for a plain ol' priority queue, use SimplePriorityQueue
• For a version of FastPriorityQueue that has stable dequeuing, use StablePriorityQueue.

---

In order to use FastPriorityQueue, the class you want to enqueue must extend the FastPriorityQueueNode class (Why?).

//Example of how to create a priority queue node class
public class MyNode : FastPriorityQueueNode
{
     //Put custom properties here
}

To actually create the priority queue, you need to pass the max queue-size to its constructor.

FastPriorityQueue<MyNode> queue = new FastPriorityQueue<MyNode>(MAX_SIZE);

This is the maximum number of nodes you will ever enqueue. For speed purposes, the queue does not attempt to resize itself; enqueuing more than the max number of nodes will cause undefined behavior.

Note that it is recommended - though not required - that you access the queue through its concrete type, FastPriorityQueue, rather than its interface IPriorityQueue, because the JIT can theoretically optimize method calls on concrete types better.

After that, calls to Enqueue(), Dequeue(), Contains() etc. are straight-forward.

MyNode myNode = new MyNode();
float priority = 10;
queue.Enqueue(myNode, priority);
//Later ...
MyNode nextNode = queue.Dequeue();

If you need to update the priority of a node, call queue.UpdatePriority(node, priority). Remember, do not alter any of the properties from the FastPriorityQueueNode base-class yourself!

queue.UpdatePriority(nodeAlreadyInQueue, 100);

Warning!

Be careful not to call UpdatePriority() on nodes that aren't in the priority queue, or to call Enqueue() on nodes that are.

Also note that the priority queue is not thread safe.

Make sure not to add the same node to two different priority queues at once. If you want to enqueue a node that once belonged to one queue into a different queue, you must call oldQueue.ResetNode(node) first, after it's been removed.

The priority queue runs much slower in DEBUG builds, due to safety checks to save you from shooting yourself in the foot. For maximum speed, these safety checks do not exist in the RELEASE build. If you are encountering a bug related to the priority queue, try running the debug build (not available over NuGet).

---

Here is a fully working minimal example

using System;
using Priority_Queue;

namespace Priority_Queue_Example
{
    public static class FastPriorityQueueExample
    {
        //The class to be enqueued.
        public class User : FastPriorityQueueNode
        {
            public string Name { get; private set; }
            public User(string name)
            {
                Name = name;
            }
        }

        private const int MAX_USERS_IN_QUEUE = 10;

        public static void RunExample()
        {
            //First, we create the priority queue.  We'll specify a max of 10 users in the queue
            FastPriorityQueue<User> priorityQueue = new FastPriorityQueue<User>(MAX_USERS_IN_QUEUE);

            //Next, we'll create 5 users to enqueue
            User user1 = new User("1 - Jason");
            User user2 = new User("2 - Tyler");
            User user3 = new User("3 - Valerie");
            User user4 = new User("4 - Joseph");
            User user42 = new User("4 - Ryan");

            //Now, let's add them all to the queue (in some arbitrary order)!
            priorityQueue.Enqueue(user4, 4);
            priorityQueue.Enqueue(user2, 0); //Note: Priority = 0 right now!
            priorityQueue.Enqueue(user1, 1);
            priorityQueue.Enqueue(user42, 4);
            priorityQueue.Enqueue(user3, 3);

            //Change user2's priority to 2.  
            //Since user2 is already in the priority queue, we call UpdatePriority() to do this
            priorityQueue.UpdatePriority(user2, 2);

            //Finally, we'll dequeue all the users and print out their names
            while(priorityQueue.Count != 0)
            {
                User nextUser = priorityQueue.Dequeue();
                Console.WriteLine(nextUser.Name);
            }

            //Output:
            //1 - Jason
            //2 - Tyler
            //3 - Valerie
            //4 - Joseph
            //4 - Ryan

            //Notice that when two users with the same priority were enqueued
            //they were dequeued in the same order that they were enqueued.
        }
    }
}