"

 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' }"

Collection subclass:#SequenceableCollection

	instanceVariableNames:''

	classVariableNames:'MissingClassInLiteralArrayErrorSignal'

	poolDictionaries:''

	category:'Collections-Abstract'

!

!SequenceableCollection 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

"

    SequenceableCollections have ordered elements which can be accessed via

    a numeric index. 

    SequenceableCollection is an abstract class - there are no instances of 

    it in the system. 

    The methods found here assume that implementations of (at least)

    #at:/#at:put: are implemented (which are always found in Object for

    indexable objects).

    For performance, some subclasses redefine more methods, knowing the details

    of how elements are stored. 

    Especially, bulk data manipulation (i.e. #replaceFrom:to:with:startingAt:) 

    and search methods (i.e. #indexOf:startingAt:) are good candidates for this

    kind of tuneup.

    See concrete subclasses (such as OrderedCollection, Array or String).

    [author:]

        Claus Gittinger

    [see also:]

        OrderedCollection Array

        CharacterArray String

"

! !

!SequenceableCollection class methodsFor:'initialization'!

initialize

    MissingClassInLiteralArrayErrorSignal isNil ifTrue:[

        MissingClassInLiteralArrayErrorSignal := ErrorSignal newSignalMayProceed:true.

        MissingClassInLiteralArrayErrorSignal nameClass:self message:#missingClassInLiteralArrayErrorSignal.

        MissingClassInLiteralArrayErrorSignal notifierString:'Missing class in literal encoding'.

    ]

    "Created: / 18.5.1999 / 14:49:51 / cg"

! !

!SequenceableCollection class methodsFor:'instance creation'!

decodeFromLiteralArray:anArray

    "create & return a new instance from information encoded in anArray.

     Redefined for faster creation.

    "

    |col i|

    col := self withSize:anArray size - 1.

    i := 1.

    anArray from:2 do:[:el| col at:i put:el decodeAsLiteralArray. i := i + 1].

    ^ col

!

new:size withAll:element

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

     initialized to element."

    |newCollection|

    newCollection := self new:size.

    newCollection atAllPut:element.

    ^ newCollection

!

newWithConcatenationOfAll:aCollectionOfCollections

    "this creates and returns a new collection consisting

     of the concatenation of all elements of the argument.

     I.e. it has the same effect as concatenating all elements

     of the argument using #, ,but is implemented more efficiently,

     by avoiding repeated garbage allocations.

     This is an O runtime algorithm, in contrast to the #, loop, which is O*O"

    |totalSize newColl idx|

    totalSize := aCollectionOfCollections 

                        inject:0

                        into:[:sumSoFar :el | sumSoFar + el size].

    newColl := self new:totalSize.

    idx := 1.

    aCollectionOfCollections do:[:el |

        |sz|

        sz := el size.

        newColl replaceFrom:idx to:(idx+sz-1) with:el startingAt:1.

        idx := idx + sz

    ].

    ^ newColl

    "

     this method optimizes the following (common) operation:

         |s|

         s := ''.

         #('hello' ' ' 'world' ' ' 'this is ' 'ST/X') do:[:e|

            s := s , e.

         ]. 

         s  

     String 

        newWithConcatenationOfAll:#('hello' ' ' 'world' ' ' 'this is ' 'ST/X')

     String 

        newWithConcatenationOfAll:#()   

     Array

        newWithConcatenationOfAll:#( (1 2 3 4) (5 6 7 8) (9 10 11 12) )   

     timing:

     -------

     speed-break-even is at around 5 elements for strings;

     for more elements, #newWithConcatenationOfAll: is much faster.

     |arr1 arr2 arr3 t|

     arr1 := #('hello' ' ' 'world' ' ' 'this is ' 'ST/X').

     arr2 := Array new:1000 withAll:'hello'.

     arr3 := Array new:10000 withAll:'hello'.

     (Array with:arr1 with:arr2 with:arr3) with:#(10000 100 10) do:[:arr :cnt |

         t := Time millisecondsToRun:[

            cnt timesRepeat:[

                String 

                    newWithConcatenationOfAll:arr

            ]

         ].

         Transcript showCR:(arr size printString , ' elements - time for #newWithConcatenationOfAll :' , (t/cnt) asFloat printString , 'mS').

         Transcript endEntry.

         t := Time millisecondsToRun:[

            cnt timesRepeat:[

                 |s|

                 s := ''.

                 arr do:[:e|

                    s := s , e.

                 ]. 

                 s  

            ]

         ].  

         Transcript showCR:(arr size printString , ' elements - time for loop over #, :' , (t/cnt) asFloat printString , 'mS').

         Transcript endEntry.

     ]

    "

!

withSize:size

    "return a new collection of size.

     For variable size collections, this is different from #new:,

     in that #new: creates an empty collection with preallocated size,

     while #withSize: creates a non empty one."

    |newCollection|

    newCollection := self new:size.

    newCollection grow:size.

    ^ newCollection

    "

     (OrderedCollection new:10) inspect.

     (OrderedCollection withSize:10) inspect.

     (Array new:10) inspect.

     (Array withSize:10) inspect.

    "

! !

!SequenceableCollection class methodsFor:'Compatibility - Squeak'!

streamContents:blockWithArg

    "create a write-stream on an instance of the receiver-class,

     evaluate blockWithArg, passing that stream,

     extract and return the streams contents."

    |stream|

    stream := WriteStream on:(self new:100).

    blockWithArg value:stream.

    ^ stream contents

    "

     |rslt|

     rslt := String streamContents:[:s | s nextPutAll:'hello'; space; nextPutAll:'world']

    "

    "Modified: / 31.10.2001 / 09:25:45 / cg"

! !

!SequenceableCollection class methodsFor:'Signal constants'!

missingClassInLiteralArrayErrorSignal

    ^ MissingClassInLiteralArrayErrorSignal

    "Created: / 18.5.1999 / 14:50:04 / cg"

! !

!SequenceableCollection methodsFor:'Compatibility - Squeak'!

allButLast

    "Answer a copy of the receiver containing all but the last

     element. Raise an error if there are not enough elements."

    ^ self allButLast:1

    "Modified: / 13.11.2001 / 13:36:36 / cg"

!

allButLast:n

    "Answer a copy of the receiver containing all but the last n

     elements. Raise an error if there are not enough elements."

    ^ self copyFrom: 1 to: self size - n

    "Modified: / 13.11.2001 / 13:36:28 / cg"

!

atPin: index 

    "Return the index'th element of me if possible.

     Return the first or last element if index is out of bounds."

    index < 1 ifTrue:[^ self first].

    index > self size ifTrue:[^ self last].

    ^ self at:index

    "

     #(1 2 3) atPin:4    

     #(1 2 3) atPin:0    

     #(1 2 3) atPin:1    

     #(1 2 3) atPin:3    

    "

!

atRandom 

    "Return any random element from the receiver"

    |max idx|

    (max := self size) == 0 ifTrue:[

        self emptyCollectionError

    ].

    idx := Random nextIntegerBetween:1 and:max.

    ^ self at:idx

    "

     #(1 2 3) atRandom  

    "

!

atWrap:index 

    "Return the index'th element of me if possible.

     Wrap the index modulu the receivers size if it is out of bounds."

    ^ self at:((index - 1) \\ (self size)) + 1

    "

     #(1 2 3) atWrap:1    

     #(1 2 3) atWrap:2    

     #(1 2 3) atWrap:3    

     #(1 2 3) atWrap:4    

     #(1 2 3) atWrap:5    

     #(1 2 3) atWrap:6    

     #(1 2 3) atWrap:7    

     #(1 2 3) atWrap:0    

     #(1 2 3) atWrap:-1    

    "

!

beginsWith:aCollection

    "Squeak & VW compatibility: same as #startsWith: - sigh"

    ^ self startsWith:aCollection

    "Modified: / 13.11.2001 / 13:49:18 / cg"

!

permutationsDo: aBlock

    "Repeatly value aBlock with a single copy of the receiver. Reorder the copy

     so that aBlock is presented all (self size factorial) possible permutations."

    self shallowCopy permutationsStartingAt:1 do:aBlock

    "

     (1 to: 4) permutationsDo:[:each | Transcript cr; show: each printString]

    "

    "Modified: / 13.11.2001 / 13:37:35 / cg"

!

permutationsStartingAt: anInteger do: aBlock

    "#(1 2 3 4) permutationsDo: [:each | Transcript cr; show: each printString]"

    |mySize|

    mySize := self size.

    anInteger > mySize ifTrue: [^self].

    anInteger = mySize ifTrue: [^aBlock value: self].

    anInteger to:mySize do:[:i | 

        self swap: anInteger with: i.

        self permutationsStartingAt: anInteger + 1 do: aBlock.

        self swap: anInteger with: i

    ]

    "Modified: / 13.11.2001 / 13:48:49 / cg"

! !

!SequenceableCollection methodsFor:'Compatibility - VW'!

replaceElementsFrom:start to:stop withArray:anArray startingAt:repStart

    ^ self replaceFrom:start to:stop with:anArray startingAt:repStart

! !

!SequenceableCollection methodsFor:'accessing'!

after:anObject

    "return the element, after anObject.

     If anObject is not in the receiver, report an error;

     if anObject is the last in the receiver, return nil.

     This depends on #after:ifAbsent: being implemented in a concrete class."

    ^ self after:anObject ifAbsent:[self errorValueNotFound:anObject]

    "

     #(4 3 2 1) asOrderedCollection after:3. 

     #(4 3 2 1) asOrderedCollection after:5 

     #(4 3 2 1) asOrderedCollection after:1 

    "

    "Created: 10.5.1996 / 13:59:29 / cg"

    "Modified: 10.5.1996 / 14:03:33 / cg"

!

after:anObject ifAbsent:exceptionBlock

    "return the element, after anObject. 

     If anObject is the last in the receiver, return nil.

     If there is no such element (anObject is not found),

     return the value from exceptionBlock."

    |idx|

    idx := self indexOf:anObject.

    idx ~~ 0 ifTrue:[

        idx == self size ifTrue:[^ nil].

        ^ self at:(idx + 1).

    ].

    ^ exceptionBlock value

    "

     #(4 3 2 1) after:3 ifAbsent:nil. 

     (2 to:10 by:2) after:4 ifAbsent:nil.     

     #(4 3 2 1) asOrderedCollection after:5 ifAbsent:nil. 

     (2 to:10 by:2) after:5 ifAbsent:nil. 

    "

!

at:index ifAbsent:exceptionBlock

    "return the element at index if valid. 

     If the index is invalid, return the result of evaluating 

     the exceptionblock.

     NOTICE: 

        in ST-80, this message is only defined for Dictionaries,

        however, having a common protocol with indexed collections

        often simplifies things."

    ((index < 1) or:[index > self size]) ifTrue:[

        ^ exceptionBlock value

    ].

    ^ self at:index

    "

     #(1 2 3) at:4 ifAbsent:['no such index']

     #(1 2 3) asOrderedCollection at:4 ifAbsent:['no such index'] 

     #(1 2 3) at:4 ifAbsent:['no such index']  

     (Dictionary with:(#foo -> #bar)

                 with:(#frob -> #baz)) 

         at:#foobar ifAbsent:['no such index']

    "

!

before:anObject

    "return the element before the argument, anObject.

     If anObject is not in the receiver, report an error;

     if anObject is the first in the receiver, return nil.

     This depends on #before:ifAbsent: being implemented in a concrete class."

    ^ self before:anObject ifAbsent:[self errorValueNotFound:anObject]

    "

     #(4 3 2 1) asOrderedCollection before:3. 

     #(4 3 2 1) asOrderedCollection before:4 

     #(4 3 2 1) asOrderedCollection before:0 

    "

    "Created: 10.5.1996 / 14:03:27 / cg"

    "Modified: 10.5.1996 / 14:03:44 / cg"

!

before:anObject ifAbsent:exceptionBlock

    "return the element, before anObject. 

     If anObject is the first in the receiver, return nil.

     If there is no such element (anObject is not found),

     return the value from exceptionBlock."

    |idx|

    idx := self indexOf:anObject.

    idx ~~ 0 ifTrue:[

        idx == 1 ifTrue:[^ nil].

        ^ self at:(idx - 1).

    ].

    ^ exceptionBlock value

    "

     #(4 3 2 1) asOrderedCollection before:3 ifAbsent:nil. 

     #(4 3 2 1) asOrderedCollection before:5 ifAbsent:nil. 

     #(4 3 2 1) asOrderedCollection before:5. 

     #(4 3 2 1) asOrderedCollection before:4 ifAbsent:nil. 

     #(4 3 2 1) asOrderedCollection before:4.            

     (2 to:10 by:2) before:4 ifAbsent:nil.            

     (2 to:10 by:2) before:5 ifAbsent:nil.            

    "

!

first

    "return the first element; 

     report an error, if the collection is empty."

    ^ self at:1

    "

     args:    

     returns: firstElement <object>

    "

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

!

first:n

    "return the n first elements of the collection.

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

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

    n > self size ifTrue:[^ self notEnoughElementsError].

    ^ self copyFirst:n

    "

     #(1 2 3 4 5) first:3           

     #(1 2 3 4 5) first:6           

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

     'hello world' first:5           

    "