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 /MLRISC/releases/release-110.84/library/orig-hash-array.sml
ViewVC logotype

Annotation of /MLRISC/releases/release-110.84/library/orig-hash-array.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4728 - (view) (download)

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

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