"

 COPYRIGHT (c) 1991 by Claus Gittinger

	      All Rights Reserved

 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.

"

"{ Package: 'stx:libbasic' }"

"{ NameSpace: Smalltalk }"

Collection subclass:#Set

	instanceVariableNames:'tally keyArray'

	classVariableNames:'DeletedEntry NilEntry'

	poolDictionaries:''

	category:'Collections-Unordered'

!

Object subclass:#EmptySlot

	instanceVariableNames:''

	classVariableNames:'TheOneAndOnlyInstance'

	poolDictionaries:''

	privateIn:Set

!

Object subclass:#NilKey

	instanceVariableNames:''

	classVariableNames:'TheOneAndOnlyInstance'

	poolDictionaries:''

	privateIn:Set

!

!Set class methodsFor:'documentation'!

copyright

"

 COPYRIGHT (c) 1991 by Claus Gittinger

	      All Rights Reserved

 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.

"

!

documentation

"

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

    The inclusion test is done using equality (=) for comparison; 

    see IdentitySet for sets using identity compare.

    Keep in mind, that a regular Set therefore treats 3.0 and 3 as equal

    and therefore:

        (Set with:3.0) includes:3

    will return true (since 3.0 and 3 are equal).

    In contrast, an IdentitySet will return false, because 3.0 and 3 are not

    identical.

    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, increased hash collisions

    are to be expected for large sets (say: > 20000 element). 

    If your objects are heavyly used in sets or dictionaries, and you need

    big collections, your instances may provide a better hash values.

    Performance hints: 

      If only symbols or smallIntegers are used as keys, 

      use an instance of IdentitySet for slightly better performance, 

      since both hashing and comparison is faster.

      If you have a rough idea how big the set is going to grow,

      create it using #new: instead of #new. Even if the size given is a

      poor guess (say half of the real size), there is some 20-30% performance

      win to expect, since many resizing operations of the set are avoided

      (resizing is expensive, as the set does a rehash).

    Examples:

        |s|

        s := Set new.

        s add:'hello'.

        s add:'world'.

        s add:#foo.

        s add:1.2345678.

        s add:'hello'.

        s printCR.

        's size -> ' print. s size printCR.

        '(s includes:''hello'') -> ' print. (s includes:'hello') printCR.

        '(s includes:#foo)    -> ' print. (s includes:#foo) printCR.

        '(s includes:''foo'')   -> ' print. (s includes:'foo') printCR.

        '(s includes:#bar)    -> ' print. (s includes:#bar) printCR.

    [author:]

        Claus Gittinger

"

! !

!Set class methodsFor:'initialization'!

initialize

    "initialize the Set class"

    DeletedEntry isNil ifTrue:[

        DeletedEntry := EmptySlot new.

        NilEntry := NilKey new.

    ].

    "

        Set initialize

    "

    "Modified: 24.1.1997 / 21:09:00 / cg"

! !

!Set class methodsFor:'instance creation'!

decodeFromLiteralArray:anArray

    "create & return a new instance from information encoded in anArray."

    |set 

     sz "{ Class: SmallInteger }"|

    sz := anArray size.

    set := self new:sz-1.

    2 to:sz do:[:idx| set add:(anArray at:idx) decodeAsLiteralArray].

    ^ set

    "

     (Set with:1234

          with:(1 @ 2)

          with:'hello'

     ) literalArrayEncoding decodeAsLiteralArray    

    "

!

new

    "return a new empty Set"

    ^ self new:7

!

new:anInteger

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

    "

     make it somewhat bigger; hashing works better if fill grade is

     below 10% (make it 75% here ..)

    "

    ^ self basicNew initializeForCapacity:(anInteger * 4 // 3)

! !

!Set class methodsFor:'queries'!

goodSizeFrom:arg 

    "return a good array size for the given argument.

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

    |n|

    "/ arg <= 11 ifTrue:[^ 11].

    "/ n := arg * 3 // 2.

    arg <= 7 ifTrue:[^ 7].

    n := arg.

    "

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

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

    "

    n <= 524288 ifTrue:[

           "2  4  8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288"

        ^ #(7  7 11 17 37 67 131 257 521 1031 2053 4099 8209 16411 32771 65537 131101 262147 524309) at:(n highBit)

    ].

    ^ n nextPrime

! !

!Set class methodsFor:'utilities'!

rehashAllSubInstances

    "rehash all sets & dictionaries.

     Useful utility if hash/identityHash method was changed

     of some object which is known to be kept in a set"

     self allSubInstances do:[:s | s rehash]

    "

     Set rehashAllSubInstances

    "

    "Created: / 24.10.1997 / 23:13:44 / cg"

! !

!Set methodsFor:'Compatibility-ST80'!

initialIndexFor:hashKey boundedBy:length

    "for ST-80 compatibility only; it is (currently) not used in this

     implementation of sets. Therefore, in ST/X it does not make sense

     to redefine it. (which may be a bad design decision, but slightly

     improves performance, by avoiding an extra message send ...)"

    |index "{ Class:SmallInteger }"|

    index := hashKey bitAnd:16r3FFFFFFF.

    index < 16r1FFFFFFF ifTrue:[

	index := index * 2

    ].

    index := index \\ length + 1.

    ^ index.

    "Modified: 1.3.1997 / 01:01:13 / cg"

! !

!Set methodsFor:'Compatibility-Squeak'!

copyWithout:elementToSkip

    "return a new collection consisting of a copy of the receiver, with

     ALL elements equal to elementToSkip are left out.

     No error is reported, if elementToSkip is not in the collection."

    ^ self select:[:each | each ~= elementToSkip]

    "

     #(1 2 3 4 5 6 7) asSet copyWithout:5

    "

!

copyWithoutAll:elementsToSkip

    "return a new collection consisting of a copy of the receiver, with

     ALL elements equal to elementToSkip are left out.

     No error is reported, if elementsToSkip is not in the collection."

    elementsToSkip size * self size > 10000 ifTrue:[

        "speed up everything"

        ^ self \ (elementsToSkip asSet).

    ].

    ^ self \ elementsToSkip

    "

     #(1 2 3 4 5 6 7) asSet copyWithoutAll:#(3 5 7 9)

     #(a b c d e f) asIdentitySet copyWithoutAll:#(d e f)

     #('a' 'b' 'c' 'd' 'e' 'f') asIdentitySet copyWithoutAll:#('d' 'e' 'f')

     #('a' 'b' 'c' 'd' 'e' 'f') asSet copyWithoutAll:#('d' 'e' 'f')

    "

!

like:anObject

    "Answer an object in the receiver that is equal to anObject,

     nil if no such object is found. 

     Relies heavily on hash properties (i.e. that two object's hashes are equal

     if the two object compare equal)"

    ^ self elementAt:anObject ifAbsent:[ nil ]

    "

     (Set withAll:#(10.0 20.0 30.0 40.0)) like:20

    "

! !

!Set methodsFor:'accessing'!

addFirst:anObject

    "add the argument, anObject to the receiver.

     If the receiver is ordered, the new element will be added at the beginning.

     An error is raised here - it does not make sense for unordered collections"

    ^ self shouldNotImplement

!

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

!

elementAt:anObject

    "return the element, if contained in the set.

     If there is none, report an error.

     This may seem confusing at first - however, it is useful with

     non-identitysets, to find an existing element, for a 

     given equal (but not identical) object.

     This is the same functionality as provided by the goodies/KeyedSet goody."

    ^ self elementAt:anObject ifAbsent:[^ self errorNotFound].

    "Modified: 20.3.1997 / 20:35:24 / cg"

!

elementAt:anObject ifAbsent:exceptionBlock

    "return the element, if contained in the set.

     If there is none, return the result from evaluating exceptionBlock.

     This may seem confusing at first - however, it is useful with

     non-identitysets, to find an existing element, for a 

     given equal (but not identical) object.

     This is the same functionality as provided by the goodies/KeyedSet

     goody."

    |index "{ Class: SmallInteger }"  ret|

    index := self find:(anObject ? NilEntry)ifAbsent:0.

    index == 0 ifTrue:[

        ^ exceptionBlock value

    ].

    ret := keyArray basicAt:index.

    ret == NilEntry ifTrue:[

        ret := nil.

    ].

    ^ ret.

    "Created: 20.3.1997 / 20:34:07 / cg"

    "Modified: 20.3.1997 / 20:35:49 / cg"

!

removeLast

    "remove the last element from the receiver.

     Return the removed element.

     An error is raised here - it does not make sense for unordered collections"

    ^ self shouldNotImplement

!

reverseDo:aBlock

    "evaluate the argument, aBlock for each element in reverse order.

     An error is raised here - it does not make sense for unordered collections"

    ^ self shouldNotImplement

! !

!Set methodsFor:'adding & removing'!

add:keyArg

    "add the argument, anObject to the receiver.

     Return the added element.

     WARNING: do not add elements while iterating over the receiver.

              Iterate over a copy to do this."

    |key index "{ Class: SmallInteger }"|

    keyArg isNil ifTrue:[

        key := NilEntry.

    ] ifFalse:[

        key := keyArg.

    ].

    index := self findKeyOrNil:key.

    (keyArray basicAt:index) isNil ifTrue:[

        "/ not already there

        keyArray basicAt:index put:key.

        tally := tally + 1.

        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 the first occurrence of oldObject from the collection and return it.

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

     Notice, that the returned object could be non-identical to the argument

     (although it will always be equal).

     WARNING: do not remove elements while iterating over the receiver.

              See #saveRemove: to do this."

    |oldObject index next removedObject|

    oldObjectArg isNil ifTrue:[

        oldObject := NilEntry.

    ] ifFalse:[

        oldObject := oldObjectArg.

    ].

    index := self find:oldObject ifAbsent:0.

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

    removedObject := keyArray basicAt:index.

    keyArray basicAt:index put:nil.

    tally := tally - 1.

    tally == 0 ifTrue:[

        keyArray := self keyContainerOfSize:(self class goodSizeFrom:0). 

    ] ifFalse:[

        index == keyArray basicSize ifTrue:[

            next := 1

        ] ifFalse:[

            next := index + 1.

        ].

        (keyArray basicAt:next) notNil ifTrue:[

            keyArray basicAt:index put:DeletedEntry.

        ].

        self possiblyShrink

    ].

    removedObject == NilEntry ifTrue:[

        removedObject := nil.

    ].

    ^ removedObject

    "Modified: / 16.11.2001 / 10:14:24 / cg"

!

removeAll

    "remove all elements from the receiver. Returns the receiver."

    self initializeForCapacity:7.

    "Modified: 12.4.1996 / 13:35:06 / cg"

!

removeIdentical:oldObjectArg ifAbsent:exceptionBlock

    "remove oldObject from the collection and return it.

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

     Uses identity compare (==) to search for an occurrence.

     WARNING: do not remove elements while iterating over the receiver.

              See #saveRemove: to do this."

    |oldObject index next|

    oldObjectArg isNil ifTrue:[

        oldObject := NilEntry.

    ] ifFalse:[

        oldObject := oldObjectArg.

    ].

    "first a quick check. 

     There is a high possibility that objects, which are

     equal are also identical"

    index := self find:oldObject ifAbsent:0.

    index ~~ 0 ifTrue:[

        oldObject ~~ (keyArray basicAt:index) ifTrue:[

            index := 0.

        ]

    ].

    index == 0 ifTrue:[

        "have to go the long and hard path..."

        index := self findIdentical:oldObject ifAbsent:0.

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

    ].

    keyArray basicAt:index put:nil.

    tally := tally - 1.

    tally == 0 ifTrue:[

        keyArray := self keyContainerOfSize:(self class goodSizeFrom:0). 

    ] ifFalse:[

        index == keyArray basicSize ifTrue:[

            next := 1

        ] ifFalse:[

            next := index + 1.

        ].

        (keyArray basicAt:next) notNil ifTrue:[

            keyArray basicAt:index put:DeletedEntry.

        ].

        self possiblyShrink

    ].

    ^ oldObjectArg

!

safeRemove:oldObject 

    "remove the element, oldObject from the collection.

     Return the element