A double-ended queue that can shrink and expand on both ends.
An index is assigned to an element when it enters the queue, and the index of an element is static (i.e., an index refers to a distinct element until that element is removed from the queue, no matter how many intervening push/pop operations occur).
One consequence of this is that the minimum index may be less than zero.
The "front" is the smallest valid index, while the "back" is the largest.
All operations are amortized O(1) with a small constant.
fold_result t ~init ~f is a short-circuiting version of fold that runs in the Result monad. If f returns an Error _, that value is returned without any additional invocations of f.
fold_until t ~init ~f ~finish is a short-circuiting version of fold. If f returns Stop _ the computation ceases and results in that value. If f returns Continue _, the fold will proceed. If f never returns Stop _, the final result is computed by finish.
Example:
type maybe_negative =
| Found_negative of int
| All_nonnegative of { sum : int }
(** [first_neg_or_sum list] returns the first negative number in [list], if any,
otherwise returns the sum of the list. *)
let first_neg_or_sum =
List.fold_until ~init:0
~f:(fun sum x ->
if x < 0
then Stop (Found_negative x)
else Continue (sum + x))
~finish:(fun sum -> All_nonnegative { sum })
;;
let x = first_neg_or_sum [1; 2; 3; 4; 5]
val x : maybe_negative = All_nonnegative {sum = 15}
let y = first_neg_or_sum [1; 2; -3; 4; 5]
val y : maybe_negative = Found_negative -3
Returns a minimum (resp maximum) element from the collection using the provided compare function, or None if the collection is empty. In case of a tie, the first element encountered while traversing the collection is returned. The implementation uses fold so it has the same complexity as fold.
create ?initial_length ?never_shrink () creates a new t. initial_length is the initial length of the dequeue; it will be able to hold initial_length elements without resizing. It must be positive. If never_shrink is true, the physical array will never shrink, only expand. If initial_length is given without never_shrink, then never_shrink is presumed to be true, otherwise never_shrink defaults to false.