1 collections define: #NoDuplicatesCollection &parents: {ExtensibleCollection}.
2 "The collection type which holds at most one of any object as an element."
3 "TODO: find out if some collections need to be non-extensible AND optimized
4 for no-duplicates. (My guess is that the answer is 'no'.)"
6 nd@(NoDuplicatesCollection traits) add: obj withOccurrences: _
11 nd@(NoDuplicatesCollection traits) add: obj
16 nd@(NoDuplicatesCollection traits) include: obj
17 "This is the default method for adding objects to NoDuplicatesCollection.
18 It should be overridden in any case, but this implementation allows for any
19 collection type to be treated as a NoDuplicatesCollection by mixing it in."
21 nd add: obj ifPresent: [obj]
24 nd@(NoDuplicatesCollection traits) exclude: obj
25 "This is the default method for removing objects from NoDuplicatesCollection.
26 It should be overridden in any case, but this implementation allows for any
27 collection type to be treated as a NoDuplicatesCollection by mixing it in."
30 nd@(NoDuplicatesCollection traits) removeEvery: obj
31 "Objects only occur once in these collections."
36 nd@(NoDuplicatesCollection traits) includeAll: c
38 c do: #(nd include: _) `er.
41 "An Unordered, Extensible Collection of elements without duplicates. Being
42 a duplicate is determined by a binary comparison and associated hash
43 function on each object."
45 collections define: #Set &parents: {NoDuplicatesCollection} &slots: {
47 #contents -> (Array newSize: 10).
48 #containsNil -> False.
49 #hashBlock -> (#hash `er) .
50 #equalsBlock -> (#= `er) .
53 collections IdentitySet ::=
54 Set cloneSettingSlots: #{#hashBlock. #equalsBlock} to: {#identityHash`er. #==`er}.
55 "IdentitySets specialize their behavior to compare solely by object identity."
57 c@(Set traits) new &capacity: n
60 [contents := c contents new &capacity: ((n ifNil: [0]) max: 1). tally := 0. ]
63 c@(Set traits) = d@(Set traits)
64 "Comparison is by iteration over each element in the Sets. This is avoided
65 when possible by making very cheap comparisons first."
69 /\ [c containsNil eqv: d containsNil]
70 /\ [c allSatisfy: [| :each | d includes: each]]]
74 [c clone `>> [contents := c contents copy. ]].
77 "The number of elements, the conceptual size of the Set."
79 c tally + (c containsNil ifTrue: [1] ifFalse: [0])
82 c@(Set traits) capacity
83 "How large the Set can be without requiring a new Array of larger size."
92 c containsNil := False.
95 c@(Set traits) atRandomBy: random
96 "Collaborate with a RandomStream to provide one of the elements at random."
99 (randomIndex ::= random next \\ c contents size) below: c contents size do:
100 [| :i | (c contents at: i) ifNotNilDo: [| :obj | ^ obj]].
101 0 below: randomIndex do:
102 [| :i | (c contents at: i) ifNotNilDo: [| :obj | ^ obj]].
105 c@(Set traits) include: obj
106 "Ensure that the object is a member of the Set by adding it if not found."
108 (c contents at: (index ::= c scanFor: obj))
109 ifNil: [c atNewIndex: index put: obj].
113 c@(Set traits) include: _@Nil [c containsNil := True. ].
115 c@(Set traits) remove: obj ifAbsent: block
117 (c contents at: (index ::= c scanFor: obj))
120 [c contents at: index put: Nil.
122 c fixCollisionsFrom: index.
126 c@(Set traits) remove: _@Nil ifAbsent: block
129 ifTrue: [c containsNil := False. ]
133 c@(Set traits) collect: block
135 result ::= c newSameSize.
136 c do: [| :each | result include: (block apply*, each)].
140 c@(Set traits) do: block
142 c containsNil ifTrue: [block apply*, Nil].
145 [| :each | each ifNotNil: [block apply*, each]]].
148 c@(Set traits) doWithIndex: block
149 "Allow for iterating through the elements with a notional indexing."
153 item ifNotNil: [block apply*, item, (index += 1)]].
156 c@(Set traits) atNewIndex: index put: obj
157 "A method which does not check for consistency, and merely inserts the
158 object and updates the size. Only trusted methods should call this."
160 c contents at: index put: obj.
165 c@(Set traits) fixCollisionsFrom: index
166 "The element at index has been removed and replaced by Nil.
167 This moves forward from there, relocating any entries that were
168 placed below due to collisions with this one."
169 [| oldIndex newIndex element |
172 [(oldIndex += 1) >= c capacity
173 ifTrue: [oldIndex := 1].
174 (element := c keyAt: oldIndex) isNil]
176 [(newIndex := c scanFor: element) = oldIndex
177 ifFalse: [c swap: oldIndex with: newIndex]].
180 c@(Set traits) fullCheck
181 "Keep the array at least 1/4 free for decent hash behavior."
183 c contents size - c tally < (c contents size // 4 max: 1)
187 c@(Set traits) growSize
188 "The default amount to grow by, either doubling the size or a minimum."
190 c contents size max: 4
193 c@(Set traits) growBy: growthAmount
194 "Replace the array with a new one larger by growthAmount, and copy over the
195 elements with the non-checking method."
197 oldElems ::= c contents.
198 c contents := c contents new &capacity: c contents size + growthAmount.
200 oldElems do: [| :each |
201 each ifNotNil: [c noCheckAdd: each]].
206 "Grow the default amount."
211 c@(Set traits) keyAt: index
212 "Subclasses can override this to make fixCollisionsFrom: work."
217 c@(Set traits) swap: index1 with: index2
218 "Subclasses can override this to make fixCollisionsFrom: work."
220 c contents swap: index1 with: index2.
223 c@(Set traits) noCheckAdd: obj
224 "Obviously, this method is faster by avoiding a consistency check, and so
225 should only be called by trusted methods."
227 c contents at: (c scanFor: obj) put: obj.
231 c@(Set traits) noCheckAdd: _@Nil
233 c containsNil := True.
236 c@(Set traits) rehash
237 "Use a cloned Set to re-calculate and place the objects in the array, and
238 then simply re-use that Set's array."
240 tempSet ::= c newSameSize.
241 c do: #(tempSet noCheckAdd: _) `er.
242 c contents := tempSet contents.
245 c@(Set traits) scanFor: obj
246 "Scan the array for the first slot containing either a Nil or an element
247 matching the object. Answer the index of that slot or 0 if no slot is
248 found. Override this to provide different matching criteria."
250 end ::= c contents size.
251 start ::= (c hashBlock apply*, obj) \\ end.
254 (element := c contents at: index) isNil
255 \/ [c equalsBlock apply*, element, obj]
257 "Search from the hash MOD size to the end."
258 start below: end do: block.
259 "Search from the beginning."
260 0 below: start do: block.
264 c@(Set traits) like: obj
265 "Answer an object in the Set that compares correctly to the given object, or
266 Nil if none such is found."
268 (c scanFor: obj) ifNotNilDo: [| :index | c contents at: index]
271 c@(Set traits) includes: obj
272 "Check the index determined by the hash, and return true whether the array
277 ifNotNilDo: [| :index | (c contents at: index) isNotNil]
280 c@(Set traits) includes: _@Nil [c containsNil].
282 c@(Collection traits) copyWithoutDuplicates &comparison: equalsBlock
283 "Iterate through the Collection, creating a new one where only the first
284 element (encountered by do:) distinct according to the comparison is included."
287 equalsBlock ifNotNil: [seen equalsBlock := equalsBlock].
289 c do: [| :each | (seen includes: each)
290 ifFalse: [result nextPut: (seen include: each)]]