(** Persistent array implementation based on Baker's Algorithm.
  @author Victor Nicollet *)

(** Persistent arrays support all elementary operations in 
  O(1) time. Read operations actually perform in amortized time,
  with a slight penalty for backtracking (linear in the number of
  undone modifications). 

  The memory footprint is linear in the number of stored elements
  plus the number of modifications (that can be undone to retrieve
  an older version from the new one). Note that extracting a sub-array 
  works in linear time by referencing a subset of indices, which may
  prevent garbage collection. If a sub-array is to be kept for
  a longer time, it could be interesting to use [copy] to
  trim off all unnecessary elements. *)

(** The type of a persistent array.*)
type 'a t 

(** Set a value. [set arr i x] sets the element [i]
  of array [arr] to the value [x]. Constant-time. *)
val set : 'a t -> int -> 'a -> 'a t

(** Extract a sub-array. [sub arr i l] extracts the array 
  containing [l] elements of [arr] starting at index [i]. 
  Constant-time. *)
val sub : 'a t -> int -> int -> 'a t

(** Swap two elements. [swap arr i j] swaps elements [i]
  and [j] of array [arr]. Constant-time. *)
val swap : 'a t -> int -> int -> 'a t

(** Get a value. [get arr i] returns the element 
  [i] of array [arr]. Constant amortized time when accessing 
  the last created array (but possibly longer otherwise). *)
val get : 'a t -> int -> 'a

(** Return the length of an array. [length arr] returns the
  number of elements of array [arr]. Constant time. *)
val length : 'a t -> int

(** Construct from an imperative array. Linear time. *)
val of_array : 'a array -> 'a t

(** Return equivalent imperative array. Linear time. *)
val to_array : 'a t -> 'a array

(** Same as [Array.make]. *)
val make : int -> 'a -> 'a t

(** Same as [Array.init]. *)
val init : int -> (int -> 'a) -> 'a t

(** Same as [Array.map]. *)
val map : ('a -> 'b) -> 'a t -> 'b t

(** Same as [Array.mapi]. *)
val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t

(** Create sa copy of an array. This is mostly useful to 
  trim the elements kept by [sub]. *)
val copy : 'a t -> 'a t

(** Same as [Array.iter]. *)
val iter : ('a -> 'b) -> 'a t -> unit

(** Same as [Array.iteri]. *)
val iteri : (int -> 'a -> 'b) -> 'a t -> unit

(** Same as [Array.fill]. *)
val fill : 'a t -> int -> int -> 'a -> 'a t

(** Same as [Array.blit]. *)
val blit : 'a t -> int -> 'a t -> int -> int -> 'a t

(** Same as [Array.fold_left]. *)
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a

(** Same as [Array.fold_right]. *)
val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b