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/hash-array.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 245 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/library/hash-array.sml

1 : monnier 245 structure HashArray :
2 :     sig include ARRAY_SIG
3 :     val array' : int * (int -> 'a) -> 'a array
4 :     val array'': int * (int -> 'a) -> 'a array
5 :     val clear : 'a array -> unit
6 :     val remove : 'a array * int -> unit
7 :     val dom : 'a array -> int list
8 :     val copy_array : 'a array -> 'a array
9 :     end =
10 :     struct
11 :     structure A = Array
12 :    
13 :     datatype 'a default = V of 'a | F of int -> 'a | U of int -> 'a
14 :     datatype 'a array =
15 :     ARRAY of (int * 'a) list A.array ref * 'a default * int ref * int ref
16 :    
17 :     type 'a vector = 'a Vector.vector
18 :    
19 :     val maxLen = A.maxLen
20 :    
21 :     exception HashArrayUnimplemented
22 :    
23 :     fun unimplemented _ = raise HashArrayUnimplemented
24 :    
25 :     fun array(n,d) = ARRAY(ref(A.array(13,[])),V d,ref n,ref 0)
26 :     fun array'(n,f) = ARRAY(ref(A.array(13,[])),F f,ref n,ref 0)
27 :     fun array''(n,f) = ARRAY(ref(A.array(13,[])),U f,ref n,ref 0)
28 :     fun clear(ARRAY(r,d,n,c)) = (r := A.array(13,[]); n := 0; c := 0)
29 :     fun copy_array(ARRAY(ref a,d,ref n,ref c)) =
30 :     let val a' = A.array(n,[])
31 :     val _ = A.copy{src=a,dst=a',si=0,di=0,len=NONE}
32 :     in ARRAY(ref a',d,ref n,ref c)
33 :     end
34 :    
35 :     fun tabulate(n,f) =
36 :     let val N = n*n+1
37 :     val N = if N < 13 then 13 else N
38 :     val a = A.array(N,[])
39 :     fun ins i =
40 :     let val pos = i mod N
41 :     val x = f i
42 :     in A.update(a,pos,(i,x)::A.sub(a,pos)); x
43 :     end
44 :     fun insert 0 = ins 0
45 :     | insert i = (ins i; insert(i-1))
46 :     in if n < 0 then
47 :     ARRAY(ref a,F(fn _ => raise Subscript),ref 0,ref 0)
48 :     else
49 :     ARRAY(ref a,V(insert(n-1)),ref n,ref n)
50 :     end
51 :    
52 :     fun fromList l =
53 :     let val n = length l
54 :     val N = n*n+1
55 :     val N = if N < 13 then 13 else N
56 :     val a = A.array(N,[])
57 :     fun ins(i,x) =
58 :     let val pos = i mod N
59 :     in A.update(a,pos,(i,x)::A.sub(a,pos)); x
60 :     end
61 :     fun insert(i,[]) = F(fn _ => raise Subscript)
62 :     | insert(i,[x]) = V(ins(i,x))
63 :     | insert(i,x::l) = (ins(i,x); insert(i+1,l))
64 :     in ARRAY(ref a,insert(0,l),ref n,ref n)
65 :     end
66 :    
67 :     fun length(ARRAY(_,_,ref n,_)) = n
68 :    
69 :     fun sub(a' as ARRAY(ref a,d,_,_),i) =
70 :     let val pos = i mod A.length a
71 :     fun search [] = (case d of
72 :     V d => d
73 :     | F f => f i
74 :     | U f => let val x = f i
75 :     in update(a',i,x); x end
76 :     )
77 :     | search ((j,x)::l) = if i = j then x else search l
78 :     in search(A.sub(a,pos)) end
79 :    
80 :     and update(a' as ARRAY(ref a,_,n,s as ref size),i,x) =
81 :     let val N = A.length a
82 :     val pos = i mod N
83 :     fun change([],l) =
84 :     if size+size >= N then grow(a',i,x)
85 :     else (s := size + 1; A.update(a,pos,(i,x)::l))
86 :     | change((y as (j,_))::l',l) =
87 :     if j = i then A.update(a,pos,(i,x)::l'@l)
88 :     else change(l',y::l)
89 :     in
90 :     change(A.sub(a,pos),[]);
91 :     if i >= !n then n := i+1 else ()
92 :     end
93 :    
94 :     and grow(ARRAY(a' as ref a,_,_,_),i,x) =
95 :     let val N = A.length a
96 :     val N' = N+N+1
97 :     val a'' = A.array(N',[])
98 :     fun insert(i,x) =
99 :     let val pos = i mod N'
100 :     in A.update(a'',pos,(i,x)::A.sub(a'',pos)) end
101 :     in
102 :     A.app (List.app insert) a;
103 :     insert(i,x);
104 :     a' := a''
105 :     end
106 :    
107 :     fun remove(a' as ARRAY(ref a,_,n,s as ref size),i) =
108 :     let val N = A.length a
109 :     val pos = i mod N
110 :     fun change([],_) = ()
111 :     | change((y as (j,_))::l',l) =
112 :     if j = i then (s := size - 1; A.update(a,pos,l'@l))
113 :     else change(l',y::l)
114 :     in change(A.sub(a,pos),[])
115 :     end
116 :    
117 :     fun extract (a as ARRAY(_,_,ref n,_),i,j) =
118 :     let val j = case j of SOME j => i+j | NONE => n
119 :     fun f(k,l) = if k < i then l else f(k-1,sub(a,k)::l)
120 :     in
121 :     Vector.fromList(f(j-1,[]))
122 :     end
123 :    
124 :     fun copy { src = src as ARRAY(_,_,ref n,_), si, len, dst, di } =
125 :     let val j = case len of SOME len => si+len | NONE => n
126 :     fun f(k,k') = if k >= j then ()
127 :     else (update(dst,k',sub(src,k)); f(k+1,k'+1))
128 :     in f(si,di)
129 :     end
130 :    
131 :     val copyVec = unimplemented
132 :    
133 :     fun app f (ARRAY(ref a,_,_,_)) = A.app (List.app (fn (_,x) => f x)) a
134 :     fun foldl f e (ARRAY(ref a,_,_,_)) =
135 :     A.foldl (fn (l,e) => List.foldl (fn ((_,x),e) => f(x,e)) e l) e a
136 :     fun foldr f e (ARRAY(ref a,_,_,_)) =
137 :     A.foldr (fn (l,e) => List.foldr (fn ((_,x),e) => f(x,e)) e l) e a
138 :    
139 :     fun modify f (ARRAY(ref a,_,_,_)) =
140 :     A.modify (List.map (fn (i,x) => (i,f x))) a
141 :    
142 :     fun appi f (ARRAY(ref a,_,ref n,_),i,j) =
143 :     let val j = case j of SOME j => i+j | NONE => n
144 :     in A.app (List.app
145 :     (fn (k,x) => if k >= i andalso k < j then f(k,x) else ())) a
146 :     end
147 :     fun foldli f e (ARRAY(ref a,_,ref n,_),i,j) =
148 :     let val j = case j of SOME j => i+j | NONE => n
149 :     in A.foldl (fn (l,e) => List.foldl
150 :     (fn ((k,x),e) => if k >= i andalso k < j then f(k,x,e) else e) e l)
151 :     e a
152 :     end
153 :     fun foldri f e (ARRAY(ref a,_,ref n,_),i,j) =
154 :     let val j = case j of SOME j => i+j | NONE => n
155 :     in A.foldr (fn (l,e) => List.foldr
156 :     (fn ((k,x),e) => if k >= i andalso k < j then f(k,x,e) else e) e l)
157 :     e a
158 :     end
159 :     fun dom(ARRAY(ref a,_,_,_)) =
160 :     A.foldl (fn (e,l) => List.foldr (fn ((i,_),l) => i::l) l e) [] a
161 :    
162 :     fun modifyi f (ARRAY(ref a,_,ref n,_),i,j) =
163 :     let val j = case j of SOME j => i+j | NONE => n
164 :     in A.modify (List.map(fn (k,x) => if k >= i andalso k < j then (k,f(k,x))
165 :     else (k,x))) a
166 :     end
167 :     end
168 :    
169 :     (*
170 :     * $Log$
171 :     *)

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