CCDeque
Imperative deque
This structure provides fast access to its front and back elements, with O(1) operations.
val create : unit -> 'a t
New deque.
val clear : _ t -> unit
Remove all elements.
val is_empty : 'a t -> bool
Is the deque empty?
equal a b
checks whether a
and b
contain the same sequence of elements.
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.
val peek_front_opt : 'a t -> 'a option
First value.
val peek_back : 'a t -> 'a
Last value.
val peek_back_opt : 'a t -> 'a option
Last value.
val remove_back : 'a t -> unit
Remove last value. If the deque is empty do nothing
val remove_front : 'a t -> unit
Remove first value. If the deque is empty do nothing
val take_back : 'a t -> 'a
Take last value.
val take_back_opt : 'a t -> 'a option
Take last value.
val take_front : 'a t -> 'a
Take first value.
val take_front_opt : 'a t -> 'a option
Take first value.
val update_back : 'a t -> ('a -> 'a option) -> unit
Update last value. If the deque is empty do nothing. If the function returns None
, remove last element; if it returns Some x
, replace last element with x
.
val update_front : 'a t -> ('a -> 'a option) -> unit
Update first value. If the deque is empty do nothing. Similar to update_back
but for the first value.
append_front ~into q
adds all elements of q
at the front of into
. O(length q)
in time.
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.
Create a deque from the sequence. Optional argument deque
disappears, use add_iter_back
instead.
add_iter_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.
add_iter_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 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.
val filter_in_place : 'a t -> ('a -> bool) -> unit
Keep only elements that satisfy the predicate.