The MONO_PRIORITYQ signature

The LeftPriorityQFn functor provides a functional implementation of priority queues using leaftist heaps.

Synopsis

signature PRIORITY
signature MONO_PRIORITYQ
functor LeftPriorityQFn (P : PRIORITY) : MONO_PRIORITYQ

Functor Argument Interface

type priority
val compare : (priority * priority) -> order

type item
val priority : item -> priority

Functor Argument Description

type priority: The abstract type of priority values.
val compare : (priority * priority) -> order: compare (pri1, pri2) returns the order of the two priority values.
type item: The type of items in the priority queue.
val priority : item -> priority: priority item returns the priority value for item.

Interface

type item
type queue

val empty : queue

val singleton : item -> queue

val fromList : item list -> queue

val insert : (item * queue) -> queue

val remove : queue -> (item * queue)

val next : queue -> (item * queue) option

val findAndRemove : queue * (item -> bool) -> (item * queue) option

val delete : queue * (item -> bool) -> queue

val merge : (queue * queue) -> queue

val numItems : queue -> int

val isEmpty : queue -> bool

Interface Description

type item: The type of items in the priority queue.
type queue: The priority queue type.
val empty : queue: The empty priority queue.
val singleton : item -> queue: singleton item returns a queue containing just item.
val fromList : item list -> queue: fromList items returns a queue containing the items.
val insert : (item * queue) -> queue: insert (pq, item) returns the queue that is pq with item added.
val remove : queue -> (item * queue): remove pq returns (item, pq'), where item is the highest priority item in pq and pq' is the result of removing item from pq. This function raises the Empty exception when pq is empty.
val next : queue -> (item * queue) option: remove pq returns SOME(item, pq'), where item is the highest priority item in pq and pq' is the result of removing item from pq. If pq is empty, then NONE is returned.
val findAndRemove : queue * (item → bool) → (item * queue) option: findAndRemove (pq, pred) returns SOME(item, pq'), where item is the highest priority item in pq such that pred item returns true, and and pq' is the result of removing item from pq. If no such item exists, then NONE is returned.
val delete : queue * (item → bool) → queue: delete (pq, pred) deletes any item in pq that satisfies the predicate and returns the resulting queue.
val merge : (queue * queue) -> queue: merge (pq1, pq2) returns the priority queue formed by merging the items in the two queues.
val numItems : queue -> int: numItems pq returns the number of items in pq.
val isEmpty : queue -> bool: isEmpty pq returns true if, and only if, pq is empty.

Synopsis

Functor Argument Interface

Functor Argument Description

Interface

Interface Description

See Also