"

 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 direct 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 detail 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.

    The most heavily used SequentialCollections in the system are probably Array, String, ByteArray

    OrderedCollection and SortedCollection.

    [author:]

        Claus Gittinger

    [see also:]

        Array ByteArray OrderedCollection SortedCollection 

        CharacterArray String

"

! !

!SequenceableCollection class methodsFor:'initialization'!

initialize

    MissingClassInLiteralArrayErrorSignal isNil ifTrue:[

	MissingClassInLiteralArrayErrorSignal := Error 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."

    |collection

     sz "{ Class: SmallInteger }"|

    sz := anArray size.

    collection := self withSize:sz-1.

    2 to:sz do:[:idx| collection at:idx-1 put:(anArray at:idx) decodeAsLiteralArray].

    ^ collection

    "

     Array

	decodeFromLiteralArray:#(Array 1 2 3)

    "

!

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."

    ^ (self new:size) grow:size.

    "

     (OrderedCollection new:10) inspect.

     (OrderedCollection withSize:10) inspect.

     (Array new:10) inspect.

     (Array withSize:10) inspect.

    "

! !

!SequenceableCollection class methodsFor:'Compatibility-Squeak'!

writeStream

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

    ^ WriteStream on:(self new:50).

    "

     OrderedCollection writeStream

    "

    "Modified: / 29-03-2007 / 15:20:02 / cg"

! !

!SequenceableCollection class methodsFor:'Signal constants'!

missingClassInLiteralArrayErrorSignal

    ^ MissingClassInLiteralArrayErrorSignal

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

! !

!SequenceableCollection class methodsFor:'instance creation-multiDimensional'!

_at:nIndices

    "this is a synthetic selector, generated by the compiler,

     if a construct of the form expr[idx...] is parsed.

     I.e.

	Array[n]

     generates

	Array _at: n

    "

    ^ self new:nIndices

!

_at:dim1 at:dim2

    "this is a synthetic selector, generated by the compiler,

     if a construct of the form expr[idx...] is parsed.

     I.e.

	Array[n,m]

     generates

	Array _at:n at:m

    "

    |data|

    data := self withSize:(dim1 * dim2).

    ^ MultiDimensionalArrayAccessor

	collection:data

	dimensions:(Array with:dim1 with:dim2)

!

_at:dim1 at:dim2 at:dim3

    "this is a synthetic selector, generated by the compiler,

     if a construct of the form expr[idx...] is parsed.

     I.e.

	Array[n,m,o]

     generates

	Array _at:n at:m at:o

    "

    |data|

    data := self withSize:(dim1 * dim2 * dim3).

    ^ MultiDimensionalArrayAccessor

	collection:data

	dimensions:(Array with:dim1 with:dim2 with:dim3)

! !

!SequenceableCollection class methodsFor:'instance creation-streaming'!

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 := self writeStream.

    blockWithArg value:stream.

    ^ stream contents

    "

     |rslt|

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

    "

    "Modified: / 29-03-2007 / 15:20:20 / cg"

!

streamContents:blockWithArg limitedTo:limit

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

     evaluate blockWithArg, passing that stream,

     extract and return the streams contents (possibly truncated)."

    |stream|

    stream := self writeStream.

    stream writeLimit:limit.

    blockWithArg value:stream.

    ^ stream contents

    "Created: / 04-06-2007 / 17:22:38 / cg"

!

streamContentsEnumerating:aReceiver using:enumeratorSelector

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

     enumerate on aReceiver using enumeratorSelector as a do-block-selector,

     and return the collected values. Especially useful, if you have a do-like

     enumerator somewhere, and you want this as a collection."

    |stream|

    stream := self writeStream.

    aReceiver perform:enumeratorSelector with:[:each |stream nextPut:each].

    ^ stream contents

    "

     String streamContentsEnumerating:'hello' using:#reverseDo:

     Array streamContentsEnumerating:Method using:#allInstancesDo:

    "

    "Created: / 29-03-2007 / 15:21:12 / cg"

!

streamContentsOf:aReceiver enumerator:enumeratorSelector

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

     enumerate on aReceiver using enumeratorSelector as a do-block-selector,

     and return the collected values. Especially useful, if you have a do-like

     enumerator somewhere, and you want this as a collection."

    |stream|

    stream := self writeStream.

    aReceiver perform:enumeratorSelector with:[:each |stream nextPut:each].

    ^ stream contents

    "

     String streamContentsOf:'hello' enumerator:#reverseDo:

     Array streamContentsOf:Method enumerator:#allInstancesDo:

    "

    "Created: / 29-03-2007 / 15:05:30 / cg"

! !

!SequenceableCollection class methodsFor:'queries'!

isAbstract

    "Return if this class is an abstract class.

     True is returned for SequenceableCollection here; false for subclasses.

     Abstract subclasses must redefine again."

    ^ self == SequenceableCollection

! !

!SequenceableCollection methodsFor:'Compatibility-Squeak'!

allButFirst

    "Return a copy of the receiver containing all but the first element.

     Raise an error if there are not enough elements."

    ^ self copyFrom:2

    "

     '1234567890' allButFirst

    "

!

allButFirst:n

    "Return a copy of the receiver containing all but the first n elements.

     Raise an error if there are not enough elements."

    ^ self copyFrom:n+1

    "

     '1234567890' allButFirst:5

    "

!

allButLast

    "Return a copy of the receiver containing all but the last element.

     Raise an error if there are not enough elements."

    ^ self allButLast:1

    "

     '1234567890' allButLast

    "

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

!

allButLast:n

    "Return 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

    "

     '1234567890' allButLast:5

    "

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

    ^ self atRandom:Random

    "

     #(1 2 3) atRandom

    "

!

atRandom:aRandomGenerator

    "Return any random element from the receiver"

    |max idx|

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

	self emptyCollectionError

    ].

    idx := aRandomGenerator nextIntegerBetween:1 and:max.

    ^ self at:idx

    "

     #(1 2 3) atRandom:(Random new)

    "

!

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"

!

collect:aBlock from:startIndex to:stopIndex

    "squeak uses a different naming here - sigh.

     Notice, that the squeak name is actually wrong and misleading, as it suggests

     collecting first and then taking the subcollection; this is wrong, as conceptually,

     this method first takes a slice (from:to:) and then collects over that.

     I.e. it is equivalent to:

	(self startIndex to:stopIndex) collect:aBlock"