Module Std_kernel.Fdeque

module Fdeque: Fdeque

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
Traverse deque elements in arbitrary order.
module Front_to_back: sig .. end
Traverse deque elements front-to-back.
module Back_to_front: sig .. end
Traverse deque elements back-to-front.
val empty : 'a t
The empty deque.
val singleton : 'a -> 'a t
A one-element deque.
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).