Module IntPQueue.Plain

This is a priority queue whose keys are low nonnegative integers.

This queue is optimized for throughput, that is, speed. When an element is extracted out of the queue, the queue may retain a pointer to this element. This creates a memory leak: that is, the existence of this pointer can prevent the garbage collector from freeing this element. In practice, we do not expect this to be a problem, especially in scenarios where the queue itself is not long-lived.

type priority = int

A priority is a nonnegative integer.

type 'a t

A priority queue is an abstract mutable data structure. It can be thought of as a bag of elements, where each element carries a certain priority.

val create : unit -> 'a t

create() creates an empty priority queue.

Time complexity: O(1).

val add : 'a t -> 'a -> priority -> unit

add q x i inserts the element x with priority i into the queue q.

Time complexity: O(1) (amortized).

val extract : 'a t -> 'a option

extract q extracts an element out of the queue q and returns it. This element has minimum priority among all of the elements that are currently present in the queue. If the queue is empty, None is returned.

Time complexity: O(p). If the queue is used in a monotonic manner (that is, if the priority that is used in every call to add is at least as high as the priority of the last element that was returned by extract) then the time complexity of n calls to extract is only O(n+p). Indeed, in this monotonic scenario, the cost of scanning the queue's main array, so as to find the next element with minimum priority, is shared between all invocations of extract.

val extract' : 'a t -> ('a * priority) option

extract' q extracts an element out of the queue q and returns a pair of this element and its priority. This element has minimum priority among all of the elements that are currently present in the queue. If the queue is empty, None is returned.

Time complexity: see extract.

val is_empty : 'a t -> bool

is_empty q tests whether the queue q is empty.

Time complexity: O(1).

val cardinal : 'a t -> int

cardinal q returns the number of elements in the queue q.

Time complexity: O(1).

val repeat : 'a t -> ('a -> unit) -> unit

repeat q f repeatedly extracts an element with minimum priority out of q and passes it to f (which may insert new elements into q), until q is exhausted.

Time complexity: the total cost of n calls to extract and n invocations of the function f.

val reset : 'a t -> unit

reset q empties the queue q, freeing up the space that the queue occupies in memory. The queue q becomes identical to a queue that has just been created by create.

Time complexity: O(1).