Module PriorityQueue


module PriorityQueue: sig .. end
Priority queues.

The PriorityQueue module provides a polymorphic and a functorial interface to an imperative priority queue data structure. A queue is implemented by embeddeding a heap in a resizable array.

The polymorphic interface requires that the elements in a priority queue are distinct w.r.t. (=). The functorial interface requires that the elements in a priority queue are distinct w.r.t. the equal function in their HashedType module. Otherwise the functions based on element values (mem, remove, reorder_up, and reorder_down) may not work correctly.


type 'a order = 'a -> 'a -> bool 
The type of priority orders on 'a. A priority order ord is a non-strict total order where ord a b = true means that the priority of b is not higher than the priority of a. When the priority of an element changes, the queue must be notified using the reorder_up or reorder_down function.
type 'a t 
The type of priority queues with element type 'a.
val make : 'a order -> 'a t
make ord creates a new priority queue with order ord.
val length : 'a t -> int
Returns the number of elements in a queue.
val is_empty : 'a t -> bool
Tests whether a queue is empty.
val add : 'a t -> 'a -> unit
Adds an elements to the queue.
val mem : 'a t -> 'a -> bool
Tests whether a queue contains a given element.
val first : 'a t -> 'a
first q returns an element with maximal priority contained in the queue q.
Raises Failure if q is empty.
val remove_first : 'a t -> unit
remove_first q removes the element returned by first q from the queue q.
Raises Failure if q is empty.
val remove : 'a t -> 'a -> unit
remove q x removes the element x from the queue q. If q does not contain the element x, the function does nothing.
val clear : 'a t -> unit
Removes all elements from a queue.
val reorder_up : 'a t -> 'a -> unit
reorder_up q x notifies the queue q that the priority of the element x has increased. If q does not contain x, the function does nothing.
val reorder_down : 'a t -> 'a -> unit
reorder_down q x notifies the queue q that the priority of the element x has decreased. If q does not contain x, the function does nothing.
module type HashedType = sig .. end
Input signature of the functor PriorityQueue.Make.
module type S = sig .. end
Output signature of the functor PriorityQueue.Make.
module Make: 
functor (H : HashedType) -> S with type elt = H.t