module DoubleQueue: sig .. end
Double ended queues
type 'a t
The type of double ended queues. Access to both the front and
the back of the queue take amortized O(1) time.
val empty : 'a t
The empty queue
val is_empty : 'a t -> bool
Returns true is the queue is empty
val hd : 'a t -> 'a
hd q Return the element at the front of the queue. If the
queue is empty, it raises Failure "hd"
val tl : 'a t -> 'a t
tl t Return the queue t with the element at the front of the
queue removed. Runs in O(1) time and stack space. If the queue
is empty, it raises Failure "tl".
val pop : 'a t -> 'a * 'a t
pop t Equivalent to (hd t), (tl t) but is more efficient.
Runs in O(1) time and stack space. If the queue is empty, it
raises Failure "pop".
val cons : 'a -> 'a t -> 'a t
cons x t Adds x to the front of queue t so that a
subsequent call to hd returns x. Runs in O(1) time and
stack space.
val hd_back : 'a t -> 'a
hd_back q Return the element at the back of the queue. If the
queue is empty, it raises Failure "hd_back". Runs in
amortized O(1) time and O(1) stack space.
val tl_back : 'a t -> 'a t
tl t Return the queue t with the element at the back of the
queue removed. Runs in amortized O(1) time and O(1) stack
space. If the queue is empty, it raises Failure "tl_back".
val pop_back : 'a t -> 'a t * 'a
pop_back t Equivalent to (hd_back t), (tl_back t) but is
more efficient. Runs in amortized O(1) time and O(1) stack
space. If the queue is empty, it raises Failure "pop_back".
val cons_back : 'a -> 'a t -> 'a t
cons_back x t Adds x to the back of queue t so that a
subsequent call to hd_back returns x. Runs in O(1) time and
stack space.
val snoc : 'a -> 'a t -> 'a t
val last : 'a t -> 'a
last q is an alias for hd_back q
val enqueue : 'a -> 'a t -> 'a t
val dequeue : 'a t -> 'a * 'a t
dequeue x t is an alias for
Reins.DoubleQueue.hd x t, removing
the first element from the front of
t.
val length : 'a t -> int
length t Returns the number of elements in the queue t
val rev : 'a t -> 'a t
rev t Reverses the order of the queue t. e.g., hd t ==
hd_back (rev t)
val append : 'a t -> 'a t -> 'a t
append t1 t2 Appends all of the elements in queue
t2 onto
the back of
t1. That is, in the resulting queue,
Reins.DoubleQueue.hd returns the first element of
t1 and
Reins.DoubleQueue.hd_back returns the last element of
t2. Runs
in O(n+m) time where n and m are the number of elements in
t1
and
t2 respectively.
val iter : ('a -> unit) -> 'a t -> unit
iter f t Iterates over each element in the queue t in order
and applies f to that element. Runs in O(n*ft) where ft is
the running time of f and uses O(fs) stack space where fs is
the stack space required by f.
val fold : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
fold f acc t Accumulates the result acc by applying f acc
x for each element x in t. Runs in O(n*ft) where ft is the
running time of f and uses O(fs) stack space where fs is the
stack space required by f.
val rev_map : ('a -> 'b) -> 'a t -> 'b t
rev_map f t Creates a new queue by applying f to each element
of t. The resulting queue is in reverse order of t. Runs in
O(n*ft) time where n is the number of elements in t and ft is
the running time of f. It uses O(fs) stack space where fs is
the stack space required by f.
val map : ('a -> 'b) -> 'a t -> 'b t
map f t Creates a new queue by applying
f to each element of
t. The resulting queue is in the same order as
t. Runs in
O(n*ft) time where n is the number of elements in
t and ft is
the running time of
f. It uses O(fs) stack space where fs is
the stack space required by
f. This function is just as
efficient as
Reins.DoubleQueue.rev_map (yielding a different
ordering) and more efficient than
DoubleQueue.rev
(DoubleQueue.rev_map t).
val to_list : 'a t -> 'a list
to_list t Convert the DoubleQueue t into a standard list.
Runs in O(n) time and O(1) stack space where n is the number of
elements in t. The resulting list has the same ordering as
t. That is, DoubleQueue.hd t == List.hd (DoubleQueue.to_list
t).
val from_list : 'a list -> 'a t
from_list l Convert the standard list l into a DoubleQueue.t.
Runs in O(n) time and O(1) stack space where n is the number of
elements in l. The resulting queue has the same order as the
original list. That is List.hd l == DoubleQueue.hd
(DoubleQueue.from_list l).
val flatten : 'a t t -> 'a t
flatten l Appends all of the elements of l into a new queue.
The current implementation is not very efficient and runs in
greater than O(n) time uses a O(n) stack space.
val to_string : ('a -> string) -> 'a t -> string
to_string to_s t Convert the queue t into a string using
to_s to individually convert each element into a string. Runs
in O(n*st) where st is the running time of to_s and uses O(ss)
stack space where ss is the amount of stack required by to_s.
val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
compare f t1 t2 Compares the queues t1 and t2 using f to
compare individual elements. Returns 0 if t1 and t2 are
equal (under f). Returns <0 if t1 is less than t2 and
returns >0 otherwise.
val gen : (?size:int -> Random.State.t -> 'a) ->
?size:int -> Random.State.t -> 'a t
gen f ?size rs Generates a random queue whose length is
bounded by size. Each element in the queue is computed by
calling f ?size rs. Runs in time O(size * ft) where ft is
the running time of f and uses O(fs) stack space where fs is
the stack space of f.