hg/stx-libbasic: comparison Set.st

equal deleted inserted replaced

-:4e8f3d37bdbf
+:deb0c3355881
 "
 "{ Package: 'stx:libbasic' }"
 Collection subclass:#Set
 	instanceVariableNames:'tally keyArray'
-	classVariableNames:'DeletedEntry'
+	classVariableNames:'DeletedEntry NilEntry'
 	poolDictionaries:''
 	category:'Collections-Unordered'
 !
 Object subclass:#EmptySlot
 ^ true.
 "Modified: 30.1.1997 / 14:58:08 / cg"
 ! !
-!Set methodsFor:'binary storage'!
-readBinaryContentsFrom: stream manager: manager
-"must rehash after reload"
-super readBinaryContentsFrom: stream manager: manager.
-self rehash
-! !
 !Set methodsFor:'comparing'!
 = aCollection
 "return true, if the argument is a Set containing the same elements
 as I do"
-aCollection species == self species ifFalse:[^ false].
+aCollection species ~~ self species ifTrue:[^ false].
-aCollection size == self size ifFalse:[^ false].
+aCollection size ~~ self size ifTrue:[^ false].
 "/ same number of elements; since I am a Set, all of
 "/ of my elements must be in the other collection ...
-^ self conform:[:element | (aCollection includes:element)]
+self do:[:eachElement | (aCollection includes:eachElement) ifFalse:[^ false]].
+^ true.
 "
 #(1 2 3 4 5) asSet = #(2 3 4 5 1) asSet
 #(nil 1 2 3 4 5) asSet = #(2 3 4 5 1) asSet�
 #(1 2 3 4 5) asSet = #(2 3 4 5 1.0) asSet
 "this hash is stupid - but for larger collections, the hashing
 time can become much bigger than the time lost in added probing.
 Time will show ...
 Notice & warning:
-	if the #= method is ever changed to compare non-dictionaries equal,
+if the #= method is ever changed to compare non-dictionaries equal,
-	the code below must be changed to assert that the same hash-value is
+the code below must be changed to assert that the same hash-value is
-	still returned.
+still returned.
-	(which may be hard to acomplish)
+(which may be hard to acomplish)
 "
 |mySize|
 mySize := self size.
 mySize == 0 ifTrue:[^ 0].
-^ ((self first) hash times:mySize) bitAnd:16r3FFFFFFF
+^ (self anElement hash times:mySize) bitAnd:16r3FFFFFFF
 "
 |d|
 d := Dictionary new.
 d at:'one' put:1.
 d at:2 put:#two.
 d at:'two' put:2.
 d hash
 "
 ! !
 !Set methodsFor:'copying'!
 postCopy
 ]
 "Modified: 1.3.1996 / 21:41:13 / cg"
 ! !
-!Set methodsFor:'inspecting'!
-inspectorClass
-"redefined to use SetInspector
-(instead of the default Inspector)."
-^ SetInspectorView
-! !
 !Set methodsFor:'obsolete set operations'!
 + aCollection
 "Kept for backward compatibility.
 !
 findNil:key
 "Look for the next slot usable for key.
 WARNING:
-	This method assumes that key is not already in the receiver
+This method assumes that key is not already in the receiver
-	AND that keyArray does not have previously removed entries
+AND that keyArray does not have previously removed entries
-	AND that there is an empty slot.
+AND that there is an empty slot.
 To be used ONLY while growing/rehashing to enter elements into a fresh
 collection - if any of the above conditions is not met, the method
 loops forever."
 |index  "{ Class:SmallInteger }"
 "/    index == 0 ifTrue:[
 "/        index := keyArray identityIndexOf:nil startingAt:1 endingAt:index.
 "/    ].
 "/ that code is completely inlined by stc ...
 [(keyArray basicAt:index) notNil] whileTrue:[
-	index == length ifTrue:[
+index == length ifTrue:[
-	    index := 1
+index := 1
-	] ifFalse:[
+] ifFalse:[
-	    index := index + 1
+index := index + 1
-	].
+].
-	"notice: no check for no nil found - we must find one since
+"notice: no check for no nil found - we must find one since
-	 this is only called after growing"
+this is only called after growing"
 ].
 ^ index
 "Modified: 21.3.1997 / 10:32:58 / cg"
 !
 |index  "{ Class:SmallInteger }"
 length "{ Class:SmallInteger }"|
 length := keyArray basicSize.
 index := (self hashFor:aKey) bitAnd:16r3FFFFFFF.
-index < 16r1FFFFFFF ifTrue:[
-	index := index * 2
+"multiply by a large prime to spread the keys over the whole range.
-].
+This causes maxChainLength to reduce from about 2000 to 6 for an
+IdentitySet of 9000 Smalltalk classes"
+index := index times:31415821.
 index := index \\ length + 1.
 ^ index.
+"
+Smalltalk allClasses maxChainLength
+"
 "Modified: 1.3.1997 / 01:01:13 / cg"
 "Created: 19.3.1997 / 15:02:41 / cg"
 !
 count := count + (self collisionsFor:eachKey).
 ]
 ].
 ^ count
+"
+self allSubInstances
+collect:[:each| each collisionCount -> each]
+thenSelect:[:each| each key > 0]
+"
 !
 collisionsFor:key
 "Return the number of searches - 1 required for key"
 |index  "{ Class:SmallInteger }"
-length "{ Class:SmallInteger }"
+length "{ Class:SmallInteger }" startIndex probe count|
-hash "{ Class:SmallInteger }"
-step "{ Class:SmallInteger }"
-startIndex probe count|
 length := keyArray basicSize.
-hash := (self hashFor:key) bitAnd:16r3FFFFFFF.
+startIndex := index := self initialIndexForKey:key.
-hash < 16r1FFFFFFF ifTrue:[
-hash := hash * 2
-].
-startIndex := index := hash \\ length + 1.
-step:= hash // length + 1.
 count := 0.
 [true] whileTrue:[
-probe := (keyArray basicAt:index).
+probe := keyArray basicAt:index.
 (probe notNil and:[key = probe]) ifTrue:[^ count].
 (self slotIsEmpty:probe) ifTrue:[self error:'non existing key'].
 index == length ifTrue:[
 index := 1.
 "return the number of set elements"
 ^ tally
 ! !
 !Set methodsFor:'testing'!
 capacity
 "return the number of elements, that the receiver is
 prepared to take.
 ! !
 !Set class methodsFor:'documentation'!
 version
-^ '$Header: /cvs/stx/stx/libbasic/Set.st,v 1.115 2012/08/13 17:11:21 stefan Exp $'
+^ '$Header: /cvs/stx/stx/libbasic/Set.st,v 1.117 2013-01-15 17:25:54 stefan Exp $'
 !
 version_CVS
-^ '�Header: /cvs/stx/stx/libbasic/Set.st,v 1.115 2012/08/13 17:11:21 stefan Exp �'
+^ '$Header: /cvs/stx/stx/libbasic/Set.st,v 1.117 2013-01-15 17:25:54 stefan Exp $'
-!
+! !
-version_SVN
-^ '$Id: Set.st 10844 2012-09-07 16:24:32Z vranyj1 $'
-! !
 Set initialize!

branch	jv
changeset 18011	deb0c3355881
parent 17966	8b5df02e171f
parent 14656	f5cab05e380f
child 18037	4cf874da38c9