"
 COPYRIGHT (c) 1991 by Claus Gittinger
	      All Rights Reserved

 This software is furnished under a license and may be used
 only in accordance with the terms of that license and with the
 inclusion of the above copyright notice.   This software may not
 be provided or otherwise made available to, or used by, any
 other person.  No title to or ownership of the software is
 hereby transferred.
"

"{ Package: 'stx:libbasic' }"

Collection subclass:#Bag
	instanceVariableNames:'contents'
	classVariableNames:''
	poolDictionaries:''
	category:'Collections-Unordered'
!

!Bag class methodsFor:'documentation'!

copyright
"
 COPYRIGHT (c) 1991 by Claus Gittinger
	      All Rights Reserved

 This software is furnished under a license and may be used
 only in accordance with the terms of that license and with the
 inclusion of the above copyright notice.   This software may not
 be provided or otherwise made available to, or used by, any
 other person.  No title to or ownership of the software is
 hereby transferred.
"
!

documentation
"
    Bag implements collections whose elements are unordered and have no
    external key. Elements may occur more than once in a bag. There is no defined
    order within a bag. 
    The default implementation uses a dictionary to store each objects occurence 
    count, using the object itself as key (i.e. using = and hash for inclusion 
    tests).

    There is also an instance creation variant (#identityNew:) creating a
    bag which compares using #== and hashes using #identityHash.
    (I'd say that an IdentityBag was a better thing to implement ... 
     ... but for compatibility ... we do it here as well)

    [Instance variables:]

        contents        <Dictionary>    for each element, the number of occurrences


    [author:]
        Claus Gittinger

    [See also:]
        Set IdentitySet
        Dictionary IdentityDictionary
        OrderedCollection Array
"
! !

!Bag class methodsFor:'instance creation'!

equalityNew:size
    "return a new empty Bag with initial space for size elements.
     Elements will be compared using equality compare (i.e. #= not #== identity)."

    ^ self basicNew initContents:size
!

identityNew
    "return a new empty Bag which compares for identity
     Elements will be compared using identity compare (i.e. #== not #= equality)."

    ^ super new initContentsForIdentity
!

identityNew:size
    "return a new empty Bag with initial space for size elements.
     Elements will be compared using identity compare (i.e. #== not #= equality)."

    ^ self basicNew initContentsForIdentity:size
!

new
    "return a new empty Bag which compares for equality (i.e. not identity)"

    ^ self basicNew initContents
!

new:size
    "return a new empty Bag with initial space for size elements.
     Elements will be compared using equality compare (i.e. #= not #== identity)."

    ^ self equalityNew:size
! !

!Bag methodsFor:'Compatibility-Dolphin'!

asAssociations
    ^ contents
! !

!Bag methodsFor:'accessing'!

at:index
    "report an error: at: is not allowed for Bags"

    ^ self errorNotKeyed
!

at:index put:anObject
    "report an error: at:put: is not allowed for Bags"

    ^ self errorNotKeyed
!

contents
    "return the dictionary which associates occurrence-counts
     to the bags elements."

    ^ contents
! !

!Bag methodsFor:'adding & removing'!

add:newObject
    "add the argument, anObject to the receiver.
     Returns the object.

     WARNING: do not add/remove elements while iterating over the receiver.
              Iterate over a copy to do this."

    |n|

    n := contents at:newObject ifAbsent:0.
    contents at:newObject put:(n + 1).
    ^ newObject

    "Modified: 1.3.1996 / 21:43:06 / cg"
!

add:newObject withOccurrences:anInteger
    "add the argument, anObject anInteger times to the receiver.
     Returns the object.

     WARNING: do not add/remove elements while iterating over the receiver.
              Iterate over a copy to do this."

    |n|

    n := contents at:newObject ifAbsent:0.
    contents at:newObject put:(n + anInteger).
    ^ newObject

    "Modified: 1.3.1996 / 21:43:12 / cg"
    "Created: 11.5.1996 / 12:13:43 / cg"
!

remove:oldObject ifAbsent:anExceptionBlock
    "Remove oldObject from the collection.
     If it was not present, return the value of the exceptionBlock;
     otherwise return the removed object.

     WARNING: do not add/remove elements while iterating over the receiver.
              Iterate over a copy to do this."

    |count|

    count := contents at:oldObject ifAbsent:0.
    (count == 0) ifTrue:[^ anExceptionBlock value].
    (count == 1) ifTrue:[
        contents removeKey:oldObject
    ] ifFalse:[ 
        contents at:oldObject put:(count - 1)
    ].
    ^ oldObject

    "Modified: 1.3.1996 / 21:43:18 / cg"
!

removeAll
    "remove all objects from the receiver collection (i.e. make it empty).
     Returns the receiver."

    contents := contents species new.

    "
     |b|

     b := Bag new.
     b add:1; add:2; add:3; add:2; add:1.
     Transcript showCR:b.

     b removeAll.

     Transcript showCR:b
    "

    "Modified: 12.4.1996 / 13:34:34 / cg"
!

removeAllOccurrencesOf:oldObject ifAbsent:anExceptionBlock
    "Remove all occurrences of oldObject from the collection.
     If it was not present, return the value of the exceptionBlock;
     otherwise return the number of removes.

     WARNING: do not add/remove elements while iterating over the receiver.
              Iterate over a copy to do this."

    |count|

    count := contents at:oldObject ifAbsent:0.
    (count == 0) ifTrue:[^ anExceptionBlock value].
    contents removeKey:oldObject.
    ^ oldObject

    "Modified: 1.3.1996 / 21:43:26 / cg"
! !

!Bag methodsFor:'comparing'!

= aBag
    aBag species == self species ifFalse:[^ false].
    self size == aBag size ifFalse:[^ false].
    self valuesAndCountsDo:[:val :cnt |
        (aBag occurrencesOf:val) == cnt ifFalse:[^ false]
    ].
    ^ true
!

hash
    |h|

    h := self size.
    self valuesAndCountsDo:[:val :cnt |
        h := h + cnt hash.
    ].
    ^ h
! !

!Bag methodsFor:'converting'!

asBag
    "return the receiver as a bag"

    "could be an instance of a subclass..."
    self class == Bag ifTrue:[
	^ self
    ].
    ^ super asBag
!

asSet
    "return the receiver as a set"

    ^ contents keys copy

    "
     |b|

     b := Bag new.
     b add:1; add:2; add:3; add:1; add:1.
     b asSet.
    "
! !

!Bag methodsFor:'copying'!

postCopy
    "must copy the contents as well"

    contents := contents copy
! !

!Bag methodsFor:'enumerating'!

do:aBlock
    "evaluate the block for all elements in the collection.

     WARNING: do not add/remove elements while iterating over the receiver.
              Iterate over a copy to do this."

    contents keysAndValuesDo:[:key :value|
        value timesRepeat:[
            aBlock value:key
        ]
    ]

    "Modified: 1.3.1996 / 21:42:39 / cg"
!

valuesAndCountsDo:aTwoArgBlock
    "evaluate the block for all distinct elements in the collection,
     passing both the element and the occurence count as arguments.

     WARNING: do not add/remove elements while iterating over the receiver.
              Iterate over a copy to do this."

    ^ contents keysAndValuesDo:aTwoArgBlock

    "Modified: 1.3.1996 / 21:42:44 / cg"
! !

!Bag methodsFor:'private'!

initContents
    "set the contents to be an empty Dictionary"

    contents := Dictionary new
!

initContents:size
    "set the contents to be an empty Dictionary with initial size"

    contents := Dictionary new:size
!

initContentsForIdentity
    "set the contents to be an empty IdentityDictionary"

    contents := IdentityDictionary new
!

initContentsForIdentity:size
    "set the contents to be an empty IdentityDictionary with initial size"

    contents := IdentityDictionary new:size
! !

!Bag methodsFor:'queries'!

size
    "return the number of bag elements"

    |count|

    count := 0.
    contents do:[:element | count := count + element].
    ^ count
! !

!Bag methodsFor:'testing'!

includes:anObject
    "return true, if anObject is in the receiver"

    ^ contents includesKey:anObject
!

occurrencesOf:anObject
    "return how many times anObject is in the receiver"

    ^ contents at:anObject ifAbsent:0
! !

!Bag class methodsFor:'documentation'!

version
    ^ '$Header: /cvs/stx/stx/libbasic/Bag.st,v 1.31 2003-05-07 14:31:15 cg Exp $'
! !