"

 COPYRIGHT (c) 1989 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' }"

Object subclass:#Collection

	instanceVariableNames:''

	classVariableNames:'InvalidKeySignal EmptyCollectionSignal ValueNotFoundSignal

		NotEnoughElementsSignal RecursiveCollectionStoreStringSignal'

	poolDictionaries:''

	category:'Collections-Abstract'

!

!Collection class methodsFor:'documentation'!

copyright

"

 COPYRIGHT (c) 1989 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

"

    Abstract superclass for all collections.

    This abstract class provides functionality common to all collections,

    without knowing how the concrete class implements things. Thus, all

    methods found here depend on some basic mechanisms to be defined in the

    concrete class. 

    These basic methods are usually defined as #subclassResponsibility here.

    Some methods are also redefined for better performance.

    Subclasses should at least implement:

        do:     - enumerate elements

    they should implement one of the following set of access messages:

    keyed collections:

        at:ifAbsent:            - fetching an element

        at:                     - fetching an element

        at:put:                 - storing an element

    unkeyed collections:

        add:                    - add an element

        remove:ifAbsent:        - remove an element

    [author:]

        Claus Gittinger

"

! !

!Collection class methodsFor:'initialization'!

initialize

    "setup the signal"

    InvalidKeySignal isNil ifTrue:[

        InvalidKeySignal := ErrorSignal newSignalMayProceed:true.

        InvalidKeySignal nameClass:self message:#invalidKeySignal.

        InvalidKeySignal notifierString:'invalid key:'.

        ValueNotFoundSignal := NotFoundSignal newSignalMayProceed:true.

        ValueNotFoundSignal nameClass:self message:#valueNotFoundSignal.

        ValueNotFoundSignal notifierString:'value not found:'.

        NotEnoughElementsSignal := NotFoundSignal newSignalMayProceed:true.

        NotEnoughElementsSignal nameClass:self message:#notEnoughElementsSignal.

        NotEnoughElementsSignal notifierString:'not enough elements in collection'.

        EmptyCollectionSignal := NotEnoughElementsSignal newSignalMayProceed:true.

        EmptyCollectionSignal nameClass:self message:#emptyCollectionSignal.

        EmptyCollectionSignal notifierString:'operation not allowed for empty collections'.

    ]

    "Modified: / 8.11.1997 / 19:18:17 / cg"

! !

!Collection class methodsFor:'instance creation'!

new:size withAll:element

    "return a new Collection of size, where all elements are

     initialized to element"

    |newCollection|

    newCollection := self new:size.

    size timesRepeat:[newCollection add:element]

!

newFrom:aCollection 

    "Return an instance of me containing the same elements as aCollection."

    ^ self withAll:aCollection

    "

     Bag newFrom:#(1 2 3 4 4 5 6 7 7 7 )  

     Set newFrom:#(1 2 3 4 4 5 6 7 7 7 ) 

    "

!

with:anObject

    "return a new Collection with one element:anObject"

    |newCollection|

    newCollection := self new.

    newCollection add:anObject.

    ^ newCollection

!

with:firstObject with:secondObject

    "return a new Collection with two elements:firstObject and secondObject"

    |newCollection|

    newCollection := self new.

    newCollection add:firstObject; add:secondObject.

    ^ newCollection

!

with:firstObject with:secondObject with:thirdObject

    "return a new Collection with three elements"

    |newCollection|

    newCollection := self new.

    newCollection add:firstObject; add:secondObject; add:thirdObject.

    ^ newCollection

!

with:firstObject with:secondObject with:thirdObject with:fourthObject

    "return a new Collection with four elements"

    |newCollection|

    newCollection := self new.

    newCollection add:firstObject; add:secondObject; add:thirdObject; add:fourthObject.

    ^ newCollection

!

with:a1 with:a2 with:a3 with:a4 with:a5

    "return a new Collection with five elements"

    |newCollection|

    newCollection := self new.

    newCollection add:a1; add:a2; add:a3; add:a4; add:a5.

    ^ newCollection

    "Modified: 22.1.1997 / 19:34:01 / cg"

!

with:a1 with:a2 with:a3 with:a4 with:a5 with:a6

    "return a new Collection with size elements"

    |newCollection|

    newCollection := self new.

    newCollection add:a1; add:a2; add:a3; add:a4; add:a5; add:a6.

    ^ newCollection

    "Created: 22.1.1997 / 19:34:14 / cg"

!

with:a1 with:a2 with:a3 with:a4 with:a5 with:a6 with:a7

    "return a new Collection with seven elements"

    |newCollection|

    newCollection := self new.

    newCollection add:a1; add:a2; add:a3; add:a4; add:a5; add:a6; add:a7.

    ^ newCollection

    "Created: 22.1.1997 / 19:34:24 / cg"

!

with:a1 with:a2 with:a3 with:a4 with:a5 with:a6 with:a7 with:a8

    "return a new Collection with eight elements"

    |newCollection|

    newCollection := self new.

    newCollection add:a1; add:a2; add:a3; add:a4; add:a5; add:a6; add:a7; add:a8.

    ^ newCollection

    "Created: 22.1.1997 / 19:34:34 / cg"

!

withAll:aCollection

    "return a new Collection with all elements taken from the argument,

     aCollection"

    |newCollection|

    newCollection := self new.

    newCollection addAll:aCollection.

    ^newCollection

! !

!Collection class methodsFor:'Signal constants'!

emptyCollectionSignal

    "return the signal used to report non-allowed operation on empty collections"

    ^ EmptyCollectionSignal

!

invalidKeySignal

    "return the signal used to report bad key usage"

    ^ InvalidKeySignal

!

notEnoughElementsSignal

    "return the signal used to report attempts for an operation, for which

     there are not enough elements in the collection"

    ^ NotEnoughElementsSignal

!

valueNotFoundSignal

    "return the signal used to report a nonexisting element."

    ^ ValueNotFoundSignal

! !

!Collection class methodsFor:'queries'!

growIsCheap

    "return true, if this collection can easily grow

     (i.e. without a need for become:).

     Returns true here; this method is redefined in fix-size

     collections"

    ^ true

! !

!Collection methodsFor:'Compatibility - Squeak'!

anyOne

    "return any element from the collection, or nil if there is none.

     Same as #anElement - for Squeak compatibility"

    ^ self anElement

!

sum

    "This is implemented using a variant of the normal inject:into: pattern. 

    The reason for this is that it is not known whether we're in the normal 

    number line, i.e. whether 0 is a good initial value for the sum. 

    Consider a collection of measurement objects, 0 would be the unitless 

    value and would not be appropriate to add with the unit-ed objects."

    | sum sample |

    sample _ self anyOne.

    sum _ self inject: sample into: [:accum :each | accum + each].

    ^ sum - sample.

!

withIndexDo:aTwoArgBlock 

    "evaluate the argument, aBlock for every element in the collection,

     passing both element and index as arguments."

    ^ self keysAndValuesDo:[:key :index |

        aTwoArgBlock value:index value:key

    ].

! !

!Collection methodsFor:'accessing'!

anElement

    "return any element from the collection, or nil if there is none"

    self do: [:each | ^ each].

    ^ nil

!

atAll:indexCollection put:anObject

    "put anObject into all indexes from indexCollection in the receiver.

     This abstract implementation requires that the receiver supports

     access via a key (and indexCollection contains valid keys).

     Notice: This operation modifies the receiver, NOT a copy;

     therefore the change may affect all others referencing the receiver."

    indexCollection do:[:index | self at:index put:anObject]

    "

     args:    indexCollection : <Collection of keys<object> >

     returns: self

    "

    "

     (Array new:10) atAll:(1 to:5) put:0

     (Array new:10) atAll:#(1 5 6 9) put:0

     (Dictionary new) atAll:#(foo bar baz) put:'hello' 

    raises an error:

     (Set new) atAll:#(foo bar baz) put:'hello' 

    "

    "Modified: / 20.5.1998 / 14:50:46 / cg"

!

fifth

    "return the fifth element of the collection.

     For unordered collections, this simply returns the fifth

     element when enumerating them.

     This should be redefined in subclasses."

    ^ self nth:5

    "

     #(1 2 3 4 5) fifth

    "

!

first

    "return the first element of the collection.

     For unordered collections, this simply returns the first

     element when enumerating them.

     This should be redefined in subclasses."

    self do:[:e | ^ e].

    "error if collection is empty"

    ^ self emptyCollectionError

!

first:n

    "return the n first elements of the collection.

     Raises an error if there are not enough elements in the receiver.

     For unordered collections, this simply returns the first

     n elements when enumerating them 

     (Warning: the contents of the returned collection is not deterministic in this case).

     This should be redefined in subclasses."

    |coll remain|

    n < 0 ifTrue:[self error:'bad (negative) argument'].

    coll := OrderedCollection new.

    remain := n.    

    self do:[:e | 

                coll add:e.

                remain := remain - 1.

                remain == 0 ifTrue:[

                    ^ coll

                ].

            ].

    "error if collection has not enough elements"

    ^ self notEnoughElementsError

    "

     #(1 2 3 4 5) first:3           

     #(1 2 3 4 5) asSet first:3           

    "

!

firstIfEmpty:exceptionValue

    "return the first element of the collection.

     If its empty, return the excveptionValue.

     (i.e. dont trigger an error as done in #first)"

    self isEmpty ifTrue:[^ exceptionValue value].

    ^  self first

    "Modified: 6.2.1996 / 15:27:17 / cg"

!

fourth

    "return the fourth element of the collection.

     For unordered collections, this simply returns the fourth

     element when enumerating them.

     This should be redefined in subclasses."

    ^ self nth:4

    "

     #(1 2 3 4) fourth

    "

!

last

    "return the last element of the collection.

     This should be redefined in subclasses."

    |theLastOne any|

    any := false.

    self do:[:e | any := true. theLastOne := e].

    any ifTrue:[

        ^ theLastOne

    ].

    "error if collection is empty"

    ^ self emptyCollectionError

!

last:n

    "return the n last elements of the collection.

     Raises an error if there are not enough elements in the receiver.

     For unordered collections, this simply returns the last

     n elements when enumerating them 

     (Warning: the contents of the returned collection is not deterministic in this case).

     This should be redefined in subclasses since the implementation here is VERY inefficient."

    |coll remain|

    n < 0 ifTrue:[self error:'bad (negative) argument'].

    coll := OrderedCollection new.

    remain := n.    

    self do:[:e | 

                coll addLast:e.

                remain > 0 ifTrue:[

                    remain := remain - 1.

                ] ifFalse:[

                    coll removeFirst.

                ].

            ].

    remain ~~ 0 ifTrue:[

        "error if collection has not enough elements"

        ^ self notEnoughElementsError

    ].

    ^ coll

    "

     #(1 2 3 4 5) last:3           

     #(1 2 3 4 5) asSet last:3           

     'hello world' last:5           

    "

!

lastIfEmpty:exceptionValue

    "return the last element of the collection.

     If its empty, return the exceptionValue.

     (i.e. dont trigger an error as done in #last)"

    self isEmpty ifTrue:[^ exceptionValue value].

    ^ self last

    "Modified: 6.2.1996 / 15:27:17 / cg"

    "Created: 6.2.1996 / 15:27:49 / cg"

!

nth:n

    "return the nth element of the collection.

     For unordered collections, this simply returns the nth

     element when enumerating them.

     This should be redefined in subclasses."

    |count|

    count := 1.

    self do:[:e | 

        count == n ifTrue:[^ e].

        count := count + 1

    ].

    "error if collection is smaller"

    ^ self notEnoughElementsError

    "

     #(1 2 3 4) nth:3

     #(1 2 3 4) nth:5

     #(1 2 3 4) asSet nth:3  

     #(1 2 3 4) asSet nth:5

    "

!

second