Функтор Pqueue.MakeMin

module MakeMin: functor (E : OrderedType) -> Min  with type elt := E.t

Функтор, создающий реализацию структуры очереди с минимальным приоритетом для элементов заданного типа с полным порядком.

Параметры:

E : OrderedType

Очереди с минимальным приоритетом

type t

Тип очередей с приоритетом.

type elt

Тип элементов очереди с приоритетом.

val create : unit -> t

Возвращает новую, изначально пустую очередь с приоритетом.

val length : t -> int

Возвращает количество элементов в очереди с приоритетом.

val is_empty : t -> bool

is_empty q является true тогда и только тогда, когда q пуста, то есть тогда и только тогда, когда length q = 0.

val add : t -> elt -> unit

add q x добавляет элемент x в очередь с приоритетом q.

val add_iter : t -> ((elt -> unit) -> 'x -> unit) -> 'x -> unit

add_iter q iter x добавляет каждый элемент x в конец q. Это iter (add q) x.

val min_elt : t -> elt option

min_elt q — это элемент q с минимальным приоритетом или None, если очередь пуста. Очередь не изменяется.

val get_min_elt : t -> elt

get_min_elt q возвращает элемент q с минимальным приоритетом или вызывает исключение Invalid_argument, если очередь пуста. Очередь не изменяется.

val pop_min : t -> elt option

pop_min q удаляет из очереди q и возвращает элемент с минимальным приоритетом или возвращает None, если очередь пуста.

val remove_min : t -> unit

remove_min q удаляет из очереди q элемент с минимальным приоритетом. Ничего не происходит, если q пуста.

val clear : t -> unit

clear q удаляет все элементы из q.

val copy : t -> t

copy q — это новая очередь с приоритетом, содержащая те же элементы, что и q.

Преобразование из других структур данных

val of_array : elt array -> t

of_array a возвращает новую очередь с приоритетом, содержащую элементы массива a. Выполняется за линейное время.

val of_list : elt list -> t

of_list l возвращает новую очередь с приоритетом, содержащую элементы списка l. Выполняется за линейное время.

val of_iter : ((elt -> unit) -> 'x -> unit) -> 'x -> t

of_iter iter x возвращает новую очередь с приоритетом, содержащую элементы x, полученные из iter.

Например, of_iter Seq.iter s возвращает новую очередь с приоритетом, содержащую все элементы последовательности s (при условии, что она конечна).

Выполняется за линейное время (не считая времени, затраченного на iter).

Итерация

Порядок обхода элементов очереди с приоритетом не определён.

Изменение очереди с приоритетом (добавление или удаление элементов) во время её обхода является ошибкой программирования. Такая ошибка может быть обнаружена и сигнализирована реализацией динамического массива, используемого для хранения очереди, но это не гарантируется.

val iter_unordered : (elt -> unit) -> t -> unit

iter_unordered f q применяет f ко всем элементам в q. Порядок передачи элементов в f не определён.

Поведение не определено, если очередь с приоритетом изменяется с помощью f во время обхода.

val fold_unordered : ('acc -> elt -> 'acc) -> 'acc -> t -> 'acc

fold_unordered f accu q — это (f (... (f (f accu x1) x2) ...) xn), где x1,x2,...,xn — элементы q. Порядок передачи элементов в f не определён.

Поведение не определено, если очередь с приоритетом изменяется с помощью f во время обхода.