Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /smlnj-lib/trunk/Util/dynamic-array.sml
ViewVC logotype

Annotation of /smlnj-lib/trunk/Util/dynamic-array.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3796 - (view) (download)

1 : monnier 467 (* dynamic-array.sml
2 :     *
3 : jhr 3337 * COPYRIGHT (c) 2009 The Fellowship of SML/NJ (http://www.smlnj.org)
4 :     * All rights reserved.
5 : monnier 467 *
6 :     * Polymorhic arrays of unbounded length
7 :     *)
8 :    
9 :     structure DynamicArray :> DYNAMIC_ARRAY =
10 :     struct
11 :    
12 :     structure A = Array
13 :    
14 : jhr 3796 (* BLOCK(arr, dflt, bnd):
15 :     * arr - current data store; is at least !bnd+1 elements
16 :     * dflt - default value
17 :     * bnd - values at !bnd and above are default for reading
18 :     *)
19 : monnier 467 datatype 'a array = BLOCK of ('a A.array ref * 'a * int ref)
20 :    
21 :     exception Subscript = General.Subscript
22 :     exception Size = General.Size
23 :    
24 :     fun array (sz, dflt) = BLOCK(ref(A.array(sz, dflt)), dflt, ref(~1))
25 :    
26 :     (* fromList (l, v) creates an array using the list of values l
27 :     * plus the default value v.
28 :     *)
29 :     fun fromList (initList, dflt) = let
30 : jhr 3796 val arr = A.fromList initList
31 : monnier 467 in
32 : jhr 3796 BLOCK(ref arr, dflt, ref(A.length arr - 1))
33 : monnier 467 end
34 :    
35 :     (* tabulate (sz,fill,dflt) acts like Array.tabulate, plus
36 :     * stores default value dflt. Raises Size if sz < 0.
37 :     *)
38 :     fun tabulate (sz, fillFn, dflt) =
39 : jhr 3796 BLOCK(ref(A.tabulate(sz, fillFn)), dflt, ref(sz-1))
40 : monnier 467
41 : jhr 3796 fun subArray (BLOCK(arr, dflt, bnd), lo, hi) = let
42 : monnier 467 val arrval = !arr
43 :     val bnd = !bnd
44 : jhr 3796 fun copy i = A.sub(arrval, i+lo)
45 : monnier 467 in
46 :     if hi <= bnd
47 : jhr 3796 then BLOCK(ref(A.tabulate(hi-lo, copy)), dflt, ref(hi-lo))
48 : monnier 467 else if lo <= bnd
49 : jhr 3796 then BLOCK(ref(A.tabulate(bnd-lo, copy)), dflt, ref(bnd-lo))
50 : monnier 467 else
51 : jhr 3796 array(0, dflt)
52 : monnier 467 end
53 :    
54 : jhr 3796 fun default (BLOCK(_, dflt, _)) = dflt
55 : monnier 467
56 : jhr 3796 fun sub (BLOCK(arr, dflt, _), idx) = (A.sub(!arr, idx))
57 : monnier 467 handle Subscript => if idx < 0 then raise Subscript else dflt
58 :    
59 : jhr 3796 fun bound (BLOCK(_, _, bnd)) = (!bnd)
60 : monnier 467
61 : jhr 3796 fun expand(arr, oldlen, newlen, dflt) = let
62 : monnier 467 fun fillfn i = if i < oldlen then A.sub(arr,i) else dflt
63 :     in
64 :     A.tabulate(newlen, fillfn)
65 :     end
66 :    
67 : jhr 3796 fun update (BLOCK(arr, dflt, bnd), idx, v) = let
68 : monnier 467 val len = A.length (!arr)
69 :     in
70 :     if idx >= len
71 : jhr 3796 then arr := expand(!arr, len, Int.max(len+len,idx+1), dflt)
72 : monnier 467 else ();
73 :     A.update(!arr,idx,v);
74 :     if idx > !bnd then bnd := idx else ()
75 :     end
76 :    
77 : jhr 3796 fun truncate (a as BLOCK(arr, dflt, bndref), sz) = let
78 : monnier 467 val bnd = !bndref
79 :     val newbnd = sz - 1
80 :     val arr_val = !arr
81 :     val array_sz = A.length arr_val
82 :     fun fillDflt (i,stop) =
83 :     if i = stop then ()
84 : jhr 3796 else (A.update(arr_val,i,dflt); fillDflt(i-1, stop))
85 : monnier 467 in
86 : jhr 3796 if newbnd < 0 then (bndref := ~1;arr := A.array(0, dflt))
87 : monnier 467 else if newbnd >= bnd then ()
88 :     else if 3 * sz < array_sz then let
89 : jhr 3796 val BLOCK(arr',_,bnd') = subArray(a, 0, newbnd)
90 : monnier 467 in
91 :     (bndref := !bnd'; arr := !arr')
92 :     end
93 : jhr 3796 else fillDflt(bnd, newbnd)
94 : monnier 467 end
95 :    
96 : jhr 3337 (* get the array slice that covers the defined portion of the array *)
97 :     fun slice (BLOCK(arr, _, bnd)) =
98 : jhr 3796 ArraySlice.slice(!arr, 0, SOME(!bnd + 1))
99 : jhr 3337
100 :     (* we implement the iterators by using the array slice operations *)
101 :     fun vector arr = ArraySlice.vector (slice arr)
102 :     fun appi f arr = ArraySlice.appi f (slice arr)
103 :     fun app f arr = ArraySlice.app f (slice arr)
104 :     fun modifyi f arr = ArraySlice.modifyi f (slice arr)
105 :     fun modify f arr = ArraySlice.modify f (slice arr)
106 :     fun foldli f init arr = ArraySlice.foldli f init (slice arr)
107 :     fun foldri f init arr = ArraySlice.foldri f init (slice arr)
108 :     fun foldl f init arr = ArraySlice.foldl f init (slice arr)
109 :     fun foldr f init arr = ArraySlice.foldr f init (slice arr)
110 :     fun findi pred arr = ArraySlice.findi pred (slice arr)
111 :     fun find pred arr = ArraySlice.find pred (slice arr)
112 :     fun exists pred arr = ArraySlice.exists pred (slice arr)
113 :     fun all pred arr = ArraySlice.all pred (slice arr)
114 :     fun collate cmp (arr1, arr2) = ArraySlice.collate cmp (slice arr1, slice arr2)
115 :    
116 :     (* TODO
117 :     val copy : {di:int, dst:'a array, src:'a array} -> unit
118 :     val copyVec : {di:int, dst:'a array, src:'a vector} -> unit
119 :     *)
120 :    
121 : monnier 467 end (* DynamicArrayFn *)
122 :    

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0