equal
deleted
inserted
replaced
22 COPYRIGHT (c) 1991-93 by Claus Gittinger |
22 COPYRIGHT (c) 1991-93 by Claus Gittinger |
23 All Rights Reserved |
23 All Rights Reserved |
24 |
24 |
25 a Set is a collection where each element occurs at most once. |
25 a Set is a collection where each element occurs at most once. |
26 |
26 |
27 %W% %E% |
27 $Header: /cvs/stx/stx/libbasic/Set.st,v 1.3 1993-10-13 00:18:06 claus Exp $ |
28 written jun 91 by claus |
28 written jun 91 by claus |
29 jan 93 claus: changed to use hashing |
29 jan 93 claus: changed to use hashing |
30 '! |
30 '! |
31 |
31 |
32 !Set class methodsFor:'instance creation'! |
32 !Set class methodsFor:'instance creation'! |
80 "Look for the key in the receiver. If it is found, return |
80 "Look for the key in the receiver. If it is found, return |
81 the index of the slot containing the key, otherwise |
81 the index of the slot containing the key, otherwise |
82 return the value of evaluating aBlock." |
82 return the value of evaluating aBlock." |
83 |
83 |
84 |index "{ Class:SmallInteger }" |
84 |index "{ Class:SmallInteger }" |
85 length "{ Class:SmallInteger }" |
85 length startIndex probe| |
86 startIndex "{ Class:SmallInteger }" |
|
87 probe| |
|
88 |
86 |
89 length := contentsArray basicSize. |
87 length := contentsArray basicSize. |
90 startIndex := key hash \\ length + 1. |
88 startIndex := key hash \\ length + 1. |
91 index := startIndex. |
89 index := startIndex. |
92 |
90 |
109 the index of the slot containing the key, otherwise |
107 the index of the slot containing the key, otherwise |
110 return the index of the first unused slot. Grow the receiver, |
108 return the index of the first unused slot. Grow the receiver, |
111 if key was not found, and no unused slots where present" |
109 if key was not found, and no unused slots where present" |
112 |
110 |
113 |index "{ Class:SmallInteger }" |
111 |index "{ Class:SmallInteger }" |
114 length "{ Class:SmallInteger }" |
112 length startIndex probe| |
115 startIndex "{ Class:SmallInteger }" |
|
116 probe| |
|
117 |
113 |
118 length := contentsArray basicSize. |
114 length := contentsArray basicSize. |
119 startIndex := key hash \\ length + 1. |
115 startIndex := key hash \\ length + 1. |
120 index := startIndex. |
116 index := startIndex. |
121 |
117 |
135 findNil:key |
131 findNil:key |
136 "Look for the next slot usable for key. This method assumes that |
132 "Look for the next slot usable for key. This method assumes that |
137 key is not already in the receiver - used only while growing/rehashing" |
133 key is not already in the receiver - used only while growing/rehashing" |
138 |
134 |
139 |index "{ Class:SmallInteger }" |
135 |index "{ Class:SmallInteger }" |
140 length "{ Class:SmallInteger }"| |
136 length| |
141 |
137 |
142 length := contentsArray basicSize. |
138 length := contentsArray basicSize. |
143 index := key hash \\ length + 1. |
139 index := key hash \\ length + 1. |
144 |
140 |
145 [(contentsArray basicAt:index) notNil] whileTrue:[ |
141 [(contentsArray basicAt:index) notNil] whileTrue:[ |
164 grow:newSize |
160 grow:newSize |
165 "change the number of element slots of the collection - to do this, |
161 "change the number of element slots of the collection - to do this, |
166 we have to rehash (which is done by re-adding all elements to a new |
162 we have to rehash (which is done by re-adding all elements to a new |
167 empty set)." |
163 empty set)." |
168 |
164 |
169 |oldElements oldSize |
165 |oldArray oldSize elem |
170 srcIndex "{ Class:SmallInteger }"| |
166 n "{ Class:SmallInteger }" | |
171 |
167 |
172 oldElements := contentsArray. |
168 oldArray := contentsArray. |
173 oldSize := tally. |
169 oldSize := tally. |
174 |
170 |
175 contentsArray := Array new:(self goodSizeFor:newSize). |
171 contentsArray := Array new:(self goodSizeFor:newSize). |
176 |
172 |
177 srcIndex := 1. |
173 n := oldArray size. |
178 oldElements do:[:elem | |
174 1 to:n do:[:srcIndex | |
|
175 elem := oldArray basicAt:srcIndex. |
179 elem notNil ifTrue:[ |
176 elem notNil ifTrue:[ |
180 "cannot be already there" |
177 "cannot be already there" |
181 contentsArray basicAt:(self findNil:elem) put:elem |
178 contentsArray basicAt:(self findNil:elem) put:elem |
182 ]. |
179 ]. |
183 srcIndex := srcIndex + 1 |
|
184 ]. |
180 ]. |
185 tally := oldSize |
181 tally := oldSize |
186 ! |
182 ! |
187 |
183 |
188 rehash |
184 rehash |
204 ! |
200 ! |
205 |
201 |
206 rehashFrom:startIndex |
202 rehashFrom:startIndex |
207 "rehash elements starting at index - after a remove" |
203 "rehash elements starting at index - after a remove" |
208 |
204 |
209 |element i length |
205 |element i "{ Class:SmallInteger }" |
|
206 length |
210 index "{ Class:SmallInteger }" | |
207 index "{ Class:SmallInteger }" | |
211 |
208 |
212 length := contentsArray basicSize. |
209 length := contentsArray basicSize. |
213 index := startIndex. |
210 index := startIndex. |
214 element := contentsArray basicAt:index. |
211 element := contentsArray basicAt:index. |