module type INTERFACE = sig
    
    type 'a t

    val init : int -> (int -> 'a) -> 'a t
    val length : 'a t -> int
    val of_list : 'a list -> 'a t
    val add : 'a t -> 'a -> unit
    val random : 'a t -> 'a
    val reset : 'a t -> unit  
    val set_state : 'a t -> Random.State.t -> unit
  end
  
module IMPLEMENTATION = struct
    
    type 'a t = {
        mutable length : int; 
        mutable left : int;
        array : 'a array;
        mutable state : Random.State.t;
      }

    let init len f =
      let array = Array.init len f in
      {
        array = array;
        length = len;
        left = len;
        state = Random.get_state ();
      }
      
    let of_list list = 
      let array = Array.of_list list in
      let len = Array.length array in
      {
        array = array;
        length = len;
        left = len;
        state = Random.get_state ();
      }
    
    let length t = t.length
    
    let add t x = 
      let len = t.length in
      t.array.(len) <- x;
      t.length <- len + 1;
      if len = t.left then 
        t.left <- len + 1
    
    let random t =
      if t.left <= 0 then raise Not_found;
      let pos = Random.State.int t.state t.left in
      let tab = t.array in
      let len = t.left-1 in 
(*      Printf.fprintf stderr "SWAP(%d)(%d)%!" pos len; *)
      let x = tab.(pos) in
      tab.(pos) <- tab.(len);
      tab.(len) <- x;
      t.left <- len;
      x
      
    let reset t = 
      t.left <- t.length

    let set_state t state = t.state <- state
      
  end

include (IMPLEMENTATION : INTERFACE)