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 copy { array; dummy; len } = { array = Array.copy array; 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])"]