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