1(* Modified for Moscow ML from SML/NJ Library 0.2 file dynamic-array.sml
2 *
3 * COPYRIGHT (c) 1993 by AT&T Bell Laboratories.
4 * See file mosml/copyrght/copyrght.att for details.
5 *
6 * Arrays of unbounded length
7 *
8 *)
9
10structure Dynarray :> Dynarray =
11struct
12
13datatype 'elem array = BLOCK of 'elem Array.array ref * 'elem
14
15fun array (sz, dflt) = BLOCK (ref (Array.array (sz, dflt)), dflt)
16
17fun subArray (BLOCK (arr, dflt), lo, hi) =
18   let
19      val arrval = !arr
20      fun copy i = Array.sub (arrval, i + lo) handle _ => dflt
21   in
22      BLOCK (ref (Array.tabulate (hi - lo, copy)), dflt)
23   end
24
25fun fromList (initlist, dflt) = BLOCK (ref (Array.fromList initlist), dflt)
26
27fun tabulate (sz, fillfn, dflt) =
28   BLOCK (ref (Array.tabulate (sz, fillfn)), dflt)
29
30fun default (BLOCK (_, dflt)) = dflt
31
32fun sub (BLOCK (arr, dflt), idx) =
33   Array.sub (!arr, idx)
34   handle Subscript => if idx < 0 then raise Subscript else dflt
35
36fun bound (BLOCK (arr, _)) = Array.length (!arr)
37
38fun expand (arr, oldlen, newlen, dflt) =
39   let
40      fun fillfn i = if i < oldlen then Array.sub (arr, i) else dflt
41   in
42      Array.tabulate (newlen, fillfn)
43   end
44
45fun update (b as BLOCK (arr, dflt), idx, v) =
46   let
47      fun max (x, y: int) = if x > y then x else y
48      val len = bound b
49   in
50      if idx >= len
51         then arr := expand (!arr, len, max (len + len, idx + 1), dflt)
52      else ()
53      ; Array.update (!arr, idx, v)
54   end
55
56end
57