"

 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 comment:'

COPYRIGHT (c) 1989 by Claus Gittinger

              All Rights Reserved

'!

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

"

!

version

"

$Header: /cvs/stx/stx/libbasic/SequenceableCollection.st,v 1.12 1994-06-02 16:21:55 claus Exp $

"

!

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. See concrete subclasses (such as OrderedCollection).

"

! !

!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

! !

!SequenceableCollection methodsFor:'accessing'!

first

    "return the first element"

    ^ self at:1

!

last

    "return the last element"

    ^ self at:(self size)

!

at:index ifAbsent:exceptionBlock

    "return the element at index if valid. 

     If the index is invalid, return the result of evaluating 

     the exceptionblock."

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

        ^ exceptionBlock value

    ].

    ^ self at:index

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

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

                 with:(#frob -> #baz)) at:#foobar ifAbsent:['no such index']"

! !

!SequenceableCollection methodsFor:'queries'!

isSequenceableCollection

    "return true, if the receiver is some kind of sequenceableCollection"

    ^ true

!

firstIndex

    "return the first elements index"

    ^ 1

!

lastIndex

    "return the last elements index"

    ^ self size

!

size

    "return the number of elements in the collection.

     concrete implementations must define this"

    ^ self subclassResponsibility

!

keys

    "return a collection with all keys in the Smalltalk dictionary"

    |sz|

    sz := self size.

    sz == 0 ifTrue:[

        ^ #()

    ].

    ^ 1 to:sz

! !

!SequenceableCollection methodsFor:'comparing'!

= aCollection

    "return true if the receiver and aCollection represent collections

     with equal contents."

    |index "{ Class: SmallInteger }"

     stop  "{ Class: SmallInteger }" |

    (aCollection == self) ifTrue:[^true].

    (aCollection isSequenceableCollection) ifFalse:[^false].

    stop := self size.

    stop == (aCollection size) ifFalse:[^false].

    index := 1.

    [index <= stop] whileTrue:[

        (self at:index) = (aCollection at:index) ifFalse:[^false].

        index := index + 1

    ].

    ^ true

    "

     #(1 2 3 4 5) = #(1 2 3 4 5)                        

     #($1 $2 $3 $4 $5) = #(1 2 3 4 5)                   

     #($1 $2 $3 $4 $5) = '12345'                       

     #($1 $2 $3 $4 $5) = '54321' asSortedCollection   

    "

!

hash

    "return a hash key for the receiver"

    "this hash is stupid - but for larger collections, the hashing

     time can become much bigger than the time lost in added probing.

     Time will show ..."

    ^ (self at:1 ifAbsent:[0]) hash * self size

    "

     #(1 2 3 4 5) hash

     #(1 2 3 4 5.0) asOrderedCollection hash

    "

!

startsWith:aCollection

    "return true, if the receivers first elements match those

     of aCollection"

    |index "{ Class: SmallInteger }"

     stop  "{ Class: SmallInteger }" |

    (aCollection == self) ifTrue:[^true].

    (aCollection isSequenceableCollection) ifFalse:[^false].

    stop := aCollection size.

    stop > self size ifTrue:[^false].

    index := 1.

    [index <= stop] whileTrue:[

        (self at:index) = (aCollection at:index) ifFalse:[^false].

        index := index + 1

    ].

    ^ true

    "

     'abcde' startsWith:#($a $b $c)

     #[1 2 3 4] startsWith:#(1 2 3)

     #(1 2 3 4) asOrderedCollection startsWith:#(1 2 3)

    "

!

endsWith:aCollection

    "return true, if the receivers last elements match those

     of aCollection"

    |index1 "{ Class: SmallInteger }"

     index2 "{ Class: SmallInteger }" 

     stop   "{ Class: SmallInteger }" 

     sz     "{ Class: SmallInteger }"|

    (aCollection == self) ifTrue:[^ true].

    (aCollection isSequenceableCollection) ifFalse:[^ false].

    stop := aCollection size.

    sz := self size.

    stop > sz ifTrue:[^false].

    index1 := sz.

    index2 := stop.

    [index2 > 0] whileTrue:[

        (self at:index1) = (aCollection at:index2) ifFalse:[^ false].

        index1 := index1 - 1.

        index2 := index2 - 1

    ].

    ^ true

    "

     'abcde' endsWith:#($d $e)

     #[1 2 3 4] endsWith:#(3 4)    

     #(1 2 3 4) asOrderedCollection endsWith:#(3 4)

    "

! !

!SequenceableCollection methodsFor:'copying'!

, aCollection

    "return a new collection formed from concatenating the receiver with

     the argument. The class of the new collection is determined by the

     receivers class, so mixing classes is possible, if the second collections

     elements can be stored into instances of the receivers class."

    |newCollection 

     mySize    "{ Class: SmallInteger }"

     newSize   "{ Class: SmallInteger }"

     otherSize "{ Class: SmallInteger }"

     dstIndex  "{ Class: SmallInteger }"|

    mySize := self size.

    otherSize := aCollection size.

    newSize := mySize + otherSize.

    newCollection := self species new:newSize.

    newCollection replaceFrom:1 to:mySize with:self startingAt:1.

    dstIndex := mySize + 1.

    (aCollection isSequenceableCollection) ifTrue:[

        "yes, aCollection has indexed elements"

        newCollection replaceFrom:dstIndex to:newSize

                             with:aCollection startingAt:1.

        ^ newCollection

    ] ifFalse:[

        "no, enumerate aCollection"

        aCollection do:[:element |

            newCollection at:dstIndex put:element.

            dstIndex := dstIndex + 1

        ]

    ].

    ^ newCollection

    "#($a $b $c) , #(1 2 3)"

    "#($a $b $c) , '123'"

    "'abc' , '123'"

    "'abc' , #($q $w $e $r $t $y) asSortedCollection"

    "'abc' , #(1 2 3 4 5)"  "-- will fail, since strings cannot store integers"

    "'abc' asArray , #(1 2 3 4 5)"

!

copyWith:newElement

    "return a new collection consisting of a copy of the receivers elements

     plus the argument."

    |newCollection mySize newSize|

    mySize := self size.

    newSize := mySize + 1.

    newCollection := self species new:newSize.

    newCollection replaceFrom:1 to:mySize with:self startingAt:1.

    newCollection at:newSize put:newElement.

    ^newCollection

    "#(1 2 3 4 5) copyWith:$a"

    "'abcdefg' copyWith:$h"

    "'abcdefg' copyWith:'123'"  "-- will fail: string cannot be stored into string"

    "'abcdefg' copyWith:1"      "-- will fail: integer cannot be stored into string"

!

copyWithoutFirst:elementToSkip

    "return a new collection consisting of a copy of the receivers elements

     without the first elementToSkip, if it was present. 

     No error is reported, if elementToSkip is not in the collection."

    |copy skipIndex sz|

    skipIndex := self indexOf:elementToSkip startingAt:1.

    (skipIndex == 0) ifTrue:[^ self copy].

    sz := self size.

    copy := self class new:(sz - 1).

    copy replaceFrom:1 to:(skipIndex - 1) with:self startingAt:1.

    copy replaceFrom:skipIndex to:(sz - 1) with:self startingAt:(skipIndex + 1).

    ^ copy

    "#($a $b $c $d $e $f $g) copyWithoutFirst:$d"

    "#($a $b $c $d $e $f $g) copyWithoutFirst:$x"

    "#(90 80 70 60 50) copyWithoutFirst:70"

    "#(90 80 70 80 60 45 80 50) copyWithoutFirst:80"

!

copyWithout:elementToSkip

    "return a new collection consisting of a copy of the receiver, with

     ALL elements equal to elementToSkip are left out.

     No error is reported, if elementToSkip is not in the collection."

    |n copy srcIndex dstIndex skipIndex sz l|

    "the code below may look like overkill, 

     however, for big collections its better to move data

     around in big chunks"

    n := self occurrencesOf:elementToSkip.

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

    sz := self size.

    copy := self species new:(sz - n).

    srcIndex := 1.

    dstIndex := 1.

    n timesRepeat:[

        skipIndex := self indexOf:elementToSkip startingAt:srcIndex.

        l := skipIndex - srcIndex.

        l ~~ 0 ifTrue:[

            copy replaceFrom:dstIndex to:(dstIndex + l - 1) 

                        with:self startingAt:srcIndex.

            dstIndex := dstIndex + l

        ].

        srcIndex := skipIndex + 1

    ].

    l := sz - srcIndex.

    copy replaceFrom:dstIndex to:(dstIndex + l)

                with:self startingAt:srcIndex.

    ^ copy

    "#($a $b $c $d $e $f $g) copyWithout:$d"

    "#($a $b $c $d $e $f $g) copyWithout:$a"

    "#($a $b $c $d $e $f $g) copyWithout:$g"

    "#($a $b $c $a $a $d $e $a $f $g) copyWithout:$a"

    "#($a $b $c $d $e $f $g) copyWithout:$x"

    "#(90 80 70 60 50) copyWithout:70"

    "#(90 80 70 80 60 45 80 50) copyWithout:80"

!

copyWithoutIndex:omitIndex

    "return a new collection consisting of receivers elements

     without the argument stored at omitIndex"

    |copy sz|

    sz := self size.

    copy := self species new:(sz - 1).

    copy replaceFrom:1 

                  to:(omitIndex - 1) 

                with:self 

          startingAt:1.

    copy replaceFrom:omitIndex 

                  to:sz - 1 

                with:self 

          startingAt:(omitIndex + 1).

    ^ copy

    "#(1 2 3 4 5 6 7 8 9 0) copyWithoutIndex:3"

    "'abcdefghijkl' copyWithoutIndex:5"

!

copyFrom:start to:stop

    "return a new collection consisting of receivers elements

     between start and stop"

    |newCollection newSize|

    newSize := stop - start + 1.

    newCollection := self species new:newSize.

    newCollection replaceFrom:1 to:newSize with:self startingAt:start.

    ^ newCollection

    "#($a $b $c $d $e $f $g) copyFrom:2 to:5"

    "'1234567890' copyFrom:2 to:5"

!

copyFrom:start

    "return a new collection consisting of receivers elements

     from start to the end of the collection"

    ^ self copyFrom:start to:(self size)

    "#($a $b $c $d $e $f $g) copyFrom:2"

    "'1234567890' copyFrom:2"

!

copyTo:stop

    "return a new collection consisting of receivers elements

     from 1 up to (including) index stop"

    ^ self copyFrom:1 to:stop

    "#($a $b $c $d $e $f $g) copyTo:5"

    "'1234567890' copyTo:4"

!

copyFirst:count

    "return a new collection consisting of the receivers first count

     elements - this is just a rename of copyTo: - for compatibility."

    ^ self copyFrom:1 to:count

    "#($a $b $c $d $e $f $g) copyFirst:5"

    "'1234567890' copyFirst:4"

!

copyLast:count

    "return a new collection consisting of the receivers last count

     elements."

    |sz|

    sz := self size.

    ^ self copyFrom:(sz - count + 1) to:sz

    "#($a $b $c $d $e $f $g) copyLast:5"

    "'1234567890' copyLast:4"

!

copyUpTo:element

    "return a new collection consisting of the receiver elements

     up-to (but excluding) the first occurence of element."

    |idx|

    idx := self indexOf:element.

    idx == 0 ifTrue:[^ nil].    "question: is this ok?"

    idx == 1 ifTrue:[^ self species new].

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

    "#($a $b $c $d $e $f $g) copyUpTo:$d"

    "'1234567890' copyUpTo:$5"

    "'1234567890' copyUpTo:$a"

    "'1234567890' copyUpTo:$1"

!

copyThrough:element

    "return a new collection consisting of the receiver elements

     up-to (AND including) the first occurence of element."

    |idx|

    idx := self indexOf:element.

    idx == 0 ifTrue:[^ nil].    "question: is this ok?"

    ^ self copyFrom:1 to:idx

    "#($a $b $c $d $e $f $g) copyThrough:$d"

    "'1234567890' copyThrough:$5"

    "'1234567890' copyThrough:$a"

    "'1234567890' copyThrough:$1"

!

copyReplaceFrom:startIndex to:endIndex with:aCollection

    "return a copy of the receiver, where the elements from startIndex to

     endIndex have been replaced by the elements of aCollection"

    |newColl replSize|

    replSize := aCollection size.

    newColl := self species new:(self size - (endIndex - startIndex + 1) + replSize).

    newColl replaceFrom:1 to:(startIndex - 1) with:self.

    newColl replaceFrom:startIndex with:aCollection.

    newColl replaceFrom:(startIndex + replSize) with:self startingAt:(endIndex + 1).

    ^ newColl

    "#(1 2 3 4 5 6 7 8 9 0) copyReplaceFrom:3 to:6 with:#(a b c d e f g h i j k)"

    "'hello world' copyReplaceFrom:6 to:6 with:' there, '"

!

copyReplaceAll:startIndex to:endIndex with:aCollection

    "return a copy of the receiver, where the elements from startIndex to

     endIndex have been replaced by the elements of aCollection"