--- a/Set.st Sat Dec 11 01:46:55 1993 +0100
+++ b/Set.st Sat Dec 11 01:59:35 1993 +0100
@@ -11,7 +11,7 @@
"
Collection subclass:#Set
- instanceVariableNames:'tally contentsArray'
+ instanceVariableNames:'tally keyArray'
classVariableNames:''
poolDictionaries:''
category:'Collections-Unordered'
@@ -24,7 +24,7 @@
a Set is a collection where each element occurs at most once.
-$Header: /cvs/stx/stx/libbasic/Set.st,v 1.4 1993-10-13 02:13:35 claus Exp $
+$Header: /cvs/stx/stx/libbasic/Set.st,v 1.5 1993-12-11 00:56:26 claus Exp $
written jun 91 by claus
jan 93 claus: changed to use hashing
'!
@@ -45,12 +45,19 @@
!Set methodsFor:'private'!
+keyContainerOfSize:n
+ "return a container for keys of size n.
+ Extracted to make life of weak subclasses easier ..."
+
+ ^ Array new:n
+!
+
fullCheck
"check if dictionary is full, grow if so.
Definition of full is currently:'filled more than 70%'"
"grow if filled more than 70% "
- tally > (contentsArray basicSize * 7 // 10) ifTrue:[
+ tally > (keyArray basicSize * 7 // 10) ifTrue:[
self grow
]
!
@@ -72,7 +79,7 @@
and set tally to zero.
The size is increased to the next prime for better hashing behavior."
- contentsArray := Array new:(self goodSizeFor:count).
+ keyArray := Array new:(self goodSizeFor:count).
tally := 0
!
@@ -84,25 +91,31 @@
|index "{ Class:SmallInteger }"
length startIndex probe|
- length := contentsArray basicSize.
+ length := keyArray basicSize.
+ length < 10 ifTrue:[
+ "assuming, that for small collections the overhead of hashing
+ is large ... maybe that proves wrong (if overhead of comparing
+ is high)"
+ ^ keyArray indexOf:key ifAbsent:aBlock
+ ].
+
startIndex := key hash \\ length + 1.
index := startIndex.
[true] whileTrue:[
- probe := (contentsArray basicAt:index).
+ probe := (keyArray basicAt:index).
key = probe ifTrue:[^ index].
- probe isNil ifTrue:[^ aBlock value].
index == length ifTrue:[
index := 1
] ifFalse:[
index := index + 1
].
- index == startIndex ifTrue:[^ aBlock value].
+ ((probe isNil) or:[index == startIndex]) ifTrue:[^ aBlock value].
]
!
-findElementOrNil:key
+findKeyOrNil:key
"Look for the key in the receiver. If it is found, return
the index of the slot containing the key, otherwise
return the index of the first unused slot. Grow the receiver,
@@ -111,12 +124,12 @@
|index "{ Class:SmallInteger }"
length startIndex probe|
- length := contentsArray basicSize.
+ length := keyArray basicSize.
startIndex := key hash \\ length + 1.
index := startIndex.
[true] whileTrue:[
- probe := contentsArray basicAt:index.
+ probe := keyArray basicAt:index.
(probe isNil or: [key = probe]) ifTrue:[^ index].
index == length ifTrue:[
@@ -124,7 +137,7 @@
] ifFalse:[
index := index + 1
].
- index == startIndex ifTrue:[^ self grow findElementOrNil:key].
+ index == startIndex ifTrue:[^ self grow findKeyOrNil:key].
]
!
@@ -135,10 +148,10 @@
|index "{ Class:SmallInteger }"
length|
- length := contentsArray basicSize.
+ length := keyArray basicSize.
index := key hash \\ length + 1.
- [(contentsArray basicAt:index) notNil] whileTrue:[
+ [(keyArray basicAt:index) notNil] whileTrue:[
index == length ifTrue:[
index := 1
] ifFalse:[
@@ -154,7 +167,7 @@
"change the number of element slots of the collection to a useful
new size"
- self grow:(contentsArray basicSize * 2)
+ self grow:(keyArray basicSize * 2)
!
grow:newSize
@@ -162,23 +175,21 @@
we have to rehash (which is done by re-adding all elements to a new
empty set)."
- |oldArray oldSize elem
- n "{ Class:SmallInteger }" |
+ |oldKeyArray elem
+ oldSize "{ Class:SmallInteger }" |
- oldArray := contentsArray.
- oldSize := tally.
+ oldKeyArray := keyArray.
- contentsArray := Array new:(self goodSizeFor:newSize).
+ keyArray := Array new:(self goodSizeFor:newSize).
- n := oldArray size.
- 1 to:n do:[:srcIndex |
- elem := oldArray basicAt:srcIndex.
+ oldSize := oldKeyArray size.
+ 1 to:oldSize do:[:srcIndex |
+ elem := oldKeyArray basicAt:srcIndex.
elem notNil ifTrue:[
"cannot be already there"
- contentsArray basicAt:(self findNil:elem) put:elem
+ keyArray basicAt:(self findNil:elem) put:elem
].
- ].
- tally := oldSize
+ ]
!
rehash
@@ -187,14 +198,14 @@
| oldArray element
n "{ Class:SmallInteger }" |
- oldArray := contentsArray.
+ oldArray := keyArray.
n := oldArray size.
- contentsArray := Array new:n.
+ keyArray := Array new:n.
1 to:n do:[:index |
element := oldArray at:index.
element notNil ifTrue:[
"cannot be already there"
- contentsArray basicAt:(self findNil:element) put:element
+ keyArray basicAt:(self findNil:element) put:element
].
]
!
@@ -206,23 +217,23 @@
length
index "{ Class:SmallInteger }" |
- length := contentsArray basicSize.
+ length := keyArray basicSize.
index := startIndex.
- element := contentsArray basicAt:index.
+ element := keyArray basicAt:index.
[element notNil] whileTrue:[
i := self findNil:element.
i == index ifTrue:[
^ self
].
- contentsArray basicAt:i put:element.
- contentsArray basicAt:index put:nil.
+ keyArray basicAt:i put:element.
+ keyArray basicAt:index put:nil.
index == length ifTrue:[
index := 1
] ifFalse:[
index := index + 1.
].
- element := contentsArray basicAt:index.
+ element := keyArray basicAt:index.
]
! !
@@ -282,9 +293,9 @@
|index|
anObject notNil ifTrue:[
- index := self findElementOrNil:anObject.
- (contentsArray basicAt:index) isNil ifTrue:[
- contentsArray basicAt:index put:anObject.
+ index := self findKeyOrNil:anObject.
+ (keyArray basicAt:index) isNil ifTrue:[
+ keyArray basicAt:index put:anObject.
tally := tally + 1.
self fullCheck.
@@ -300,12 +311,12 @@
|index next|
index := self find:oldObject ifAbsent:[^ exceptionBlock value].
- contentsArray basicAt:index put:nil.
+ keyArray basicAt:index put:nil.
tally := tally - 1.
tally == 0 ifTrue:[
- contentsArray := Array new:(self goodSizeFor:0).
+ keyArray := Array new:(self goodSizeFor:0).
] ifFalse:[
- index == contentsArray basicSize ifTrue:[
+ index == keyArray basicSize ifTrue:[
next := 1
] ifFalse:[
next := index + 1.
@@ -314,7 +325,7 @@
however, since there is some probability that the next
element is nil, this saves a send sometimes
"
- (contentsArray basicAt:next) notNil ifTrue:[
+ (keyArray basicAt:next) notNil ifTrue:[
self rehashFrom:next.
]
].
@@ -326,7 +337,7 @@
do:aBlock
"perform the block for all members in the collection."
- contentsArray do:[:each |
+ keyArray do:[:each |
each notNil ifTrue:[
aBlock value:each
]