"====================================================================== | | Set Method Definitions | ======================================================================" "====================================================================== | | Copyright (C) 1988, 1989, 1990 Free Software Foundation, Inc. | Written by Steve Byrne. | | This file is part of GNU Smalltalk. | | GNU Smalltalk is free software; you can redistribute it and/or modify it | under the terms of the GNU General Public License as published by the Free | Software Foundation; either version 1, or (at your option) any later version. | | GNU Smalltalk 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 General Public License for more | details. | | You should have received a copy of the GNU General Public License along with | GNU Smalltalk; see the file COPYING. If not, write to the Free Software | Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. | ======================================================================" " | Change Log | ============================================================================ | Author Date Change | sbyrne 19 Sep 89 Converted to use real method categories. | | sbyrne 25 Apr 89 created. | " Collection variableSubclass: #Set instanceVariableNames: 'tally' classVariableNames: '' poolDictionaries: '' category: nil. 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 ^self new: 4 ! new: anInteger ^(super new: anInteger) setTally !! !Set methodsFor: 'accessing'! at: index self error: 'at: not allowed for Set' ! at: index put: value self error: 'at:put: not allowed for Set' ! add: newObject | index | newObject isNil ifTrue: [ ^newObject ]. index _ self findObjectIndex: newObject. (self basicAt: index) isNil ifTrue: [ self basicAt: index put: newObject. tally _ tally + 1 ]. ^newObject !! !Set methodsFor: 'Removing from a collection'! remove: oldObject ifAbsent: anExceptionBlock | index | index _ self findObjectIndexNoGrow: oldObject ifAbsent: [ ^anExceptionBlock value ]. tally _ tally - 1. self rehashObjectsAfter: index. ^oldObject !! !Set methodsFor: 'testing collections'! includes: anObject ^(self basicAt: (self findObjectIndex: anObject)) ~~ nil ! isEmpty ^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 here." anObject isNil ifTrue: [ ^1 ]. (self includes: anObject) ifTrue: [ ^1 ] ifFalse: [ ^0 ] ! 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." ^self inject: tally into: [ :hashValue :member | hashValue + member hash ] ! = aSet "Returns true if the two sets have the same membership, false if not" 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 basicSize do: [ :i | (self basicAt: i) notNil ifTrue: [ aBlock value: (self basicAt: i) ] ] !! !Set methodsFor: 'printing'! printOn: aStream | firstTime | aStream nextPutAll: self class name , ' ('. firstTime _ true. self do: [ :element | firstTime ifTrue: [ firstTime _ false ] ifFalse: [ aStream nextPutAll: ' ' ]. element storeOn: aStream ]. aStream nextPut: $). !! !Set methodsFor: 'storing'! storeOn: aStream | hasElements | aStream nextPutAll: '(Set 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: 'private methods'! setTally "Instance variable initialization." tally _ 0 ! rehashObjectsAfter: index "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 size count element | i _ index. size _ self basicSize. count _ size. self basicAt: index put: nil. [ count _ count - 1. i _ i \\ size + 1. element _ self basicAt: i. count > 0 and: [ element notNil ] ] whileTrue: [ self basicAt: i put: nil. self basicAt: (self findObjectIndex: element) put: element ]. ^self ! findObjectIndex: anObject ifFull: aBlock "Tries to see if anObject exists as an indexed variable. If it's searched the entire set and the object is not to be found, aBlock is evaluated and it's value is returned." | index count size newSet element | size _ self basicSize. index _ anObject hash \\ size + 1. count _ size. [ count > 0 ] whileTrue: [ element _ self basicAt: index. (element isNil or: [ element = anObject ]) ifTrue: [ ^index ]. index _ index \\ size + 1. count _ count - 1 ]. ^aBlock value ! findObjectIndex: anObject "Finds the given object in the set and returns its index. If the set doesn't contain the object and there is no nil element, the set is grown and then the index of where the object would go is returned." ^self findObjectIndex: anObject ifFull: [ self grow. self findObjectIndexNoGrow: anObject ifAbsent: [ self error: 'failed to grow a new empty element!!!' ] ] ! findObjectIndexNoGrow: anObject ifAbsent: aBlock | index | index _ self findObjectIndex: anObject ifFull: [ 0 ]. index = 0 ifTrue: [ ^aBlock value ] ifFalse: [ ^index ] ! grow | newSet | newSet _ self species new: self basicSize + self growSize. self do: [ :element | newSet add: element ]. ^self become: newSet ! growSize ^self basicSize "this will double the size" !!