module Sa = Bsdiff.Suffix_array

let suffixes t = List.init (Sa.length t) (fun i -> Sa.suffix t i)

(* The sorted suffixes of "banana": "" < "a" < "ana" < "anana" < "banana" < "na"
   < "nana", i.e. start positions 6 5 3 1 0 4 2. *)
let test_banana () =
  let t = Sa.v "banana" in
  Alcotest.(check (list int)) "banana" [ 6; 5; 3; 1; 0; 4; 2 ] (suffixes t)

let test_empty () =
  let t = Sa.v "" in
  Alcotest.(check (list int)) "empty" [ 0 ] (suffixes t)

(* Every adjacent pair of suffixes must be in strictly increasing order; this is
   the defining invariant, checked on awkward shapes: repeated bytes, periodic
   data, all 256 byte values. *)
let test_sorted_invariant () =
  let suffix_of s i = String.sub s i (String.length s - i) in
  List.iter
    (fun s ->
      let t = Sa.v s in
      let order = suffixes t in
      ignore
        (List.fold_left
           (fun prev i ->
             (match prev with
             | Some p ->
                 if not (String.compare (suffix_of s p) (suffix_of s i) < 0)
                 then
                   Alcotest.failf "suffixes %d and %d out of order in %S" p i s
             | None -> ());
             Some i)
           None order))
    [
      "aaaaaaaaaaaaaaaa";
      "abababababababab";
      "mississippi";
      String.init 256 Char.chr;
      String.init 1000 (fun i -> Char.chr (i * 37 land 0xff));
    ]

let test_longest_match () =
  let t = Sa.v "the quick brown fox" in
  let len, pos = Sa.longest_match t ~target:"a quick brown cat" ~pos:1 in
  Alcotest.(check int) "match length" 13 len;
  Alcotest.(check int) "match position" 3 pos;
  let len, _ = Sa.longest_match t ~target:"zzz" ~pos:0 in
  Alcotest.(check int) "no match" 0 len

let suite =
  ( "suffix_array",
    [
      Alcotest.test_case "banana" `Quick test_banana;
      Alcotest.test_case "empty" `Quick test_empty;
      Alcotest.test_case "sorted invariant" `Quick test_sorted_invariant;
      Alcotest.test_case "longest match" `Quick test_longest_match;
    ] )