Up

module Core_queue

: sig

A queue implemented with an array.

The implementation will grow the array as necessary. The array will never automatically be shrunk, but the size can be interrogated and set with capacity and set_capacity.

Iteration functions (iter, fold, map, concat_map, filter, filter_map, filter_inplace, and some functions from Container.S1) will raise if the queue is modified during iteration.

Differences from the standard module: enqueue replaces push and add, and takes the queue first. dequeue replaces pop and take, and returns an option rather than raising Empty. dequeue_exn is available if you want to raise Empty. iter and fold take labeled arguments. blit_transfer replaces transfer but is markedly different; see below.

#
type 'a t
include Container.S1 with type 'a t := 'a t
include Invariant.S1 with type 'a t := 'a t
include Binary_searchable.S1 with type 'a t := 'a t
#
val create : ?capacity:int -> unit -> _ t

Create an empty queue.

#
val singleton : 'a -> 'a t
#
val enqueue : 'a t -> 'a -> unit
#
val dequeue : 'a t -> 'a option
#
val dequeue_exn : 'a t -> 'a
#
val peek : 'a t -> 'a option
#
val peek_exn : 'a t -> 'a
#
val clear : _ t -> unit
#
val copy : 'a t -> 'a t
#
val blit_transfer : src:'a t -> dst:'a t -> ?len:int -> unit -> unit

Transfers up to len elements from the front of src to the end of dst, removing them from src. It is an error if len < 0.

Aside from a call to set_capacity dst if needed, runs in O(len) time

#
val of_list : 'a list -> 'a t

of_list list returns a queue t with the elements of list in the same order as the elements of list (i.e. the first element of t is the first element of the list).

#
val map : 'a t -> f:('a -> 'b) -> 'b t
#
val concat_map : 'a t -> f:('a -> 'b list) -> 'b t

creates a new queue with elements equal to List.concat_map ~f (to_list t).

#
val filter_map : 'a t -> f:('a -> 'b option) -> 'b t

filter_map creates a new queue with elements equal to List.filter_map ~f (to_list t).

#
val filter : 'a t -> f:('a -> bool) -> 'a t

filter is like filter_map, except with List.filter.

#
val filter_inplace : 'a t -> f:('a -> bool) -> unit

filter_inplace t ~f removes all elements of t that don't satisfy f. If f raises, t is unchanged. This is inplace in that it modifies t; however, it uses space linear in the final length of t.

#
val of_array : 'a array -> 'a t
#
val get : 'a t -> int -> 'a

get t i returns the i'th element in t, where the 0'th element is at the front of t and the length t - 1 element is at the back.

#
val set : 'a t -> int -> 'a -> unit
#
val capacity : _ t -> int

Returns the current length of the backing array.

#
val set_capacity : _ t -> int -> unit

set_capacity t capacity sets the capacity of t's backing array to at least max capacity (length t). If the capacity changes, then this involves allocating a new backing array and copying the queue elements over.

#
val t_of_sexp : (Sexplib.Sexp.t -> 'a) -> Sexplib.Sexp.t -> 'a t
#
val sexp_of_t : ('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t
#
val bin_t : 'a Bin_prot.Type_class.t -> 'a t Bin_prot.Type_class.t
#
val bin_read_t : 'a Bin_prot.Read.reader -> 'a t Bin_prot.Read.reader
#
val __bin_read_t__ : 'a Bin_prot.Read.reader -> (int -> 'a t) Bin_prot.Read.reader
#
val bin_reader_t : 'a Bin_prot.Type_class.reader -> 'a t Bin_prot.Type_class.reader
#
val bin_size_t : 'a Bin_prot.Size.sizer -> 'a t Bin_prot.Size.sizer
#
val bin_write_t : 'a Bin_prot.Write.writer -> 'a t Bin_prot.Write.writer
#
val bin_writer_t : 'a Bin_prot.Type_class.writer -> 'a t Bin_prot.Type_class.writer
end