BucketQueue

Gives back the smallest priority first, for whole-number priorities that move forward a little at a time, as in path-finding. Each entry is a priority and a u32 value, a whole number from 0 to 4,294,967,295, such as a cell id. A value outside that range wraps, and a SlotMap or SlotAllocator handle can be outside it, so push an index into your own array of handles.

The queue does not check its window. After each push, the highest priority in the queue must be less than Span above both the lowest priority in it and the last priority popped since it was last empty, or pops can come out in the wrong order with no error. Use MinHeap when that cannot be promised.

local Open = Collections.BucketQueue.new({ Span = 64 })
Open:Push(3, 30)
Open:Push(1, 10)
print(Open:Pop()) -- 1 10

Summary

Member	Description
.new()	Creates an empty queue.
:Push()	Adds Value at Priority.
:Pop()	Removes and returns the entry with the smallest priority.
:Count()	How many entries the queue holds.
:Clear()	Removes every entry.
BucketQueue	The type BucketQueue.new returns.
Config	Settings for BucketQueue.new.

Functions

new

function BucketQueue.new(Config: Config): BucketQueue

Creates an empty queue. It allocates memory in proportion to Span up front. Errors if Span is not a whole number of 1 or more, or PopOrder is not “fifo”, “lifo” or nil.

Methods

Push

function BucketQueue:Push(Priority: number, Value: number)

Adds Value at Priority. Afterwards the highest priority in the queue must be less than Span above both the lowest priority in it and the last priority popped since it was last empty. Raises and stores nothing when Priority is not a whole number or Value is not a number.

Pop

function BucketQueue:Pop(): (number?, number?)

Removes and returns the entry with the smallest priority.

Returns	Description
number?	the smallest priority, or nil when the queue is empty
number?	its value

Count

function BucketQueue:Count(): number

How many entries the queue holds.

Clear

function BucketQueue:Clear()

Removes every entry.

Types

BucketQueue

export type BucketQueue = {
	Pop: (self: BucketQueue) -> (number?, number?),
	Push: (self: BucketQueue, Priority: number, Value: number) -> (),
	Count: (self: BucketQueue) -> number,
	Clear: (self: BucketQueue) -> (),
}

The type BucketQueue.new returns.

Config

export type Config = {
	Span: number,
	InitialBucketCapacity: number?,
	PopOrder: "fifo" | "lifo" | nil,
}

Settings for BucketQueue.new.

Field	Type	Description
Span	number	how many priorities the window covers
InitialBucketCapacity	number?	entries per bucket to make room for up front, 8 by default
PopOrder	"fifo" | "lifo" | nil	which of equal priorities comes out first, “fifo” by default