portableML/poly/Intmap.sml

58          right: 'a intmap}
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}
84       | T' (k,v,E,r as T{right=E,left=E,...}) =
85           T{key=k,value=v,cnt=2,left=E,right=r}
86       | T' (k,v,l as T{right=E,left=E,...},E) =
87           T{key=k,value=v,cnt=2,left=l,right=E}
89       | T' (p as (_,_,E,T{left=T _,right=E,...})) = double_L p
90       | T' (p as (_,_,T{left=E,right=T _,...},E)) = double_R p
93       | T' (p as (_,_,E,T{left=T{cnt=ln,...},right=T{cnt=rn,...},...})) =
95       | T' (p as (_,_,T{left=T{cnt=ln,...},right=T{cnt=rn,...},...},E)) =
99       | T' (p as (_,_,T{right=E,...},E)) = single_R p
101       | T' (p as (k,v,l as T{cnt=ln,left=ll,right=lr,...},
102                       r as T{cnt=rn,left=rl,right=rr,...})) =
103           if rn >= wt ln then (*right is too big*)
117           else T{key=k,value=v,cnt=ln+rn+1,left=l,right=r}
124       fun delmin (T{left=E,right,...}) = right
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}
145         | mem (T(n as {key,left,right,...})) =
146             if x > key then mem right
154       | remove (set as T{key,left,right,value,...},x) =
157             in (T'(key,value,left',right),v) end
159             let val (right',v) = remove(right,x)
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
195               T{cnt=cnt, key=key,value=value',left = left', right = a right}
201         | a (T{key,value,left,right,cnt}) = let
205               T{cnt=cnt, key=key,value=value',left = left', right = a right}