Up  

Module type Cf_heap.T

module type T = sig .. end

This module defines the common interface to functional heaps in the Cf library.

type t

The heap type

module Element: sig .. end

A module defining the type of the element.

val nil : t

The empty heap.

val empty : t -> bool

Use empty h to test whether the heap h is empty.

val size : t -> int

Use size h to count the number of elements in the heap h. Runs in O(n) time and O(log N) space.

val head : t -> Element.t

Use head h to obtain the element on the top of the heap h. Raises Not_found if the heap is empty.

val tail : t -> t

Use tail h to obtain the heap produced by discarding the element on the top of heap h. If h is the empty heap, then the empty heap is returned.

val pop : t -> (Element.t * t) option

Use pop h to obtain the head and the tail of a heap h in one operation. Returns None if the h is empty.

val put : Element.t -> t -> t

Use put e h to obtain a new heap that is the result of inserting the element e into the heap h.

val merge : t -> t -> t

Use merge h1 h2 to obtain a new heap that is the result of merging all the elements of h1 and h2 into a single heap.

val iterate : (Element.t -> unit) -> t -> unit

Use iterate f h to apply f to every element in the heap h in an arbitrary order (not top to bottom). Runs in O(n) time and O(1) space.

val predicate : (Element.t -> bool) -> t -> bool

Use predicate f h to test whether all the elements in heap h satisfy the predicate function f. Runs in O(n) time (with a short cut when an element is found to fail the predicate) and O(1) space. Visits the elements in the heap in arbitrary order (not top to bottom).

val fold : ('b -> Element.t -> 'b) -> 'b -> t -> 'b

Use fold f s h to produce the result of folding a value s into the elements of heap h with the folding function f in an arbitrary order (not top to bottom). Runs in O(n) time and O(1) space.

val filter : (Element.t -> bool) -> t -> t

Use filter f h to apply f to each element in the heap h in an arbitrary order (not to top bottom), and produce a new heap that contains only those elements for which f pair returned true.

val partition : (Element.t -> bool) -> t -> t * t

Use partition f h to obtain a pair of new heaps that are the result of applying the partitioning function f to each element in the heap h in an arbitrary order (not top to bottom). The first heap returned will contain all the elements for which f pair returned true, and the second heap will return all the remaining elements.

val of_seq : Element.t Cf_seq.t -> t

Use of_seq z to construct a heap from a sequence of elements. Evaluates the whole sequence. Runs in O(n) time and O(1) space.

val of_list : Element.t list -> t

Use of_list s to construct a heap from a list of elements. Runs in O(n) time and O(1) space.

val to_seq : t -> Element.t Cf_seq.t

Use to_seq h to produce a sequence of elements in top to bottom order from the heap h.

val to_seq2 : t -> (Element.t * t) Cf_seq.t

Use to_seq2 h to produce a sequence of elements from the heap h where the first element of each pair is a key-value pair obtained from the head of the heap, and the second element of the pair is the corresponding tail of the heap.