|
1 " |
|
2 COPYRIGHT (c) 1991-93 by Claus Gittinger |
|
3 All Rights Reserved |
|
4 |
|
5 This software is furnished under a license and may be used |
|
6 only in accordance with the terms of that license and with the |
|
7 inclusion of the above copyright notice. This software may not |
|
8 be provided or otherwise made available to, or used by, any |
|
9 other person. No title to or ownership of the software is |
|
10 hereby transferred. |
|
11 " |
|
12 |
|
13 Collection subclass:#Set |
|
14 instanceVariableNames:'tally contentsArray' |
|
15 classVariableNames:'' |
|
16 poolDictionaries:'' |
|
17 category:'Collections-Unordered' |
|
18 ! |
|
19 |
|
20 Set comment:' |
|
21 |
|
22 COPYRIGHT (c) 1991-93 by Claus Gittinger |
|
23 All Rights Reserved |
|
24 |
|
25 a Set is a collection where each element occurs at most once. |
|
26 |
|
27 %W% %E% |
|
28 written jun 91 by claus |
|
29 jan 93 claus: changed to use hashing |
|
30 '! |
|
31 |
|
32 !Set class methodsFor:'instance creation'! |
|
33 |
|
34 new |
|
35 "return a new empty Set" |
|
36 |
|
37 ^ self new:7 |
|
38 ! |
|
39 |
|
40 new:anInteger |
|
41 "return a new empty Set with space for anInteger elements" |
|
42 |
|
43 ^ self basicNew setTally:anInteger |
|
44 ! ! |
|
45 |
|
46 !Set methodsFor:'private'! |
|
47 |
|
48 goodSizeFor:arg |
|
49 "return a good array size for the given argument. |
|
50 Returns the next prime after arg" |
|
51 |
|
52 arg <= 7 ifTrue:[^ 7]. |
|
53 arg <= 16384 ifTrue:[ |
|
54 "2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384" |
|
55 ^ #(7 7 11 17 37 67 131 257 521 1031 2053 4099 8209 16411) at:(arg highBit) |
|
56 ]. |
|
57 ^ arg bitOr:1 |
|
58 ! |
|
59 |
|
60 setTally:count |
|
61 "initialize the contents array (for at least count slots) |
|
62 and set tally to zero. |
|
63 The size is increased to the next prime for better hashing behavior." |
|
64 |
|
65 contentsArray := Array new:(self goodSizeFor:count). |
|
66 tally := 0 |
|
67 ! |
|
68 |
|
69 find:key ifAbsent:aBlock |
|
70 "Look for the key in the receiver. If it is found, return |
|
71 the index of the slot containing the key, otherwise |
|
72 return the value of evaluating aBlock." |
|
73 |
|
74 |index "{ Class:SmallInteger }" |
|
75 length "{ Class:SmallInteger }" |
|
76 startIndex "{ Class:SmallInteger }" |
|
77 probe| |
|
78 |
|
79 length := contentsArray basicSize. |
|
80 startIndex := key hash \\ length + 1. |
|
81 index := startIndex. |
|
82 |
|
83 [true] whileTrue:[ |
|
84 probe := (contentsArray basicAt:index). |
|
85 key = probe ifTrue:[^ index]. |
|
86 probe isNil ifTrue:[^ aBlock value]. |
|
87 |
|
88 index == length ifTrue:[ |
|
89 index := 1 |
|
90 ] ifFalse:[ |
|
91 index := index + 1 |
|
92 ]. |
|
93 index == startIndex ifTrue:[^ aBlock value]. |
|
94 ] |
|
95 ! |
|
96 |
|
97 findElementOrNil:key |
|
98 "Look for the key in the receiver. If it is found, return |
|
99 the index of the slot containing the key, otherwise |
|
100 return the index of the first unused slot. Grow the receiver, |
|
101 if key was not found, and no unused slots where present" |
|
102 |
|
103 |index "{ Class:SmallInteger }" |
|
104 length "{ Class:SmallInteger }" |
|
105 startIndex "{ Class:SmallInteger }" |
|
106 probe| |
|
107 |
|
108 length := contentsArray basicSize. |
|
109 startIndex := key hash \\ length + 1. |
|
110 index := startIndex. |
|
111 |
|
112 [true] whileTrue:[ |
|
113 probe := contentsArray basicAt:index. |
|
114 (probe isNil or: [key = probe]) ifTrue:[^ index]. |
|
115 |
|
116 index == length ifTrue:[ |
|
117 index := 1 |
|
118 ] ifFalse:[ |
|
119 index := index + 1 |
|
120 ]. |
|
121 index == startIndex ifTrue:[^ self grow findElementOrNil:key]. |
|
122 ] |
|
123 ! |
|
124 |
|
125 findNil:key |
|
126 "Look for the next slot usable for key. This method assumes that |
|
127 key is not already in the receiver - used only while growing/rehashing" |
|
128 |
|
129 |index "{ Class:SmallInteger }" |
|
130 length "{ Class:SmallInteger }"| |
|
131 |
|
132 length := contentsArray basicSize. |
|
133 index := key hash \\ length + 1. |
|
134 |
|
135 [(contentsArray basicAt:index) notNil] whileTrue:[ |
|
136 index == length ifTrue:[ |
|
137 index := 1 |
|
138 ] ifFalse:[ |
|
139 index := index + 1 |
|
140 ]. |
|
141 "notice: no check for no nil found - we must find one since |
|
142 this is only called after growing" |
|
143 ]. |
|
144 ^ index |
|
145 ! |
|
146 |
|
147 grow |
|
148 "change the number of element slots of the collection to a useful |
|
149 new size" |
|
150 |
|
151 self grow:(contentsArray basicSize * 2) |
|
152 ! |
|
153 |
|
154 grow:newSize |
|
155 "change the number of element slots of the collection - to do this, |
|
156 we have to rehash (which is done by re-adding all elements to a new |
|
157 empty set)." |
|
158 |
|
159 |oldElements oldSize |
|
160 srcIndex "{ Class:SmallInteger }"| |
|
161 |
|
162 oldElements := contentsArray. |
|
163 oldSize := tally. |
|
164 self setTally:newSize. |
|
165 |
|
166 srcIndex := 1. |
|
167 oldElements do:[:elem | |
|
168 elem notNil ifTrue:[ |
|
169 "cannot be already there" |
|
170 contentsArray basicAt:(self findNil:elem) put:elem |
|
171 ]. |
|
172 srcIndex := srcIndex + 1 |
|
173 ]. |
|
174 tally := oldSize |
|
175 ! |
|
176 |
|
177 rehash |
|
178 "rehash is done by re-adding all elements to a new empty set." |
|
179 |
|
180 | oldArray | |
|
181 |
|
182 oldArray := contentsArray. |
|
183 contentsArray := Array new:(contentsArray size). |
|
184 oldArray do:[:element | |
|
185 element notNil ifTrue:[ |
|
186 "cannot be already there" |
|
187 contentsArray basicAt:(self findNil:element) put:element |
|
188 ]. |
|
189 ] |
|
190 ! |
|
191 |
|
192 rehashFrom:startIndex |
|
193 "rehash elements starting at index - after a remove" |
|
194 |
|
195 |element i length |
|
196 index "{ Class:SmallInteger }" | |
|
197 |
|
198 length := contentsArray basicSize. |
|
199 index := startIndex. |
|
200 element := contentsArray basicAt:index. |
|
201 [element notNil] whileTrue:[ |
|
202 i := self findNil:element. |
|
203 i == index ifTrue:[ |
|
204 ^ self |
|
205 ]. |
|
206 contentsArray basicAt:i put:element. |
|
207 contentsArray basicAt:index put:nil. |
|
208 |
|
209 index == length ifTrue:[ |
|
210 index := 1 |
|
211 ] ifFalse:[ |
|
212 index := index + 1. |
|
213 ]. |
|
214 element := contentsArray basicAt:index. |
|
215 ] |
|
216 ! ! |
|
217 |
|
218 !Set methodsFor:'accessing'! |
|
219 |
|
220 at:index |
|
221 "report an error: at: is not allowed for Sets" |
|
222 |
|
223 ^ self errorNotKeyed |
|
224 ! |
|
225 |
|
226 at:index put:anObject |
|
227 "report an error: at:put: is not allowed for Sets" |
|
228 |
|
229 ^ self errorNotKeyed |
|
230 ! ! |
|
231 |
|
232 !Set methodsFor:'testing'! |
|
233 |
|
234 size |
|
235 "return the number of set elements" |
|
236 |
|
237 ^ tally |
|
238 ! |
|
239 |
|
240 includes:anObject |
|
241 "return true if the argument anObject is in the receiver" |
|
242 |
|
243 ^ (self find:anObject ifAbsent:[0]) ~~ 0 |
|
244 ! |
|
245 |
|
246 isEmpty |
|
247 "return true if the receiver is empty" |
|
248 |
|
249 ^ tally == 0 |
|
250 ! |
|
251 |
|
252 occurrencesOf:anObject |
|
253 "return the number of occurrences of anObject in the receiver" |
|
254 |
|
255 (self find:anObject ifAbsent:[0]) == 0 ifTrue:[^ 0]. |
|
256 ^ 1 |
|
257 ! |
|
258 |
|
259 isFixedSize |
|
260 "return true if the receiver cannot grow - this will vanish once |
|
261 Arrays and Strings learn how to grow ..." |
|
262 |
|
263 ^ false |
|
264 ! ! |
|
265 |
|
266 !Set methodsFor:'adding & removing'! |
|
267 |
|
268 add:anObject |
|
269 "add the argument, anObject to the receiver" |
|
270 |
|
271 |index| |
|
272 |
|
273 anObject notNil ifTrue:[ |
|
274 index := self findElementOrNil:anObject. |
|
275 (contentsArray basicAt:index) isNil ifTrue:[ |
|
276 contentsArray basicAt:index put:anObject. |
|
277 tally := tally + 1. |
|
278 |
|
279 "grow if filled more than 70% " |
|
280 tally > (contentsArray basicSize * 7 // 10) ifTrue:[ |
|
281 self grow |
|
282 ] |
|
283 ] |
|
284 ]. |
|
285 ^ anObject |
|
286 ! |
|
287 |
|
288 remove:oldObject ifAbsent:exceptionBlock |
|
289 "remove oldObject from the collection and return it. |
|
290 If it was not in the collection return the value of exceptionBlock." |
|
291 |
|
292 |index next| |
|
293 |
|
294 index := self find:oldObject ifAbsent:[^ exceptionBlock value]. |
|
295 contentsArray basicAt:index put:nil. |
|
296 tally := tally - 1. |
|
297 tally == 0 ifTrue:[ |
|
298 contentsArray := Array new:(self goodSizeFor:0). |
|
299 ] ifFalse:[ |
|
300 index == contentsArray basicSize ifTrue:[ |
|
301 next := 1 |
|
302 ] ifFalse:[ |
|
303 next := index + 1. |
|
304 ]. |
|
305 "this check is redundant - is also done in rehashFrom:, |
|
306 however, since there is some probability that the next |
|
307 element is nil, this saves a send sometimes |
|
308 " |
|
309 (contentsArray basicAt:next) notNil ifTrue:[ |
|
310 self rehashFrom:next. |
|
311 ] |
|
312 ]. |
|
313 ^ oldObject |
|
314 ! ! |
|
315 |
|
316 !Set methodsFor:'enumerating'! |
|
317 |
|
318 do:aBlock |
|
319 "perform the block for all members in the collection." |
|
320 |
|
321 contentsArray do:[:each | |
|
322 each notNil ifTrue:[ |
|
323 aBlock value:each |
|
324 ] |
|
325 ] |
|
326 ! ! |