module Fqueue: sig
.. end
Simple implementation of a polymorphic functional queue.
Push and top and bottom are O(1). Pop and take are O(1) amortized.
to_list and length are O(n).
exception Bug of string
exception Empty
type 'a
t
val test_invariants : 'a t -> unit
test via asserts whether invariants hold
val empty : 'a t
The empty queue
val push : 'a -> 'a t -> 'a t
push a single element on queue
val push_top : 'a -> 'a t -> 'a t
push a single element on the *top* of the queue
val enq : 'a -> 'a t -> 'a t
alias for push
val bot_exn : 'a t -> 'a
returns the bottom (most-recently enqueued element). Raises Empty
if no element is
found.
val bot : 'a t -> 'a option
like bot_exn
, but returns result optionally, without exception
val top_exn : 'a t -> 'a
Like bot_exn
, except returns top (least-recently enqueued element
val top : 'a t -> 'a option
like top_exn
, but returns result optionally, without exception
val pop_exn : 'a t -> 'a * 'a t
Like top_exn
, but returns pair of the top element, and a new queue with the top element
removed
val pop : 'a t -> ('a * 'a t) option
Like pop_exn
, but returns result optionally, without exception
val deq : 'a t -> ('a * 'a t) option
alias for pop
val deq_exn : 'a t -> 'a * 'a t
alias for pop_exn
val discard : 'a t -> 'a t
Returns version of queue with top element removed
val to_list : 'a t -> 'a list
converts queue to list, from most to least recently enqueued item
val length : 'a t -> int
val is_empty : 'a t -> bool