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.

See Also

The Util Library