blob: 4f5ddf9bbaf4babcbcb82f44f0f669799b9bbea1 (
plain)
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
|
module type INTERFACE = sig
type 'a t
val init : int -> (int -> 'a) -> 'a t
val length : 'a t -> int
val of_list : 'a list -> 'a t
val add : 'a t -> 'a -> unit
val random : 'a t -> 'a
val reset : 'a t -> unit
val set_state : 'a t -> Random.State.t -> unit
end
module IMPLEMENTATION = struct
type 'a t = {
mutable length : int;
mutable left : int;
array : 'a array;
mutable state : Random.State.t;
}
let init len f =
let array = Array.init len f in
{
array = array;
length = len;
left = len;
state = Random.get_state ();
}
let of_list list =
let array = Array.of_list list in
let len = Array.length array in
{
array = array;
length = len;
left = len;
state = Random.get_state ();
}
let length t = t.length
let add t x =
let len = t.length in
t.array.(len) <- x;
t.length <- len + 1;
if len = t.left then
t.left <- len + 1
let random t =
if t.left <= 0 then raise Not_found;
let pos = Random.State.int t.state t.left in
let tab = t.array in
let len = t.left-1 in
(* Printf.fprintf stderr "SWAP(%d)(%d)%!" pos len; *)
let x = tab.(pos) in
tab.(pos) <- tab.(len);
tab.(len) <- x;
t.left <- len;
x
let reset t =
t.left <- t.length
let set_state t state = t.state <- state
end
include (IMPLEMENTATION : INTERFACE)
|
