dev/sw/int-binary-map.sml

70           value : 'a,
80     fun N(k,v,E,E) = T{key=k,value=v,cnt=1,left=E,right=E}
81       | N(k,v,E,r as T n) = T{key=k,value=v,cnt=1+(#cnt n),left=E,right=r}
82       | N(k,v,l as T n,E) = T{key=k,value=v,cnt=1+(#cnt n),left=l,right=E}
84           T{key=k,value=v,cnt=1+(#cnt n)+(#cnt n'),left=l,right=r}
86     fun single_L (a,av,x,T{key=b,value=bv,left=y,right=z,...}) =
89     fun single_R (b,bv,T{key=a,value=av,left=x,right=y,...},z) =
92     fun double_L (a,av,w,T{key=c,value=cv,left=T{key=b,value=bv,left=x,right=y,...},right=z,...}) =
95     fun double_R (c,cv,T{key=a,value=av,left=w,right=T{key=b,value=bv,left=x,right=y,...},...},z) =
99     fun T' (k,v,E,E) = T{key=k,value=v,cnt=1,left=E,right=E}
101           T{key=k,value=v,cnt=2,left=E,right=r}
103           T{key=k,value=v,cnt=2,left=l,right=E}
133           else T{key=k,value=v,cnt=ln+rn+1,left=l,right=r}
136       fun min (T{left=E,key,value,...}) = (key,value)
141         | delmin (T{key,value,left,right,...}) = T'(key,value,delmin left,right)
153     fun insert (E,x,v) = T{key=x,value=v,cnt=1,left=E,right=E}
154       | insert (T(set as {key,left,right,value,...}),x,v) =
155           if key > x then T'(key,value,insert(left,x,v),right)
156           else if key < x then T'(key,value,left,insert(right,x,v))
157           else T{key=x,value=v,left=left,right=right,cnt= #cnt set}
160       | update (T(set as {key,left,right,value,...}),x,f) =
161           if key > x then T'(key,value,update(left,x,f),right)
162           else if key < x then T'(key,value,left,update(right,x,f))
163           else T{key=x,value=f(value),left=left,right=right,cnt= #cnt set}
170                 else SOME(#value n)
176      |  findSome (T{key,value,...}) = SOME (key,value)
179       | remove (set as T{key,left,right,value,...},x) =
182             in (T'(key,value,left',right),v) end
185             in (T'(key,value,left,right'),v) end
186           else (delete'(left,right),value)
190             | d2l (T{key,value,left,right,...}, l) =
191                 d2l(left, value::(d2l(right,l)))
198             | d2l (T{key,value,left,right,...}, l) =
199                 d2l(left, (key,value)::(d2l(right,l)))
215                   | ((T{key=x1, value=y1, ...}, r1), (T{key=x2, value=y2, ...}, r2)) => (
231             | appf (T{key,value,left,right,...}) = (
232                 appf left; f(key,value); appf right)
240             | mapf (T{key,value,left,right,cnt}) = let
242                 val value' = f(key, value)
245                   T{cnt=cnt, key=key, value=value', left = left', right = right'}
254             | fold (T{key,value,left,right,...},v) =
255                 fold (right, f(key, value, fold(left, v)))
263             | fold (T{key,value,left,right,...},v) =
264                 fold (left, f(key, value, fold(right, v)))