tools-poly/poly/Binarymap.sml

56 	  value : 'a,
67     fun N(k,v,E,E) = T{key=k,value=v,cnt=1,left=E,right=E}
68       | N(k,v,E,r as T n) = T{key=k,value=v,cnt=1+(#cnt n),left=E,right=r}
69       | N(k,v,l as T n,E) = T{key=k,value=v,cnt=1+(#cnt n),left=l,right=E}
71           T{key=k,value=v,cnt=1+(#cnt n)+(#cnt n'),left=l,right=r}
73     fun single_L (a,av,x,T{key=b,value=bv,left=y,right=z,...}) =
76     fun single_R (b,bv,T{key=a,value=av,left=x,right=y,...},z) =
79     fun double_L (a,av,w,T{key=c,value=cv,
80 			   left=T{key=b,value=bv,left=x,right=y,...},
84     fun double_R (c,cv,T{key=a,value=av,left=w,
85 			 right=T{key=b,value=bv,left=x,right=y,...},...},z) =
89     fun T' (k,v,E,E) = T{key=k,value=v,cnt=1,left=E,right=E}
91           T{key=k,value=v,cnt=2,left=E,right=r}
93           T{key=k,value=v,cnt=2,left=l,right=E}
123           else T{key=k,value=v,cnt=ln+rn+1,left=l,right=r}
126       fun min (T{left=E,key,value,...}) = (key,value)
131         | delmin (T{key,value,left,right,...}) =
132 	  T'(key,value,delmin left,right)
144 	let fun ins E = T{key=x,value=v,cnt=1,left=E,right=E}
145 	      | ins (T(set as {key,left,right,value,...})) =
147 		    GREATER => T'(key,value,ins left,right)
148 		  | LESS    => T'(key,value,left,ins right)
150 			T{key=x,value=v,left=left,right=right,cnt= #cnt set}
159 		  | _       => #value n
166 	      | rm (set as T{key,left,right,value,...}) =
169 				in (T'(key, value, left', right), v) end
171 				in (T'(key, value, left, right'), v) end
172 		   | _       => (delete'(left,right),value))
178 	      | d2l (T{key,value,left,right,...}) res =
179 		d2l left ((key,value) :: d2l right res)
184         | a (T{key,value,left,right,...}) = (a right; f(key,value); a left)
189         | a (T{key,value,left,right,...}) = (a left; f(key,value); a right)
194         | a (T{key,value,left,right,...}) v = a left (f(key,value,a right v))
199         | a (T{key,value,left,right,...}) v = a right (f(key,value,a left v))
204         | a (T{key,value,left,right,cnt}) = let
206             val value' = f(key,value)
208               T{cnt=cnt, key=key,value=value',left = left', right = a right}
214 	      | a (T{key,value,left,right,cnt}) =
217 		    T{cnt=cnt, key=key, value=f value, left = left',