"

 COPYRIGHT (c) 1991 by Claus Gittinger

 This software is furnished under a license and may be used

 only in accordance with the terms of that license and with the

 inclusion of the above copyright notice.   This software may not

 be provided or otherwise made available to, or used by, any

 other person.  No title to or ownership of the software is

 hereby transferred.

"

Collection subclass:#Set

       instanceVariableNames:'tally keyArray'

       classVariableNames:'DeletedEntry'

       poolDictionaries:''

       category:'Collections-Unordered'

!

Set comment:'

COPYRIGHT (c) 1991 by Claus Gittinger

'!

!Set class methodsFor:'documentation'!

copyright

"

 COPYRIGHT (c) 1991 by Claus Gittinger

 This software is furnished under a license and may be used

 only in accordance with the terms of that license and with the

 inclusion of the above copyright notice.   This software may not

 be provided or otherwise made available to, or used by, any

 other person.  No title to or ownership of the software is

 hereby transferred.

"

!

version

"

"

!

documentation

"

    a Set is a collection where each element occurs at most once.

    The inclusion test is done using = for comparison; 

    see IdentitySet for sets using identity compare.

    Sets use hashing for fast access, this access is considerably faster,

    if a good hash-number is returned by the elements.

    Notice that the default hash (Object>>hash) is not perfect, due to

    the implementation of hash-keys in ST/X. If your objects heavyly

    used in sets or dictionaries, you should provide some better hash

    values.

    Examples:

"

! !

!Set class methodsFor:'initialization'!

initialize

    "initialize the Set class"

    DeletedEntry isNil ifTrue:[

    ].

    "Set initialize"

! !

!Set class methodsFor:'instance creation'!

new

    "return a new empty Set"

    ^ self new:7

!

new:anInteger

    "return a new empty Set with space for anInteger elements"

! !

!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 collection is full (after an add); grow if so.

     Definition of full is currently:'filled more than 75%'"

    |sz "{Class: SmallInteger}" |

    "grow if filled more than 75% "

    sz := keyArray basicSize.

    tally > (sz * 3 // 4) ifTrue:[

       self grow

    ]

!

emptyCheck

    "check if set has become too empty (after a remove)

     - shrink if filled less than 12.5%"

    |sz      "{Class: SmallInteger}"

     newSize "{Class: SmallInteger}" |

    sz := keyArray basicSize.

    sz > 30 ifTrue:[

    ]

!

goodSizeFor:arg

    "return a good array size for the given argument.

     Returns the next prime after arg, since prime sizes are good for hashing."

    arg <= 11 ifTrue:[^ 11].

    "

     mhmh - this returns good numbers for collections with up-to about

     500k elements; if you have bigger ones, add some more primes here ...

    "

    arg <= 524288 ifTrue:[

    ].

    "

     make it odd - at least

    "

    ^ arg bitOr:1

!

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."

    keyArray := self keyContainerOfSize:(self goodSizeFor:count). 

    tally := 0

!

find:key ifAbsent:aBlock

    "Look for the key in the receiver.  If it is found, return

     the index of the slot containing the key, otherwise

     return the value of evaluating aBlock."

    |index  "{ Class:SmallInteger }"

     length "{ Class:SmallInteger }"

     startIndex probe|

    length := keyArray basicSize.

    length < 10 ifTrue:[

    ].

    startIndex := key hash \\ length + 1.

    index := startIndex.

    [true] whileTrue:[

    ]

!

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 "{ Class:SmallInteger }"

     startIndex probe|

    length := keyArray basicSize.

    startIndex := key hash \\ length + 1.

    index := startIndex.

    [true] whileTrue:[

    ]

!

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 "{ Class:SmallInteger }"|

    length := keyArray basicSize.

    index := key hash \\ length + 1.

    [(keyArray basicAt:index) notNil] whileTrue:[

    ].

    ^ index

!

grow

    "change the number of element slots of the collection to a useful

     new size"

    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)."

    |elem oldKeyArray newKeyArray deletedEntry

     oldSize "{ Class:SmallInteger }"|

    oldKeyArray := keyArray.

    keyArray := newKeyArray := self keyContainerOfSize:(self goodSizeFor:newSize). 

    oldSize := oldKeyArray size.

    deletedEntry := DeletedEntry.

    1 to:oldSize do:[:srcIndex |

    ].

!

rehash

    "rehash is done by re-adding all elements to a new empty set.

     Rehash is needed after a binaryRead, for example."

    |element oldKeyArray newKeyArray

     n "{ Class:SmallInteger }"|

    oldKeyArray := keyArray.

    n := oldKeyArray size.

    keyArray := newKeyArray := self keyContainerOfSize:n.

    1 to:n do:[:index |

    ]

!

rehashFrom:startIndex

    "rehash elements starting at index - after a remove.

     Notice: due to the new implementation of remove, 

    |element i "{ Class:SmallInteger }"

     length

     index "{ Class:SmallInteger }" |

    length := keyArray basicSize.

    index := startIndex.

    element := keyArray basicAt:index.

    [element notNil] whileTrue:[

    ]

! !

!Set methodsFor:'accessing'!

at:index

    "report an error: at: is not allowed for Sets"

    ^ self errorNotKeyed

!

at:index put:anObject

    "report an error: at:put: is not allowed for Sets"

    ^ self errorNotKeyed

! !

!Set methodsFor:'testing'!

size

    "return the number of set elements"

    ^ tally

!

includes:anObject

    "return true if the argument anObject is in the receiver"

    ^ (self find:anObject ifAbsent:[0]) ~~ 0

!

isEmpty

    "return true if the receiver is empty"

    ^ tally == 0

!

occurrencesOf:anObject

    "return the number of occurrences of anObject in the receiver"

    (self find:anObject ifAbsent:[0]) == 0 ifTrue:[^ 0].

    ^ 1

!

isFixedSize

    "return true if the receiver cannot grow - this will vanish once

     Arrays and Strings learn how to grow ..."

    ^ false

! !

!Set methodsFor:'adding & removing'!

add:anObject

    "add the argument, anObject to the receiver"

    |index "{ Class: SmallInteger }"|

    anObject notNil ifTrue:[

    ].

    ^ anObject

!

remove:oldObject ifAbsent:exceptionBlock

    "remove oldObject from the collection and return it.

     If it was not in the collection return the value of exceptionBlock."

    |index next|

"this is actually the same as:

    index := self find:oldObject ifAbsent:[^ exceptionBlock value].

 but cheaper, since there will be no new block to create

 (remember: [0] blocks are super-cheap)

"

    index := self find:oldObject ifAbsent:[0].

    index == 0 ifTrue:[^ exceptionBlock value].

    keyArray basicAt:index put:nil.

    tally := tally - 1.

    tally == 0 ifTrue:[

    ] ifFalse:[

    ].

    ^ oldObject

!

removeAll

    "remove all elements from the receiver."

    self setTally:7.

! !

!Set methodsFor:'enumerating'!

do:aBlock

    "perform the block for all members in the collection."

    |sz "{ Class: SmallInteger }"

     element|

    sz := keyArray size.

    1 to:sz do:[:index |

    ]

! !

!Set methodsFor: 'binary storage'!

readBinaryContentsFrom: stream manager: manager

    "must rehash after reload"

    super readBinaryContentsFrom: stream manager: manager.

    self rehash

! !