Something went wrong. Try again.
My own corner of monopam
Something went wrong. Try again.
2.0 kB · 58 lines
OCaml
at main
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859module 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; ] )