Flattens the AST.

1 files changed, 90 insertions, 0 deletions

diff --git a/discocaml/arraylist.ml b/discocaml/arraylist.ml
new file mode 100644
index 0000000..d1a9ecd
--- /dev/null
+++ b/discocaml/arraylist.ml
@@ -0,0 +1,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])"]