"======================================================================
|
|   Set Method Definitions
|
|   $Revision: 1.7.5$
|   $Date: 2000/05/28 16:56:52$
|   $Author: pb$
|
 ======================================================================"


"======================================================================
|
| Copyright 1988-92, 1994-95, 1999, 2000 Free Software Foundation, Inc.
| Written by Steve Byrne and Paolo Bonzini.
|
| This file is part of the GNU Smalltalk class library.
|
| The GNU Smalltalk class library is free software; you can redistribute it
| and/or modify it under the terms of the GNU Lesser General Public License
| as published by the Free Software Foundation; either version 2.1, or (at
| your option) any later version.
| 
| The GNU Smalltalk class library is distributed in the hope that it will be
| useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser
| General Public License for more details.
| 
| You should have received a copy of the GNU Lesser General Public License
| along with the GNU Smalltalk class library; see the file COPYING.LESSER.
| If not, write to the Free Software Foundation, 59 Temple Place - Suite
| 330, Boston, MA 02111-1307, USA.  
|
 ======================================================================"


Collection variableSubclass: #Set
	   instanceVariableNames: 'tally'
	   classVariableNames: ''
	   poolDictionaries: ''
	   category: 'Collections-Unordered'
!

Set comment:
'I am the typical set object; I can store any objects uniquely.  I
use the = operator to determine duplication of objects.' !


!Set class methodsFor: 'instance creation'!

new
    "Answer a new instance of the receiver with a default size"
    ^self new: 5
!

new: anInteger
    "Answer a new instance of the receiver with the given size"
    | realSize |
    realSize := 5 max: anInteger.
    ^(self basicNew: realSize) initialize: realSize
! !


!Set methodsFor: 'accessing'!

at: index
    self shouldNotImplement
!

at: index put: value
    self shouldNotImplement
!

add: newObject
    "Add newObject to the set, if and only if the set doesn't already contain
     an occurrence of it. Don't fail if a duplicate is found. Answer anObject"
    | index absent |
    newObject isNil ifTrue: [ ^newObject ].
    absent := false.
    index := self findIndex: newObject ifAbsent: [ absent := true ].
    self primAt: index put: newObject.
    absent ifTrue: [ self incrementTally ].
    ^newObject
! !



!Set methodsFor: 'Removing from a collection'!

remove: oldObject ifAbsent: anExceptionBlock
    "Remove oldObject to the set. If it is found, answer oldObject.
     Otherwise, evaluate anExceptionBlock and return its value."
    | index |
    index := self findIndex: oldObject ifAbsent: [ ^anExceptionBlock value ].
    self primAt: index put: nil.
    self decrementTally.
    self rehashObjectsAfter: index.
    ^oldObject
! !



!Set methodsFor: 'copying'!

shallowCopy
    "Returns a shallow copy of the receiver (the instance variables are
     not copied)"
    ^(self copyEmpty: self primSize)
        copyAllFrom: self;
        yourself
!

deepCopy
    "Returns a deep copy of the receiver (the instance variables are
     copies of the receiver's instance variables)"
    | newSet |
    newSet := self copyEmpty: self primSize.
    self do: [ :each | newSet addWhileGrowing: each copy ].
    ^newSet
! !


!Set methodsFor: 'testing collections'!

includes: anObject
    "Answer whether the receiver contains an instance of anObject."
    ^(self findIndexOrAnswerNil: anObject) notNil
!

isEmpty
    "Answer whether the receiver is empty."
    ^tally == 0
!

occurrencesOf: anObject
    "Return the number of occurrences of anObject.  Since we're a set, this
    is either 0 or 1.  Nil is never directly in the set, so we special case
    it (the result is always 1)."
    anObject isNil ifTrue: [ ^1 ].
    ^(self includes: anObject)
    	ifTrue: [ 1 ]
	ifFalse: [ 0 ]
!

capacity
    "Answer how many elements the receiver can hold before having to grow."
    ^self primSize * 3 // 4
!

size
    "Answer the receiver's size"
    ^tally
!

hash
    "Return the hash code for the members of the set.  Since order is
    unimportant, we use a commutative operator to compute the hash value."
    | hashValue |
    hashValue := tally.
    self do: [ :member |
	hashValue := hashValue bitXor: (self hashFor: member)
    ].
    ^hashValue
!

= aSet
    "Returns true if the two sets have the same membership, false if not"
    self class == aSet class ifFalse: [ ^false ].
    self == aSet ifTrue: [ ^true ].
    tally = aSet size  ifFalse: [ ^false ].
    self do: [ :element | (aSet includes: element)
    	    	    	    ifFalse: [ ^false ] ].
    ^true
! !



!Set methodsFor: 'enumerating the elements of a collection'!

do: aBlock
    "Enumerate all the non-nil members of the set"
    1 to: self primSize do:
    	[ :i | (self primAt: i) notNil
	    	  ifTrue: [ aBlock value: (self primAt: i) ] ]
! !



!Set methodsFor: 'storing'!

storeOn: aStream
    "Store on aStream some Smalltalk code which compiles to the receiver"
    | hasElements |
    aStream nextPut: $(;
	    nextPutAll: self classNameString;
	    nextPutAll: ' new'.

    hasElements := false.
    self do:
    	[ :element | aStream nextPutAll: ' add: '.
		     element storeOn: aStream.
		     aStream nextPut: $;.
		     hasElements := true ].
    hasElements ifTrue: [ aStream nextPutAll: ' yourself' ].
    aStream nextPut: $).
! !


!Set methodsFor: 'rehashing'!

rehash
    "Rehash the receiver"
    | copy |
    copy := self copy.
    self resetTally.

    1 to: self primSize do: [:i |
	self primAt: i put: nil
    ].

    copy do: [:each | self whileGrowingAdd: each ]
! !


!Set methodsFor: 'private methods'!

initialize: anInteger
    "Private - Instance variable initialization."
    self resetTally.
!

resetTally
    "Private - Reset the tally of elements in the receiver."
    tally := 0
!

incrementTally
    tally := tally + 1.
    tally >= (self primSize * 3 // 4) ifTrue: [ self growBy: self growSize ].
!

decrementTally
    tally := tally - 1.
!

addWhileGrowing: value
    "Private - Add the newObject association to the receiver. Don't check for
     the set to be full - we want SPEED!."
    self
	primAt: (self findIndex: value)
	put: value.
    tally := tally + 1.
    ^value
!

copyAllFrom: aSet
    | value |
    1 to: aSet primSize do: [ :index |
	value := aSet primAt: index.
	value isNil ifFalse: [ self addWhileGrowing: value ]
    ].
    ^self
!

rehashObjectsAfter: index
    "Private - Rehashes all the objects in the collection after index to
     see if any of them hash to index.  If so, that object is copied to
     index, and the process repeats with that object's index, until a nil
     is encountered."
    | i j size element |
    i := index.
    size := self primSize.
    [   i = size ifTrue: [ i := 1 ] ifFalse: [ i := i + 1 ].
	element := self primAt: i.
	element notNil
    ]   whileTrue: [
	j := self findIndex: element.
	(self primAt: j) isNil ifTrue: [
	    self primAt: j put: element.
	    self primAt: i put: nil
	]
    ]
!

hashFor: anElement

    "Answer the hash value for anElement"

    ^anElement hash
!

is: anElement sameAs: searchedObject

    "Answer whether findIndex: should stop scanning the receiver: anElement has
     been found and findIndex:'s parameter was searchedObject"

    ^anElement = searchedObject
!

findIndex: anObject
    "Tries to see if anObject exists as an indexed variable. As soon as nil
    or anObject is found, the index of that slot is answered"

    | index size element |
    size := self primSize.
    index := (self hashFor: anObject) \\ size + 1.
    index to: size do: [ :i |
	element := self primAt: i.
	(element isNil or: [ self is: element sameAs: anObject ])
	    ifTrue: [ ^i ]
    ].
    1 to: index - 1 do: [ :i |
	element := self primAt: i.
	(element isNil or: [ self is: element sameAs: anObject ])
	    ifTrue: [ ^i ]
    ].
    ^index
!
	    
findIndex: anObject ifAbsent: aBlock
    "Finds the given object in the set and returns its index.  If the set
    doesn't contain the object, aBlock is evaluated; the index is always
    answered, even if the set doesn't contain anObject"

    | index |
    index := self findIndex: anObject.
    (self primAt: index) isNil ifTrue: [ aBlock value ].
    ^index
!

findIndexOrAnswerNil: anObject
    "Finds the given object in the set and returns its index.  If the set
    doesn't contain the object, answer nil."

    | index |
    index := self findIndex: anObject.
    (self primAt: index) isNil ifTrue: [ ^nil ].
    ^index
!

grow
    ^self growBy: self growSize
!

growBy: delta
    "Private - Grow by the receiver by delta places"

    | newSet |
    newSet := self class new: self primSize + delta.
    newSet copyAllFrom: self.
    ^self become: newSet
!

growSize
    "this will almost double the size, keeping it an odd number; if size < 7,
     it will make size = 7"
    | size |
    size := self primSize.
    ^(size - 1) max: (7 - size)
! !


!Set methodsFor: 'awful ST-80 compatibility hacks'!

findObjectIndex: object
    "Tries to see if anObject exists as an indexed variable. As soon as nil
    or anObject is found, the index of that slot is answered"
    ^self findIndex: object
! !
