" Smalltalk/OrderedCollection.st				-*- Smalltalk -*- "

OrderedCollection : SequenceableCollection ( array firstIndex lastIndex )

OrderedCollection new: size
[
  self := self _clone.
  self setCollection: (Array new: size).
]

OrderedCollection reset
[
    firstIndex := array size // 3.
    lastIndex := firstIndex.
]

OrderedCollection setCollection: anArray
[
    array := anArray.
    self reset
]


OrderedCollection growSize
[
    ^3 max: array size + 1
]

OrderedCollection makeRoomAtFirst
[
    self size = 0
        ifTrue:
          [ firstIndex := lastIndex := array size ]
        ifFalse:
          [ | count newSize newArray in out |
            count := self size.
            newSize := count + self growSize.
            newArray := Array new: newSize.
            out := newSize.
            in := lastIndex.
            [in > firstIndex] whileTrue: [newArray at: (out := out - 1) put: (array at: (in := in - 1))].
            array := newArray.
	    lastIndex := newSize.
	    firstIndex := lastIndex - count ]
]

OrderedCollection makeRoomAtLast
[
    self size = 0
        ifTrue:
          [ firstIndex := lastIndex := 0 ]
        ifFalse:
          [ | newArray inOut |
            newArray := Array new: array size + self growSize.
            inOut := firstIndex.
            [ inOut < lastIndex ]
		whileTrue:
                  [ newArray at: inOut put: (array at: inOut).
                    inOut := inOut + 1 ].
            array := newArray ]
]

OrderedCollection addFirst: newObject
[
    " Add newObject to the beginning of the receiver.  Answer newObject. "
    firstIndex = 0 ifTrue: [self makeRoomAtFirst].
    ^array at: (firstIndex := firstIndex - 1) put: newObject.
]

OrderedCollection addLast: newObject
[
    " Add newObject to the end of the receiver.  Answer newObject. "
    lastIndex = array size ifTrue: [self makeRoomAtLast].
    array at: lastIndex put: newObject.
    lastIndex := lastIndex + 1.
    ^newObject
]

OrderedCollection add: newObject
[
    ^self addLast: newObject
]

OrderedCollection removeFirst
[
    " Remove the first element of the receiver and answer it.  If the
      receiver is empty, create an error notification. "
    | firstObject | 
    self emptyCheck.
    firstObject := array at: firstIndex.
    array at: firstIndex put: nil.
    firstIndex := firstIndex + 1.
    ^firstObject
]

OrderedCollection removeLast
[
    " Remove the last element of the receiver and answer it.  If the
      receiver is empty, create an error notification. "
    | lastObject |
    self emptyCheck.
    lastIndex := lastIndex - 1.
    lastObject := array at: lastIndex.
    array at: lastIndex put: nil.
    ^lastObject
]

OrderedCollection at: index
[
    ^array at: firstIndex + index
]

OrderedCollection at: index put: anObject
[
    ^array at: firstIndex + index put: anObject
]

OrderedCollection size
[
    ^lastIndex - firstIndex
]

OrderedCollection insert: anObject before: spotIndex
[
    firstIndex = 0
        ifTrue: 
            [ | delta |
	      delta := spotIndex - firstIndex.
	      self makeRoomAtFirst.
              spotIndex := firstIndex + delta ].
    firstIndex := firstIndex - 1.
    array
        replaceFrom: firstIndex
        to:	     spotIndex - 1
        with:        array
        startingAt:  firstIndex + 1.
    array at: spotIndex - 1 put: anObject.
    ^ anObject
]

OrderedCollection collect: unaryBlock
[
    | newCollection |
    newCollection := self species new: self size.
    firstIndex to: lastIndex - 1 do: [:index | newCollection addLast: (unaryBlock value: (array at: index))].
    ^newCollection
]