portableML/poly/Intmap.sml

55          value: 'a,
64     fun N(k,v,E,E) = T{key=k,value=v,cnt=1,left=E,right=E}
65       | N(k,v,E,r as T n) = T{key=k,value=v,cnt=1+(#cnt n),left=E,right=r}
66       | N(k,v,l as T n,E) = T{key=k,value=v,cnt=1+(#cnt n),left=l,right=E}
68           T{key=k,value=v,cnt=1+(#cnt n)+(#cnt n'),left=l,right=r}
70     fun single_L (a,av,x,T{key=b,value=bv,left=y,right=z,...}) =
73     fun single_R (b,bv,T{key=a,value=av,left=x,right=y,...},z) =
76     fun double_L (a,av,w,T{key=c,value=cv,left=T{key=b,value=bv,left=x,right=y,...},right=z,...}) =
79     fun double_R (c,cv,T{key=a,value=av,left=w,right=T{key=b,value=bv,left=x,right=y,...},...},z) =
83     fun T' (k,v,E,E) = T{key=k,value=v,cnt=1,left=E,right=E}
85           T{key=k,value=v,cnt=2,left=E,right=r}
87           T{key=k,value=v,cnt=2,left=l,right=E}
117           else T{key=k,value=v,cnt=ln+rn+1,left=l,right=r}
120       fun min (T{left=E,key,value,...}) = (key,value)
125         | delmin (T{key,value,left,right,...}) = T'(key,value,delmin left,right)
137     fun insert (E,x,v) = T{key=x,value=v,cnt=1,left=E,right=E}
138       | insert (T(set as {key,left,right,value,...}),x,v) =
139           if key > x then T'(key,value,insert(left,x,v),right)
140           else if key < x then T'(key,value,left,insert(right,x,v))
141           else T{key=x,value=v,left=left,right=right,cnt= #cnt set}
148             else #value n
154       | remove (set as T{key,left,right,value,...},x) =
157             in (T'(key,value,left',right),v) end
160             in (T'(key,value,left,right'),v) end
161           else (delete'(left,right),value)
165         | d2l (T{key,value,left,right,...}) res =
166           d2l left ((key,value) :: d2l right res)
171         | a (T{key,value,left,right,...}) = (a left; f(key,value); a right)
176         | a (T{key,value,left,right,...}) = (a right; f(key,value); a left)
181         | a (T{key,value,left,right,...}) v = a left (f(key,value,a right v))
186         | a (T{key,value,left,right,...}) v = a right (f(key,value,a left v))
191         | a (T{key,value,left,right,cnt}) = let
193             val value' = f(key,value)
195               T{cnt=cnt, key=key,value=value',left = left', right = a right}
201         | a (T{key,value,left,right,cnt}) = let
203             val value' = f value
205               T{cnt=cnt, key=key,value=value',left = left', right = a right}