Module BatDeque

The type of double-ended queues

A synonym for convenience

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

The empty deque.

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

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

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

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

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

rev dq reverses dq. O(1)

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

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)

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

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)

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

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)

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)

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

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

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

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

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

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

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

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

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

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

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.

Print the contents of the deque. O(n)