(*
* FIFO- an applicative, O(1) FIFO (queue)
* Copyright (C) 2003 Brian Hurt
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version,
* with the special exception on linking described in file LICENSE.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*)
(** Applicative, O(1) FIFO (queue)
*
* This module implements a first-in, first-out queue. Elements can be
* added to either the head of the queue or the tail of the queue,
* and can be removed from the head of the queue, in amoritized O(1) cost.
* The data structure is fully applicative (aka functional aka immutable).
*
* The interface to this module is designed to be similiar to the
* {!Queue} standard library, but obviously the differences between being
* imperitive and functional makes it impossible to be a drop-in replacement.
*)
type 'a t
(** The type of a fifo *)
exception Empty
(** Raised when {!head} or {!remove} is called on an empty queue. *)
val empty: 'a t
(** The empty fifo *)
val create: unit -> 'a t
(** Create an empty fifo- just returns {!empty}. *)
val add: 'a -> 'a t -> 'a t
(** [add x a] adds the element [x] to the tail of fifo [a], returning the
updated fifo. *)
val push: 'a -> 'a t -> 'a t
(** a synonym for {!add} *)
val append: 'a -> 'a t -> 'a t
(** Another synonym for {!add} *)
val head: 'a t -> 'a
(** [head a] returns the head element (the element at the head) of fifo [a],
or throws {!Empty} if the queue is empty. *)
val peek: 'a t -> 'a
(** A synonym for {!head}. *)
val remove: 'a t -> 'a t
(** [remove a] removes the head element of the fifo [a], or throws
{!Empty} if the queue is empty. *)
val pop: 'a t -> 'a * 'a t
(** A combination of {!head} and {!remove}. *)
val prepend: 'a -> 'a t -> 'a t
(** [prepend x a] adds the element [x] to the head of fifo [a]- such that
it will be the next object returned by {!head}. Note that this is an
O(1) operation. *)
val unpop: 'a -> 'a t -> 'a t
(** A synonym for {!prepend}. *)
val is_empty: 'a t -> bool
(** Returns false if the fifo has one or more elements in it, true
otherwise. *)
val length: 'a t -> int
(** Returns the number of elements in the fifo. Note that this is an
O(N) operation. *)
val iter: ('a -> unit) -> 'a t -> unit
(** [iter f q] applies [f] to all the elements of [q]. Because of the
structure of the fifo, this routine consumes O(N) memory, but maintains
an in-order traversal of the queue. If the order of traversal is
unimportant, use {!iter_fast} and avoid the O(N) penalty. *)
val iter_fast: ('a -> unit) -> 'a t -> unit
(** [iter_fast f a] applies [f] to all elements of [q]. The order of
application is not gaurenteed, however, allowing the function to
run in O(1) stack and memory usage. *)
val fold: ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
(** [fold f accu q] is equivelent to [List.fold_left f accu l] where
[l] is the list of elements in the queue. Because of the structure of
the fifo, this routine consumes O(N) memory, but maintains an
in-order traversal of the queue. If the order of the traversal is
unimportant, use {!fold_fast} and avoid the O(N) penalty. *)
val fold_fast: ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
(** [fold_fast f accu q] is the same as {!fold}, except that the order
of traversal is not gaurenteed. This allows the function run in
O(1) stack and memory usage. *)
val map: ('a -> 'b) -> 'a t -> 'b t
(** Converts all the elements in the queue from one type to another.
Because of the structure of the fifo, this routine consumes O(N) memory,
but maintains an in-order traversal of the queue. If the order of
the traversal is unimportant, use {!map_fast} and avoid the O(N)
penalty. *)
val map_fast: ('a -> 'b) -> 'a t -> 'b t
(** The same as {!map}, but the order of traversal is unspecified, allowing
the function to run in O(1) stack and memory usage. *)
val to_list: 'a t -> 'a list
(** Converts the queue to a list (maintaining the order of the queue). *)
val enum: 'a t -> 'a Enum.t
(** returns an enumeration of the queue. *)
val of_enum: 'a Enum.t -> 'a t
(** Creates a queue from an enumeration. *)