hg/stx-libbasic: comparison Set.st

equal deleted inserted replaced

-:8e03bd717355
+:62303f84ff5f
 other person.  No title to or ownership of the software is
 hereby transferred.
 "
 Collection subclass:#Set
-instanceVariableNames:'tally contentsArray'
+instanceVariableNames:'tally keyArray'
 classVariableNames:''
 poolDictionaries:''
 category:'Collections-Unordered'
 !
 COPYRIGHT (c) 1991 by Claus Gittinger
 All Rights Reserved
 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
 '!
 !Set class methodsFor:'instance creation'!
 ^ self basicNew setTally:anInteger
 ! !
 !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
 ]
 !
 goodSizeFor:arg
 setTally:count
 "initialize the contents array (for at least count slots)
 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
 !
 find:key ifAbsent:aBlock
 "Look for the key in the receiver.  If it is found, return
 return the value of evaluating aBlock."
 |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,
 if key was not found, and no unused slots where present"
 |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:[
 index := 1
 ] ifFalse:[
 index := index + 1
 ].
-index == startIndex ifTrue:[^ self grow findElementOrNil:key].
+index == startIndex ifTrue:[^ self grow findKeyOrNil:key].
 ]
 !
 findNil:key
 "Look for the next slot usable for key.  This method assumes that
 key is not already in the receiver - used only while growing/rehashing"
 |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:[
 index := index + 1
 ].
 grow
 "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
 "change the number of element slots of the collection - to do this,
 we have to rehash (which is done by re-adding all elements to a new
 empty set)."
-|oldArray oldSize elem
+|oldKeyArray elem
-n "{ Class:SmallInteger }" |
+oldSize "{ Class:SmallInteger }" |
-oldArray := contentsArray.
+oldKeyArray := keyArray.
-oldSize := tally.
+keyArray := Array new:(self goodSizeFor:newSize).
-contentsArray := Array new:(self goodSizeFor:newSize).
+oldSize := oldKeyArray size.
-n := oldArray size.
+1 to:oldSize do:[:srcIndex |
-1 to:n do:[:srcIndex |
+elem := oldKeyArray basicAt:srcIndex.
-elem := oldArray 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
 "rehash is done by re-adding all elements to a new empty set."
 | 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
 ].
 ]
 !
 rehashFrom:startIndex
 |element i "{ Class:SmallInteger }"
 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.
+keyArray basicAt:i put:element.
-contentsArray basicAt:index put:nil.
+keyArray basicAt:index put:nil.
 index == length ifTrue:[
 index := 1
 ] ifFalse:[
 index := index + 1.
 ].
-element := contentsArray basicAt:index.
+element := keyArray basicAt:index.
 ]
 ! !
 !Set methodsFor:'accessing'!
 "add the argument, anObject to the receiver"
 |index|
 anObject notNil ifTrue:[
-index := self findElementOrNil:anObject.
+index := self findKeyOrNil:anObject.
-(contentsArray basicAt:index) isNil ifTrue:[
+(keyArray basicAt:index) isNil ifTrue:[
-contentsArray basicAt:index put:anObject.
+keyArray basicAt:index put:anObject.
 tally := tally + 1.
 self fullCheck.
 ]
 ].
 If it was not in the collection return the value of exceptionBlock."
 |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.
 ].
 "this check is redundant - is also done in rehashFrom:,
 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.
 ]
 ].
 ^ oldObject
 ! !
 !Set methodsFor:'enumerating'!
 do:aBlock
 "perform the block for all members in the collection."
-contentsArray do:[:each |
+keyArray do:[:each |
 each notNil ifTrue:[
 aBlock value:each
 ]
 ]
 ! !

changeset 13	62303f84ff5f
parent 5	67342904af11
child 41	a14247b04d03