open Printf
open OUnit

let rec random_string ?(acc = []) len =
  if len > 0 then
    random_string ~acc:(Char.chr (Random.int 255) :: acc) (len-1)
  else
    let s = String.create (List.length acc) in
    let i = ref 0 in
      List.iter (fun c -> s.[!i] <- c; incr i) acc;
      s

let test_empty_props () =
  assert_equal 0 (Rope.length (Rope.empty))

let string_conversions () =
  let roundtrip x =
    assert_equal ~printer:(fun x -> x) ~msg:"Rope.to/of_string round-trip"
      x (Rope.to_string (Rope.of_string x))
  in
    List.iter roundtrip [""; "foo"; String.make 1000 'a']

let test_is_empty () =
  let test r =
    assert_bool
      (sprintf "\"%s\" should be empty" (String.escaped (Rope.to_string r)))
      (Rope.is_empty r) in
  let test_not r = assert_bool "should not be empty" (not (Rope.is_empty r)) in
    test Rope.empty;
    test (Rope.of_string "");
    test (Rope.make 0 'a');
    test_not (Rope.make 1 'a');
    test_not (Rope.of_string "a")

let test_length () =
  let test_l (len, r) =
    assert_equal ~printer:string_of_int len (Rope.length r)
  in
    List.iter test_l
      [0, Rope.empty; 1, Rope.of_string "x";
       1000, Rope.make 1000 'x']

let test_concat () =
  let test (s, l, r) =
    let c = Rope.concat l r in
      assert_equal ~printer:string_of_int ~msg:"Wrong length"
        (Rope.length l + Rope.length r) (Rope.length c);
      assert_equal ~printer:(fun s -> s) s (Rope.to_string c)
  in
    List.iter test
      ["", Rope.empty, Rope.empty;
       "a", Rope.empty, Rope.of_string "a";
       "a", Rope.of_string "a", Rope.empty;
       "ab", Rope.of_string "a", Rope.of_string "b";
       (String.make 1000 'a' ^ String.make 1000 'b',
        Rope.make 1000 'a', Rope.make 1000 'b');
       (String.make 100000 'a' ^ String.make 10000 'b',
        Rope.make 100000 'a', Rope.make 10000 'b')]

let test_get () =
  let test (s, r) =
    for i = 0 to String.length s - 1 do
      assert_equal s.[i] (Rope.get i r)
    done
  in
    for i = 0 to 1000 do
      let s1 = random_string 100 in
      let s2 = random_string 100 in
        List.iter test
          [s1, Rope.of_string s1; s2, Rope.of_string s2;
           s1 ^ s2, Rope.concat (Rope.of_string s1) (Rope.of_string s2)]
    done

let test_set () =
  let test r =
    let lim = Rope.length r - 1 in
      for i = 0 to lim do
        let r' = Rope.set i 'y' r in
          for j = 0 to lim do
             assert_equal
              ~msg:"length of modified rope"
              ~printer:string_of_int
              (lim + 1) (Rope.length r');
            if j <> i then assert_equal (Rope.get j r) (Rope.get j r')
            else assert_equal 'y' (Rope.get j r')
          done
      done
  in
    List.iter test
      [Rope.make 100 'x';
       Rope.of_string (String.concat "" (Array.to_list (Array.make 700 "x")));
       Array.fold_left (fun r x -> Rope.concat r (Rope.of_string x))
         Rope.empty (Array.init 100 string_of_int)]

let test_sub () =
  let test (sub, s, m, n) =
    let x = Rope.to_string (Rope.sub m n (Rope.of_string s)) in
    let msg = sprintf "sub %d %d" m n in
      assert_equal
        ~msg:(msg ^ " length ->")
        ~printer:string_of_int (String.length sub) (String.length x);
      assert_equal
        ~msg:(msg ^ " contents ->")
        ~printer:String.escaped sub x in
  let size = 10000 in
  let half_size = size / 2 in
  let s = Array.init 3 (fun _ -> random_string size) in
    List.iter test [
      "", "abc", 0, 0;
      "", "abc", 1, 0;
      "", "abc", 3, 0;
      "a", "abc", 0, 1;
      "a", "bac", 1, 1;
      "a", "bca", 2, 1;
      "a", String.make 1000 'x' ^ "a", 1000, 1;

      s.(0), s.(0) ^ s.(1) ^ s.(2), 0, size;

      String.sub s.(0) half_size half_size ^ String.sub s.(1) 0 half_size,
      s.(0) ^ s.(1) ^ s.(2), half_size, size;

      String.sub s.(0) half_size half_size ^ s.(1) ^ String.sub s.(2) 0 half_size,
      s.(0) ^ s.(1) ^ s.(2), half_size, 2 * size
    ];
    List.iter (fun (s, m, n) ->
                 assert_raises Rope.Out_of_bounds
                   ~msg:(sprintf "sub %d %d \"%s\"" m n (String.escaped s))
                   (fun () -> Rope.sub m n (Rope.of_string s)))
      ["", 1, 0; "a", 1, 1; "abc", -1, 0; "abc", 1, -1;
       "abc", 0, 4; (String.make 10000 'x'), 9000, 1001]

let test_insert () =
  let test (s, into, off) =
    let r = Rope.of_string into in
    let r' = Rope.insert off (Rope.of_string s) r in
    let len = String.length s in
    let tlen = String.length into in
      assert_equal (len + String.length into) (Rope.length r');
      assert_equal ~printer:String.escaped
        (Rope.to_string (Rope.sub 0 off r))
        (Rope.to_string (Rope.sub 0 off r'));
      assert_equal ~printer:String.escaped
        s (Rope.to_string (Rope.sub off len r'));
      assert_equal ~printer:String.escaped
        (Rope.to_string (Rope.sub off (tlen - off) r))
        (Rope.to_string (Rope.sub (off + len) (tlen - off) r')) in

  let s = random_string 10000 in
    List.iter test [
      "", "", 0;
      "a", "", 0;
      "", "abc", 3;
      "abc", "def", 0;
      "abc", "def", 2;
      "abc", "def", 3;
      "abc", s, 0;
      "abc", s, String.length s / 2;
      "abc", s, String.length s;
    ]

let rec loop_append s r i =
  if i > 0 then loop_append s (Rope.concat r s) (i - 1)
  else r

let iter_helper msg hash hash' count count' =
  assert_equal
    ~msg:"how many times the func was called"
    ~printer:string_of_int !count !count';
  assert_equal ~msg ~printer:string_of_int !hash !hash'

let test_iter () =
  let r = loop_append (Rope.of_string (random_string 10)) Rope.empty 10000 in
  let str = Rope.to_string r in
  let hash = ref 0 and hash' = ref 0 in
  let callcount = ref 0 and callcount' = ref 0 in
  let dohash counter h c =
    incr counter; h := 223 * !h + Char.code c
  in
    String.iter (dohash callcount hash) str;
    Rope.iter (dohash callcount' hash') r;
    iter_helper "hash computed with iter" hash hash' callcount callcount';
    let dohash2 h i c = h := 223 * !h + i * Char.code c in
    let i = ref 0 in
    let iteri f x = let n = !i in incr i; f n x in
      String.iter (iteri (dohash2 hash)) str;
      Rope.iteri (dohash2 hash') r;
      iter_helper "hash computed with iteri" hash hash' callcount callcount'

let test_rangeiter () =
  let dohash counter h c =
    incr counter; h := 223 * !h + Char.code c in
  let r = loop_append (Rope.of_string (random_string 10)) Rope.empty 10000 in
  let s = Rope.to_string r in
  let len = Rope.length r in
    for i = 0 to 100 do
      let hash  = ref 0 and hash'  = ref 0 in
      let count = ref 0 and count' = ref 0 in
      let m = Random.int (len + 1) in (* also allow sub len 0 *)
      let n = Random.int (len - m) in
        String.iter (dohash count hash) (String.sub s m n);
        Rope.rangeiter (dohash count' hash') m n r;
        iter_helper "hash computed with rangeiter" hash hash' count count';
    done;
    List.iter (fun (s, m, n) ->
                 assert_raises Rope.Out_of_bounds
                   ~msg:(sprintf "rangeiter %d %d \"%s\"" m n (String.escaped s))
                   (fun () -> Rope.rangeiter ignore m n (Rope.of_string s)))
      ["foo", -1, 0; "", 1, 0; "aaa", 1, 3]

let test_make () =
  let test s len c = assert_equal s (Rope.to_string (Rope.make len c)) in
    assert_bool "should be empty" (Rope.is_empty (Rope.make 0 'a'));
    assert_equal Rope.empty (Rope.make 0 'a');
    test "a" 1 'a';
    test "aa" 2 'a';
    test (String.make 1000 'a') 1000 'a'

let suite = "Rope" >::: [
  "empty"              >:: test_empty_props;
  "string conversions" >:: string_conversions;
  "is_empty"           >:: test_is_empty;
  "make"               >:: test_make;
  "concat"             >:: test_concat;
  "length"             >:: test_length;
  "get"                >:: test_get;
  "set"                >:: test_set;
  "sub"                >:: test_sub;
  "insert"             >:: test_insert;
  "iter and iteri"     >:: test_iter;
  "rangeiter"          >:: test_rangeiter;
]

let _ = run_test_tt_main suite