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 /sml/trunk/src/MLRISC/library/dynamic-array.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/library/dynamic-array.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 470 - (view) (download)

1 : monnier 411 (*
2 :     * Dynamic (dense) array.
3 :     *
4 :     * -- Allen
5 :     *)
6 :    
7 : monnier 469 structure DynArray :
8 : monnier 411 sig include ARRAY
9 : monnier 245 val baseArray : 'a array -> 'a Array.array
10 : monnier 411 val checkArray: 'a array * 'a Array.array -> unit
11 : monnier 245 val clear : 'a array * int -> unit
12 :     end =
13 :     struct
14 :     structure A = Array
15 :     type 'a vector = 'a A.vector
16 :     datatype 'a array = ARRAY of 'a A.array ref * 'a * int ref
17 :    
18 :     exception Subscript = General.Subscript
19 :     exception Size = General.Size
20 :     exception Unimplemented
21 :    
22 :     infix 9 sub
23 :    
24 :     val maxLen = A.maxLen
25 :    
26 :     fun array (n,d) = ARRAY(ref(A.array (n,d)), d, ref 0)
27 :     fun clear (ARRAY(a,def,cnt),n) = (a := A.array(n,def); cnt := n)
28 :    
29 :     fun baseArray(ARRAY(ref a,_,_)) = a
30 : monnier 411 fun checkArray(ARRAY(ref a,_,_),a') = if a = a' then () else raise Match
31 : monnier 245
32 :     fun length (ARRAY (ref a,_,ref n)) = n
33 :    
34 :     fun (ARRAY(ref a, d, _)) sub i = A.sub(a,i) handle _ => d
35 :    
36 :     fun update (ARRAY(r as ref a, d, n), i, e) =
37 :     (A.update(a,i,e); n := Int.max(!n,i+1)) handle Subscript =>
38 :     let val new_size = Int.max(i+1,!n*2)
39 :     val new_size = if new_size < 10 then 10 else new_size
40 :     val new_array = A.array(new_size,d)
41 :     in A.copy {src = a, si = 0, len = NONE, dst = new_array, di = 0};
42 :     r := new_array;
43 :     n := i+1;
44 :     A.update(new_array, i, e)
45 :     end
46 :    
47 :     fun extract (ARRAY(r as ref a, _, ref n), i, j) = A.extract (a, i, j)
48 :    
49 :     fun copy { src = ARRAY(ref a,_,sz), si, len, dst, di } =
50 :     let val n = case len of SOME l => si + l
51 :     | NONE => !sz
52 :     fun cp(i,j) =
53 :     if i < n then (update(dst,j,A.sub(a,i)); cp(i+1,j+1)) else ()
54 :     in cp (si, di)
55 :     end
56 :    
57 :     fun copyVec { src, si, len, dst = ARRAY(ref a,_,sz), di } =
58 :     A.copyVec { src = src, si = si, len = len, dst = a, di = di }
59 :    
60 :     fun tabulate (n, f) =
61 :     let val array = A.tabulate(n, f)
62 :     val default = A.sub(array,0)
63 :     in
64 :     ARRAY(ref array, default, ref n)
65 :     end handle Subscript => raise Size
66 :    
67 :     fun fromList l =
68 :     let val array = A.fromList l
69 :     val default = A.sub(array,0)
70 :     in
71 :     ARRAY(ref array, default, ref (List.length l))
72 :     end handle Subscript => raise Size
73 :    
74 :     fun app f (ARRAY (ref a,_,ref n)) =
75 :     A.appi (fn (_,x) => f x) (a,0,SOME n)
76 :    
77 :     fun foldl f u (ARRAY (ref a,_,ref n)) =
78 :     A.foldli (fn (_,x,y) => f (x,y)) u (a, 0, SOME n)
79 :    
80 :     fun foldr f u (ARRAY (ref a,_,ref n)) =
81 :     A.foldri (fn (_,x,y) => f (x,y)) u (a, 0, SOME n)
82 :    
83 :     fun modify f (ARRAY (ref a,_,ref n)) =
84 :     A.modifyi (fn (_,x) => f x) (a, 0, SOME n)
85 :    
86 :     fun appi f (ARRAY(ref a,_,ref n), i, j) = A.appi f (a, i, j)
87 :    
88 :     fun foldli f u (ARRAY(ref a,_,ref n), i, j) = A.foldli f u (a, i, j)
89 :    
90 :     fun foldri f u (ARRAY(ref a,_,ref n), i, j) = A.foldri f u (a, i, j)
91 :    
92 :     fun modifyi f (ARRAY(ref a,_,ref n), i, j) = A.modifyi f (a, i, j)
93 :    
94 :     end
95 :    

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