blob: d1a9ecded017a03774a28d5e5f64ff4b4ec37705 (
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
|
type 'a t = { mutable array : 'a array; dummy : 'a; mutable len : int }
(* Utilities *)
let next_pow2 x =
(* From Bit Twiddling Hacks *)
let x = x - 1 in
let x = x lor (x lsr 1) in
let x = x lor (x lsr 2) in
let x = x lor (x lsr 4) in
let x = x lor (x lsr 8) in
let x = x lor (x lsr 16) in
let x = x lor (x lsr 32) in
x + 1
let%test _ = next_pow2 0 = 0
let%test _ = next_pow2 1 = 1
let%test _ = next_pow2 2 = 2
let%test _ = next_pow2 3 = 4
let%test _ = next_pow2 4 = 4
let%test _ = next_pow2 5 = 8
let%test _ = next_pow2 15 = 16
let%test _ = next_pow2 50 = 64
let%test _ = next_pow2 12345 = 16384
(* Arraylist operations *)
let make len dummy =
{ array = Array.make (max (next_pow2 len) 4) dummy; dummy; len }
let length { len; _ } = len
let get { array; len; _ } i =
if i >= len then
raise
(Invalid_argument
(Format.sprintf
"index %d out of bounds for an Arraylist.t of length %d" i len))
else array.(i)
let set { array; len; _ } i x =
if i >= len then
raise
(Invalid_argument
(Format.sprintf
"index %d out of bounds for an Arraylist.t of length %d" i len))
else array.(i) <- x
let push arraylist x =
if Array.length arraylist.array = arraylist.len then
arraylist.array <-
Array.init (arraylist.len * 2) (fun i ->
if i < arraylist.len then arraylist.array.(i) else arraylist.dummy);
arraylist.array.(arraylist.len) <- x;
arraylist.len <- arraylist.len + 1
let to_array { array; len; _ } = Array.sub array 0 len
module Array_for_pp = struct
type 'a t = 'a array [@@deriving show { with_path = false }]
end
let pp (fmt_elem : Format.formatter -> 'a -> unit) (fmt : Format.formatter)
(arraylist : 'a t) : unit =
Array_for_pp.pp fmt_elem fmt (to_array arraylist)
let%expect_test _ =
let xs = make 3 0 in
push xs 3;
set xs 0 1;
set xs 1 1;
set xs 2 2;
push xs 5;
print_endline ([%derive.show: int t] xs);
[%expect "[|1; 1; 2; 3; 5|]"]
let%expect_test _ =
let xs = make 0 false in
let add x =
let index = length xs in
push xs x;
index
in
let i = add false and j = add true and k = add true in
print_endline
([%derive.show: int list * bool list]
([ i; j; k ], [ get xs i; get xs j; get xs k ]));
[%expect "([0; 1; 2], [false; true; true])"]
|
