(*

 * ExtLib Testing Suite

 * Copyright (C) 2004 Janne Hellsten

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public

 * License as published by the Free Software Foundation; either

 * version 2.1 of the License, or (at your option) any later version,

 * with the special exception on linking described in file LICENSE.

 *

 * This library is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with this library; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 *)

open ExtList

module B = BitSet

let biased_rnd_28 () = 

  let n_bits = [| 4; 8; 16; 28 |] in

  let n = n_bits.(Random.int (Array.length n_bits)) in

  Random.int (1 lsl n)

let popcount n = 

  let p = ref 0 in

  for i = 0 to 29 do

    if n land (1 lsl i) <> 0 then

      incr p

  done;

  !p

let set_bitset s n = 

  for i = 0 to 29 do

    if (n land (1 lsl i)) <> 0 then

      B.set s i

  done;

  assert (popcount n = B.count s)

let bitset_of_int n = 

  assert (n <= (1 lsl 29));

  let s = B.create 30 in

  set_bitset s n;

  s

let int_of_bitset s = 

  let n = ref 0 in

  for i = 0 to 29 do

    if B.is_set s i then

      n := !n lor (1 lsl i)

  done;

  !n

let bitset_of_int_scale n scl = 

  assert (n <= (1 lsl 29));

  let s = B.create 30 in

  for i = 0 to 29 do

    if (n land (1 lsl i)) <> 0 then

      B.set s (i*scl)

  done;

  assert (popcount n = B.count s);

  s

let int_of_bitset_scale s scl = 

  let n = ref 0 in

  for i = 0 to 29 do

    if B.is_set s (i*scl) then

      n := !n lor (1 lsl i)

  done;

  !n

let test_rnd_creation () =

  for i = 0 to 255 do

    let r1 = biased_rnd_28 () in

    let s = bitset_of_int r1 in

    let c = B.copy s in

    assert (int_of_bitset s = r1);

    assert (c = s);

    assert (B.compare c s = 0);

    B.unite c s;

    assert (c = s);

    B.intersect c (B.empty ());

    assert (B.count c = 0);

  done

let test_intersect () = 

  for i = 0 to 255 do

    let s = bitset_of_int (biased_rnd_28 ()) in

    B.intersect s (B.empty ());

    assert (B.count s = 0)

  done

let test_diff () = 

  for i = 0 to 255 do

    let r = biased_rnd_28 () in

    let s = bitset_of_int r in

    if r <> 0 then

      assert (B.count s <> 0);

    assert (B.count ((B.diff s s)) = 0);

  done

let test_sym_diff () =

  for i = 0 to 255 do

    let s = (Random.int 3)+1 in

    let r1 = biased_rnd_28 () in

    let r2 = biased_rnd_28 () in

    let s1 = bitset_of_int_scale r1 s in

    let s2 = bitset_of_int_scale r2 s in

    assert (int_of_bitset_scale (bitset_of_int_scale r1 s) s = r1);

    assert (int_of_bitset_scale (B.sym_diff s1 s2) s = r1 lxor r2);

    assert (int_of_bitset_scale (B.sym_diff s2 s1) s = r1 lxor r2);

    assert (B.count (B.sym_diff s1 s1) = 0);

    assert (B.count (B.sym_diff s2 s2) = 0);

  done

let test_compare () =

  assert (B.compare (B.empty ()) (B.empty ()) = 0);

  for i = 0 to 255 do

    let r1 = biased_rnd_28 () in

    let r2 = biased_rnd_28 () in

    let s1 = bitset_of_int r1 

    and s2 = bitset_of_int r2 in

    let sr = B.compare s1 s2

    and ir = compare r1 r2 in

    assert (sr = ir);

    assert (B.compare s1 s1 = 0);

    assert (B.compare s2 s2 = 0)

  done;

  for i = 0 to 255 do

    let scl = (Random.int 15)+1 in

    let r1 = biased_rnd_28 () in

    let r2 = biased_rnd_28 () in

    let s1 = bitset_of_int_scale r1 scl

    and s2 = bitset_of_int_scale r2 scl in

    let sr = B.compare s1 s2

    and ir = compare r1 r2 in

    assert (sr = ir)

  done;

  for i = 1 to 255 do

    let s1 = bitset_of_int (i-1) in

    let s2 = bitset_of_int i in

    assert (B.compare s1 s2 = -1)

  done;

  for i = 1 to 255 do

    let s1 = bitset_of_int (i-1) in

    let s2 = bitset_of_int i in

    assert (B.compare s1 s2 = -1)

  done

module BSSet = Set.Make (struct type t = BitSet.t let compare = B.compare end)

let test_compare_2 () = 

  let nums = List.init 256 Std.identity in

  let num_set = 

    List.fold_left (fun acc e -> BSSet.add (bitset_of_int e) acc) BSSet.empty nums in

  List.iter

    (fun e -> 

       let bs = bitset_of_int e in

       assert (BSSet.mem bs num_set)) nums

let test_compare_3 () = 

  for i = 0 to 63 do

    for j = 0 to 63 do

      let b1 = B.create ((Random.int 128)+32) in

      let b2 = B.create ((Random.int 128)+32) in

      set_bitset b1 i;

      set_bitset b2 j;

      assert (B.compare b1 b2 = compare i j)

    done

  done

let test_empty () = 

  for len = 0 to 63 do

    let s = B.empty () in

    for i = 0 to len do 

      assert (not (B.is_set s i));

      B.set s i

    done;

    assert (not (B.is_set s (len+1)));

    for i = 0 to len do 

      assert (B.is_set s i)

    done

  done

let test_exceptions () = 

  let expect_exn f =

    try 

      f ();

      false (* Should've raised an exception! *)

    with B.Negative_index _ -> true in

  let s = B.create 100 in

  assert (expect_exn (fun () -> B.set s (-15)));

  assert (expect_exn (fun () -> B.unset s (-15)));

  assert (expect_exn (fun () -> B.toggle s (-15)));

  assert (expect_exn 

            (fun () ->

               let s = B.create 8 in

               B.is_set s (-19)))

module IS = Set.Make (struct type t = int let compare = compare end)

let set_of_int n = 

  let rec loop accu i =

    if i < 30 then

      if ((1 lsl i) land n) <> 0 then

        loop (IS.add i accu) (i+1)

      else 

        loop accu (i+1)

    else accu in

  loop IS.empty 0

let int_of_set s = 

  IS.fold (fun i acc -> (1 lsl i) lor acc) s 0

let test_set_opers () = 

  let rnd_oper () = 

    match Random.int 3 with

      0 -> (IS.inter, B.inter)

    | 1 -> (IS.diff, B.diff)

    | 2 -> (IS.union, B.union)

    | _ -> assert false in

  for i = 0 to 255 do

    let r1 = biased_rnd_28 () in

    let r2 = biased_rnd_28 () in

    let s1 = set_of_int r1

    and s2 = set_of_int r2

    and bs1 = bitset_of_int r1 

    and bs2 = bitset_of_int r2 in

    assert (int_of_set s1 = r1);

    assert (int_of_set s2 = r2);

    assert (int_of_bitset bs1 = r1);

    assert (int_of_bitset bs2 = r2);

    let (isop,bsop) = rnd_oper () in

    let is = isop s1 s2 

    and bs = bsop bs1 bs2 in

    let is_int = int_of_set is in

    let bs_int = int_of_bitset bs in

    assert (is_int = bs_int);

  done

let test_unite () =

  for i = 0 to 255 do

    let r1 = biased_rnd_28 () in

    let s = bitset_of_int r1 in

    let c = B.copy s in

    assert (int_of_bitset s = r1);

    let pop = B.count c in

    B.unite c (B.empty ());

    assert (B.count c = pop);

  done

let test_intersect_2 () =

  for i = 0 to 255 do

    let r1 = biased_rnd_28 () in

    let s = bitset_of_int r1 in

    let c = B.copy s in

    assert (int_of_bitset s = r1);

    B.intersect c (B.empty ());

    assert (B.count c = 0);

  done

let test_differentiate () = 

  for i = 0 to 255 do

    let r1 = biased_rnd_28 () in

    let s = bitset_of_int r1 in

    let d = B.copy s in

    B.differentiate d s;

    assert (B.count d = 0);

    for j = 0 to 32 do

      B.set s (Random.int 256)

    done;

    let d = B.copy s in

    B.differentiate d (B.empty ());

    assert (B.count s = B.count d);

    assert (B.compare d s = 0);

    B.differentiate d s;

    assert (B.count d = 0);

  done

(* TODO *)

let test_differentiate_sym () = 

  for i = 0 to 255 do

    let r1 = biased_rnd_28 () in

    let r2 = biased_rnd_28 () in

    let s = bitset_of_int r1 in

    let d = B.copy s in

    B.differentiate_sym d s;

    assert (B.count d = 0);

    for j = 0 to 32 do

      B.set s (Random.int 256)

    done;

    let d = B.copy s in

    B.differentiate_sym d (B.empty ());

    assert (B.count s = B.count d);

    assert (B.compare d s = 0);

    B.differentiate_sym d s;

    assert (B.count d = 0);

    let s1 = bitset_of_int r1 

    and s2 = bitset_of_int r2 in

    let d1 = B.copy s1 in

    B.differentiate_sym d1 s2;

    assert (r1 lxor r2 = int_of_bitset d1);

  done

let test_bs_1 () = 

  let b = BitSet.empty () in

  BitSet.set b 8;

  BitSet.set b 9;

  assert (not (BitSet.is_set b 7));

  assert (BitSet.is_set b 8);

  assert (BitSet.is_set b 9);

  assert (not (BitSet.is_set b 10));

  ()

let test_enum_1 () = 

  let b = BitSet.empty () in

  BitSet.set b 0;

  BitSet.set b 1;

  let e = BitSet.enum b in

  let a = Enum.get e in

  let b = Enum.get e in

  assert (Option.get a = 0);

  assert (Option.get b = 1);

  ()

let test_enum_2 () = 

  let n = 13 in

  let b = BitSet.empty () in

  for i = 0 to n do

    BitSet.set b i

  done;

  let e = BitSet.enum b in

  for i = 0 to n do

    let a = Enum.get e in

    match a with

      Some v -> assert (v = i)

    | None -> assert false

  done;

  assert (Enum.get e = None);

  ()

let test_enum_3 () = 

  let b = BitSet.empty () in

  BitSet.set b 9;

  BitSet.set b 10;

  let e = BitSet.enum b in

  let i = Enum.get e in

  let j = Enum.get e in

  assert (Option.get i = 9);

  begin

    match j with

      Some v -> 

        assert (v = 10);

    | None -> 

        assert false (* Should NOT come here! *)

  end;

  assert (Enum.get e = None);

  ()

(* Bug reported by Pascal Zimmer on Feb 27, 2007.  The latter assert

   returned None when it should've returned Some 9. *)

let test_enum_regr_pz () = 

  let b = BitSet.empty () in

  BitSet.set b 8;

  BitSet.set b 9;

  let e = BitSet.enum b in

  let i = Enum.get e in

  let j = Enum.get e in

  assert (Option.get i = 8);

  begin

    match j with

      Some v -> 

        assert (v = 9);

    | None -> 

        assert false (* Should NOT come here! *)

  end;

  ()

let () =

  Util.register "BitSet" [

    "basic", test_bs_1;

    "enum_1", test_enum_1;

    "enum_2", test_enum_2;

    "enum_3", test_enum_3;

    "enum_regr_pz", test_enum_regr_pz;

    "intersect", test_intersect;

    "diff", test_diff;

    "sym_diff", test_sym_diff;

    "rnd_creation", test_rnd_creation;

    "empty", test_empty;

    "exceptions", test_exceptions;

    "compare", test_compare;

    "compare_2", test_compare_2;

    "compare_3", test_compare_3;

    "set_opers", test_set_opers;

    "unite",test_unite;

    "intersect_2",test_intersect_2;

    "differentiate",test_differentiate;

    "differentiate_sym", test_differentiate_sym;

  ]