requires: {#ExtensibleCollection}. provides: {#NoDuplicatesCollection. #Set. #IdentitySet}. collections addPrototype: #NoDuplicatesCollection derivedFrom: {ExtensibleCollection}. "TODO: find out if some collections need to be non-extensible AND optimized for no-duplicates. (My guess is that the answer is 'no'.)" nd@(NoDuplicatesCollection traits) add: obj withOccurrences: _ [ nd include: obj ]. nd@(NoDuplicatesCollection traits) add: obj [ nd include: obj ]. nd@(NoDuplicatesCollection traits) include: obj "This is the default method for adding objects to NoDuplicatesCollection. It should be overridden in any case, but this implementation allows for any collection type to be treated as a NoDuplicatesCollection by mixing it in." [ nd add: obj ifPresent: [obj] ]. nd@(NoDuplicatesCollection traits) removeEvery: obj "Objects only occur once in these collections." [ nd remove: obj ]. nd@(NoDuplicatesCollection traits) includeAll: c [ c do: [| :each | nd include: each]. c ]. collections addPrototype: #Set derivedFrom: {NoDuplicatesCollection}. "An Unordered, Extensible Collection of elements without duplicates. Being a duplicate is determined by a binary comparison and associated hash function on each object." Set addSlot: #tally valued: 0. "The number of elements in the set." Set addSlot: #contents valued: (Array newSize: 10). "The storage area for the set. The non-Nil elements are the objects in the Set. A heuristic of at most 75% capacity is usually automatically maintained by replacing the array with a larger one as needed." Set addSlot: #hashBlock valued: [| :obj | obj hash]. Set addSlot: #equalsBlock valued: [| :a :b | a = b]. collections addSlot: #IdentitySet valued: Set clone. IdentitySet hashBlock: [| :obj | obj identityHash]. IdentitySet equalsBlock: [| :a :b | a == b]. "IdentitySets specialize their behavior to compare solely by object identity." c@(Set traits) newSize: n [| newC | newC: c clone. newC contents: (c contents newSize: (n max: 1)). newC tally: 0. newC ]. c@(Set traits) = d@(Set traits) "Comparison is by iteration over each element in the Sets. This is avoided when possible by making very cheap comparisons first." [ c == d or: [c size = d size and: [c do: [| :each | (d includes: each) ifFalse: [^ False]]. True]] ]. c@(Set traits) copy [| newC | newC: c clone. newC contents: c contents copy. newC ]. c@(Set traits) size "The number of elements, the conceptual size of the Set." [ c tally ]. c@(Set traits) capacity "How large the Set can be without requiring a new Array of larger size." [ c contents size ]. c@(Set traits) atRandomBy: random "Collaborate with a RandomStream to provide one of the elements at random." [| index | c emptyCheck. ind: (random seed: c contents size). index below: c contents size do: [| :i | (c contents at: i) ifNotNil: [^ c contents at: i]]. 0 below: index do: [| :i | (c contents at: i) ifNotNil: [^ c contents at: i]]. ]. _@(Set traits) accepts: _@Nil "The set implementation uses nils to pad the underlying array." [ False ]. c@(Set traits) include: obj "Ensure that the object is a member of the Set by adding it if not found." [| index | obj ifNil: [^ Nil]. index: (c scanFor: obj). (c contents at: index) ifNil: [c atNewIndex: index put: obj]. obj ]. c@(Set traits) include: _@Nil [Nil]. "Sets can't include Nil. Derive from Set and add a #hasNil slot if you need that to be the case; also the behavior will need adjustment in several places." c@(Set traits) remove: obj ifAbsent: block [| index | index: (c scanFor: obj). (c contents at: index) ifNil: [^ block do]. c contents at: index put: Nil. c tally: c tally - 1. c fixCollisionsFrom: index. obj ]. c@(Set traits) collect: block [| newSet | newSet: c newSameSize. c contents do: [| :each | each ifNotNil: [newSet include: (block applyWith: each)]]. newSet ]. c@(Set traits) do: block [ c tally = 0 ifTrue: [^ c]. c contents do: [| :each | each ifNotNil: [block applyWith: each]]. ]. c@(Set traits) doWithIndex: block "Allow for iterating through the elements with a notional indexing." [| index | index: -1. c do: [| :item | item ifNotNil: [block applyWith: item with: (index: index + 1)]]. ]. c@(Set traits) atNewIndex: index put: obj "A method which does not check for consistency, and merely inserts the object and updates the size. Only trusted methods should call this." [ c contents at: index put: obj. c tally: c tally + 1. c fullCheck ]. c@(Set traits) fixCollisionsFrom: index "The element at index has been removed and replaced by Nil. This moves forward from there, relocating any entries that were placed below due to collisions with this one." [| length oldIndex newIndex element | oldIndex: index. length: c capacity. [oldIndex: oldIndex + 1. oldIndex >= length ifTrue: [oldIndex: 1]. (element: (c keyAt: oldIndex)) isNil] whileFalse: [newIndex: (c scanFor: element). oldIndex = newIndex ifFalse: [c swap: oldIndex with: newIndex]]. c ]. c@(Set traits) fullCheck "Keep the array at least 1/4 free for decent hash behavior." [| size | size: c contents size. size - c tally < (size // 4 max: 1) ifTrue: [c grow]. c ]. c@(Set traits) growSize "The default amount to grow by, either doubling the size or a minimum." [ c contents size max: 4 ]. c@(Set traits) growBy: growthAmount "Replace the array with a new one larger by growthAmount, and copy over the elements with the non-checking method." [| oldElems | oldElems: c contents. c contents: (c contents newSize: c contents size + growthAmount). c tally: 0. oldElems do: [| :each | each ifNotNil: [c noCheckAdd: each]]. c ]. c@(Set traits) grow "Grow the default amount." [ c growBy: c growSize ]. c@(Set traits) keyAt: index "Subclasses can override this to make fixCollisionsFrom: work." [ c contents at: index ]. c@(Set traits) swap: index1 with: index2 "Subclasses can override this to make fixCollisionsFrom: work." [ c contents swap: index1 with: index2. c ]. c@(Set traits) noCheckAdd: obj "Obviously, this method is faster by avoiding a consistency check, and so should only be called by trusted methods." [ c contents at: (c scanFor: obj) put: obj. c tally: c tally + 1. c ]. c@(Set traits) rehash "Use a cloned Set to re-calculate and place the objects in the array, and then simply re-use that Set's array." [| tempSet | tempSet: c newSameSize. c do: [| :each | tempSet noCheckAdd: each]. c contents: tempSet contents. c ]. c@(Set traits) scanFor: obj "Scan the array for the first slot containing either a Nil or an element matching the object. Answer the index of that slot or 0 if no slot is found. Override this to provide different matching criteria." [| element start end block | end: c contents size. start: (c hashBlock applyWith: obj) \\ end. block: [| :index | ((element: (c contents at: index)) isNil or: [c equalsBlock applyWith: element with: obj]) ifTrue: [^ index]]. "Search from the hash MOD size to the end." start below: end do: block. "Search from the beginning." 0 below: start do: block. Nil ]. c@(Set traits) like: obj "Answer an object in the Set that compares correctly to the given object, or Nil if none such is found." [| index | index: (c scanFor: obj). index ifNotNil: [c contents at: index] ]. c@(Set traits) includes: obj "Check the index determined by the hash, and return true whether the array slot isn't empty." [ (c scanFor: obj) ifNotNilDo: [| :index | ^ (c contents at: index) isNotNil ]. False ].