(***********************************************************************)
(* Growable Arrays                                                     *)
(*                                                                     *)
(* This a wrapper around the standard OCaml array, but will grow       *)
(* automatically on get or set outside the current size of the         *)
(* array.                                                              *)
(*                                                                     *)
(* The interface is the same as the standard OCaml array where         *)
(* applicable (and implemented).                                       *)
(***********************************************************************)

  $ Id$

(** Array operations. *)

(** The type of growable arrays *)
type 'a t

(** The default value to a new element of the growable array *)
type 'a fill =
    Elem of 'a
    (* A default value *)
  | Susp of (int -> 'a)
    (* A function given an index to generate a default value *)

val make : int -> 'a fill -> 'a t
(** [GrowArray.make n x] returns a fresh growable array of size
   at least [n] with default value specified by [x].

   Raise [Invalid_argument] if [n < 0] or [n > Sys.max_array_length]. *)

val num_alloc_index: 'a t -> int
(** [GrowArray.num_alloc_index a] returns the number of allocated entries in 
 * the array **)

val max_init_index : 'a t -> int
(** [GrowArray.max_init_index a] returns the maximum index to
    which has been written.

    Returns -1 if no writes have been made. *)

val reset_max_init_index : 'a t -> unit
* [ GrowArray.reset_init a ] resets the max_init_index . You should probably 
    use [ GrowArray.clear a ] instead if you also want to delete the contents .
   use [GrowArray.clear a] instead if you also want to delete the contents. *)

val getg : 'a t -> int -> 'a
* [  a n ] returns the element number [ n ] of array [ a ] . 
    The first element has number 0 . 
    The last element has number [ GrowArray.length a - 1 ] . 

    If [ n ] is outside the range 0 to [ ( GrowArray.max_init_index a ) ] , 
    then the array grows to at least [ n ] and yields the default value .
   The first element has number 0.
   The last element has number [GrowArray.length a - 1].

   If [n] is outside the range 0 to [(GrowArray.max_init_index a)],
   then the array grows to at least [n] and yields the default value. *)

val setg : 'a t -> int -> 'a -> unit
* [ GrowArray.setg a n x ] modifies array [ a ] in place , replacing 
    element number [ n ] with [ x ] . 

    If [ n ] is outside the range 0 to [ ( GrowArray.max_init_index a ) ] , 
    then the array grows to at least [ n ] and yields the default value .
   element number [n] with [x].

   If [n] is outside the range 0 to [(GrowArray.max_init_index a)],
   then the array grows to at least [n] and yields the default value. *)

val get : 'a t -> int -> 'a
(** [GrowArray.get a n] returns the element number [n] of grow array [a].

   Raise [Invalid_argument "Array.get"]  if [n] is outside the range
   of the underlying array. *)

val set : 'a t -> int -> 'a -> unit
(** [GrowArray.set a n x] modifies grow array [a] in place, replacing
   element number [n] with [x].

   Raise [Invalid_argument "Array.set"] if [n] is outside the range
   of the underlying array. *)
        
val clear: 'a t -> unit 
* [ GrowArray.clear a ] clears the contents of the array and sets 
    max_init_index to -1 .   Suspension thunks will be rerun to regenerate the 
    initial values of the array .
   max_init_index to -1.  Suspension thunks will be rerun to regenerate the 
   initial values of the array. *)

val copy : 'a t -> 'a t
(** [GrowArray.copy a] returns a copy of [a], that is, a fresh array
   containing the same elements as [a]. *)

val deep_copy : 'a t -> ('a -> 'a) -> 'a t
(** [GrowArray.copy a f] returns a deep copy of [a] using f to
    copy elements of [a]. *)

val iter : ('a -> unit) -> 'a t -> unit
* [ GrowArray.iter f a ] applies function [ f ] in turn to all 
    the elements of [ a ] .   It is equivalent to 
    [ f  ) ; f a.(1 ) ; ... ; f a.(GrowArray.length a - 1 ) ; ( ) ] .
   the elements of [a].  It is equivalent to
   [f a.(0); f a.(1); ...; f a.(GrowArray.length a - 1); ()]. *)

val iteri : (int -> 'a -> unit) -> 'a t -> unit
* Same as { ! GrowArray.iter } , but the 
    function is applied to the index of the element as first argument , 
    and the element itself as second argument .
   function is applied to the index of the element as first argument,
   and the element itself as second argument. *)

val iter2 : (int -> 'a -> 'b -> unit) -> 'a t -> 'b t -> unit
* Same as { ! GrowArray.iteri } , but the function is applied to two arrays . 
   [ iter2 f a b ]   is equivalent to 
   [ f 0  )  ) ; f 1 a.(1 ) b.(1 ) ; ... ;   f n a.(n ) b.(n ) ; ( ) ] 
   where n is the larger of ( max_init_index a ) or ( max_init_index b ) . 
   The shorter array will grow to match the longer .
  [iter2 f a b]  is equivalent to
  [f 0 a.(0) b.(0); f 1 a.(1) b.(1); ...;  f n a.(n) b.(n); ()]
  where n is the larger of (max_init_index a) or (max_init_index b).
  The shorter array will grow to match the longer.*)

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
* [ GrowArray.fold_left f x a ] computes 
    [ f ( ... ( f ( f x  ) ) a.(1 ) ) ... ) a.(n-1 ) ] , 
    where [ n ] is the length of the array [ a ] .
   [f (... (f (f x a.(0)) a.(1)) ...) a.(n-1)],
   where [n] is the length of the array [a]. *)

val fold_lefti : ('a -> int -> 'b -> 'a) -> 'a -> 'b t -> 'a
* [ GrowArray.fold_lefti f x a ] computes 
    [ f ( ... ( f ( f x 0  ) ) 1 a.(1 ) ) ... ) ( n-1 ) a.(n-1 ) ] , 
    where [ n ] is the length of the array [ a ] .
   [f (... (f (f x 0 a.(0)) 1 a.(1)) ...) (n-1) a.(n-1)],
   where [n] is the length of the array [a]. *)

val fold_right : ('b -> 'a -> 'a) -> 'b t -> 'a -> 'a
* [ GrowArray.fold_right f a x ] computes 
    [ f  ) ( f a.(1 ) ( ... ( f a.(n-1 ) x ) ... ) ) ] , 
    where [ n ] is the length of the array [ a ] .
   [f a.(0) (f a.(1) ( ... (f a.(n-1) x) ...))],
   where [n] is the length of the array [a]. *)

val d_growarray : Pretty.doc -> (int -> 'a -> Pretty.doc) -> unit -> 'a t
                             -> Pretty.doc
(** [GrowArray.d_growarray sep f () a] creates a {!Pretty.doc} for growable
   array a using separator sep and element printer f. *)


val restoreGA: ?deepCopy:('a -> 'a) -> 'a t -> unit -> unit
(** Given a growable array, produce a thunk that later restores it to its
    current value *)

val find: 'a t -> ('a -> bool) -> int option
* Returns the index of the first element in the array that satisfies the 
     predicate , or None if there is no such element
    predicate, or None if there is no such element *)

*********************************************************************
 Growable Arrays                                                     
                                                                     
 This a wrapper around the standard OCaml array, but will grow       
 automatically on get or set outside the current size of the         
 array.                                                              
                                                                     
 The interface is the same as the standard OCaml array where         
 applicable (and implemented).                                       
*********************************************************************
* Array operations. 
* The type of growable arrays 
* The default value to a new element of the growable array 
 A default value 
 A function given an index to generate a default value 
* [GrowArray.make n x] returns a fresh growable array of size
   at least [n] with default value specified by [x].

   Raise [Invalid_argument] if [n < 0] or [n > Sys.max_array_length]. 
* [GrowArray.num_alloc_index a] returns the number of allocated entries in 
 * the array *
* [GrowArray.max_init_index a] returns the maximum index to
    which has been written.

    Returns -1 if no writes have been made. 
* [GrowArray.get a n] returns the element number [n] of grow array [a].

   Raise [Invalid_argument "Array.get"]  if [n] is outside the range
   of the underlying array. 
* [GrowArray.set a n x] modifies grow array [a] in place, replacing
   element number [n] with [x].

   Raise [Invalid_argument "Array.set"] if [n] is outside the range
   of the underlying array. 
* [GrowArray.copy a] returns a copy of [a], that is, a fresh array
   containing the same elements as [a]. 
* [GrowArray.copy a f] returns a deep copy of [a] using f to
    copy elements of [a]. 
* [GrowArray.d_growarray sep f () a] creates a {!Pretty.doc} for growable
   array a using separator sep and element printer f. 
* Given a growable array, produce a thunk that later restores it to its
    current value 

  $ Id$


type 'a t

type 'a fill =
    Elem of 'a
  | Susp of (int -> 'a)

val make : int -> 'a fill -> 'a t

val num_alloc_index: 'a t -> int

val max_init_index : 'a t -> int

val reset_max_init_index : 'a t -> unit
* [ GrowArray.reset_init a ] resets the max_init_index . You should probably 
    use [ GrowArray.clear a ] instead if you also want to delete the contents .
   use [GrowArray.clear a] instead if you also want to delete the contents. *)

val getg : 'a t -> int -> 'a
* [  a n ] returns the element number [ n ] of array [ a ] . 
    The first element has number 0 . 
    The last element has number [ GrowArray.length a - 1 ] . 

    If [ n ] is outside the range 0 to [ ( GrowArray.max_init_index a ) ] , 
    then the array grows to at least [ n ] and yields the default value .
   The first element has number 0.
   The last element has number [GrowArray.length a - 1].

   If [n] is outside the range 0 to [(GrowArray.max_init_index a)],
   then the array grows to at least [n] and yields the default value. *)

val setg : 'a t -> int -> 'a -> unit
* [ GrowArray.setg a n x ] modifies array [ a ] in place , replacing 
    element number [ n ] with [ x ] . 

    If [ n ] is outside the range 0 to [ ( GrowArray.max_init_index a ) ] , 
    then the array grows to at least [ n ] and yields the default value .
   element number [n] with [x].

   If [n] is outside the range 0 to [(GrowArray.max_init_index a)],
   then the array grows to at least [n] and yields the default value. *)

val get : 'a t -> int -> 'a

val set : 'a t -> int -> 'a -> unit
        
val clear: 'a t -> unit 
* [ GrowArray.clear a ] clears the contents of the array and sets 
    max_init_index to -1 .   Suspension thunks will be rerun to regenerate the 
    initial values of the array .
   max_init_index to -1.  Suspension thunks will be rerun to regenerate the 
   initial values of the array. *)

val copy : 'a t -> 'a t

val deep_copy : 'a t -> ('a -> 'a) -> 'a t

val iter : ('a -> unit) -> 'a t -> unit
* [ GrowArray.iter f a ] applies function [ f ] in turn to all 
    the elements of [ a ] .   It is equivalent to 
    [ f  ) ; f a.(1 ) ; ... ; f a.(GrowArray.length a - 1 ) ; ( ) ] .
   the elements of [a].  It is equivalent to
   [f a.(0); f a.(1); ...; f a.(GrowArray.length a - 1); ()]. *)

val iteri : (int -> 'a -> unit) -> 'a t -> unit
* Same as { ! GrowArray.iter } , but the 
    function is applied to the index of the element as first argument , 
    and the element itself as second argument .
   function is applied to the index of the element as first argument,
   and the element itself as second argument. *)

val iter2 : (int -> 'a -> 'b -> unit) -> 'a t -> 'b t -> unit
* Same as { ! GrowArray.iteri } , but the function is applied to two arrays . 
   [ iter2 f a b ]   is equivalent to 
   [ f 0  )  ) ; f 1 a.(1 ) b.(1 ) ; ... ;   f n a.(n ) b.(n ) ; ( ) ] 
   where n is the larger of ( max_init_index a ) or ( max_init_index b ) . 
   The shorter array will grow to match the longer .
  [iter2 f a b]  is equivalent to
  [f 0 a.(0) b.(0); f 1 a.(1) b.(1); ...;  f n a.(n) b.(n); ()]
  where n is the larger of (max_init_index a) or (max_init_index b).
  The shorter array will grow to match the longer.*)

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
* [ GrowArray.fold_left f x a ] computes 
    [ f ( ... ( f ( f x  ) ) a.(1 ) ) ... ) a.(n-1 ) ] , 
    where [ n ] is the length of the array [ a ] .
   [f (... (f (f x a.(0)) a.(1)) ...) a.(n-1)],
   where [n] is the length of the array [a]. *)

val fold_lefti : ('a -> int -> 'b -> 'a) -> 'a -> 'b t -> 'a
* [ GrowArray.fold_lefti f x a ] computes 
    [ f ( ... ( f ( f x 0  ) ) 1 a.(1 ) ) ... ) ( n-1 ) a.(n-1 ) ] , 
    where [ n ] is the length of the array [ a ] .
   [f (... (f (f x 0 a.(0)) 1 a.(1)) ...) (n-1) a.(n-1)],
   where [n] is the length of the array [a]. *)

val fold_right : ('b -> 'a -> 'a) -> 'b t -> 'a -> 'a
* [ GrowArray.fold_right f a x ] computes 
    [ f  ) ( f a.(1 ) ( ... ( f a.(n-1 ) x ) ... ) ) ] , 
    where [ n ] is the length of the array [ a ] .
   [f a.(0) (f a.(1) ( ... (f a.(n-1) x) ...))],
   where [n] is the length of the array [a]. *)

val d_growarray : Pretty.doc -> (int -> 'a -> Pretty.doc) -> unit -> 'a t
                             -> Pretty.doc


val restoreGA: ?deepCopy:('a -> 'a) -> 'a t -> unit -> unit

val find: 'a t -> ('a -> bool) -> int option
* Returns the index of the first element in the array that satisfies the 
     predicate , or None if there is no such element
    predicate, or None if there is no such element *)
