1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
let id x = x
module Array = struct
include Array
(** Perfect Fisher-Yates shuffle
(http://www.nist.gov/dads/HTML/fisherYatesShuffle.html). *)
let shuffle a =
let permute i j =
let tmp = a.(i) in
a.(i) <- a.(j);
a.(j) <- tmp
in
let l = Array.length a in
for i = 0 to l - 1 do
permute i (i + Random.int (l - i))
done
end
module List = struct
include List
let rec assoc_nth l n = function
| [] -> raise Not_found
| (x, v) :: t when x = l -> if n = 0 then v else assoc_nth l (n - 1) t
| _ :: t -> assoc_nth l n t
let assoc_all x l =
filter_map (fun (y, v) -> if x = y then Some v else None) l
let rec last = function [x] -> x | _ :: l -> last l | [] -> raise Not_found
let rec prefix n l =
match l with
| [] -> []
| x :: l -> if n = 0 then [] else x :: prefix (n - 1) l
let shuffle l =
let a = Array.of_list l in
Array.shuffle a;
Array.to_list a
end
module String = struct
include String
let ends_with s a =
let ls = String.length s in
let la = String.length a in
ls >= la && String.sub s (ls - la) la = a
let split_char c s =
let rec aux res n =
try
let n' = index_from s n c in
let s0 = sub s n (n' - n) in
aux (s0 :: res) (n' + 1)
with Not_found -> (if n = 0 then s else sub s n (length s - n)) :: res
in
List.rev (aux [] 0)
end
let read_retry read buf off len =
let r = ref 0 in
let loop = ref true in
while !loop do
let n = read buf (off + !r) (len - !r) in
r := !r + n;
loop := !r <> 0 && !r < len && n <> 0
done;
!r
module Unix = struct
include Unix
let read_retry fd = read_retry (read fd)
end
module Int = struct
include Int
let find p =
let ans = ref 0 in
try
while true do
if p !ans then raise Exit else incr ans
done;
assert false
with Exit -> !ans
end
module Fun = struct
include Fun
(** Execute a function at most once. *)
let once =
let already = ref false in
fun f ->
if not !already then (
already := true;
f ())
end