requires: {#ExtensibleCollection. #Dictionary. #SortedArray}. provides: {#Bag}. collections addPrototype: #Bag derivedFrom: {ExtensibleCollection}. "Bags are unsorted collections that can have multiple copies of the same object. Basically, they map distinguishable instance objects to the number of times they occur; they're excellent for accumulating counts." Bag addSlot: #contents valued: Dictionary newEmpty. "A Mapping from objects to the number of occurrences of each." b@(Bag traits) newSized: n "This can't really relate to the actual size of the bag, just the number of unique element values." [| newB | newB: b clone. newB contents: (b contents newSize: n). newB ]. b@(Bag traits) newSize: n "This is an approximation included for protocol completeness. The core method newSized: should be used by the caller if it knows better (basically, if it too is a Bag, and knows what composition of objects is being delivered in advance)." [ b newSized: n ]. b@(Bag traits) newEmpty [ b newSized: 4 ]. b@(Bag traits) size "Total up the number of occurrences for each element." [ b contents inject: 0 into: [| :tally :each | tally + each] ]. b@(Bag traits) copy [| newB | newB: b clone. newB contents: b contents copy. newB ]. b@(Bag traits) accepts: obj "Answers whether the object can be part of the bag, as determined by the implementation as element->numOccurrences mapping." [ b contents acceptsKey: obj ]. b@(Bag traits) add: obj withOccurrences: n "Add n number of b's." [ b contents at: obj put: (b contents at: obj ifAbsent: [0]) + n. obj ]. b@(Bag traits) as: c@(Set traits) "Collect the elements contained. Ignore the number of occurrences." [ b contents keySet as: c ]. b@(Bag traits) add: obj "How the default add: compatible protocol works for bags." [ b add: obj withOccurrences: 1 ]. b@(Bag traits) include: obj "To make sure the object is in the collection at least once, check to see if it is a key in the contents, if not, add it and set the count to 1." [ (b includes: obj) ifFalse: [b at: obj put: 1]. b ]. b@(Bag traits) do: block "Perform the block for each occurrence of each element in the bag." [ b contents keysAndValuesDo: [| :key :val | val timesRepeat: [block applyWith: key]]. b ]. b@(Bag traits) elementsAndOccurrencesDo: block "Perform the block for each element and its occurrence in the Bag." [ b contents keysAndValuesDo: block. b ]. b@(Bag traits) includes: obj "If it's a key, then there are occurrences of it." [ b contents includesKey: obj ]. b@(Bag traits) occurrencesOf: obj "If it's a key, return the number of occurrences noted." [ (b includes: obj) ifTrue: [b contents at: obj] ifFalse: [0] ]. b@(Bag traits) remove: obj ifAbsent: block "Decrement the number of occurrences noted. Remove the key entirely if there's only 1. Otherwise, run the exception." [| count | (count: (b contents at: obj ifAbsent: [^ block do])) = 1 ifTrue: [b contents removeKey: obj] ifFalse: [b contents at: obj put: count - 1]. obj ]. b@(Bag traits) removeEvery: obj "An optimization for bags." [ b contents removeKey: obj. obj ]. b@(Bag traits) sortedCounts "Return a collection of counts in decreasing order." [| counts | counts: (SortedArray newSizeOf: b contents). counts sortBlock: [| :x :y | x >= y]. b contents keysAndValuesDo: [| :key :val | counts add: val -> key]. counts ]. b@(Bag traits) sortedElements "Return a collection of sorted elements with counts." [| elements | elements: (SortedArray newSizeOf: b). b contents associationsDo: [| :assoc | elements add: assoc]. elements ].