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/branches/idlbasis-devel/src/system/Basis/Implementation/word8-array-slice.sml
ViewVC logotype

Annotation of /sml/branches/idlbasis-devel/src/system/Basis/Implementation/word8-array-slice.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 866 - (view) (download)

1 : dbm 850 (* word8-array-slice-sig.sml
2 :     *
3 :     * COPYRIGHT (c) 2000 Bell Labs, Lucent Technologies.
4 :     *
5 :     *)
6 :    
7 :     structure Word8ArraySlice: MONO_ARRAY_SLICE =
8 :     struct
9 :    
10 :     structure A = InlineT.Word8Array
11 :     type elem = Word8.word
12 : blume 866 type array = Word8Array.array
13 : dbm 850 type vector = Word8Vector.vector
14 :     type vector_slice = Word8VectorSlice.slice
15 :     datatype slice = SL of {base: array, start: int, stop: int}
16 :    
17 :     val (op <) = InlineT.DfltInt.<
18 :     val (op >=) = InlineT.DfltInt.>=
19 :     val (op +) = InlineT.DfltInt.+
20 :     val sub' = A.sub
21 : blume 866 val update' = A.update
22 : dbm 850 val geu = InlineT.DfltInt.geu
23 :    
24 :     (* val full : array -> slice *)
25 :     (* val slice : array * int * int option -> slice *)
26 :     (* val subslice : slice * int * int option -> slice *)
27 :     (* val base : slice -> array * int * int *)
28 :     (* val vector : slice -> vector *)
29 :     (* val copy : {src : slice, dst : array, di : int} -> unit *)
30 :     (* val copyVec : {src : vector_slice, dst : array, di : int} -> unit *)
31 :     (* val isEmpty : slice -> bool *)
32 :     (* val getItem : slice -> (elem * slice) option *)
33 :     (* val appi : (int * elem -> unit) -> slice -> unit *)
34 :     (* val app : (elem -> unit) -> slice -> unit *)
35 :     (* val modifyi : (int * elem -> elem) -> slice -> unit *)
36 :     (* val modify : (elem -> elem) -> slice -> unit *)
37 :     (* val foldli : (int * elem * 'b -> 'b) -> 'b -> slice -> 'b *)
38 :     (* val foldr : (elem * 'b -> 'b) -> 'b -> slice -> 'b *)
39 :     (* val foldl : (elem * 'b -> 'b) -> 'b -> slice -> 'b *)
40 :     (* val foldri : (int * elem * 'b -> 'b) -> 'b -> slice -> 'b *)
41 :     (* val findi : (int * elem -> bool) -> slice -> (int * elem) option *)
42 :     (* val find : (elem -> bool) -> slice -> elem option *)
43 :     (* val exists : (elem -> bool) -> slice -> bool *)
44 :     (* val all : (elem -> bool) -> slice -> bool *)
45 :     (* val collate : (elem * elem -> order) -> slice * slice -> order *)
46 :    
47 :     (*----------------------------------------------------------------------*)
48 :     (* val length : slice -> int *)
49 :     fun length(SL{start,stop,...}) = stop - start
50 :    
51 :     (* val sub : slice * int -> elem *)
52 :     (* sub(s,j) valid if 0<=j<stop-start, otherwise raises Subscript *)
53 :     fun sub (SL{base, start, stop}, j) =
54 :     let val j' = start+j
55 :     in if geu(j', stop) (* checks for j' >= 0 *)
56 :     then raise Core.Subscript
57 :     else sub'(base, j')
58 :     end
59 :    
60 :     (* val update : slice * int * elem -> unit *)
61 : blume 866 fun update (SL{base,start,stop},j,x) =
62 :     let val j' = start + j
63 :     in if geu (j', stop) then raise Core.Subscript
64 :     else update' (base, j', x)
65 :     end
66 : dbm 850
67 : blume 866 (* val full : array -> slice *)
68 :     fun full base = SL{base=base,start=0,stop=A.length base}
69 :     (*
70 : dbm 850 let val blen = V.length base
71 :     in if geu(start, blen) (* checks start >= 0 *)
72 :     then raise Core.Subscript
73 :     else case lenOp
74 :     of NONE => SL{base=base,start=start,stop=blen}
75 :     | SOME n =>
76 :     if geu(n, blen-start) (* checks n >= 0 *)
77 :     then raise Core.Subscript
78 :     else SL{base=base,start=start,stop=start+n}
79 :     end
80 : blume 866 *)
81 : dbm 850
82 :     (* val slice : vector * int * int option -> slice *)
83 :     fun slice (base,start,lenOp) =
84 : blume 866 let val blen = A.length base
85 : dbm 850 in if geu(start, blen) (* checks start >= 0 *)
86 :     then raise Core.Subscript
87 :     else case lenOp
88 :     of NONE => SL{base=base,start=start,stop=blen}
89 :     | SOME n =>
90 :     if geu(n, blen-start) (* checks n >= 0 *)
91 :     then raise Core.Subscript
92 :     else SL{base=base,start=start,stop=start+n}
93 :     end
94 :    
95 :     (* val subslice : slice * int * int option -> slice *)
96 :     fun subslice (SL{base, start, stop}, i, sz) =
97 :     if geu(i, stop-start) (* checks start >= 0 *)
98 :     then raise Core.Subscript
99 :     else case sz
100 :     of NONE => SL{base=base,start=start+i,stop=stop}
101 :     | SOME n =>
102 :     if geu(n, stop-start-i) (* checks n >= 0 *)
103 :     then raise Core.Subscript
104 :     else SL{base=base,start=start+i,stop=start+i+n}
105 :    
106 : blume 866 (*
107 : dbm 850 (* val base : slice -> vector * int * int *)
108 :     fun full base = SL{base=base,start=0,stop=V.length base}
109 : blume 866 let val blen = A.length base
110 : dbm 850 in if geu(start, blen) (* checks start >= 0 *)
111 :     then raise Core.Subscript
112 :     else case lenOp
113 :     of NONE => SL{base=base,start=start,stop=blen}
114 :     | SOME n =>
115 :     if geu(n, blen-start) (* checks n >= 0 *)
116 :     then raise Core.Subscript
117 :     else SL{base=base,start=start,stop=start+n}
118 :     end
119 : blume 866 *)
120 : dbm 850
121 :     (* val vector : slice -> vector *)
122 :     fun vector (SL{base,start,stop}) =
123 : blume 866 Word8Vector.tabulate(stop-start, fn n => sub'(base,n+start))
124 : dbm 850
125 :     (* utility functions *)
126 :     fun checkLen n =
127 : blume 866 if InlineT.DfltInt.ltu(Word8Vector.maxLen, n)
128 : dbm 850 then raise General.Size
129 :     else ()
130 :    
131 :     fun rev ([], l) = l
132 :     | rev (x::r, l) = rev (r, x::l)
133 :    
134 :     (* val concat : slice list -> vector *)
135 :     (* DBM: this is inefficient since it unnecessarily creates an intermediate
136 :     * list containing all elements. Should calculate total length and preallocate
137 :     * result vector and then copy elements directly from slices. *)
138 :     fun concat [v] = vector v
139 :     | concat vl =
140 :     (* get the total length and flatten the list *)
141 :     let val len = List.foldl (fn (vs,i) => (length vs)+i) 0 vl
142 :     val _ = checkLen len
143 :     val v = InlineT.Word8Vector.create len
144 :     fun cpslice (SL{base,start,stop},j) =
145 :     let fun cp (i,j) =
146 :     if i = stop then j
147 :     else (InlineT.Word8Vector.update(v,j,sub'(base,i));
148 :     cp (i+1,j+1))
149 :     in cp (start,stop)
150 :     end
151 :     in List.foldl cpslice 0 vl;
152 :     v
153 :     end
154 :    
155 :     (* val isEmpty : slice -> bool *)
156 :     fun isEmpty (SL{base,start,stop}) = stop<=start
157 :    
158 :     (* val getItem : slice -> (elem * slice) option *)
159 :     fun getItem (SL{base,start,stop}) =
160 :     if stop<=start then NONE
161 : blume 866 else SOME(sub'(base, start), SL{base=base,start=start+1,stop=stop})
162 : dbm 850
163 :     (* val appi : (int * elem -> unit) -> slice -> unit *)
164 :     fun appi f (SL{base,start,stop}) =
165 :     let fun app i = if (i < stop)
166 :     then (f (i, sub'(base, i)); app(i+1))
167 :     else ()
168 :     in app start
169 :     end
170 :    
171 :     (* val app : (elem -> unit) -> slice -> unit *)
172 : blume 866 fun app f (SL{base,start,stop}) =
173 : dbm 850 let fun app i = if (i < stop)
174 :     then (f (sub'(base, i)); app(i+1))
175 :     else ()
176 :     in app start
177 :     end
178 :    
179 :     (* val mapi : (int * elem -> 'b) -> slice -> vector *)
180 : blume 859 fun mapi f (SL{base,start,stop}) =
181 : dbm 850 let val len = stop - start
182 :     fun mapf (i, l) = if (i < stop)
183 :     then mapf (i+1, f (i, sub'(base, i)) :: l)
184 :     else Assembly.A.create_v(len, rev(l, []))
185 :     in if (len > 0)
186 :     then mapf (start, [])
187 :     else Assembly.vector0
188 :     end
189 :    
190 :     (* val map : (elem -> 'b) -> slice -> vector *)
191 : blume 859 fun map f (SL{base,start,stop}) =
192 : dbm 850 let val len = stop - start
193 :     fun mapf (i, l) = if (i < stop)
194 :     then mapf (i+1, f (sub'(base, i)) :: l)
195 :     else Assembly.A.create_v(len, rev(l, []))
196 :     in
197 :     if (len > 0)
198 :     then mapf (start, [])
199 :     else Assembly.vector0
200 :     end
201 :    
202 :     (* val foldli : (int * elem * 'b -> 'b) -> 'b -> slice -> 'b *)
203 :     fun foldli f init (SL{base,start,stop}) =
204 :     let fun fold (i, accum) = if (i < stop)
205 :     then fold (i+1, f (i, sub'(base, i), accum))
206 :     else accum
207 :     in fold (start, init)
208 :     end
209 :    
210 :     (* val foldri : (int * elem * 'b -> 'b) -> 'b -> slice -> 'b *)
211 :     fun foldri f init (SL{base,start,stop}) =
212 :     let fun fold (i, accum) = if (i >= start)
213 :     then fold (i-1, f (i, sub'(base, i), accum))
214 :     else accum
215 :     in fold (stop - 1, init)
216 :     end
217 :    
218 :     (* val foldl : (elem * 'b -> 'b) -> 'b -> slice -> 'b *)
219 : blume 866 fun foldl f init (SL{base,start,stop}) =
220 : dbm 850 let fun fold (i, accum) = if (i < stop)
221 :     then fold (i+1, f (sub'(base, i), accum))
222 :     else accum
223 :     in fold (start, init)
224 :     end
225 :    
226 :     (* val foldr : (elem * 'b -> 'b) -> 'b -> slice -> 'b *)
227 :     fun foldr f init (SL{base,start,stop}) =
228 :     let fun fold (i, accum) = if (i >= start)
229 :     then fold (i-1, f (sub'(base, i), accum))
230 :     else accum
231 :     in fold (stop - 1, init)
232 :     end
233 :    
234 :     (* val findi : (int * elem -> bool) -> slice -> (int * elem) option *)
235 :     fun findi f (SL{base,start,stop}) =
236 :     let fun findi' i =
237 :     if (i < stop)
238 :     then let val item = (i,sub'(base, i))
239 :     in if f(item)
240 :     then SOME item
241 :     else findi' (i+1)
242 :     end
243 :     else NONE
244 :     in findi' start
245 :     end
246 :    
247 :     (* val find : (elem -> bool) -> slice -> elem option *)
248 :     fun find f (SL{base,start,stop}) =
249 :     let fun find' i =
250 :     if (i < stop)
251 :     then let val item = sub'(base, i)
252 :     in if f item
253 :     then SOME(item)
254 : blume 866 else find' (i+1)
255 : dbm 850 end
256 :     else NONE
257 :     in find' start
258 :     end
259 :    
260 :     (* val exists : (elem -> bool) -> slice -> bool *)
261 :     fun exists f (SL{base,start,stop}) =
262 :     let fun exists' i =
263 :     if (i < stop)
264 :     then if f(sub'(base, i))
265 :     then true
266 :     else exists' (i+1)
267 :     else false
268 :     in exists' start
269 :     end
270 :    
271 :     (* val all : (elem -> bool) -> slice -> bool *)
272 :     fun all f (SL{base,start,stop}) =
273 :     let fun all' i =
274 :     if (i < stop)
275 :     then if f(sub'(base, i))
276 :     then all' (i+1)
277 :     else false
278 :     else true
279 :     in all' start
280 :     end
281 :    
282 :     (* val collate : (elem * elem -> order) -> slice * slice -> order *)
283 :     fun collate comp (SL{base,start,stop},SL{base=base',start=start',stop=stop'}) =
284 :     let fun cmp (i,i') =
285 :     if (i < stop)
286 :     then if (i' >= stop') then GREATER
287 : blume 859 else case comp(sub'(base, i),
288 : dbm 850 sub'(base', i'))
289 :     of EQUAL => cmp(i+1,i'+1)
290 :     | x => x
291 :     else if (i' < stop') then LESS
292 :     else EQUAL
293 :     in cmp(start,start')
294 :     end
295 : blume 866
296 :     fun base (SL{base=b,start,stop}) = (b, start, stop - start)
297 :    
298 :     fun copy {src = SL{base,start,stop},dst,di} =
299 :     if di < 0 orelse
300 :     di + (stop - start) > A.length dst
301 :     then raise Core.Subscript
302 :     else if di <= start
303 :     then let fun cp i =
304 :     if (i < stop)
305 :     then (update'(dst,di+i,sub'(base, i));
306 :     cp(i+1))
307 :     else ()
308 :     in cp start
309 :     end
310 :     else let fun cp i =
311 :     if (i >= start)
312 :     then (update'(dst,di+i,sub'(base, i));
313 :     cp(i-1))
314 :     else ()
315 :     in cp (stop-1)
316 :     end
317 :    
318 :     fun copyVec {src,dst,di} =
319 :     if di < 0 orelse
320 :     di + Word8VectorSlice.length src > A.length dst
321 :     then raise Core.Subscript
322 :     else Word8VectorSlice.appi(fn (i,x) => update'(dst,di+i,x)) src
323 :    
324 :     fun modifyi f (sl as SL{base,start,stop}) =
325 :     appi (fn (i, x) => update' (base, start+i, f (i, x))) sl
326 :    
327 :     fun modify f (sl as SL{base,start,stop}) =
328 :     appi (fn (i, x) => update' (base, start+i, f x)) sl
329 : dbm 850 end (* structure Word8ArraySlice *)

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