package core

  1. Overview
  2. Docs
package core
Legend:
Library
Module
Module type
Parameter
Class
Class type

A simple polymorphic functional double-ended queue. Use this if you need a queue-like data structure that provides enqueue and dequeue accessors on both ends. For strictly first-in, first-out access, see Fqueue.

Amortized running times assume that enqueue/dequeue are used sequentially, threading the changing deque through the calls.

type 'a t
include Bin_prot.Binable.S1 with type 'a t := 'a t
val bin_shape_t : Bin_prot.Shape.t -> Bin_prot.Shape.t
val bin_size_t : ('a, 'a t) Bin_prot.Size.sizer1
val bin_write_t : ('a, 'a t) Bin_prot.Write.writer1
val bin_read_t : ('a, 'a t) Bin_prot.Read.reader1
val __bin_read_t__ : ('a, int -> 'a t) Bin_prot.Read.reader1
val bin_writer_t : ('a, 'a t) Bin_prot.Type_class.S1.writer
val bin_reader_t : ('a, 'a t) Bin_prot.Type_class.S1.reader
val bin_t : ('a, 'a t) Bin_prot.Type_class.S1.t
include Ppx_compare_lib.Comparable.S1 with type 'a t := 'a t
val compare : 'a Base__Ppx_compare_lib.compare -> 'a t Base__Ppx_compare_lib.compare
include Ppx_compare_lib.Equal.S1 with type 'a t := 'a t
val equal : 'a Base__Ppx_compare_lib.equal -> 'a t Base__Ppx_compare_lib.equal
include Ppx_hash_lib.Hashable.S1 with type 'a t := 'a t
val hash_fold_t : 'a Base__Ppx_hash_lib.hash_fold -> 'a t Base__Ppx_hash_lib.hash_fold
include Sexplib0.Sexpable.S1 with type 'a t := 'a t
val t_of_sexp : (Sexplib0__.Sexp.t -> 'a) -> Sexplib0__.Sexp.t -> 'a t
val sexp_of_t : ('a -> Sexplib0__.Sexp.t) -> 'a t -> Sexplib0__.Sexp.t

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).

val mem : 'a t -> 'a -> equal:('a -> 'a -> bool) -> bool
val length : 'a t -> int
val is_empty : 'a t -> bool
val iter : 'a t -> f:('a -> unit) -> unit
val fold : 'a t -> init:'acc -> f:('acc -> 'a -> 'acc) -> 'acc
val fold_result : 'a t -> init:'acc -> f:('acc -> 'a -> ('acc, 'e) Base__.Result.t) -> ('acc, 'e) Base__.Result.t
val fold_until : 'a t -> init:'acc -> f:('acc -> 'a -> ('acc, 'final) Base__Container_intf.Continue_or_stop.t) -> finish:('acc -> 'final) -> 'final
val exists : 'a t -> f:('a -> bool) -> bool
val for_all : 'a t -> f:('a -> bool) -> bool
val count : 'a t -> f:('a -> bool) -> int
val sum : (module Base__Container_intf.Summable with type t = 'sum) -> 'a t -> f:('a -> 'sum) -> 'sum
val find : 'a t -> f:('a -> bool) -> 'a option
val find_map : 'a t -> f:('a -> 'b option) -> 'b option
val to_list : 'a t -> 'a list
val to_array : 'a t -> 'a array
val min_elt : 'a t -> compare:('a -> 'a -> int) -> 'a option
val max_elt : 'a t -> compare:('a -> 'a -> int) -> 'a option
val invariant : 'a Base__Invariant_intf.inv -> 'a t Base__Invariant_intf.inv
val (>>=) : 'a t -> ('a -> 'b t) -> 'b t
val (>>|) : 'a t -> ('a -> 'b) -> 'b t
module Monad_infix : sig ... end
val bind : 'a t -> f:('a -> 'b t) -> 'b t
val return : 'a -> 'a t
val map : 'a t -> f:('a -> 'b) -> 'b t
val join : 'a t t -> 'a t
val ignore_m : 'a t -> unit t
val all : 'a t list -> 'a list t
val all_unit : unit t list -> unit t
module Let_syntax : sig ... end
module Arbitrary_order : sig ... end

Traverse deque elements in arbitrary order.

module Front_to_back : sig ... end

Traverse deque elements front-to-back. Incurs up to O(n) additional time and space cost over Arbitrary_order.

module Back_to_front : sig ... end

Traverse deque elements back-to-front. Incurs up to O(n) additional time and space cost over Arbitrary_order.

val empty : _ t

The empty deque.

val singleton : 'a -> 'a t

A one-element deque.

val of_list : 'a Base.List.t -> '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 Base.Option.t

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 Base.Option.t
val peek_front_exn : 'a t -> 'a
val peek_back : 'a t -> 'a Base.Option.t
val peek_back_exn : 'a t -> 'a
val drop : 'a t -> [ `back | `front ] -> 'a t Base.Option.t

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 Base.Option.t
val drop_front_exn : 'a t -> 'a t
val drop_back : 'a t -> 'a t Base.Option.t
val drop_back_exn : 'a t -> 'a t
val dequeue : 'a t -> [ `back | `front ] -> ('a * 'a t) Base.Option.t

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) Base.Option.t
val dequeue_front_exn : 'a t -> 'a * 'a t
val dequeue_back : 'a t -> ('a * 'a t) Base.Option.t
val dequeue_back_exn : 'a t -> 'a * 'a t
module Stable : sig ... end
module Private : sig ... end
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events Blog Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct