! ========================================================================
! Copyright (C) by VMware, Inc. 1991-2011.  All Rights Reserved
!
! $Id: sequenc.gs,v 1.10.2.1 2008-01-30 22:09:07 bille Exp $
!
! ========================================================================

removeallmethods SequenceableCollection
removeallclassmethods SequenceableCollection

! ------------------- Class methods for SequenceableCollection
category: 'For Documentation Installation only'
classmethod: SequenceableCollection
installDocumentation

| doc txt |
doc := GsClassDocumentation newForClass: self.

txt := (GsDocText new) details:
'SequenceableCollection is an abstract superclass for collections that define a
 consistent ordering on their elements.  You can think of the elements as
 forming a sequence of objects, numbered from 1 to n.  You can use the Integer i
 as an index to refer to the ith element in that sequence.  The elements are
 said to be indexable.

 The indexability of SequenceableCollections should not be confused with indexes
 that are specially built on UnorderedCollections to improve their performance
 when they search their elements (using associative access).' .
doc documentClassWith: txt.

txt := (GsDocText new) details:
'Methods in the Adding category modify their receivers.  They generally execute
 faster than methods in the Concatenating category, which do not modify their
 receivers.  Please see that category for more comparative information.' .
doc documentCategory: #Adding with: txt.

txt := (GsDocText new) details:
'Methods in this category are obsolete and are provided only for compatibility
 with earlier releases of GemStone.  They will be removed in a future release.'.
doc documentCategory: #'Backward Compatibility' with: txt.

txt := (GsDocText new) details:
'Methods in the Concatenating category do not modify their receivers.  They copy
 their receivers and then apply the concatenation to the copy.  Thus, they
 generally execute slower than methods in the Adding category, which do modify
 their receivers.

 Consider the following code example involving Strings:

    | n result |
    n := 1000.
    result := String new.
    n timesRepeat: [result := result , $x.].
    ^ result

 Each time through the loop, this code first generates a new instance of String,
 a copy of the previous result, to which it then adds one Character.  In n times
 through the loop then, n * (n - 1) / 2 Characters are copied, and n Characters
 are added.  Thus, the time complexity to execute such a loop is proportional to
 n * (n + 1) / 2.  Space and garbage collection overhead can be expensive, too.

 The following code example executes in time that is proportional to n, without
 any of the space and garbage collection overhead of the previous example:

    | n result |
    n := 1000.
    result := String new.
    n timesRepeat: [ result add: $x].
    ^ result

 The result is the same in both examples.' .
doc documentCategory: #Concatenating with: txt.

self description: doc.
%

category: 'Instance Creation'
classmethod: SequenceableCollection
with: aValue

"(R) Returns an instance of the receiver containing the argument."

"Reimplemented to take advantage of the new: optimization "

| inst |
inst := self new: 1.
inst at: 1 put: aValue.
^inst
%

category: 'Instance Creation'
classmethod: SequenceableCollection
with: aValue with: val2

"(R) Returns an instance of the receiver containing the arguments."

"Reimplemented to take advantage of the new: optimization "

| inst |

inst := self new: 2.
inst at: 1 put: aValue;
     at: 2 put: val2.

^inst
%

category: 'Instance Creation'
classmethod: SequenceableCollection
with: aValue with: val2 with: val3

"(R) Returns an instance of the receiver containing the arguments."

"Reimplemented to take advantage of the new: optimization "

| inst |

inst := self new: 3.
inst at: 1 put: aValue;
     at:2 put: val2;
     at:3 put: val3.

^inst
%

category: 'Instance Creation'
classmethod: SequenceableCollection
with: aValue with: val2 with: val3 with: val4

"(R) Returns an instance of the receiver containing the arguments."

"Reimplemented to take advantage of the new: optimization "

| inst |

inst := self new: 4.
inst at: 1 put: aValue;
     at:2 put: val2;
     at:3 put: val3;
     at:4 put: val4.

^inst
%

! ------------------- Instance methods for SequenceableCollection

category: 'Backward Compatibility'
method: SequenceableCollection
+ aSequenceableCollection

"Obsolete in GemStone 5.0.  Use the , method instead."

^ self , aSequenceableCollection
%

category: 'Concatenating'
method: SequenceableCollection
, aSequenceableCollection

"Returns a new instance of the receiver's class that contains the elements of
 the receiver followed by the elements of aSequenceableCollection.

 Warning: Creating a new instance and copying the receiver take time.  If you
 can safely modify the receiver, it can be much faster to use the addAll:
 method.  See the documentation of the Concatenating category for more details."

| newCollection |

newCollection := self copy.

1 to: aSequenceableCollection size do: [ :i |
  newCollection addLast: (aSequenceableCollection at: i).
  ].

^ newCollection
%

category: 'Comparing'
method: SequenceableCollection
= aSequenceableCollection

"Returns true if all of the following conditions are true:

 1.  The receiver and aSequenceableCollection are of the same class.
 2.  The two collections are the same size.
 3.  The corresponding elements of the receiver and aSequenceableCollection
     are equal."

"Note: In GemStone 4.1, this method returned true only if the corresponding 
 elements of the receiver and the argument were identical (in addition to the
 two collections being of the same class and size)."

| selfSize |

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

(self class == aSequenceableCollection class)
  ifFalse: [ ^ false ].

selfSize := self size.
(selfSize == aSequenceableCollection size)
  ifFalse: [ ^ false ].

1 to: selfSize do: [ :i|
  ((self at: i) = (aSequenceableCollection at: i))
    ifFalse: [ ^ false ].
  ].

^ true.
%

category: 'Comparing'
method: SequenceableCollection
hasIdenticalContents: aSequenceableCollection

"Returns true if all of the following conditions are true:

 1.  The receiver and aSequenceableCollection are of the same class.
 2.  The two collections are the same size.
 3.  The corresponding elements of the receiver and aSequenceableCollection
     are identical."

"Note: This provides the behavior of SequenceableCollection>>= in GemStone 4.1."

| selfSize |

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

(self class == aSequenceableCollection class)
  ifFalse: [ ^ false ].

selfSize := self size.
(selfSize == aSequenceableCollection size)
  ifFalse: [ ^ false ].

1 to: selfSize do: [ :i|
  ((self at: i) == (aSequenceableCollection at: i))
    ifFalse: [ ^ false ].
  ].

^ true.
%

category: 'Adding'
method: SequenceableCollection
add: newObject

"Makes newObject one of the receiver's elements and returns newObject. The 
 new element is actually added as the last element of the receiver. This 
 method is therefore equivalent to #addLast:."

"Note: In GemStone 4.1, this method returned the receiver."

^ self at: ((self size) + 1) put: newObject.
%

category: 'Adding'
method: SequenceableCollection
add: newObject before: target

"Adds newObject to the receiver immediately before the first element that is
 equal to target.  An object immediately precedes another if its index is one
 less than that of the other.  Returns newObject if the operation is successful.
 Raises an error if the operation fails."

| index |

index := self indexOf: target.
(index == 0) ifTrue: [ self _error: #rtErrObjNotFound args: #[ target ]].
^ self insertAll: #[ newObject ] at: index.
%

category: 'Adding'
method: SequenceableCollection
add: newObject after: target

"Adds newObject to the receiver immediately after the first element that is
 equal to target.  An object immediately follows another if its index is one
 greater than that of the other.  Returns newObject if the operation is
 successful.  Raises an error if the operation fails."

| index |

index := self indexOf: target.
(index == 0) ifTrue: [ self _error: #rtErrObjNotFound args: #[ target ]].
^ self insertAll: #[ newObject ] at: (index + 1).
%

category: 'Adding'
method: SequenceableCollection
addAll: aCollection before: target

"Adds all the elements of aCollection to the receiver immediately before the
 first element that is equal to target.  An object immediately precedes another
 if its index is one less than that of the other.  Returns aCollection if the
 operation is successful.  Raises an error if the operation fails."

| index |

index := self indexOf: target.
(index == 0) ifTrue: [ self _error: #rtErrObjNotFound args: #[ target ]].
^ self insertAll: aCollection at: index.
%

category: 'Adding'
method: SequenceableCollection
addAll: aCollection afterIndex: index

"Adds all the elements of aCollection to the receiver in the traversal order
 defined by the do: method for aCollection.  Inserts the new elements into the
 receiver immediately after the element in the receiver at position index.  If
 index is equal to zero, inserts the elements of aCollection at the beginning of
 the receiver.  Returns aCollection.

 The argument index must be a non-negative integer less than or equal to the 
 receiver's size."

^ self insertAll: aCollection at: (index + 1).
%

category: 'Adding'
method: SequenceableCollection
addAll: aCollection beforeIndex: index

"Adds all the elements of aCollection to the receiver in the traversal order
 defined by the do: method for aCollection.  Inserts the new elements into the
 receiver immediately before the element in the receiver at position index.  If
 index is equal to the receiver's size plus one, inserts the elements of
 aCollection at the end of the receiver.  Returns aCollection.

 The argument index must be a positive integer less than or equal to the 
 receiver's size plus one."

^ self insertAll: aCollection at: (index).
%

category: 'Adding'
method: SequenceableCollection
addLast: newObject

"Adds newObject as the last element of the receiver and returns newObject."

"Note: In GemStone 4.1, this method returned the receiver."

^ self at: ((self size) + 1) put: newObject.
%

category: 'Accessing'
method: SequenceableCollection
after: anObject

"Returns the object immediately following the first object which is equal to 
 anObject in the receiver."

| index |

index := self indexOf: anObject 
             ifAbsent: [^ self _errorNotFound: anObject].

(index == (self size))
  ifTrue: [
    "This is the last element. There cannot be anything after it."
    ^ self _errorNotFound: anObject.
    ].

^ self at: (index + 1).
%

category: 'Comparing'
method: SequenceableCollection
at: anIndex equals: aSequenceableCollection

"Returns true if aSequenceableCollection is contained in the receiver starting
 at index anIndex. Returns false otherwise."

| seqCollSize index |
seqCollSize := aSequenceableCollection size.

((anIndex + seqCollSize - 1) > (self size))
  ifTrue: [ ^ false ].

index := anIndex.
1 to: seqCollSize do: [ :j|
  ((self at: index) = (aSequenceableCollection at: j))
    ifFalse: [ ^ false ].
  index := index + 1.
  ].

^ true.
%

category: 'Updating'
method: SequenceableCollection
atAll: aCollection put: anObject

"The argument aCollection is a collection of Integers that are used as indexes
 into the receiver.  At each element in the receiver for which its index is in
 aCollection, this method replaces the element with the argument anObject.
 Returns anObject."

aCollection do: [ :index | self at: index put: anObject].
^ anObject.
%

category: 'Updating'
method: SequenceableCollection
atAllPut: anObject

"Assigns anObject to each of the receiver's elements and returns anObject."

1 to: self size do: [ :index | self at: index put: anObject].
^ anObject.
%

category: 'Accessing'
method: SequenceableCollection
before: anObject

"Returns the object immediately before the first object which is equal to 
 anObject in the receiver."

| index |

index := self indexOf: anObject 
             ifAbsent: [^ self _errorNotFound: anObject].

(index == 1)
  ifTrue: [
    "This is the first element. There cannot be anything before it."
    ^ self _errorNotFound: anObject.
    ].

^ self at: (index - 1).
%

category: 'Enumerating'
method: SequenceableCollection
collect: aBlock

"(R) Evaluates aBlock with each of the receiver's elements as the argument.
 Collects the resulting values into a collection of class specified by 
 sending #speciesForCollect message to the receiver. Returns the new 
 collection. The argument aBlock must be a one-argument block.

 The result preserves the ordering of the receiver.  That is, if element a 
 comes before element b in the receiver, then element a is guaranteed to come 
 before b in the result."

|result mySize|

mySize := self size.
result:= self speciesForCollect new: mySize .
1 to: mySize do: [:i| result at:i put:(aBlock value: (self at:i))] .
^result
%

category: 'Copying'
method: SequenceableCollection
copyEmpty

"Returns an empty copy of the receiver."

^self species new
%

! fixed bug 35799
category: 'Copying'
method: SequenceableCollection
copyFrom: startIndex to: stopIndex

"Returns a new SequenceableCollection containing the elements of the receiver
 between startIndex and stopIndex, inclusive.  The result is of the same class
 as the receiver.

 Both startIndex and stopIndex must be positive integers not larger than the
 size of the receiver, with startIndex <= stopIndex.
 If startIndex > stopIndex and both are positive, an empty collection is returned.
 "

| result |
(startIndex > stopIndex) ifTrue: [ 
  stopIndex < 0 ifTrue:[ self _error: #rtErrBadCopyFromTo args: #[stopIndex] ].
  ^ self class new 
].
(startIndex < 1)
   ifTrue: [ ^ self _errorIndexOutOfRange: startIndex].

((stopIndex > self size) _or: [(stopIndex < 0)])
   ifTrue: [ ^ self _errorIndexOutOfRange: stopIndex].

result := (self class new: (stopIndex - startIndex + 1)).
self copyFrom: startIndex to: stopIndex into: result startingAt: 1.
^ result
%

category: 'Copying'
method: SequenceableCollection
copyFrom: index1 to: index2 into: aSeqCollection startingAt: destIndex

"Copies the elements of the receiver between index1 and index2, inclusive,
 into aSeqCollection starting at destIndex, overwriting the previous
 contents.  If aSeqCollection is the same object as the receiver, the
 source and destination blocks may overlap. Returns the receiver."

"Implementation uses _basicAt:put: so that inheritance by
 things like SortedCollection will work."

| i |

(index1 > index2)
  ifTrue: [ ^ index1 _error: #rtErrBadCopyFromTo args: #[index2]].

(index1 < 1)
  ifTrue: [ ^ self _errorIndexOutOfRange: index1].

(index2 > self size)
  ifTrue: [ ^ self _errorIndexOutOfRange: index2].

((destIndex < 1) _or: [(destIndex > (aSeqCollection size + 1))])
   ifTrue: [ ^ aSeqCollection _errorIndexOutOfRange: destIndex].

((self == aSeqCollection) & (destIndex >= index1) & (destIndex <= index2))
  ifTrue: [
    "extend size of collection first if needed and copy from back to front "
    ((destIndex + index2 - index1) > aSeqCollection size) 
      ifTrue: [ aSeqCollection size: (destIndex + index2 - index1) ].

    i := destIndex + (index2 - index1).
    index2 downTo: index1 do: [ :j |
      self _basicAt: i put: (self at: j).
      i := i - 1.
      ].
    ]
  ifFalse: [
    i := destIndex.
    index1 to: index2 do: [ :j |
      aSeqCollection _basicAt: i put: (self at: j).
      i := i + 1.
      ].
  ].

^ self.
%

category: 'Copying' 
method: SequenceableCollection
copyFrom: index1 count: aCount into: aColl startingAt: destIndex

"Copies elements of the receiver from (receiver at: index1)
  to (receiver at: (index2 + aCount - 1)), inclusive 
 into aColl starting at destIndex, overwriting the previous contents.

 If (index2 + aCount - 1) is beyond the end of the receiver, then 
 the copy will stop with the element  (receiver at: (receiver size)) .

 aColl must be a kind of SequenceableCollection .

 Returns the number of elements copied."
    
| numToCopy endIdx limit |
numToCopy := aCount .
endIdx := index1 + numToCopy - 1 .
limit := self size .
endIdx > limit ifTrue:[
  endIdx := limit .
  numToCopy := endIdx - index1 + 1 .
].
self copyFrom: index1 to: endIdx into: aColl startingAt: destIndex .
^ numToCopy
%


category: 'Copying'
method: SequenceableCollection
copyReplaceAll: oldSubCollection with: newSubCollection

"Returns a modified copy of the receiver in which all sequences of elements
 within the receiver that match the elements of oldSubCollection are replaced
 by the elements of newSubCollection."

| selfSize newSubCollSize oldSubCollSize result sourceIndex targetIndex 
  subIndex |

selfSize := self size.
newSubCollSize := newSubCollection size.
oldSubCollSize := oldSubCollection size.

result := self species new.

sourceIndex := 1.
targetIndex := 1.

[ sourceIndex <= selfSize ] whileTrue: [
  subIndex := self indexOfSubCollection: oldSubCollection 
              startingAt: sourceIndex 
              ifAbsent: [
                self copyFrom: sourceIndex 
                           to: selfSize 
                         into: result 
                   startingAt: targetIndex.
                ^ result.
                ].

  (subIndex > sourceIndex)
    ifTrue: [
      self copyFrom: sourceIndex
                 to: (subIndex - 1) 
               into: result 
         startingAt: targetIndex.

      targetIndex := targetIndex + (subIndex - sourceIndex).
      ].

  (newSubCollSize > 0)
    ifTrue: [
      newSubCollection copyFrom: 1
                             to: newSubCollSize
                           into: result
                     startingAt: targetIndex.
      ].


  targetIndex := targetIndex + newSubCollSize.
  sourceIndex := subIndex + oldSubCollSize.
  ].

^ result.
%

category: 'Copying'
method: SequenceableCollection
copyReplaceFrom: startIndex to: stopIndex with: aSequenceableCollection

    "Returns a copy of the receiver in which all elements in the
    receiver between indexes startIndex and stopIndex inclusive have
    been replaced by those contained in aSequenceableCollection."

    | selfSize seqCollSize targetIndex result |
    startIndex > stopIndex ifTrue: 
        [^startIndex _error: #rtErrBadCopyFromTo args: #[stopIndex]].

    seqCollSize := aSequenceableCollection size.
    seqCollSize == 0 ifTrue: 
        [^self copy].

    result := self species new.
    targetIndex := 1.

    startIndex > 1 ifTrue: 
        [self 
             copyFrom: 1
             to: startIndex - 1
             into: result
             startingAt: targetIndex.
         targetIndex := targetIndex + startIndex - 1].

    aSequenceableCollection
        copyFrom: 1
        to: seqCollSize
        into: result
        startingAt: targetIndex.

    targetIndex := targetIndex + seqCollSize.

    selfSize := self size.
    stopIndex < selfSize ifTrue:
        [self
             copyFrom: stopIndex + 1
             to: selfSize
             into: result
             startingAt: targetIndex].

    ^result
%

category: 'Copying'
method: SequenceableCollection
copyReplaceFrom: startIndex to: stopIndex withObject: anObject

"Returns a copy of the receiver in which all elements in the receiver between
 indexes startIndex and stopIndex inclusive have been replaced by anObject." 

| targetIndex result |

(startIndex > stopIndex) 
  ifTrue: [ ^ startIndex _error: #rtErrBadCopyFromTo args: #[stopIndex]].

result := self species new.
targetIndex := 1.

(startIndex > 1) 
  ifTrue: [
    self copyFrom: 1
               to: (startIndex - 1)
             into: result
       startingAt: targetIndex.
    
    targetIndex := targetIndex + startIndex - 1.
    ].

result at: targetIndex put: anObject.
targetIndex := targetIndex + 1.

self copyFrom: (stopIndex + 1)
               to: (self size)
             into: result
       startingAt: targetIndex.

^ result.
%

category: 'Copying'
method: SequenceableCollection
copyReplacing: oldObject with: newObject

"Returns a copy of the receiver in which all occurrences of objects equal to
 oldObject have been replaced by newObject."

| result | 

result := self copy.
1 to: result size do: [ :i |
  (oldObject = (result at: i))
    ifTrue: [ result at: i put: newObject ]
  ].

^ result.
%

category: 'Copying'
method: SequenceableCollection
copyWith: anObject

"Returns a copy of the receiver with anObject appended at the end."

| newCollection |

newCollection := self copy.
newCollection addLast: anObject.

^ newCollection.
%

category: 'Copying'
method: SequenceableCollection
copyWithout: anObject

"Returns a copy of the receiver that does not contain the given object.
 Comparisons are by equality."

"Note: In GemStone 4.1, the comparisons were by identity."

| copy element sz |

copy := self class new.

sz := 0.
1 to: self size do: [:i |
  element := self at: i.
  (element = anObject) 
    ifFalse: [
      sz := sz + 1.
      copy at: sz put: element.
      ]
  ].

^copy
%

category: 'Backward Compatibility'
method: SequenceableCollection
deleteFrom: startIndex to: stopIndex

"Obsolete in GemStone 5.0.  Use the removeFrom:to: method instead."

^ self removeFrom: startIndex to: stopIndex.
%

category: 'Backward Compatibility'
method: SequenceableCollection
deleteObjectAt: anIndex

"Obsolete in GemStone 5.0.  Use the removeAtIndex: method instead."

^ self removeAtIndex: anIndex
%

category: 'Enumerating'
method: SequenceableCollection
detect: aBlock ifNone: exceptionBlock

"(R) Evaluates aBlock repeatedly, with elements of the receiver as the argument.
 Returns the first element for which aBlock evaluates to true.  If none of
 the receiver's elements evaluates to true, this evaluates the argument
 exceptionBlock and returns its value.  The argument aBlock must be a
 one-argument block, and exceptionBlock must be a zero-argument block."

1 to: self size do: [ :i| (aBlock value: (self at: i)) ifTrue: [^self at: i]]. 
^exceptionBlock value
%

category: 'Enumerating'
method: SequenceableCollection
doWithIndex: aBlock

"Evaluates the two argument block aBlock using each element of the receiver as 
 the first argument and the corresponding index as the second argument. Returns
 the receiver."

1 to: self size do: [ :i |
  aBlock value: (self at: i) value: i.
  ].

^ self.
%

category: 'Backward Compatibility'
method: SequenceableCollection
eq: aSequenceableCollection

"Obsolete in GemStone 5.0.  Use the = method instead."

^ self = aSequenceableCollection.
%

category: 'Searching'
method: SequenceableCollection
findFirst: aBlock

"Returns the index of the first element in the receiver which causes the one
 argument block, aBlock, to evaluate true. Returns 0 if no element in the 
 receiver causes the block to evaluate true."

1 to: self size do: [:i|
  (aBlock value: (self at: i)) ifTrue: [^i]].

^0
%

category: 'Searching'
method: SequenceableCollection
findLast: aBlock

"Returns the index of the last element in the receiver which causes the one
 argument block, aBlock, to evaluate true. Returns 0 if no element in the 
 receiver causes the block to evaluate true."

self size downTo: 1 do: [:i|
  (aBlock value: (self at: i)) ifTrue: [^i]].

^0
%

category: 'Accessing'
method: SequenceableCollection
first

"Returns the first element of the receiver.  Generates an error if the receiver
 is empty."

(self size == 0)
ifTrue: "attempt to access an empty Collection"
   [ ^ self _error: #objErrCollectionEmpty].
^ self at: 1
%

category: 'Updating'
method: SequenceableCollection
first: anObject

"Stores the given object in the first position in the receiver and returns
 anObject."

"Note: In GemStone 4.1 and earlier versions, this method returned the receiver."

^ self at: 1 put: anObject.
%

category: 'Enumerating'
method: SequenceableCollection
from: startIndex to: stopIndex do: aBlock

"Evaluates the one argument block aBlock using each element of the receiver 
 starting at startIndex and ending at stopIndex. Returns the receiver."

((startIndex < 1) | (stopIndex > self size))
   ifTrue: [ ^ self _errorIndexOutOfRange: startIndex ].

startIndex to: stopIndex do: [ :i|
  aBlock value: (self at: i).
  ].

^ self.
%

category: 'Enumerating'
method: SequenceableCollection
from: startIndex to: stopIndex doWithIndex: aBlock

"Evaluates the two argument block aBlock using each element of the receiver 
 starting at startIndex and ending at stopIndex as the first argument and the
 corresponding index as the second argument. Returns the receiver."

((startIndex < 1) | (stopIndex > self size))
   ifTrue: [ ^ self _errorIndexOutOfRange: startIndex ].

startIndex to: stopIndex do: [ :i|
  aBlock value: (self at: i) value: i.
  ].

^ self.
%

category: 'Comparing'
method: SequenceableCollection
hash

"Returns a numeric hash key for the receiver."

| mySize interval hashValue |

(mySize := self size) == 0
  ifTrue: [ ^15243 ].

"Choose an interval so that we sample at most 5 elements of the receiver"
interval := ((mySize - 1) // 4) max: 1.

hashValue := 4459.
1 to: mySize by: interval do: [ :i | | anElement |
  anElement := self at: i.
  (anElement isKindOf: SequenceableCollection)
    ifTrue: [
      hashValue := (hashValue bitShift: -1) bitXor: anElement size.
      ]
    ifFalse: [
      hashValue := (hashValue bitShift: -1) bitXor: anElement hash.
      ].
  ].

^ hashValue abs
%

category: 'Searching'
method: SequenceableCollection
indexOf: anObject

"Returns the index of the first element in the receiver that is equivalent to 
 the argument. If the receiver does not have any elements equivalent to the
 argument, returns, zero."

"Note: In GemStone 4.1, this method checked for an element that was identical to
 the argument. For similar behavior, use #indexOfIdentical:"

^ self indexOf: anObject ifAbsent: [ 0 ].
%

category: 'Searching'
method: SequenceableCollection
indexOfIdentical: anObject

"Returns the index of the first element in the receiver that is identical to 
 the argument. If the receiver does not have any elements identical to the
 argument, returns, zero."

^ self _indexOfIdentical: anObject.
%

category: 'Searching'
method: SequenceableCollection
indexOf: anObject ifAbsent: anExceptionBlock

"Returns the index of the first element in the receiver that is equivalent to 
 the argument. If the receiver does not have any elements equivalent to the
 argument, returns the value of evaluating anExceptionBlock."

1 to: self size do: [:i |
  (anObject = (self at: i)) ifTrue: [^i]
  ].

^ anExceptionBlock value.
%

category: 'Searching'
method: SequenceableCollection
includesIdentical: anObject

"(R) Returns true if anObject is identical to one of the elements of the
 receiver.  Returns false otherwise."

^ (self _indexOfIdentical: anObject) > 0
%

category: 'Searching'
method: SequenceableCollection
_indexOfIdentical: anObject

"Private.  Returns the index of the first element in the receiver that is
 identical to the argument.  If the receiver does not have any elements that are
 identical to the argument, returns zero."

1 to: self size do: [:i |
  (anObject == (self at: i)) ifTrue: [^i]
  ].

^ 0.
%

category: 'Searching'
method: SequenceableCollection
indexOf: anObject startingAt: index

"Returns the index of the first element in the receiver that is equivalent to 
 the argument. If the receiver does not have any elements equivalent to the
 argument, returns 0."

"Note: In GemStone 4.1, this method checked for an element that was identical to
 the argument."

^ self indexOf: anObject startingAt: index ifAbsent: [0].
%

category: 'Searching'
method: SequenceableCollection
indexOf: anObject startingAt: index ifAbsent: anExceptionBlock

"Returns the index of the first element in the receiver that is equivalent to 
 the argument. If the receiver does not have any elements equivalent to the
 argument, returns the value of evaluating anExceptionBlock"

"Note: In GemStone 4.1, this method checked for an element that was identical to
 the argument."

index to: self size do: [ :i |
  (anObject = (self at: i)) ifTrue: [ ^i ].
  ].

^ anExceptionBlock value.
%

category: 'Searching'
method: SequenceableCollection
indexOfSubCollection: aSubColl startingAt: anIndex

"Returns the index of the first element of the receiver where that element and
 the subsequent ones are equal to those in aSubColl. The search is begun in the
 receiver at starting at anIndex. Returns 0 if no match is found."
 
^ self indexOfSubCollection: aSubColl startingAt: anIndex ifAbsent: [0].
%
category: 'Searching'
method: SequenceableCollection
occurrencesOfDistinctEqualSubCollection: aCollection
    "Answer the number of *distinct* *non-overlapping* occurrences of
    aCollection in the receiver using equality not identity."

    | otherSize selfSize currentStart currentResult count |
    otherSize := aCollection size.
    selfSize := self size.
    count := 0.
    currentStart := 1.
    [(currentStart + otherSize - 1) <= selfSize] whileTrue:
        [currentResult := self indexOfSubCollection: aCollection startingAt: currentStart ifAbsent: [^count].
         count := count + 1.
         currentStart := currentResult + otherSize].
    ^count
%

category: 'Searching'
method: SequenceableCollection
indexOfSubCollection: aSubColl startingAt: anIndex ifAbsent: anExceptionBlock

"Returns the index of the first element of the receiver where that element and
 the subsequent ones are equal to those in aSubColl. The search is begun in the
 receiver at starting at anIndex. Returns the value of evaluating 
 anExceptionBlock if no match is found."

| subCollSize |

subCollSize := aSubColl size.
(aSubColl size == 0) ifTrue: [ ^ anExceptionBlock value ].

anIndex to: (self size - subCollSize + 1) do: [ :i |
  (self at: i equals: aSubColl) ifTrue: [ ^ i ].
  ].

^ anExceptionBlock value.
%

category: 'Backward Compatibility'
method: SequenceableCollection
indexOfValue: anObject

"Obsolete in GemStone 5.0.  Use the indexOf: method instead."

^ self indexOf: anObject.
%

category: 'Backward Compatibility'
method: SequenceableCollection
insert: aSequenceableCollection at: anIndex

"Obsolete in GemStone 5.0.  Use the insertAll:at: method instead."

aSequenceableCollection _validateClass: SequenceableCollection.
^ self insertAll: aSequenceableCollection at: anIndex.
%

category: 'Adding'
method: SequenceableCollection
insertAll: aCollection at: anIndex

"Inserts all the elements of aCollection into the receiver beginning at index
 anIndex.  Returns aCollection.

 The argument anIndex must be greater than or equal to one.  If anIndex is one
 greater than the size of the receiver, appends aCollection to the receiver.  If
 anIndex is more than one greater than the size of the receiver, generates an
 error."

<primitive: 606 >
| array argCls |
argCls := aCollection class .
(aCollection isKindOf: Interval) ifTrue:[
  self insertAll: aCollection asArray at: anIndex  .
  ^ aCollection 
  ].
((argCls isSubclassOf: CharacterCollection )
 _or:[ argCls isSubclassOf: ByteArray ]) ifTrue:[
   array := Array new: aCollection size .
   1 to: aCollection size do:[:j|
     array at: j put: (aCollection at: j)
     ].
   self insertAll: array at: anIndex .
   array size: 0 .
   ^ aCollection
   ].
aCollection _validateClasses:
  #[ Array, OrderedCollection, SequenceableCollection].
(anIndex _isInteger)
  ifFalse: [ ^ self _errorNonIntegerIndex: anIndex].
(anIndex < 1 _or: [ anIndex > (self size + 1)]) "out of bounds"
  ifTrue: [ ^ self _errorIndexOutOfRange: anIndex].

^ self _primitiveFailed: #insertAll:at:
%

category: 'Adding'
method: SequenceableCollection
insertObject: anObject at: anIndex

"Inserts anObject into the receiver at index anIndex and returns anObject." 

"use the insertAll:at: primitive for proper modification tracking."

self insertAll: #[ anObject ] at: anIndex .
^ anObject
%

category: 'Accessing'
method: SequenceableCollection
last

"Returns the last element of the receiver.  Generates an error if the receiver
 is empty."

(self size == 0)
ifTrue: "attempt to access an empty Collection"
   [ ^ self _error: #objErrCollectionEmpty].
^self at: self size
%

category: 'Updating'
method: SequenceableCollection
last: anObject

"Stores the given object in the last position in the receiver and returns
 anObject."

"Note: in GemStone 4.1 and earlier versions, this method returned the receiver."

^ self at: (self size) put: anObject.
%

category: 'Streams'
method: SequenceableCollection
readStream

"Returns a ReadStream on the receiver."

^ReadStream on: self
%

category: 'Enumerating'
method: SequenceableCollection
reject: aBlock

"(R) Evaluates aBlock with each of the receiver's elements as the argument.
 Stores the values for which aBlock is false into a collection of the same
 class as the receiver, and returns the new collection.  The argument aBlock
 must be a one-argument block.

 The result preserves the ordering of the receiver.  That is, if element a 
 comes before element b in the receiver, then element a is guaranteed to come 
 before b in the result."

|result element |

result := self speciesForSelect new.
1 to: self size do: [ :i|
  element := self at: i.
  (aBlock value: element) ifFalse: [result add: element]
  ].
^ result
%

category: 'Removing'
method: SequenceableCollection
remove: oldObject ifAbsent: anExceptionBlock

"(R) Removes from the receiver an object that is equivalent to oldObject.
 Returns oldObject.  If several elements of the receiver are equivalent to 
 oldObject, only one instance is removed.  If oldObject has no equivalent 
 elements in the receiver, evaluates anExceptionBlock and returns the result
 of the evaluation."

"Note: In GemStone 4.1, this method returned the receiver if an object
 equivalent to oldObject was found in the receiver."

| index |

index := self indexOf: oldObject.
index == 0
  ifTrue: [^ anExceptionBlock value]
  ifFalse: [^ self removeAtIndex: index]
%


! fixed  35501
category: 'Backward Compatibility'
method: SequenceableCollection
removeAll: aCollection ifAbsent: errorBlock

"Obsolete in GemStone 5.0."

"Removes all occurrences of the each of the elements of aCollection from the 
 receiver.  Iterates over aCollection using do: [required].  Executes the given
 one-argument block if an object in aCollection is not in the receiver.  The
 block argument may be nil, in which case the object-not-found error will be
 ignored."

self == aCollection ifTrue:[
  self size: 0 .
  ^ aCollection
  ].
aCollection do: [:obj | | idx |
  idx := self indexOf: obj.
  idx == 0 ifTrue: [
    errorBlock ~~ nil ifTrue: [ errorBlock value: obj ].
  ].
  [ idx > 0 ] whileTrue: [
    self removeFrom: idx to: idx.
    idx := self indexOf: obj startingAt: idx
  ].
].
^ aCollection
%


category: 'Removing'
method: SequenceableCollection
removeAllSuchThat: aBlock

"Removes all elements of the receiver for which aBlock returns true.  Returns
 the receiver."

| indexes |

indexes := Array new.
1 to: self size do: [:idx |
  (aBlock value: (self at: idx)) ifTrue: [
    indexes add: idx
  ]
].

indexes reverseDo: [:each |
  self removeFrom: each to: each
].
%

! Generates an error if the receiver is smaller than index.  [True?]
category: 'Removing'
method: SequenceableCollection
removeAtIndex: anIndex

"Removes the element at the given index.  Returns the removed element."

| anObj |
anObj := self at: anIndex .
self removeFrom: anIndex to: anIndex  .
^ anObj
%

category: 'Removing'
method: SequenceableCollection
removeFirst

"Removes the first element of the receiver.  Returns the removed element."

^ self removeAtIndex: 1
%

category: 'Removing'
method: SequenceableCollection
removeFrom: startIndex to: stopIndex

"Removes the elements of the receiver from startIndex to stopIndex inclusive.
 Returns the receiver. 

 The size of the receiver is decreased by stopIndex - startIndex + 1."

<primitive: 601>

(stopIndex < startIndex)
ifTrue:
   [ ^ startIndex _error: #rtErrBadCopyFromTo args: #[stopIndex]].
((stopIndex > self size) _or: [(stopIndex < 1)])
   ifTrue: [ ^ self _errorIndexOutOfRange: stopIndex].
(startIndex < 1)
   ifTrue: [ ^ self _errorIndexOutOfRange: startIndex].
^ self _primitiveFailed: #removeFrom:to:
%

category: 'Backward Compatibility'
method: SequenceableCollection
removeIndex: index

"Obsolete in GemStone 5.0.  Use the removeAtIndex: method instead."

^ self removeAtIndex: index. 
%

category: 'Removing'
method: SequenceableCollection
removeLast

"Removes the last element of the receiver.  Returns the removed element."

| lastElement selfSize |

selfSize := self size.
lastElement := self at: selfSize.
self size: (selfSize - 1).

^ lastElement.
%

category: 'Removing'
method: SequenceableCollection
removeIdentical: oldObject ifAbsent: anExceptionBlock

"(R) Removes from the receiver an object that is identical to oldObject.
 Returns oldObject.  If several elements of the receiver are identical to
 oldObject, only one instance is removed.  If oldObject is not present
 in the receiver, evaluates anExceptionBlock and returns the result
 of the evaluation."

| idx |

idx := self _indexOfIdentical: oldObject.
(idx == 0) ifTrue: [
  ^ anExceptionBlock value.
] ifFalse: [
  ^ self removeAtIndex: idx.
].
%

category: 'Backward Compatibility'
method: SequenceableCollection
removeValue: oldObject

"Obsolete in GemStone 5.0.  Use the remove: method instead."

"Note: In GemStone 4.1, this method returned the receiver."

^ self remove: oldObject.
%

category: 'Updating'
method: SequenceableCollection
replaceFrom: startIndex to: stopIndex with: aCollection

"Replaces the elements of the receiver between the indexes startIndex and 
 stopIndex with the elements of aCollection.  Returns the receiver."

| i |

((aCollection size) == (stopIndex - startIndex + 1))
  ifFalse: [ ^ self errorDifferentSizeCollections].

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

(aCollection isKindOf: SequenceableCollection) ifTrue:[
  aCollection copyFrom: 1 to: aCollection size 
              into: self startingAt: startIndex .
  ^ self
  ].
i := 1.
aCollection do: [ :element | 
  self at: i put: element.
  i := i + 1.
  ].

^ self.
%

category: 'Updating'
method: SequenceableCollection
replaceFrom: startIndex to: stopIndex with: aSeqCollection startingAt: repIndex

"Replaces the elements of the receiver between the indexes startIndex and 
 stopIndex inclusive with the elements of aSeqCollection starting at startIndex. 
 Returns the receiver."

| j |

((self == aSeqCollection) _and: [repIndex < startIndex])
  ifTrue: [
    j := repIndex + (stopIndex - startIndex).
    stopIndex downTo: startIndex do: [ :i |
      self at: i put: (aSeqCollection at: j).
      j := j - 1.
      ].
    ^ self.
    ].

j := repIndex.    
startIndex to: stopIndex do: [:i|
  self at: i put: (aSeqCollection at: j).
  j := j + 1.
  ].

^ self.
%

category: 'Updating'
method: SequenceableCollection
replaceFrom: startIndex to: stopIndex withObject: anObject

"Replaces the elements of the receiver between the indexes startIndex and 
 stopIndex with anObject. Returns the receiver."

startIndex to: stopIndex do: [ :i| self at: i put: anObject].
^ self.
%

category: 'Copying'
method: SequenceableCollection
reverse

"Returns a copy of the receiver with its elements in reverse order."

| copy size index |

size := self size.
copy := self species new: size.
index := 1.
size downTo: 1 do: [ :i |
  copy at: index put: (self at: i).
  index := index + 1.
].
^copy.
%

category: 'Enumerating'
method: SequenceableCollection
reverseDo: aBlock

"Evaluates the one-argument block aBlock using each element of the receiver,
 in reverse order, as the argument."

self size downTo: 1 do: [ :index |
  aBlock value: (self at: index).
  ].

^ self
%

category: 'Enumerating'
method: SequenceableCollection
select: aBlock

"(R) Evaluates aBlock with each of the receiver's elements as the argument.
 Stores the values for which aBlock is true into a collection of the same
 class as the receiver, and returns the new collection.  The argument aBlock
 must be a one-argument block.

 The result preserves the ordering of the receiver.  That is, if element a 
 comes before element b in the receiver, then element a is guaranteed to come 
 before b in the result."

| result each |

result:= self speciesForSelect new.
1 to: self size do:[ :i|
  each := self at: i.
  (aBlock value: each) ifTrue: [result add: each]
  ].

^result
%

category: 'Private'
method: SequenceableCollection
_asCollectionForSorting

""

^ self
%

category: 'Private'
method: SequenceableCollection
verifyAreTrue

"Returns true if all elements of the receiver are true.  Otherwise, returns 
 self."

self do: [:each | (true == each) ifFalse: [ ^ self ]].
^ true
%

category: 'Private'
method: SequenceableCollection
verifyAreFalse

"Returns true if all elements of the receiver are false.  Otherwise, returns 
 self."

self do: [:each | (false == each) ifFalse: [ ^ self ]].
^ true
%

category: 'Private'
method: SequenceableCollection
verifyElementsIn: aSeqColl

"Check for equality in corresponding elements.  Returns true if the receiver
 and the argument are equal. Otherwise returns self."

(self size == aSeqColl size)
   ifFalse: [ ^ self ].
1 to: self size do: [:i |
   (self at: i) = (aSeqColl at: i)
      ifFalse: [ ^ self ]].
^ true
%

category: 'Enumerating'
method: SequenceableCollection
with: aSequenceableCollection do: aBlock

"Evaluate a two argument block aBlock using each element of the receiver as the
 first argument and the corresponding element of aSequenceableCollection as the
 second argument.  Returns the receiver."

(self size == aSequenceableCollection size)
  ifFalse: [ ^ self errorDifferentSizeCollections ].

1 to: self size do: [ :i|
  aBlock value: (self at: i) value: (aSequenceableCollection at: i).
  ].

^ self.
%
