blob: aed0f2b836141bbcb9685792890bcff90c5ef607 (
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
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
type t = {
storage: int array;
nbits: int;
}
;;
let int_bits =
if max_int = (1 lsl 30) - 1
then 31
else 63
;;
let create nbits flag =
{ storage = Array.make (nbits / int_bits + 1) (if flag then lnot 0 else 0);
nbits = nbits }
;;
(*
* mutate v0 in place: v0.(i) <- v0.(i) op v1.(i), returning bool indicating
* whether any bits in v0 changed in the process.
*)
let process (op:int -> int -> int) (v0:t) (v1:t) : bool =
let changed = ref false in
assert (v0.nbits = v1.nbits);
assert ((Array.length v0.storage) = (Array.length v1.storage));
Array.iteri
begin
fun i w1 ->
let w0 = v0.storage.(i) in
let w0' = op w0 w1 in
if not (w0' = w0)
then changed := true;
v0.storage.(i) <- w0';
end
v1.storage;
!changed
;;
let union = process (lor) ;;
let intersect = process (land) ;;
let copy = process (fun _ w1 -> w1) ;;
let get (v:t) (i:int) : bool =
assert (i >= 0);
assert (i < v.nbits);
let w = i / int_bits in
let b = i mod int_bits in
let x = 1 land (v.storage.(w) lsr b) in
x = 1
;;
let equal (v1:t) (v0:t) : bool =
v0 = v1
;;
let clear (v:t) : unit =
for i = 0 to (Array.length v.storage) - 1
do
v.storage.(i) <- 0
done
;;
let invert (v:t) : unit =
for i = 0 to (Array.length v.storage) - 1
do
v.storage.(i) <- lnot v.storage.(i)
done
;;
(* dst = dst - src *)
let difference (dst:t) (src:t) : bool =
invert src;
let b = intersect dst src in
invert src;
b
;;
let set (v:t) (i:int) (x:bool) : unit =
assert (i >= 0);
assert (i < v.nbits);
let w = i / int_bits in
let b = i mod int_bits in
let w0 = v.storage.(w) in
let flag = 1 lsl b in
v.storage.(w) <-
if x
then w0 lor flag
else w0 land (lnot flag)
;;
let to_list (v:t) : int list =
if v.nbits = 0
then []
else
let accum = ref [] in
let word = ref v.storage.(0) in
for i = 0 to (v.nbits-1) do
if i mod int_bits = 0
then word := v.storage.(i / int_bits);
if (1 land (!word)) = 1
then accum := i :: (!accum);
word := (!word) lsr 1;
done;
!accum
;;
(*
* Local Variables:
* fill-column: 78;
* indent-tabs-mode: nil
* buffer-file-coding-system: utf-8-unix
* compile-command: "make -k -C $RBUILD 2>&1 | sed -e 's/\\/x\\//x:\\//g'";
* End:
*)
|
