annotate lib/growvect.ml @ 0:bfdcc3820b32

Basis
author Mike Spivey <mike@cs.ox.ac.uk>
date Thu, 05 Oct 2017 08:04:15 +0100
parents
children
rev   line source
0
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
1 (* lib/growvect.ml *)
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
2 (* Copyright (c) 2017 J. M. Spivey *)
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
3
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
4 type 'a t =
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
5 { mutable size: int;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
6 mutable elements: 'a array }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
7
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
8 let create n =
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
9 { size = 0; elements = Array.make n (Obj.magic ()) }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
10
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
11 let make n v =
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
12 { size = n; elements = Array.make n v }
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
13
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
14 let clear v =
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
15 v.size <- 0
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
16
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
17 let size v = v.size
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
18
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
19 let get v i =
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
20 if i >= v.size then raise (Invalid_argument "index out of bounds");
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
21 Array.get v.elements i
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
22
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
23 let set v i x =
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
24 if i >= v.size then raise (Invalid_argument "index out of bounds");
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
25 Array.set v.elements i x
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
26
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
27 let append v x =
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
28 let n = Array.length v.elements in
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
29 if v.size >= n then begin
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
30 let newv = Array.make (2*n) (Obj.magic ()) in
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
31 Array.blit v.elements 0 newv 0 n;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
32 v.elements <- newv
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
33 end;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
34 Array.set v.elements v.size x;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
35 v.size <- v.size+1
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
36
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
37 let iter f v =
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
38 for i = 0 to v.size-1 do f v.elements.(i) done
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
39
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
40 let to_list v =
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
41 let rec loop n xs =
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
42 if n = 0 then xs else loop (n-1) (v.elements.(n-1)::xs) in
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
43 loop v.size []