"

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

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

    "

!

first

    "return the first element"

    ^ self at:1

!

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"

    ^ self at:(self size)

! !

!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 anElement and, if present remove and return it.

     If not present, return the value of evaluating aBlock.

     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]

    "

!

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.

    ^ element

    "

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

     #(1 2 3 4 5) asOrderedCollection removeAtIndex:6

     #($a $b $c $d $e $f $g) removeAtIndex:3

    "

!

removeFirst

    "remove the first element of the receiver and return it.

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

    ^ self removeAtIndex:1

    "

     |a|

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

     a removeFirst.

     a 

    "

!

removeFromIndex:startIndex toIndex:endIndex

    "remove the elements stored at indexes between startIndex and endIndex.

     Return the receiver.

     Returning the receiver is a historic leftover - it may at one

     time return a collection of the removed elements.

     Notice, that this is modifies the receiver - NOT a copy; 

     therefore any other users of the receiver will also see this change.

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

    |size newSize|

    (endIndex >= (size := self size)) ifTrue:[

	self grow:(startIndex - 1)

    ] ifFalse:[

	newSize := size - endIndex + startIndex - 1.

	self replaceFrom:startIndex to:newSize with:self startingAt:(endIndex + 1).

	self grow:newSize

    ]

"/    |newSize|

"/

"/    newSize := self size - endIndex + startIndex - 1.

"/    newSize <= 0 ifTrue:[

"/        self grow:0

"/    ] ifFalse:[

"/        self replaceFrom:startIndex to:newSize with:self startingAt:(endIndex + 1).

"/        self grow:newSize

"/    ]

    "

     #(1 2 3 4 5 6 7 8 9 0) asOrderedCollection removeFromIndex:3 toIndex:5 

     #(1 2 3 4 5 6 7 8 9 0) removeFromIndex:3 toIndex:5 

     #(1 2 3 4 5 6 7 8 9 0) asOrderedCollection removeFromIndex:1 toIndex:10 

     #(1 2 3 4 5 6 7 8 9 0) removeFromIndex:1 toIndex:10 

    "

!

removeIndex:index

    "remove the argument stored at index. Return the receiver.

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

    self removeFromIndex:index toIndex:index

    "

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

     #(1 2 3 4 5) asOrderedCollection removeIndex:6

     #($a $b $c $d $e $f $g) removeIndex:3

    "

!

removeLast

    "remove the last element of the receiver and return it.

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

    ^ self removeAtIndex:(self size) 

    "

     |a|

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

     a removeLast.

     a   

    "

! !

!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   

    "

!

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)

    "

!

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)

    "

! !

!SequenceableCollection methodsFor:'converting'!

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