1 " |
1 " |
2 COPYRIGHT (c) 1991 by Claus Gittinger |
2 COPYRIGHT (c) 1991 by Claus Gittinger |
3 All Rights Reserved |
3 All Rights Reserved |
4 |
4 |
5 This software is furnished under a license and may be used |
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 |
6 only in accordance with the terms of that license and with the |
7 inclusion of the above copyright notice. This software may not |
7 inclusion of the above copyright notice. This software may not |
8 be provided or otherwise made available to, or used by, any |
8 be provided or otherwise made available to, or used by, any |
17 category:'Collections-Unordered' |
17 category:'Collections-Unordered' |
18 ! |
18 ! |
19 |
19 |
20 Set comment:' |
20 Set comment:' |
21 COPYRIGHT (c) 1991 by Claus Gittinger |
21 COPYRIGHT (c) 1991 by Claus Gittinger |
22 All Rights Reserved |
22 All Rights Reserved |
23 |
23 |
24 $Header: /cvs/stx/stx/libbasic/Set.st,v 1.12 1994-08-22 12:13:25 claus Exp $ |
24 $Header: /cvs/stx/stx/libbasic/Set.st,v 1.13 1994-10-10 00:28:14 claus Exp $ |
25 '! |
25 '! |
26 |
26 |
27 !Set class methodsFor:'documentation'! |
27 !Set class methodsFor:'documentation'! |
28 |
28 |
29 copyright |
29 copyright |
30 " |
30 " |
31 COPYRIGHT (c) 1991 by Claus Gittinger |
31 COPYRIGHT (c) 1991 by Claus Gittinger |
32 All Rights Reserved |
32 All Rights Reserved |
33 |
33 |
34 This software is furnished under a license and may be used |
34 This software is furnished under a license and may be used |
35 only in accordance with the terms of that license and with the |
35 only in accordance with the terms of that license and with the |
36 inclusion of the above copyright notice. This software may not |
36 inclusion of the above copyright notice. This software may not |
37 be provided or otherwise made available to, or used by, any |
37 be provided or otherwise made available to, or used by, any |
66 used in sets or dictionaries, you should provide some better hash |
58 used in sets or dictionaries, you should provide some better hash |
67 values. |
59 values. |
68 |
60 |
69 Examples: |
61 Examples: |
70 |
62 |
71 |s| |
63 |s| |
72 s := Set new. |
64 s := Set new. |
73 s add:'hello'. |
65 s add:'hello'. |
74 s add:'world'. |
66 s add:'world'. |
75 s add:#foo. |
67 s add:#foo. |
76 s add:1.2345678. |
68 s add:1.2345678. |
77 s add:'hello'. |
69 s add:'hello'. |
78 |
70 |
79 s printNL. |
71 s printNL. |
80 's size -> ' print. s size printNL. |
72 's size -> ' print. s size printNL. |
81 '(s includes:''hello'') ->' print. (s includes:'hello') printNL. |
73 '(s includes:''hello'') ->' print. (s includes:'hello') printNL. |
82 '(s includes:#foo) ->' print. (s includes:#foo) printNL. |
74 '(s includes:#foo) ->' print. (s includes:#foo) printNL. |
83 '(s includes:#bar) ->' print. (s includes:#bar) printNL. |
75 '(s includes:#bar) ->' print. (s includes:#bar) printNL. |
84 " |
76 " |
85 ! ! |
77 ! ! |
86 |
78 |
87 !Set class methodsFor:'initialization'! |
79 !Set class methodsFor:'initialization'! |
88 |
80 |
89 initialize |
81 initialize |
90 "initialize the Set class" |
82 "initialize the Set class" |
91 |
83 |
92 DeletedEntry isNil ifTrue:[ |
84 DeletedEntry isNil ifTrue:[ |
93 DeletedEntry := Object new |
85 DeletedEntry := Object new |
94 ]. |
86 ]. |
95 |
87 |
96 "Set initialize" |
88 "Set initialize" |
97 ! ! |
89 ! ! |
98 |
90 |
105 ! |
97 ! |
106 |
98 |
107 new:anInteger |
99 new:anInteger |
108 "return a new empty Set with space for anInteger elements" |
100 "return a new empty Set with space for anInteger elements" |
109 |
101 |
110 ^ self basicNew setTally:anInteger |
102 " |
|
103 make it somewhat bigger; hashing works better if fill grade is |
|
104 below 10% (make it 75% here ..) |
|
105 " |
|
106 ^ self basicNew setTally:(anInteger * 4 // 3) |
|
107 ! ! |
|
108 |
|
109 !Set methodsFor:'copying'! |
|
110 |
|
111 postCopy |
|
112 "have to copy the keyArray too" |
|
113 |
|
114 keyArray := keyArray shallowCopy |
111 ! ! |
115 ! ! |
112 |
116 |
113 !Set methodsFor:'private'! |
117 !Set methodsFor:'private'! |
114 |
118 |
115 keyContainerOfSize:n |
119 keyContainerOfSize:n |
139 |sz "{Class: SmallInteger}" |
143 |sz "{Class: SmallInteger}" |
140 newSize "{Class: SmallInteger}" | |
144 newSize "{Class: SmallInteger}" | |
141 |
145 |
142 sz := keyArray basicSize. |
146 sz := keyArray basicSize. |
143 sz > 30 ifTrue:[ |
147 sz > 30 ifTrue:[ |
144 tally < (sz // 8) ifTrue:[ |
148 tally < (sz // 8) ifTrue:[ |
145 newSize := sz // 7. |
149 newSize := sz // 7. |
146 self grow:newSize |
150 self grow:newSize |
147 ] |
151 ] |
148 ] |
152 ] |
149 ! |
153 ! |
150 |
154 |
151 goodSizeFor:arg |
155 goodSizeFor:arg |
152 "return a good array size for the given argument. |
156 "return a good array size for the given argument. |
157 " |
161 " |
158 mhmh - this returns good numbers for collections with up-to about |
162 mhmh - this returns good numbers for collections with up-to about |
159 500k elements; if you have bigger ones, add some more primes here ... |
163 500k elements; if you have bigger ones, add some more primes here ... |
160 " |
164 " |
161 arg <= 524288 ifTrue:[ |
165 arg <= 524288 ifTrue:[ |
162 "2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288" |
166 "2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288" |
163 ^ #(11 11 11 17 37 67 131 257 521 1031 2053 4099 8209 16411 32771 65537 131101 262147 524309) at:(arg highBit) |
167 ^ #(11 11 11 17 37 67 131 257 521 1031 2053 4099 8209 16411 32771 65537 131101 262147 524309) at:(arg highBit) |
164 ]. |
168 ]. |
165 " |
169 " |
166 make it odd - at least |
170 make it odd - at least |
167 " |
171 " |
168 ^ arg bitOr:1 |
172 ^ arg bitOr:1 |
186 length "{ Class:SmallInteger }" |
190 length "{ Class:SmallInteger }" |
187 startIndex probe| |
191 startIndex probe| |
188 |
192 |
189 length := keyArray basicSize. |
193 length := keyArray basicSize. |
190 length < 10 ifTrue:[ |
194 length < 10 ifTrue:[ |
191 "assuming, that for small collections the overhead of hashing |
195 "assuming, that for small collections the overhead of hashing |
192 is large ... maybe that proves wrong (if overhead of comparing |
196 is large ... maybe that proves wrong (if overhead of comparing |
193 is high)" |
197 is high)" |
194 ^ keyArray indexOf:key ifAbsent:aBlock |
198 ^ keyArray indexOf:key ifAbsent:aBlock |
195 ]. |
199 ]. |
196 |
200 |
197 startIndex := key hash \\ length + 1. |
201 startIndex := key hash \\ length + 1. |
198 index := startIndex. |
202 index := startIndex. |
199 |
203 |
200 [true] whileTrue:[ |
204 [true] whileTrue:[ |
201 probe := (keyArray basicAt:index). |
205 probe := (keyArray basicAt:index). |
202 key = probe ifTrue:[^ index]. |
206 key = probe ifTrue:[^ index]. |
203 |
207 |
204 index == length ifTrue:[ |
208 index == length ifTrue:[ |
205 index := 1 |
209 index := 1 |
206 ] ifFalse:[ |
210 ] ifFalse:[ |
207 index := index + 1 |
211 index := index + 1 |
208 ]. |
212 ]. |
209 ((probe isNil) or:[index == startIndex]) ifTrue:[^ aBlock value]. |
213 ((probe isNil) or:[index == startIndex]) ifTrue:[^ aBlock value]. |
210 ] |
214 ] |
211 ! |
215 ! |
212 |
216 |
213 findKeyOrNil:key |
217 findKeyOrNil:key |
214 "Look for the key in the receiver. If it is found, return |
218 "Look for the key in the receiver. If it is found, return |
223 length := keyArray basicSize. |
227 length := keyArray basicSize. |
224 startIndex := key hash \\ length + 1. |
228 startIndex := key hash \\ length + 1. |
225 index := startIndex. |
229 index := startIndex. |
226 |
230 |
227 [true] whileTrue:[ |
231 [true] whileTrue:[ |
228 probe := keyArray basicAt:index. |
232 probe := keyArray basicAt:index. |
229 (probe isNil or: [key = probe]) ifTrue:[^ index]. |
233 (probe isNil or: [key = probe]) ifTrue:[^ index]. |
230 probe == DeletedEntry ifTrue:[ |
234 probe == DeletedEntry ifTrue:[ |
231 keyArray basicAt:index put:nil. |
235 keyArray basicAt:index put:nil. |
232 ^ index |
236 ^ index |
233 ]. |
237 ]. |
234 |
238 |
235 index == length ifTrue:[ |
239 index == length ifTrue:[ |
236 index := 1 |
240 index := 1 |
237 ] ifFalse:[ |
241 ] ifFalse:[ |
238 index := index + 1 |
242 index := index + 1 |
239 ]. |
243 ]. |
240 index == startIndex ifTrue:[^ self grow findKeyOrNil:key]. |
244 index == startIndex ifTrue:[^ self grow findKeyOrNil:key]. |
241 ] |
245 ] |
242 ! |
246 ! |
243 |
247 |
244 findNil:key |
248 findNil:key |
245 "Look for the next slot usable for key. This method assumes that |
249 "Look for the next slot usable for key. This method assumes that |
250 |
254 |
251 length := keyArray basicSize. |
255 length := keyArray basicSize. |
252 index := key hash \\ length + 1. |
256 index := key hash \\ length + 1. |
253 |
257 |
254 [(keyArray basicAt:index) notNil] whileTrue:[ |
258 [(keyArray basicAt:index) notNil] whileTrue:[ |
255 index == length ifTrue:[ |
259 index == length ifTrue:[ |
256 index := 1 |
260 index := 1 |
257 ] ifFalse:[ |
261 ] ifFalse:[ |
258 index := index + 1 |
262 index := index + 1 |
259 ]. |
263 ]. |
260 "notice: no check for no nil found - we must find one since |
264 "notice: no check for no nil found - we must find one since |
261 this is only called after growing" |
265 this is only called after growing" |
262 ]. |
266 ]. |
263 ^ index |
267 ^ index |
264 ! |
268 ! |
265 |
269 |
266 grow |
270 grow |
282 keyArray := newKeyArray := self keyContainerOfSize:(self goodSizeFor:newSize). |
286 keyArray := newKeyArray := self keyContainerOfSize:(self goodSizeFor:newSize). |
283 |
287 |
284 oldSize := oldKeyArray size. |
288 oldSize := oldKeyArray size. |
285 deletedEntry := DeletedEntry. |
289 deletedEntry := DeletedEntry. |
286 1 to:oldSize do:[:srcIndex | |
290 1 to:oldSize do:[:srcIndex | |
287 elem := oldKeyArray basicAt:srcIndex. |
291 elem := oldKeyArray basicAt:srcIndex. |
288 (elem notNil and:[elem ~~ deletedEntry]) ifTrue:[ |
292 (elem notNil and:[elem ~~ deletedEntry]) ifTrue:[ |
289 "cannot be already there" |
293 "cannot be already there" |
290 newKeyArray basicAt:(self findNil:elem) put:elem |
294 newKeyArray basicAt:(self findNil:elem) put:elem |
291 ]. |
295 ]. |
292 ]. |
296 ]. |
293 ! |
297 ! |
294 |
298 |
295 rehash |
299 rehash |
296 "rehash is done by re-adding all elements to a new empty set. |
300 "rehash is done by re-adding all elements to a new empty set. |
302 oldKeyArray := keyArray. |
306 oldKeyArray := keyArray. |
303 n := oldKeyArray size. |
307 n := oldKeyArray size. |
304 keyArray := newKeyArray := self keyContainerOfSize:n. |
308 keyArray := newKeyArray := self keyContainerOfSize:n. |
305 |
309 |
306 1 to:n do:[:index | |
310 1 to:n do:[:index | |
307 element := oldKeyArray at:index. |
311 element := oldKeyArray at:index. |
308 (element notNil and:[element ~~ DeletedEntry]) ifTrue:[ |
312 (element notNil and:[element ~~ DeletedEntry]) ifTrue:[ |
309 "cannot be already there" |
313 "cannot be already there" |
310 newKeyArray basicAt:(self findNil:element) put:element |
314 newKeyArray basicAt:(self findNil:element) put:element |
311 ]. |
315 ]. |
312 ] |
316 ] |
313 ! |
317 ! |
314 |
318 |
315 rehashFrom:startIndex |
319 rehashFrom:startIndex |
316 "rehash elements starting at index - after a remove. |
320 "rehash elements starting at index - after a remove. |
317 Notice: due to the new implementation of remove, |
321 Notice: due to the new implementation of remove, |
318 this is no longer needed" |
322 this is no longer needed" |
319 |
323 |
320 |element i "{ Class:SmallInteger }" |
324 |element i "{ Class:SmallInteger }" |
321 length |
325 length |
322 index "{ Class:SmallInteger }" | |
326 index "{ Class:SmallInteger }" | |
323 |
327 |
324 length := keyArray basicSize. |
328 length := keyArray basicSize. |
325 index := startIndex. |
329 index := startIndex. |
326 element := keyArray basicAt:index. |
330 element := keyArray basicAt:index. |
327 [element notNil] whileTrue:[ |
331 [element notNil] whileTrue:[ |
328 i := self findNil:element. |
332 i := self findNil:element. |
329 i == index ifTrue:[ |
333 i == index ifTrue:[ |
330 ^ self |
334 ^ self |
331 ]. |
335 ]. |
332 keyArray basicAt:i put:element. |
336 keyArray basicAt:i put:element. |
333 keyArray basicAt:index put:nil. |
337 keyArray basicAt:index put:nil. |
334 |
338 |
335 index == length ifTrue:[ |
339 index == length ifTrue:[ |
336 index := 1 |
340 index := 1 |
337 ] ifFalse:[ |
341 ] ifFalse:[ |
338 index := index + 1. |
342 index := index + 1. |
339 ]. |
343 ]. |
340 element := keyArray basicAt:index. |
344 element := keyArray basicAt:index. |
341 ] |
345 ] |
342 ! ! |
346 ! ! |
343 |
347 |
344 !Set methodsFor:'accessing'! |
348 !Set methodsFor:'accessing'! |
345 |
349 |
395 "add the argument, anObject to the receiver" |
399 "add the argument, anObject to the receiver" |
396 |
400 |
397 |index "{ Class: SmallInteger }"| |
401 |index "{ Class: SmallInteger }"| |
398 |
402 |
399 anObject notNil ifTrue:[ |
403 anObject notNil ifTrue:[ |
400 index := self findKeyOrNil:anObject. |
404 index := self findKeyOrNil:anObject. |
401 (keyArray basicAt:index) isNil ifTrue:[ |
405 (keyArray basicAt:index) isNil ifTrue:[ |
402 keyArray basicAt:index put:anObject. |
406 keyArray basicAt:index put:anObject. |
403 tally := tally + 1. |
407 tally := tally + 1. |
404 |
408 |
405 self fullCheck. |
409 self fullCheck. |
406 ] |
410 ] |
407 ]. |
411 ]. |
408 ^ anObject |
412 ^ anObject |
409 ! |
413 ! |
410 |
414 |
411 remove:oldObject ifAbsent:exceptionBlock |
415 remove:oldObject ifAbsent:exceptionBlock |
425 index == 0 ifTrue:[^ exceptionBlock value]. |
429 index == 0 ifTrue:[^ exceptionBlock value]. |
426 |
430 |
427 keyArray basicAt:index put:nil. |
431 keyArray basicAt:index put:nil. |
428 tally := tally - 1. |
432 tally := tally - 1. |
429 tally == 0 ifTrue:[ |
433 tally == 0 ifTrue:[ |
430 keyArray := self keyContainerOfSize:(self goodSizeFor:0). |
434 keyArray := self keyContainerOfSize:(self goodSizeFor:0). |
431 ] ifFalse:[ |
435 ] ifFalse:[ |
432 index == keyArray basicSize ifTrue:[ |
436 index == keyArray basicSize ifTrue:[ |
433 next := 1 |
437 next := 1 |
434 ] ifFalse:[ |
438 ] ifFalse:[ |
435 next := index + 1. |
439 next := index + 1. |
436 ]. |
440 ]. |
437 (keyArray basicAt:next) notNil ifTrue:[ |
441 (keyArray basicAt:next) notNil ifTrue:[ |
438 keyArray basicAt:index put:DeletedEntry. |
442 keyArray basicAt:index put:DeletedEntry. |
439 ]. |
443 ]. |
440 self emptyCheck |
444 self emptyCheck |
441 ]. |
445 ]. |
442 ^ oldObject |
446 ^ oldObject |
443 ! |
447 ! |
444 |
448 |
445 removeAll |
449 removeAll |