(***********************************************************************)
(*                                                                     *)
(*                           Objective Caml                            *)
(*                                                                     *)
               , projet Cristal , INRIA Rocquencourt         
(*                                                                     *)
   Copyright 1996 Institut National de Recherche en Informatique et   
   en Automatique .   All rights reserved .   This file is distributed    
   under the terms of the GNU Library General Public License , with    
(*  the special exception on linking described in file ../LICENSE.     *)
(*                                                                     *)
(***********************************************************************)

  $ I d : queue.mli , v 1.16 2002/06/27 08:48:26 xleroy Exp $

* First - in first - out queues . 

    This module implements queues ( FIFOs ) , with in - place modification . 


   This module implements queues (FIFOs), with in-place modification.
*)

type 'a t
(** The type of queues containing elements of type ['a]. *)


exception Empty
* Raised when { ! Queue.take } or { !  } is applied to an empty queue .


val create : unit -> 'a t
(** Return a new queue, initially empty. *)

val add : 'a -> 'a t -> unit
(** [add x q] adds the element [x] at the end of the queue [q]. *)

val push : 'a -> 'a t -> unit
(** [push] is a synonym for [add]. *)

val take : 'a t -> 'a
* [ take q ] removes and returns the first element in queue [ q ] , 
    or raises [ Empty ] if the queue is empty .
   or raises [Empty] if the queue is empty. *)

val pop : 'a t -> 'a
(** [pop] is a synonym for [take]. *)

val peek : 'a t -> 'a
* [ peek q ] returns the first element in queue [ q ] , without removing 
    it from the queue , or raises [ Empty ] if the queue is empty .
   it from the queue, or raises [Empty] if the queue is empty. *)

val top : 'a t -> 'a
(** [top] is a synonym for [peek]. *)

val clear : 'a t -> unit
(** Discard all elements from a queue. *)

val copy : 'a t -> 'a t
(** Return a copy of the given queue. *)

val is_empty : 'a t -> bool
(** Return [true] if the given queue is empty, [false] otherwise. *)

val length : 'a t -> int
(** Return the number of elements in a queue. *)

val iter : ('a -> unit) -> 'a t -> unit
(** [iter f q] applies [f] in turn to all elements of [q],
   from the least recently entered to the most recently entered.
   The queue itself is unchanged. *)

val fold : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
(** [fold f accu q] is equivalent to [List.fold_left f accu l],
   where [l] is the list of [q]'s elements. The queue remains
   unchanged. *)

val transfer : 'a t -> 'a t -> unit
* [ transfer q1 q2 ] adds all of [ q1 ] 's elements at the end of 
    the queue [ q2 ] , then clears [ q1 ] . It is equivalent to the 
    sequence [ iter ( fun x - > add x q2 ) q1 ; clear q1 ] , but runs 
    in constant time .
   the queue [q2], then clears [q1]. It is equivalent to the
   sequence [iter (fun x -> add x q2) q1; clear q1], but runs
   in constant time. *)

*********************************************************************
                                                                     
                           Objective Caml                            
                                                                     
                                                                     
  the special exception on linking described in file ../LICENSE.     
                                                                     
*********************************************************************
* The type of queues containing elements of type ['a]. 
* Return a new queue, initially empty. 
* [add x q] adds the element [x] at the end of the queue [q]. 
* [push] is a synonym for [add]. 
* [pop] is a synonym for [take]. 
* [top] is a synonym for [peek]. 
* Discard all elements from a queue. 
* Return a copy of the given queue. 
* Return [true] if the given queue is empty, [false] otherwise. 
* Return the number of elements in a queue. 
* [iter f q] applies [f] in turn to all elements of [q],
   from the least recently entered to the most recently entered.
   The queue itself is unchanged. 
* [fold f accu q] is equivalent to [List.fold_left f accu l],
   where [l] is the list of [q]'s elements. The queue remains
   unchanged. 
               , projet Cristal , INRIA Rocquencourt         
   Copyright 1996 Institut National de Recherche en Informatique et   
   en Automatique .   All rights reserved .   This file is distributed    
   under the terms of the GNU Library General Public License , with    

  $ I d : queue.mli , v 1.16 2002/06/27 08:48:26 xleroy Exp $

* First - in first - out queues . 

    This module implements queues ( FIFOs ) , with in - place modification . 


   This module implements queues (FIFOs), with in-place modification.
*)

type 'a t


exception Empty
* Raised when { ! Queue.take } or { !  } is applied to an empty queue .


val create : unit -> 'a t

val add : 'a -> 'a t -> unit

val push : 'a -> 'a t -> unit

val take : 'a t -> 'a
* [ take q ] removes and returns the first element in queue [ q ] , 
    or raises [ Empty ] if the queue is empty .
   or raises [Empty] if the queue is empty. *)

val pop : 'a t -> 'a

val peek : 'a t -> 'a
* [ peek q ] returns the first element in queue [ q ] , without removing 
    it from the queue , or raises [ Empty ] if the queue is empty .
   it from the queue, or raises [Empty] if the queue is empty. *)

val top : 'a t -> 'a

val clear : 'a t -> unit

val copy : 'a t -> 'a t

val is_empty : 'a t -> bool

val length : 'a t -> int

val iter : ('a -> unit) -> 'a t -> unit

val fold : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b

val transfer : 'a t -> 'a t -> unit
* [ transfer q1 q2 ] adds all of [ q1 ] 's elements at the end of 
    the queue [ q2 ] , then clears [ q1 ] . It is equivalent to the 
    sequence [ iter ( fun x - > add x q2 ) q1 ; clear q1 ] , but runs 
    in constant time .
   the queue [q2], then clears [q1]. It is equivalent to the
   sequence [iter (fun x -> add x q2) q1; clear q1], but runs
   in constant time. *)
