package ocaml-compiler

  1. Overview
  2. Docs
package ocaml-compiler
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module Pqueue.MakeMinSource

Functor building an implementation of the min-priority queue structure given a totally ordered type for elements.

Parameters

module E : OrderedType

Signature

Min-priority queues

Sourcetype t

The type of priority queues.

Sourceval create : unit -> t

Return a new priority queue, initially empty.

Sourceval length : t -> int

Return the number of elements in a priority queue.

Sourceval is_empty : t -> bool

is_empty q is true iff q is empty, that is, iff length q = 0.

Sourceval add : t -> E.t -> unit

add q x adds the element x in the priority queue q.

Sourceval add_iter : t -> ((E.t -> unit) -> 'x -> unit) -> 'x -> unit

add_iter q iter x adds each element of x to the end of q. This is iter (add q) x.

Sourceval min_elt : t -> E.t option

min_elt q is an element of q with minimal priority or None if the queue is empty. The queue is not modified.

Sourceval get_min_elt : t -> E.t

get_min_elt q returns an element of q with minimal priority, or raises Stdlib.Invalid_argument if the queue is empty. The queue is not modified.

Sourceval pop_min : t -> E.t option

pop_min q removes and returns an element in queue q with minimal priority, or returns None if the queue is empty.

Sourceval remove_min : t -> unit

remove_min q removes an element in queue q with minimal priority. It does nothing if q is empty.

Sourceval clear : t -> unit

clear q removes all elements from q.

Sourceval copy : t -> t

copy q is a new priority queue with the same elements q has.

Conversions from other data structures

Sourceval of_array : E.t array -> t

of_array a returns a new priority queue containing the elements of array a. Runs in linear time.

Sourceval of_list : E.t list -> t

of_list l returns a new priority queue containing the elements of list l. Runs in linear time.

Sourceval of_iter : ((E.t -> unit) -> 'x -> unit) -> 'x -> t

of_iter iter x returns a new priority queue containing the elements of x, obtained from iter.

For example, of_iter Seq.iter s returns a new priority queue containing all the elements of the sequence s (provided it is finite).

Runs in linear time (excluding the time spent in iter).

Iteration

The order in which the elements of a priority queue are traversed is unspecified.

It is a programming error to mutate a priority queue (by adding or removing elements) during an iteration of the queue. Such an error may be detected and signaled by the backing dynamic array implementation, but this is not guaranteed.

Sourceval iter_unordered : (E.t -> unit) -> t -> unit

iter_unordered f q applies f to all elements in q. The order in which the elements are passed to f is unspecified.

The behavior is not specified if the priority queue is modified by f during the iteration.

Sourceval fold_unordered : ('acc -> E.t -> 'acc) -> 'acc -> t -> 'acc

fold_unordered f accu q is (f (... (f (f accu x1) x2) ...) xn) where x1,x2,...,xn are the elements of q. The order in which the elements are passed to f is unspecified.

The behavior is not specified if the priority queue is modified by f during the iteration.