"

 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.

"

!

version

    ^ '$Header: /cvs/stx/stx/libbasic/SequenceableCollection.st,v 1.40 1995-11-11 15:26:36 cg 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

!

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

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.

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

    "

!

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

!

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

! !

!SequenceableCollection methodsFor:'queries'!

isSequenceable

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

    ^ true

!

isSequenceableCollection

    "OBSOLETE: use isSequenceable for ST-80 compatibility.

     This method is a historic leftover and will be removed."

    ^ 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:'converting'!

asStringWithCRs

    "return a string generated by concatenating my elements 

     (which must be strings or nil) and embedding cr characters in between.

     Nil entries and empty strings are counted as empty lines."

    ^ self asStringWithCRsFrom:1 to:(self size)

!

asStringWithCRsFrom:firstLine to:lastLine

    "return a string generated by concatenating some of my elements 

     (which must be strings or nil) and embedding cr characters in between.

     Nil entries and empty strings are counted as empty lines."

    ^ self asStringWithCRsFrom:firstLine to:lastLine compressTabs:false withCR:true

!

asStringWithCRsFrom:firstLine to:lastLine compressTabs:compressTabs

    "return part of myself as a string with embedded cr's.

     My elements must be strings or nil.

     If the argument compressTabs is true, leading spaces are converted

     to tab-characters (8col tabs).

     Nil entries and empty strings are taken as empty lines."

    ^ self asStringWithCRsFrom:firstLine to:lastLine compressTabs:compressTabs withCR:true

!

asStringWithCRsFrom:firstLine to:lastLine compressTabs:compressTabs withCR:withCR

    "return part of myself as a string with embedded cr's.

     My elements must be strings or nil; nil entries and empty strings are

     taken as empty lines.

     If the argument compressTabs is true, leading spaces are converted

     to tab-characters (8col tabs). WithCR controls whether the last line

     should be followed by a cr or not."

    ^ self asStringWith:(Character cr)

		   from:firstLine 

		     to:lastLine 

	   compressTabs:compressTabs 

		  final:(withCR ifTrue:[Character cr] ifFalse:[nil])

!

asStringWith:sepCharacter from:firstLine to:lastLine compressTabs:compressTabs final:endCharacter

    "return part of myself as a string with embedded sepCharacters.

     My elements must be strings or nil; nil entries and empty strings are

     taken as empty lines.

     If the argument compressTabs is true, leading spaces are converted

     to tab-characters (8col tabs). The last line is followed by a final

     character (if non-nil).

     This method is tuned for big collections, in not creating many

     intermediate strings (has linear runtime). For very small collections

     and small strings, it may be faster to use the comma , operation."

    |idx1        "{ Class:SmallInteger }"

     idx2        "{ Class:SmallInteger }"

     totalLength "{ Class:SmallInteger }"

     pos         "{ Class:SmallInteger }"

     newString lineString spaces idx nTabs sepCnt|

    "

     first accumulate the size of the string, to avoid

     countless reallocations. If tabs are compressed,

     the size computed is not exact, but gives an upper bound ...

    "

    totalLength := 0.

    sepCnt := sepCharacter notNil ifTrue:[1] ifFalse:[0].

    idx1 := firstLine.

    idx2 := lastLine.

    idx1 to:idx2 do:[:lineIndex |

	lineString := self at:lineIndex.

	lineString isNil ifTrue:[

	    totalLength := totalLength + sepCnt

	] ifFalse: [

	    totalLength := totalLength + lineString size + sepCnt

	].

    ].

    endCharacter isNil ifTrue:[

	totalLength := totalLength - 1

    ].

    spaces := '        '.

    newString := String new:totalLength.

    "

     now, replace ...

    "

    pos := 1.

    idx1 to:idx2 do:[:lineIndex |

	|thisLen|

	lineString := self at:lineIndex.

	thisLen := lineString size.

	thisLen ~~ 0 ifTrue:[

	    compressTabs ifTrue:[

		"

		 mhmh: could use withTabs from String-class here,

		 but we should avoid creating too many temporary strings

		 (especially, since this method is typically used when converting

		 big texts such as when saving in the filebrowser ...).

		 Therefore, we convert tabs inline here doing a direct replace

		 in newString."

		idx := lineString findFirst:[:c | (c ~~ Character space)].

		nTabs := (idx-1) // 8.

		nTabs ~~ 0 ifTrue:[

		    "any tabs"

		    newString atAll:(pos to:pos+nTabs-1) put:(Character tab).

		    pos := pos + nTabs.

		    newString replaceFrom:pos with:lineString startingAt:(nTabs * 8 + 1).

		    pos := pos + thisLen - (nTabs * 8).

		] ifFalse:[

		    newString replaceFrom:pos with:lineString.

		    pos := pos + thisLen

		].

	    ] ifFalse:[

		newString replaceFrom:pos with:lineString.

		pos := pos + thisLen

	    ]

	].

	(sepCharacter notNil 

	and:[lineIndex ~~ lastLine]) ifTrue:[

	    newString at:pos put:sepCharacter.

	    pos := pos + 1

	] ifFalse:[

	    endCharacter notNil ifTrue:[

		newString at:pos put:endCharacter.

		pos := pos + 1

	    ]

	]

    ].

    "

     in case of tab compression, the result has to be

     cut to size ... sorry

    "

    pos ~~ totalLength ifTrue:[

	^ newString copyTo:(pos - 1)

    ].

    ^ newString

    "

     creating entries for searchpath:

     #('foo' 'bar' 'baz' '/foo/bar') 

	asStringWith:$: from:1 to:4 compressTabs:false final:nil 

     with trailing colon:

     #('foo' 'bar' 'baz' '/foo/bar') 

	asStringWith:$: from:1 to:4 compressTabs:false final:$: 

     concatenating all elements:

     #('foo' 'bar' 'baz') 

	asStringWith:nil from:1 to:3 compressTabs:false final:nil 

     creating a string from a collection of lines:

     #('foo' 'bar' 'baz') 

	asStringWith:(Character cr) from:1 to:3 compressTabs:false final:(Character cr) 

    "

!

decodeAsLiteralArray

    |cls|

    cls := Smalltalk at:(self first) ifAbsent:nil.

    cls isNil ifTrue:[

	^ self error:'unknown class in spec:' , self first.

    ].

    ^ cls new fromLiteralArrayEncoding:self.

    "

     #(Point 10 20) decodeAsLiteralArray  

     #(Rectangle 100 200 400 500) decodeAsLiteralArray 

    "

!

literalArrayEncoding

    ^ (self collect:[:el | el literalArrayEncoding]) asArray

    "

     (Array with:(Color red:50 green:50 blue:50)

	    with:(1 @ 2)

     ) literalArrayEncoding   

    "

! !

!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 isSequenceable) 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) bitAnd:16r3FFFFFFF

    "

     #(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 isSequenceable) 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 isSequenceable) 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