module Fdeque:sig
..end
Fqueue
.
Amortized running times assume that enqueue/dequeue are used sequentially, threading
the changing deque through the calls.
type 'a
t
include Container.S1
Container
operations traverse deque elements front-to-back, like Front_to_back
below. If you need faster traversal and don't care about the order, use
Arbitrary_order
below.
is_empty
and length
have worst-case complexity O(1).
include Invariant.S1
module Arbitrary_order:sig
..end
module Front_to_back:sig
..end
module Back_to_front:sig
..end
val empty : 'a t
val singleton : 'a -> 'a t
val of_list : 'a list -> 'a t
of_list
returns a deque with elements in the same front-to-back order as the
list.val rev : 'a t -> 'a t
rev t
returns t
, reversed.
Complexity: worst-case O(1)
val enqueue : 'a t -> [ `back | `front ] -> 'a -> 'a t
enqueue t side x
produces t
updated with x
added to its side
.
Complexity: worst-case O(1).
val enqueue_front : 'a t -> 'a -> 'a t
val enqueue_back : 'a t -> 'a -> 'a t
val peek : 'a t -> [ `back | `front ] -> 'a option
peek t side
produces Some
of the element at the side
of t
, or None
if t
is
empty.
Complexity: worst-case O(1).
val peek_exn : 'a t -> [ `back | `front ] -> 'a
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 drop : 'a t -> [ `back | `front ] -> 'a t option
drop t side
produces Some
of t
with the element at its side
removed, or
None
if t
is empty.
Complexity: amortized O(1), worst-case O(length t).
val drop_exn : 'a t -> [ `back | `front ] -> 'a t
val drop_front : 'a t -> 'a t option
val drop_front_exn : 'a t -> 'a t
val drop_back : 'a t -> 'a t option
val drop_back_exn : 'a t -> 'a t
val dequeue : 'a t -> [ `back | `front ] -> ('a * 'a t) option
dequeue t side
produces Option.both (peek t side) (drop t side)
.
Complexity: amortized O(1), worst-case O(length t).
val dequeue_exn : 'a t -> [ `back | `front ] -> 'a * 'a t
val dequeue_front : 'a t -> ('a * 'a t) option
val dequeue_front_exn : 'a t -> 'a * 'a t
val dequeue_back : 'a t -> ('a * 'a t) option
val dequeue_back_exn : 'a t -> 'a * 'a t
module Stable:sig
..end
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 compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
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
Container
operations traverse deque elements front-to-back, like Front_to_back
below. If you need faster traversal and don't care about the order, use
Arbitrary_order
below.
is_empty
and length
have worst-case complexity O(1).
Traverse deque elements in arbitrary order.
Traverse deque elements front-to-back. Incurs up to O(n) additional time and space
cost over Arbitrary_order
.
Traverse deque elements back-to-front. Incurs up to O(n) additional time and space
cost over Arbitrary_order
.
The empty deque.
A one-element deque.
of_list
returns a deque with elements in the same front-to-back order as the
list.
rev t
returns t
, reversed.
Complexity: worst-case O(1)
enqueue t side x
produces t
updated with x
added to its side
.
Complexity: worst-case O(1).
peek t side
produces Some
of the element at the side
of t
, or None
if t
is
empty.
Complexity: worst-case O(1).
drop t side
produces Some
of t
with the element at its side
removed, or
None
if t
is empty.
Complexity: amortized O(1), worst-case O(length t).
dequeue t side
produces Option.both (peek t side) (drop t side)
.
Complexity: amortized O(1), worst-case O(length t).