Module CCDeque

Imperative deque

This structure provides fast access to its front and back elements, with O(1) operations

type 'a t

Contains 'a elements, queue in both ways

exception Empty
val create : unit ‑> 'a t

New deque.

val clear : _ t ‑> unit

Remove all elements.

val is_empty : 'a t ‑> bool

Is the deque empty?

val equal : eq:('a ‑> 'a ‑> bool) ‑> 'a t ‑> 'a t ‑> bool

equal a b checks whether a and b contain the same sequence of elements.

val compare : cmp:('a ‑> 'a ‑> int) ‑> 'a t ‑> 'a t ‑> int

compare a b compares lexicographically a and b

val length : 'a t ‑> int

Number of elements. Used to be linear time, now constant time.

val push_front : 'a t ‑> 'a ‑> unit

Push value at the front.

val push_back : 'a t ‑> 'a ‑> unit

Push value at the back.

val peek_front : 'a t ‑> 'a

First value, or

val peek_back : 'a t ‑> 'a

Last value, or

val take_back : 'a t ‑> 'a

Take last value, or

val take_front : 'a t ‑> 'a

Take first value, or

val append_front : into:'a t ‑> 'a t ‑> unit

append_front ~into q adds all elements of q at the front of into. O(length q) in time.

val append_back : into:'a t ‑> 'a t ‑> unit

append_back ~into q adds all elements of q at the back of into. O(length q) in time.

val iter : ('a ‑> unit) ‑> 'a t ‑> unit

Iterate on elements.

val fold : ('b ‑> 'a ‑> 'b) ‑> 'b ‑> 'a t ‑> 'b

Fold on elements.

Conversions

type 'a gen = unit ‑> 'a option
type 'a sequence = ('a ‑> unit) ‑> unit
val of_seq : 'a sequence ‑> 'a t
val to_seq : 'a t ‑> 'a sequence

Iterate on the elements.

val of_gen : 'a gen ‑> 'a t

of_gen g makes a deque containing the elements of g.

val to_gen : 'a t ‑> 'a gen

Iterate on elements of the deque.

val add_seq_front : 'a t ‑> 'a sequence ‑> unit

add_seq_front q seq adds elements of seq into the front of q, in reverse order. O(n) in time, where n is the number of elements to add.

val add_seq_back : 'a t ‑> 'a sequence ‑> unit

add_seq_back q seq adds elements of seq into the back of q, in order. O(n) in time, where n is the number of elements to add.

val copy : 'a t ‑> 'a t

Fresh copy, O(n) in time.

val of_list : 'a list ‑> 'a t

Conversion from list, in order.

val to_list : 'a t ‑> 'a list

List of elements, in order. Less efficient than to_rev_list.

val to_rev_list : 'a t ‑> 'a list

Efficient conversion to list, in reverse order.

print

type 'a printer = Format.formatter ‑> 'a ‑> unit
val pp : 'a printer ‑> 'a t printer

Print the elements.