package batteries

  1. Overview
  2. Docs
A community-maintained standard library extension

Install 

dune-project
 Dependency

github.com Readme Edit opam file Versions (15)

Authors

  1. O
    OCaml batteries-included team

Maintainers

  1. C
    Cedric Cellier <rixed@happyleptic.org>
  2. F
    Francois Berenger <unixjunkie@sdf.org>
  3. Gabriel Scherer
  4. T
    Thibault Suzanne <thi.suzanne@gmail.com>
  5. S
    Simmo Saan <simmo.saan@gmail.com>

Sources

batteries-3.10.0.tar.gz
md5=b7f3b99f12f21b1da6b6aa13d993206d
sha512=8b7f2479eb0271bcfd9168887c1e4a9a815c512eab3ee61b150fc4dfa9ec803e4f73115155f20b3017e4a822148d0e6d1c1e8e5f96790fd691b419dd39a908a2

doc/batteries.unthreaded/BatDeque/index.html

Module BatDequeSource

Functional double-ended queues

Sourcetype +'a dq

The type of double-ended queues

Sourcetype 'a t = 'a dq

A synonym for convenience

include BatEnum.Enumerable with type 'a enumerable = 'a t
Sourcetype 'a enumerable = 'a t

The data structure, e.g. 'a List.t

include BatInterfaces.Mappable with type 'a mappable = 'a t
Sourcetype 'a mappable = 'a t

The data structure, e.g. 'a List.t

Sourceval size : 'a dq -> int

size dq is the number of elements in the dq. O(1)

Construction

Sourceval empty : 'a dq

The empty deque.

Sourceval cons : 'a -> 'a dq -> 'a dq

cons x dq adds x to the front of dq. O(1)

Sourceval snoc : 'a dq -> 'a -> 'a dq

snoc x dq adds x to the rear of dq. O(1)

Deconstruction

Sourceval front : 'a dq -> ('a * 'a dq) option

front dq returns Some (x, dq') iff x is at the front of dq and dq' is the rest of dq excluding x, and None if dq has no elements. O(1) amortized, O(n) worst case

Sourceval rear : 'a dq -> ('a dq * 'a) option

rear dq returns Some (dq', x) iff x is at the rear of dq and dq' is the rest of dq excluding x, and None if dq has no elements. O(1) amortized, O(n) worst case

Basic operations

Sourceval eq : ?eq:('a -> 'a -> bool) -> 'a dq -> 'a dq -> bool

eq dq1 dq2 is true if dq1 and dq2 have the same sequence of elements. A custom function can be optionally provided with the eq parameter (default is Pervasives.(=)).

  • since 2.2.0
Sourceval rev : 'a dq -> 'a dq

rev dq reverses dq. O(1)

Sourceval is_empty : 'a dq -> bool

is_empty dq returns true iff dq has no elements. O(1)

Sourceval at : ?backwards:bool -> 'a dq -> int -> 'a option

at ~backwards dq k returns the kth element of dq, from the front if backwards is false, and from the rear if backwards is true. By default, backwards = false. O(n)

Sourceval map : ('a -> 'b) -> 'a dq -> 'b dq

map f dq returns a deque where every element x of dq has been replaced with f x. O(n)

Sourceval mapi : (int -> 'a -> 'b) -> 'a dq -> 'b dq

mapi f dq returns a deque where every element x of dq has been replaced with f n x, where n is the position of x from the front of dq. O(n)

Sourceval iter : ('a -> unit) -> 'a dq -> unit

iter f dq calls f x on each element x of dq. O(n)

Sourceval iteri : (int -> 'a -> unit) -> 'a dq -> unit

iteri f dq calls f n x on each element x of dq. The first argument to f is the position of the element from the front of dq. O(n)

Sourceval find : ?backwards:bool -> ('a -> bool) -> 'a dq -> (int * 'a) option

find ~backwards f dq returns Some (n, x) if x at position n is such that f x is true, or None if there is no such element. The position n is from the rear if backwards is true, and from the front if backwards is false. By default, backwards is false. O(n)

Sourceval fold_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a dq -> 'acc

fold_left f acc dq is equivalent to List.fold_left f acc (to_list dq), but more efficient. O(n)

Sourceval fold_right : ('a -> 'acc -> 'acc) -> 'a dq -> 'acc -> 'acc

fold_right f dq acc is equivalent to List.fold_right f (to_list dq) acc, but more efficient. O(n)

Sourceval append : 'a dq -> 'a dq -> 'a dq

append dq1 dq2 represents the concatenateion of dq1 and dq2. O(min(m, n))

Sourceval append_list : 'a dq -> 'a list -> 'a dq

append_list dq l is equivalent to append dq (of_list l), but more efficient. O(min(m, n))

Sourceval prepend_list : 'a list -> 'a dq -> 'a dq

prepend_list l dq is equivalent to append (of_list l) dq, but more efficient. O(min(m, n))

Sourceval rotate_forward : 'a dq -> 'a dq

A cyclic shift of deque elements from rear to front by one position. As a result, the front element becomes the rear element. Time: O(1) amortized, O(n) worst-case.

  • since 2.3.0
Sourceval rotate_backward : 'a dq -> 'a dq

A cyclic shift of deque elements from front to rear by one position. As a result, the rear element becomes the front element. Time: O(1) amortized, O(n) worst-case.

  • since 2.3.0

Transformation

Sourceval of_list : 'a list -> 'a dq

of_list l is a deque representation of the elements of l. O(n)

Sourceval to_list : 'a dq -> 'a list

to_list dq is a list representation of the elements of dq. O(n)

Sourceval of_enum : 'a BatEnum.t -> 'a dq

of_enum e is a deque representation of the elements of e. Consumes the enumeration e. O(n)

Sourceval enum : 'a dq -> 'a BatEnum.t

enum dq is an enumeration of the elements of dq from the front to the rear. This function is O(1), but generating each element of the enumeration is amortized O(1), and O(n) worst case.

Printing

Sourceval print : ?first:string -> ?last:string -> ?sep:string -> ('a, 'b) BatIO.printer -> ('a dq, 'b) BatIO.printer

Print the contents of the deque. O(n)