"

 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.

"

Collection subclass:#SequenceableCollection

	instanceVariableNames:''

	classVariableNames:''

	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:'instance creation'!

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

!

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 methodsFor:'accessing'!

after:anObject

    "return the element, after anObject.

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

     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 there is no such element,

     return the value from exceptionBlock."

    ^ self subclassResponsibility

    "Created: 10.5.1996 / 14:00:10 / cg"

!

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'] 

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

     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 there is no such element,

     return the value from exceptionBlock."

    ^ self subclassResponsibility

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

!

first

    "return the first element"

    ^ self at:1

    "

     args:    

     returns: firstElement <object>

    "

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

!

keyAtEqualValue:value

    "return the index of a value.

     This is normally not used (use indexOf:), but makes the

     protocol more compatible with dictionaries."

    ^ self indexOf:value

!

keyAtEqualValue:value ifAbsent:exceptionBlock

    "return the index of a value.

     This is normally not used (use indexOf:), but makes the

     protocol more compatible with dictionaries."

    ^ self indexOf:value ifAbsent:exceptionBlock

!

keyAtValue:value

    "return the index of a value.

     This is normally not used (use indexOf:), but makes the

     protocol more compatible with dictionaries."

    ^ self identityIndexOf:value

!

keyAtValue:value ifAbsent:exceptionBlock

    "return the index of a value.

     This is normally not used (use indexOf:), but makes the

     protocol more compatible with dictionaries."

    ^ self identityIndexOf:value ifAbsent:exceptionBlock

!

last

    "return the last element"

    |sz|

    (sz := self size) == 0 ifFalse:[

        ^ self at:sz

    ].

    "error if collection is empty"

    ^ self emptyCollectionError

!

swap:index1 with:index2

    "exchange two elements"

    |t|

    t := self at:index1.

    self at:index1 put:(self at:index2).

    self at:index2 put:t

    "Modified: 15.10.1997 / 19:27:08 / cg"

!

upTo:anElement

    "return a new collection consisting of the receivers elements upTo

     (but excluding) anElement.

     If anElement is not in the receiver, the returned collection

     will consist of all elements of the receiver"

    |pos|

    pos := self indexOf:anElement.

    pos == 0 ifTrue:[^ self copy].

    ^ self copyFrom:1 to:(pos - 1)

    "

     #(1 2 3 4 5 6 7 8 9) upTo:5  

     'hello world' upTo:Character space  

     #(9 8 7 6 5 4 3 2 1) asSortedCollection upTo:5 

     raises an error:

     (Dictionary new 

        at:#foo put:'foo';

        at:#bar put:'bar';

        at:#baz put:'baz';

        yourself) upTo:#bar

    "

    "Modified: 11.5.1996 / 11:14:05 / cg"

!

upTo:anElement count:count

    "return a new collection consisting of the receivers elements upTo

     (but excluding) count found anElements, i.e. the first found count-1 

     elements are included in the returned collection; if count < 0 the 

     procedure is done from the end of the collection backwards.

     If anElement is not in the receiver, the returned collection

     will consist of all elements of the receiver"

    |startPos endPos pos found|

    (count == 0 or: [count == 1]) ifTrue:[

        ^ self upTo:anElement

    ].

    startPos := 1.

    endPos   := self size.

    found    := 0.

    count > 1 ifTrue:[

        pos := 0.

        [pos < self size and: [found < count]]

            whileTrue: [pos := pos + 1. (self at: pos) == anElement ifTrue: [found := found + 1]].

        found == count ifTrue:[

            endPos   := pos - 1

        ]

    ].     

    count < 0 ifTrue:[

        pos := self size + 1.

        [pos > 1 and: [found < count abs]]

            whileTrue: [pos := pos - 1. (self at: pos) == anElement ifTrue: [found := found + 1]].

        found == count abs ifTrue:[

            startPos := pos + 1

        ]

    ].    

    ^ self copyFrom: startPos to: endPos

    "

     'hello1_hello2_hello3' upTo:$_ count:  2     returns first two 'hellos' 

     'hello1_hello2_hello3' upTo:$_ count: -1     returns last 'hello'

    "

! !

!SequenceableCollection methodsFor:'adding & removing'!

add:anObject

    "append the argument, anObject to the collection.

     Return the argument, anObject.

     Notice, that this is modifies the receiver NOT a copy.

     Also note, that it may be a slow operation for some collections,

     due to the grow:-message, which is inefficient for fixed size 

     collections (i.e. for Strings and Arrays it is not recommened)."

    |newSize|

    newSize := self size + 1.

    self grow:newSize.

    self at:newSize put:anObject.

    ^ anObject

    "

     |a|

     a := #(1 2 3 4 5 6 7 8).

     a add:'hello'.

     a

    "

    "

     |c|

     c := #(1 2 3 4 5 6 7 8) asOrderedCollection.

     c add:'hello'.

     c

    "

!

add:anElement beforeIndex:index

    "insert the first argument, anObject into the collection before slot index.

     Return the receiver (sigh - ST-80 compatibility).

     Notice, that this is modifies the receiver NOT a copy.

     Also note, that it may be a slow operation for some collections,

     due to the grow:-message, which is inefficient for fixed size 

     collections (i.e. for Strings and Arrays it is not recommened)."

    |newSize|

    newSize := self size + 1.

    self grow:newSize.

    self replaceFrom:index + 1 to:newSize with:self startingAt:index.

    self at:index put:anElement

    "

     #(1 2 3 4 5 6 7 8) add:'hello' beforeIndex:5

    "

!

addFirst:anObject

    "prepend the argument, anObject to the collection.

     Return the argument, anObject.

     Notice, that this is modifies the receiver NOT a copy.

     Also note, that it may be a slow operation for some collections,

     due to the grow:-message, which is inefficient for fixed size 

     collections (i.e. for Strings and Arrays it is not recommened)."

    |newSize|

    newSize := self size + 1.

    self grow:newSize.

    self replaceFrom:2 to:newSize with:self startingAt:1.

    self at:1 put:anObject.

    ^ anObject

    "

     |a| 

     a:= #(1 2 3 4 5 6 7 8). 

     a addFirst:'hello'. 

     a 

    "

    "

     |c|

     c := #(1 2 3 4 5 6 7 8) asOrderedCollection.

     c addFirst:'hello'.

     c

    "

!

remove:anElement ifAbsent:aBlock

    "search for an object which is equal to anElement;

     if found remove and return it; if not, return the value from evaluating aBlock.

     Use equality compare (=) to search for an occurrence.

     Notice, that this is modifies the receiver NOT a copy.

     Also note, that it may be a slow operation for some collections,

     due to the grow:-message, which is inefficient for fixed size 

     collections (i.e. for Strings and Arrays it is not recommened)."

    |any 

     dstIndex "{ Class: SmallInteger }"

     sz       "{ Class: SmallInteger }"|

    dstIndex := 1.

    any := false.

    sz := self size.

    1 to:sz do:[:srcIndex |

        (anElement = (self at:srcIndex)) ifTrue:[

            any := true

        ] ifFalse:[

            (dstIndex ~~ srcIndex) ifTrue:[

                self at:dstIndex put:(self at:srcIndex)

            ].

            dstIndex := dstIndex + 1

        ]

    ].

    any ifTrue:[

        self grow:dstIndex - 1.

        ^ anElement

    ].

    ^ aBlock value

    "

     #(1 2 3 4 5 6 7 8 9 0) remove:3 ifAbsent:[Transcript showCR:'no']

     #(1 2 3 4 5 6 7 8 9 0) remove:99 ifAbsent:[#oops]

     #(1.0 2.0 3.0 4.0 5.0) remove:5 ifAbsent:[#oops]

     #(1.0 2.0 3.0 4.0 5.0) removeIdentical:5 ifAbsent:[#oops]

    "

    "Modified: 1.2.1997 / 11:49:01 / cg"

!

removeAllSuchThat:aBlock

    "remove all elements that meet a test criteria as specified in aBlock.

     The argument, aBlock is evaluated for successive elements and all those,

     for which it returns true, are removed.

     Return a collection containing the removed elements."

    "/ this is a q&d implementation (possibly slow).

    |runIndex removed element|

    removed := self species new.

    runIndex := 1.

    [runIndex <= self size] whileTrue:[

        element := self at:runIndex.

        (aBlock value:element) ifTrue:[

            removed add:element.

            self removeAtIndex:runIndex

        ] ifFalse:[

            runIndex := runIndex + 1

        ]

    ].

    ^ removed

    "

     |coll|

     coll := OrderedCollection withAll:(1 to:10).

     Transcript showCR:(coll removeAllSuchThat:[:el | el even]).

     Transcript showCR:coll

    "

    "Created: 11.5.1996 / 09:49:30 / cg"

!

removeAtIndex:anIndex

    "remove the element stored at anIndex. Return the removed object.

     Notice, that this is modifies the receiver NOT a copy.

     Also note, that it may be a slow operation for some collections,

     due to the grow:-message, which is inefficient for fixed size 

     collections (i.e. for Strings and Arrays it is not recommened)."

    |element|

    element := self at:anIndex.

    self removeFromIndex:anIndex toIndex:anIndex.