module Dequeue:sig
..end
An index is assigned to an element when it enters the queue, and the index of an element is static (i.e. an index refers to a distinct element until that element is removed from the queue, no matter how many intervening push/pop operations occur).
One consequence of this is that the minimum index may be < 0.
The "front" is the smallest valid index, while the "back" is the largest.
All operations are amortized O(1) with a small constant.
type 'a
t
include Binary_searchable.S1
include Container.S1
val create : ?initial_length:int -> ?never_shrink:bool -> unit -> 'a t
create ?initial_length ?never_shrink ()
create a new t
. initial_length
is the
initial length of the dequeue; it will be able to hold initial_length
elements
without resizing. It must be positive. If never_shrink
is true, the physical array
will never shrink; only expand. If initial_length
is given without never_shrink
then never_shrink
is presumed to be true
, otherwise never_shrink
defaults to
false
.val front_index : 'a t -> int option
front_index t
return the index of the front item in t
.val front_index_exn : 'a t -> int
front_index_exn t
throws an exception if t
is empty, otherwise returns the index
of the front item in t
val back_index : 'a t -> int option
back_index t
return the index of the back item in t
.val back_index_exn : 'a t -> int
back_index_exn t
throws an exception if t
is empty, otherwise returns the index
of the back item in t
val get_opt : 'a t -> int -> 'a option
get_opt t i
return the element at index i
. Return None
if i
is invalid.val get : 'a t -> int -> 'a
get t i
return the element at index i
. Raise an exception if i
is
invalid.val peek : 'a t -> [ `back | `front ] -> 'a option
peek t back_or_front
return the value at the back or front of the dequeue without
removing it.val peek_front : 'a t -> 'a option
val peek_front_exn : 'a t -> 'a
val peek_back : 'a t -> 'a option
val peek_back_exn : 'a t -> 'a
val set_exn : 'a t -> int -> 'a -> unit
set_exn t i v
mutate the element at i
.val iter' : 'a t -> [ `back_to_front | `front_to_back ] -> f:('a -> unit) -> unit
iter' t ~f
iter over the elements of t
.val iteri : 'a t -> f:(int -> 'a -> unit) -> unit
iteri t ~f
iter over the elements of t `front_to_back
passing in the index.val iteri' : 'a t ->
[ `back_to_front | `front_to_back ] -> f:(int -> 'a -> unit) -> unit
iteri' t ~f
as iter
, but also passes in the index of the current element.val fold' : 'a t ->
[ `back_to_front | `front_to_back ] -> init:'b -> f:('b -> 'a -> 'b) -> 'b
fold' t ~init ~f
fold over the elements of t
val foldi : 'a t -> init:'b -> f:(int -> 'b -> 'a -> 'b) -> 'b
foldi t ~init ~f
as fold
, but also passes in the index of the current element.val foldi' : 'a t ->
[ `back_to_front | `front_to_back ] ->
init:'b -> f:(int -> 'b -> 'a -> 'b) -> 'b
foldi' t ~init ~f
as fold'
, but also passes in the index of the current element to
f
.val enqueue : 'a t -> [ `back | `front ] -> 'a -> unit
enqueue t back_or_front v
push v
onto the back_or_front
of t
.val enqueue_front : 'a t -> 'a -> unit
val enqueue_back : 'a t -> 'a -> unit
val clear : 'a t -> unit
clear t
removes all elements from t
.val drop : ?n:int -> 'a t -> [ `back | `front ] -> unit
drop ?n t back_or_front
drop n
elements (default 1) from the back_or_front
of
t
. If t
has fewer than n
elements then it is cleared.val drop_front : ?n:int -> 'a t -> unit
val drop_back : ?n:int -> 'a t -> unit
val dequeue : 'a t -> [ `back | `front ] -> 'a option
dequeue t back_or_front
remove and return the back_or_front
of t
val dequeue_exn : 'a t -> [ `back | `front ] -> 'a
val dequeue_front : 'a t -> 'a option
val dequeue_front_exn : 'a t -> 'a
val dequeue_back : 'a t -> 'a option
val dequeue_back_exn : 'a t -> 'a
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
create ?initial_length ?never_shrink ()
create a new t
. initial_length
is the
initial length of the dequeue; it will be able to hold initial_length
elements
without resizing. It must be positive. If never_shrink
is true, the physical array
will never shrink; only expand. If initial_length
is given without never_shrink
then never_shrink
is presumed to be true
, otherwise never_shrink
defaults to
false
.front_index t
return the index of the front item in t
.front_index_exn t
throws an exception if t
is empty, otherwise returns the index
of the front item in t
back_index t
return the index of the back item in t
.back_index_exn t
throws an exception if t
is empty, otherwise returns the index
of the back item in t
get_opt t i
return the element at index i
. Return None
if i
is invalid.get t i
return the element at index i
. Raise an exception if i
is
invalid.peek t back_or_front
return the value at the back or front of the dequeue without
removing it.set_exn t i v
mutate the element at i
.iter' t ~f
iter over the elements of t
.iteri t ~f
iter over the elements of t `front_to_back
passing in the index.iteri' t ~f
as iter
, but also passes in the index of the current element.fold' t ~init ~f
fold over the elements of t
foldi t ~init ~f
as fold
, but also passes in the index of the current element.foldi' t ~init ~f
as fold'
, but also passes in the index of the current element to
f
.enqueue t back_or_front v
push v
onto the back_or_front
of t
.clear t
removes all elements from t
.drop ?n t back_or_front
drop n
elements (default 1) from the back_or_front
of
t
. If t
has fewer than n
elements then it is cleared.dequeue t back_or_front
remove and return the back_or_front
of t