type bit_set_32 = int;;

let max_size_bit_set_32 = 32;;

let empty () : bit_set_32 = 0
;;

let create (i : int) : bit_set_32 =
    assert ((0 <= i) && (i < max_size_bit_set_32));
    1 lsl i
;;

let ( << ) = ( lsl );;
let ( >> ) = ( lsr );;

let copy (b : bit_set_32) : bit_set_32 =
    b + 0 (* enough ? *)
;;
let clone = copy;;

let set (b : bit_set_32) (n : int) : bit_set_32 =
    b lor (1 lsl n)
;;

let add = set;;

let unset (b : bit_set_32) (n : int) : bit_set_32 =
    b land (lnot (1 lsl n))
;;

let remove = unset;;

let put (b : bit_set_32) (p : bool) (n : int) : bit_set_32 =
    if p then set b n else unset b n
;;

let is_set (b : bit_set_32) (n : int) : bool =
    let i = (b land (1 lsl n)) lsr n in
    i = 1
;;

let contains_int = is_set;;
let is_in = is_set;;

let toggle (b : bit_set_32) (n : int) : bit_set_32 =
    put b (not (is_set b n)) n
;;

let compare (b1 : bit_set_32) (b2 : bit_set_32) : int =
    Pervasives.compare b1 b2
;;

let equals (b1 : bit_set_32) (b2 : bit_set_32) : bool =
    b1 = b2
;;

let count (b : bit_set_32) : int =
    let s = ref 0 in
    for n = 0 to max_size_bit_set_32 - 1 do
        if is_set b n then incr s
    done;
    !s
;;

let length = count;;

let bit_set_32_to_list (b : bit_set_32) : (int list) =
    let list_of_b = ref [] in
    for n = 0 to max_size_bit_set_32 - 1 do
        if is_set b n then
        list_of_b := n :: !list_of_b
    done;
    List.rev (!list_of_b)
;;

let bit_set_32_from_list (list_of_b : int list) : bit_set_32 =
    let b = ref (empty()) in
    List.iter (fun i -> b := add !b i) list_of_b;
    !b
;;

let bit_set_32_iter (f : int -> unit) (b : bit_set_32) : unit =
    List.iter f (bit_set_32_iter_to_list b)
;;

let bit_set_32_to_string (b : bit_set_32) : string =
    let list_of_b = bit_set_32_to_list b in
    match List.length list_of_b with
    | 0 -> "{}"
    | 1 -> "{" ^ (string_of_int (List.hd list_of_b)) ^ "}"
    | _ -> begin
        let s = ref ("{" ^ (string_of_int (List.hd list_of_b))) in
        List.iter (fun i -> s := !s ^ ", " ^ (string_of_int i)) (List.tl list_of_b);
        !s ^ "}"
    end
;;

let print_bit_set_32 (b : bit_set_32) : unit =
    print_endline (bit_set_32_to_string b)
;;

let complementaire (b : bit_set_32) : bit_set_32 =
    lnot b
;;

let intersection (b1 : bit_set_32) (b2 : bit_set_32) : bit_set_32 =
    b1 land b2
;;

let union (b1 : bit_set_32) (b2 : bit_set_32) : bit_set_32 =
    b1 lor b2
;;

let contains (b1 : bit_set_32) (b2 : bit_set_32) : bool =
    (union b1 b2) = b2
;;

let difference (b1 : bit_set_32) (b2 : bit_set_32) : bit_set_32 =
    intersection b1 (complementaire b2)
;;

let difference_sym (b1 : bit_set_32) (b2 : bit_set_32) : bit_set_32 =
    b1 lxor b2
;;

print_bit_set_32 (empty());;

let b1 = bit_set_32_from_list [0; 12]
and b2 = bit_set_32_from_list [1; 3; 6]
and b3 = bit_set_32_from_list [0; 3; 6; 17]
;;

print_bit_set_32 b1;;
print_bit_set_32 b2;;
print_bit_set_32 b3;;

(is_in b1 3);;
(is_in b2 3);;
(is_in b3 3);;

(is_in b1 0);;
(is_in b2 0);;
(is_in b3 0);;

print_bit_set_32 (add b1 20);;
print_bit_set_32 (add b2 20);;
print_bit_set_32 (add b3 20);;

print_bit_set_32 (remove b1 3);;
print_bit_set_32 (remove b2 3);;
print_bit_set_32 (remove b3 3);;

length b1;;
length b2;;
length b3;;

print_bit_set_32 (complementaire b1);;
print_bit_set_32 (complementaire b2);;
print_bit_set_32 (complementaire b3);;

print_bit_set_32 (complementaire (union (union b1 b2) b3));;

print_bit_set_32 (union b1 b2);;
print_bit_set_32 (union b1 b3);;
print_bit_set_32 (union b2 b3);;

contains b1 b2;;
contains b1 b3;;
contains b1 (intersection b1 b3);;
contains (intersection b1 b3) b1;;
contains b1 (union b1 b3);;
contains b2 b3;;

print_bit_set_32 (intersection b1 b2);;
print_bit_set_32 (intersection b1 b3);;
print_bit_set_32 (intersection b2 b3);;

print_bit_set_32 (difference b1 b2);;
print_bit_set_32 (difference b1 b3);;
print_bit_set_32 (difference b2 b3);;

print_bit_set_32 (difference_sym b1 b2);;
print_bit_set_32 (difference_sym b1 b3);;
print_bit_set_32 (difference_sym b2 b3);;

let time (n : int) (f : unit -> 'a) : float =
    let t = Sys.time() in
    for _ = 0 to n-1 do
        ignore (f ());
    done;
    let delta_t = Sys.time() -. t in
    let t_moyen = delta_t /. (float_of_int n) in
    Printf.printf "    Temps en secondes: %fs\n" t_moyen;
    flush_all ();
    t_moyen
;;

Random.self_init();;

let random_int_0_31 () =
    Random.int 32
;;

let test_bit_set_32 n n1 n2 () =
    let b = ref (empty ()) in
    for _ = 0 to n do
        let nb_ajout = Random.int n1 in
        let nb_retrait = Random.int n2 in
        for i = 0 to nb_ajout + nb_retrait do
            let n = random_int_0_31 () in
            if i mod 2 = 0 then
                b := add !b n
            else
                b := remove !b n;
        done
    done;
    length !b
;;

test_bit_set_32 100 20 10 ();;

let test_boolarray n n1 n2 () =
    let b = Array.make max_size_bit_set_32 false in
    for _ = 0 to n do
        let nb_ajout = Random.int n1 in
        let nb_retrait = Random.int n2 in
        for i = 0 to nb_ajout + nb_retrait do
            let n = random_int_0_31 () in
            if i mod 2 = 0 then
                b.(n) <- true
            else
                b.(n) <- false
        done;
    done;
    Array.fold_left (+) 0 (Array.map (fun x -> if x then 1 else 0) b)
;;

test_boolarray 100 20 10 ();;

module Int = struct
   type t = int
   let compare = compare
 end;;

module Int32Set = Set.Make(Int);;

let test_Int32Set n n1 n2 () =
    let b = ref (Int32Set.empty) in
    for _ = 0 to n do
        let nb_ajout = Random.int n1 in
        let nb_retrait = Random.int n2 in
        for i = 0 to nb_ajout + nb_retrait do
            let n = random_int_0_31 () in
            if i mod 2 = 0 then
                b := Int32Set.add n !b
            else
                b := Int32Set.remove n !b
        done;
    done;
    Int32Set.cardinal !b
;;

test_Int32Set 100 20 10 ();;

time 500 (test_bit_set_32 1000 30 20);;

time 500 (test_boolarray 1000 30 20);;

time 500 (test_Int32Set 1000 30 20);;

time 500 (test_bit_set_32 500 100 110);;

time 500 (test_boolarray 500 100 110);;

time 500 (test_Int32Set 500 100 110);;