module OrderedInt : Set.ORDERED =
struct
  type elem = Elem of int

  let cons e = Elem e

  let eq = (=)

  let lt = (<)

  let leq = (<=)
end

(* it's separate from SetTester because, for certain Set, you
   might have special Set elements and different generator 
   although way of testing the Set would be the same         *)
module IntGenerator : Set.GENERATOR =
  struct

    (* well, I don't really undrestand why doens't it want to compile 
       if defined as in comments. I think that's another reason to 
       complain :P  *)
    module O = (* (OrderedInt : Set.ORDERED with type elem = int) *)
    struct
      type elem = int

      let eq = (=)
      let lt = (<)
      let leq = (<=)
    end (* O *)

    type p =
        Const
      | Sequential of bool
      | Random of float

    let rec generate_list j =
      if j > 1 then
        List.rev((j)::(List.rev (generate_list (j - 1))))
      else if j = 1 then [1] else []

    let gen_parametrised_list = function _ -> function _ -> []

  end


module SetTester (G : Set.GENERATOR) (SF : Set.SET_FUNCTOR) =
struct

  module S = SF(G.O)

  let list = G.generate_list 89

  type elem = S.elem

  let empty = S.empty()

  (* E L E M E N T ' S   G E N E R A T O R S *)

  (* integers from i to j *)
  let rec list_i_to_j i j =
    if j > i then
      List.rev(j::(List.rev (list_i_to_j i (j - 1))))
    else if i = j then [i] else []

  let init_random =
    Random.self_init()

  let random_int_from_i_to_j i j =
    i + Random.int (j - i)

  let rec list_of_n_rand_from_i_to_j n i j =
    let rec pom k a =
      if k > 0 then
        pom (k-1) ((random_int_from_i_to_j i j)::a)
      else a
    in
      pom n []

  (* gives true with propability s / r *)
  let prop_s_div_r s r =
    if s >= r then
      true
    else
      if Random.int r < s then
        true
      else
        false

  (* adds k times element min to list l in random places *)
  let add_k_min_to_l k min l =
    let (_, _, w) =
      List.fold_left
        (* f *)
        (fun (r, s, w) h ->
           if prop_s_div_r s r
         then
           (r - 1, s - 1, min::h::w)
           else
             (r - 1, s, h::w))
        (* a *)
        (List.length l, k, [])
        (* l *)
        l
    in
      List.rev w



  (* this module is parametrized *)
  (* feel free to change the default values *)
  (* though they can be changed dynamically *)

  (* P A R A M E T E R S *)

  (* elem and min need to be of same type 'a *)
  let min = ref 0
  (* min should be only used with minimal key *)
  let elem = ref 1
  (* defines the smallest key in the list *)
  let min_key = ref 0

  let num_of_min = ref 100

  let num_of_other = ref 1000

  let num_of_delete = ref 1000

  (* please remember, that the same list is used for *)
  (* either speed and correctness testing *)

  let keys = ref []

  let key_gen () =
    begin
      init_random;
      keys :=
        ( add_k_min_to_l
            !num_of_min
            !min_key
            ( list_of_n_rand_from_i_to_j !num_of_other (!min_key + 1) (!min_key + !num_of_other)) );
    end

  let insert_elements l =
    List.fold_left
      (* f *)
      (fun s h -> S.insert s h )
      (* a *)
      (S.empty())
      (* l *)
      l

  let divide_elements size_of_first =
    let (elem1, elem2, _) =
      List.fold_left
        (* f *)
        (fun (e1, e2, c) h ->
           if c > 0 then
             (h::e1, e2, c - 1)
           else
             (e1, h::e2, c) )
        (* a *)
        ([], [], size_of_first)
        (* l *)
        list
    in (elem1, elem2)

  let correct_insert_member s e =
    let (inserted, not_inserted) =
      divide_elements (List.length list)
    in
    let s = insert_elements inserted
    in
    let correct_inserted =
      List.fold_left
        (* f *)
        (fun a h ->
           if a then
             S.member s h
           else false)
        (* a *)
        true
        (* l *)
        inserted
    in
      if correct_inserted then
        List.fold_left
          (* f *)
          (fun a h ->
             if a then
               not (S.member s h)
             else false)
          (* a *)
          true
          (* l *)
          not_inserted
      else
        false

end;;