Source file `owl_utils_stack.ml`

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
# 1 "src/base/misc/owl_utils_stack.ml"
(*
 * OWL - OCaml Scientific and Engineering Computing
 * Copyright (c) 2016-2020 Liang Wang <liang.wang@cl.cam.ac.uk>
 *)

(* A naive implementation of stack for Owl's internal use. *)

type 'a t =
  { mutable used : int
  ; mutable size : int
  ; mutable data : 'a array
  }

let allocate_space x = Array.(append x (copy x))

let make () = { used = 0; size = 0; data = [||] }

let push s x =
  if s.size = 0 then s.data <- [| x |];
  if s.used = s.size
  then (
    s.data <- allocate_space s.data;
    s.size <- Array.length s.data);
  s.data.(s.used) <- x;
  s.used <- s.used + 1


let pop s =
  match s.used with
  | 0 -> None
  | i ->
    s.used <- i - 1;
    Some s.data.(s.used)


let peek s =
  match s.used with
  | 0 -> None
  | i -> Some s.data.(i - 1)


let is_empty s = s.used = 0

let mem s x = Array.mem x s.data

let memq s x = Array.memq x s.data

let to_array s = Array.sub s.data 0 s.used