Priority Queue

Priority queues can be used for various tasks, such as for pathfinding (in Dijkstra-like algorithms) or simple decision making (which action to perform next). This implementation aims to be sufficiently fast for such tasks without compromising in useful functionality.

TIP: For heavy tasks, uncomment the line loading test_perf.lua from init.lua and run init.lua from the command line, preferably with LuaJIT, to check whether the mod performs with adequate speed.

API: 🔗

priority_queue:new(type) 🔗

Returns a priority queue of a specified type:

• 0: smaller priorities are more important
• 1: larger priorities are more important
• 2: simple version of 0
• 3: simple version of 1

If type is not specified, it defaults to 0.

The behaviour of simple versions is explained below, at the end of the section.

TIP: Internally, types 1 and 3 are using types 0 and 2 as a base and wrapping some of their functions to negate priorities. Because of this, it is slighly faster to call the methods of type 0 and 2 queues with -priority as an argument instead of calling the methods of types 1 and 3 with priority. However, in practice the difference in negligible.

instance:insert(value, priority) 🔗

Inserts a value into the queue with the given priority. If the value already exists, its priority is updated instead.

Returns:

• true if the value is new
• false if the value already exists

instance:extract() 🔗

Returns the value and priority of the most important element, in that order, removing the element from the queue. If the queue is empty, nil is returned instead.

instance:peek() 🔗

Acts like extract(), with the distinction that the element is not removed.

instance:search(value) 🔗

Tests whether the queue contains an element with the given value. If yes, returns true; otherwise returns false.

instance:delete(value) 🔗

Removes the element with the given value. Returns true on success, and false if the queue does not contain the given value.

instance:clear() 🔗

Removes all stored elements from the queue.

instance:size() 🔗

Returns the number of elements stored in the queue.

TIP: To avoid the overhead of a function call, it is possible to get the size by simply reading instance._size. However, be careful to never write to it manually.

Simple versions 🔗

The implementation of the default queues comes with some helpful features, such as the ability to update priorities, and the option to remove arbitrary elements after insertion. Such features, however, come with a small performance overhead, which might prove to be a nuisance. For those situations, it is possible to opt out from the more advanced features for performance gains by using the simple versions of the queues. These versions function like their default counterparts, excluding the exceptions listed below:

• insert() allows duplicates and will not update priorities.
• delete() and search() methods are disabled.

TIP: For reference, the simple versions seem to be about 13% faster.

Examples 🔗

Basic usage 🔗

local min_queue = priority_queue:new(0)

min_queue:insert("A", 2)
min_queue:insert("B", 1)
min_queue:insert("C", 3)

local value, priority = min_queue:extract()
print(value) -- prints "B"