diff -r cb7a12afe736 -r e3a375d5f6a8 Set.st --- a/Set.st Tue Feb 04 21:09:59 2014 +0100 +++ b/Set.st Wed Apr 01 10:20:10 2015 +0100 @@ -11,6 +11,8 @@ " "{ Package: 'stx:libbasic' }" +"{ NameSpace: Smalltalk }" + Collection subclass:#Set instanceVariableNames:'tally keyArray' classVariableNames:'DeletedEntry NilEntry' @@ -363,13 +365,21 @@ keyArray basicAt:index put:key. tally := tally + 1. - self fullCheck. + self possiblyGrow. ]. ^ keyArg "Modified: 30.1.1997 / 14:58:08 / cg" ! +clearContents + "remove all elements from the receiver, but do not resize. + Returns the receiver." + + keyArray atAllPut:nil. + tally := 0. +! + remove:oldObjectArg ifAbsent:exceptionBlock "remove oldObject from the collection and return it. If it was not in the collection return the value of exceptionBlock. @@ -404,7 +414,7 @@ (keyArray basicAt:next) notNil ifTrue:[ keyArray basicAt:index put:DeletedEntry. ]. - self emptyCheck + self possiblyShrink ]. removedObject == NilEntry ifTrue:[ removedObject := nil. @@ -466,12 +476,12 @@ (keyArray basicAt:next) notNil ifTrue:[ keyArray basicAt:index put:DeletedEntry. ]. - self emptyCheck + self possiblyShrink ]. ^ oldObjectArg ! -saveRemove:oldObject +safeRemove:oldObject "remove the element, oldObject from the collection. Return the element (could be non-identical to oldObject, since I hash on equality, not on identity). @@ -487,13 +497,13 @@ You may want to manually resize the receiver using #emptyCheck. (after the loop)" - ^ self saveRemove:oldObject ifAbsent:[]. + ^ self safeRemove:oldObject ifAbsent:[]. "Created: / 16.11.2001 / 10:23:48 / cg" "Modified: / 16.11.2001 / 10:24:03 / cg" ! -saveRemove:oldObjectArg ifAbsent:exceptionValueProvider +safeRemove:oldObjectArg ifAbsent:exceptionValueProvider "remove the element, oldObject from the collection. Return the element (could be non-identical to oldObject, since I hash on equality, not on identity). @@ -580,7 +590,7 @@ s add:9. s do:[:v | v odd ifTrue:[ - s saveRemove:v + s safeRemove:v ] ]. s inspect @@ -590,6 +600,20 @@ "Modified: / 16.11.2001 / 10:22:59 / cg" ! +saveRemove:oldObject + + "bad spelling - kept for backward compatibility (2014-06-04)" + + ^ self safeRemove:oldObject. +! + +saveRemove:oldObjectArg ifAbsent:exceptionValueProvider + + "bad spelling - kept for backward compatibility (2014-06-04)" + + ^ self safeRemove:oldObjectArg ifAbsent:exceptionValueProvider. +! + testAndAdd:keyArg "add the argument, anObject to the receiver. Answer true, if the element did already exist in the collection, @@ -612,7 +636,7 @@ keyArray basicAt:index put:key. tally := tally + 1. - self fullCheck. + self possiblyGrow. ^ false. ]. ^ true. @@ -790,7 +814,6 @@ ! ! - !Set methodsFor:'obsolete set operations'! + aCollection @@ -834,7 +857,7 @@ startIndex := index := self initialIndexForKey:key. - [true] whileTrue:[ + [ probe := (keyArray basicAt:index). (probe notNil and:[probe ~~ DeletedEntry and:[key = probe]]) ifTrue:[^ index]. (self slotIsEmpty:probe) ifTrue:[^ aBlock value]. @@ -845,7 +868,7 @@ index := index + 1 ]. index == startIndex ifTrue:[^ aBlock value]. - ] + ] loop. "Modified: / 03-02-2011 / 13:53:18 / sr" ! @@ -871,7 +894,7 @@ length := keyArray basicSize. startIndex := index := self initialIndexForKey:key. - [true] whileTrue:[ + [ probe := keyArray basicAt:index. (probe notNil and:[probe ~~ DeletedEntry and:[key = probe]]) ifTrue:[^ index]. (self slotIsEmpty:probe) ifTrue:[ @@ -898,7 +921,7 @@ ]. ^ self grow findKeyOrNil:key ]. - ] + ] loop. "Modified: / 27-02-2011 / 15:30:42 / cg" ! @@ -1075,43 +1098,6 @@ !Set methodsFor:'private-grow & shrink'! -emptyCheck - "check if the receiver has become too empty (after a remove) - and shrink if it makes sense. - Definition of 'too empty' is 'filled less than 12.5% (i.e. 1/8th)'" - - |sz "{Class: SmallInteger}" - newSize "{Class: SmallInteger}" | - - sz := keyArray basicSize. - sz > 56 ifTrue:[ - " - shrink if too empty - " - tally < (sz // 8) ifTrue:[ - newSize := sz // 4. - self grow:newSize - ] - ] - - "Modified: 19.3.1997 / 16:02:55 / cg" -! - -fullCheck - "check if collection is full (after an add); grow if so. - Definition of 'full' is currently: 'filled more than 75% (i.e. 3/4th)'" - - |sz "{Class: SmallInteger}" | - - " - grow if filled more than 75% - " - sz := keyArray basicSize. - tally > (sz * 3 // 4) ifTrue:[ - self grow - ] -! - grow "change the number of element slots of the collection to a useful new size" @@ -1142,6 +1128,43 @@ newKeyArray basicAt:(self findNil:elem) put:elem ]. ]. +! + +possiblyGrow + "check if collection is full (after an add); grow if so. + Definition of 'full' is currently: 'filled more than 75% (i.e. 3/4th)'" + + |sz "{Class: SmallInteger}" | + + " + grow if filled more than 75% + " + sz := keyArray basicSize. + tally > (sz * 3 // 4) ifTrue:[ + self grow + ] +! + +possiblyShrink + "check if the receiver has become too empty (after a remove) + and shrink if it makes sense. + Definition of 'too empty' is: 'filled less than 12.5% (i.e. 1/8th)'" + + |sz "{Class: SmallInteger}" + newSize "{Class: SmallInteger}" | + + sz := keyArray basicSize. + sz > 56 ifTrue:[ + " + shrink if too empty + " + tally < (sz // 8) ifTrue:[ + newSize := sz // 4. + self grow:newSize + ] + ] + + "Modified: 19.3.1997 / 16:02:55 / cg" ! ! !Set methodsFor:'queries'! @@ -1179,7 +1202,7 @@ startIndex := index := self initialIndexForKey:key. count := 0. - [true] whileTrue:[ + [ probe := keyArray basicAt:index. (probe notNil and:[key = probe]) ifTrue:[^ count]. (self slotIsEmpty:probe) ifTrue:[self error:'non existing key']. @@ -1191,7 +1214,7 @@ ]. count := count + 1. index == startIndex ifTrue:[self error:'non existing key']. - ] + ] loop. ! maxChainLength @@ -1219,6 +1242,19 @@ ! ! +!Set methodsFor:'searching'! + +findFirst:aBlock ifNone:exceptionValue + "find the index of the first element, for which evaluation of the argument, aBlock returns true; + return its index or the value from exceptionValue if none detected. + This is much like #detect:ifNone:, however, here an INDEX is returned, + while #detect:ifNone: returns the element. + + Sets do not have indices." + + ^ self shouldNotImplement +! ! + !Set methodsFor:'testing'! capacity @@ -1269,6 +1305,7 @@ !Set methodsFor:'visiting'! acceptVisitor:aVisitor with:aParameter + "dispatch for visitor pattern; send #visitSet:with: to aVisitor." ^ aVisitor visitSet:self with:aParameter ! ! @@ -1297,11 +1334,11 @@ !Set class methodsFor:'documentation'! version - ^ '$Header: /cvs/stx/stx/libbasic/Set.st,v 1.122 2013-11-14 15:33:50 stefan Exp $' + ^ '$Header: /cvs/stx/stx/libbasic/Set.st,v 1.131 2015-02-04 21:08:10 stefan Exp $' ! version_CVS - ^ '$Header: /cvs/stx/stx/libbasic/Set.st,v 1.122 2013-11-14 15:33:50 stefan Exp $' + ^ '$Header: /cvs/stx/stx/libbasic/Set.st,v 1.131 2015-02-04 21:08:10 stefan Exp $' ! !