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

SequenceableCollection subclass:#OrderedCollection
         instanceVariableNames:'contentsArray firstIndex lastIndex'
         classVariableNames:''
         poolDictionaries:''
         category:'Collections-Sequenceable'
!

OrderedCollection comment:'

COPYRIGHT (c) 1989 by Claus Gittinger
              All Rights Reserved

OrderedCollection have ordered elements. Insertion and removal at both ends
is possible - therefore they can be used for queues and stacks.

Instance variables:

contentsArray   <Array>         the actual contents
firstIndex      <SmallInteger>  index of first valid element
lastIndex       <SmallInteger>  index of last valid element

$Header: /cvs/stx/stx/libbasic/OrderedCollection.st,v 1.6 1993-12-11 00:53:00 claus Exp $
written spring 89 by claus
'!

!OrderedCollection class methodsFor:'instance creation'!

new:size
    "create a new OrderedCollection"

    ^ (self basicNew) initContents:size
!

new
    "create a new OrderedCollection"

    ^ (self basicNew) initContents:10
! !

!OrderedCollection methodsFor:'queries'!

size
    "return the number of elements in the collection"

    ^ lastIndex - firstIndex + 1
!

isFixedSize
    "return true if the receiver cannot grow - this will vanish once
     Arrays and Strings learn how to grow ..."

    ^ false
! !

!OrderedCollection methodsFor:'copying'!

, aCollection
    "return a new collection formed from concatenating the receiver with
     the argument"

    |newCollection|

    newCollection := self species new:(self size + aCollection size).
    self do:[:element |
        newCollection add:element
    ].
    aCollection do:[:element |
        newCollection add:element
    ].
    ^ newCollection

    "#(1 2 3) asOrderedCollection , #(4 5 6) asOrderedCollection"
!

copy
    "return a new OrderedCollection containing the elements of the receiver."

    "redefinition is a consequence of the implementation with a
     separate array - otherwise we get a shallow copy of the
     contents array, which is not what we want here"

    ^ self copyFrom:1 to:self size
!

copyFrom:start to:stop
    "return a new OrderedCollection containing the elements
     from start to stop."

    |newCollection sz|

    sz := stop - start + 1.
    newCollection := self species new:sz.
    newCollection grow:sz.
    newCollection replaceFrom:1 to:sz with:self startingAt:start.
    ^ newCollection
! !

!OrderedCollection methodsFor:'adding & removing'!

removeFirst
    "remove the first element from the collection; return the element"

    |anObject |

    anObject := contentsArray at:firstIndex.
    contentsArray at:firstIndex put:nil.
    firstIndex := firstIndex + 1.
    firstIndex > lastIndex ifTrue:[
        "reset to avoid ever growing"
        firstIndex := 1.
        lastIndex := 0 
    ].
    ^ anObject
!

removeLast
    "remove the last element from the collection; return the element"

    |anObject |

    anObject := contentsArray at:lastIndex.
    contentsArray at:lastIndex put:nil.
    lastIndex := lastIndex - 1.
    firstIndex > lastIndex ifTrue:[
        "reset to avoid ever growing"
        firstIndex := 1.
        lastIndex := 0 
    ].
    ^ anObject
!

remove:anObject ifAbsent:exceptionBlock
    "remove the first occurrence of anObject from the collection;
     return the value of exceptionBlock if anObject is not in
     the collection"

    |index "{ Class:SmallInteger }"|

    index := firstIndex.
    [index <= lastIndex] whileTrue:[
        anObject = (contentsArray at:index) ifTrue:[
            contentsArray replaceFrom:index to:(contentsArray size - 1)
                            with:contentsArray startingAt:(index + 1).
            contentsArray at:lastIndex put:nil.
            lastIndex := lastIndex - 1.
            firstIndex > lastIndex ifTrue:[
                "reset to avoid ever growing"
                firstIndex := 1.
                lastIndex := 0 
            ].
            ^ anObject
        ].
        index := index + 1
    ].
    ^ exceptionBlock value
!

add:anObject
    "add the argument, anObject to the end of the collection
     Return the argument, anObject."

    (lastIndex == contentsArray size) ifTrue:[
        self makeRoomAtLast
    ].
    lastIndex := lastIndex + 1.
    contentsArray at:lastIndex put:anObject.
    ^ anObject

    "
     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here'
    "
!

addFirst:anObject
    "add the argument, anObject to the beginning of the collection.
     Return the argument, anObject."

    (firstIndex == 1) ifTrue:[
        self makeRoomAtFront
    ].
    firstIndex := firstIndex - 1.
    contentsArray at:firstIndex put:anObject.
    ^ anObject

    "
     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c addFirst:'here'
    "
!

add:anObject beforeIndex:index
    "insert the argument, anObject to become located at index.
     Return the argument, anObject."

    self makeRoomAtIndex:(index - firstIndex + 1).
    contentsArray at:(index - firstIndex + 1) put:anObject.
    ^ anObject

    "
     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' beforeIndex:3
    "
!

add:newObject after:oldObject
    "insert the argument, newObject after oldObject.
     If oldObject is not in the receiver, report an error,
     otherwise return the argument, anObject."

    |idx|

    idx := self indexOf:oldObject.
    idx ~~ 0 ifTrue:[
        ^ self add:newObject beforeIndex:(idx + 1).
    ].
    self errorNotFound

    "
     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' after:3
     c add:'here' after:1
    "
! 


add:newObject before:oldObject
    "insert the argument, newObject before oldObject.
     If oldObject is not in the receiver, report an error,
     otherwise return the argument, anObject."

    |idx|

    idx := self indexOf:oldObject.
    idx ~~ 0 ifTrue:[
        ^ self add:newObject beforeIndex:idx.
    ].
    self errorNotFound

    "
     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' after:3
     c add:'here' after:1
    "
! !

!OrderedCollection methodsFor:'grow & shrink'!

grow:newSize
    "grow the receiver to newSize"

    |newContents|

    newSize <= (lastIndex - firstIndex + 1) ifTrue:[
        lastIndex := firstIndex + newSize - 1
    ] ifFalse:[
        newContents := Array new:newSize.
        newContents replaceFrom:1 to:(lastIndex - firstIndex + 1) with:contentsArray.
        contentsArray := newContents.
        firstIndex := 1.
        lastIndex := newSize
    ]
! !

!OrderedCollection methodsFor:'accessing'!

at:anInteger
    "return the element at index, anInteger"

    |idx|

    idx := anInteger + firstIndex - 1.
    ((anInteger < 1) or:[idx > lastIndex]) ifTrue:[
        self subscriptBoundsError
    ] ifFalse:[
        ^ contentsArray at:idx
    ]
!

at:anInteger put:anObject
    "set the element at index, to be anInteger"

    |idx|

    idx := anInteger + firstIndex - 1.
    ((anInteger < 1) or:[idx > lastIndex]) ifTrue:[
        self subscriptBoundsError
    ] ifFalse:[
        ^ contentsArray at:idx put:anObject
    ]
! !

!OrderedCollection methodsFor:'filing & replacing'!

replaceFrom:start to:stop with:aCollection startingAt:repStart
    "redefined - can be done faster"

    |end|

    end := stop + firstIndex - 1.
    ((start >= 1) and:[end <= lastIndex]) ifTrue:[
        ^ contentsArray replaceFrom:(start + firstIndex - 1)
                                 to:end
                               with:aCollection
                         startingAt:repStart
    ].
    ^ super replaceFrom:start to:stop with:aCollection startingAt:repStart
! !

!OrderedCollection methodsFor:'private'!

setFirstIndex:newFirstIndex lastIndex:newLastIndex
    "set first and last index"

    firstIndex := newFirstIndex.
    lastIndex := newLastIndex.
!

makeRoomAtLast
    "grow the contents for more room at the end"

    |newContents 
     oldSize "{ Class:SmallInteger }"
     newSize "{ Class:SmallInteger }" |

    oldSize := contentsArray size.
    newSize := oldSize * 2.
    newSize == 0 ifTrue:[ newSize := 1].
    newContents := Array new:newSize.
    newContents replaceFrom:1 to:oldSize with:contentsArray.
    contentsArray := newContents
!

makeRoomAtFront
    "grow the contents for more room at the beginning"

    |newContents
     oldSize "{ Class:SmallInteger }"
     newSize "{ Class:SmallInteger }" |

    oldSize := contentsArray size.
    newSize := oldSize * 2.
    newSize == 0 ifTrue:[ newSize := 1].
    newContents := Array new:newSize.
    newContents replaceFrom:(oldSize + 1) to:newSize with:contentsArray startingAt:1.
    contentsArray := newContents.
    firstIndex := firstIndex + oldSize.
    lastIndex := lastIndex + oldSize
!

makeRoomAtIndex:index
    "grow the contents for inserting at index
     i.e.
     #(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:3 -> #(1 2 nil 3 4 5 6)
     #(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:1 -> #(nil 1 2 3 4 5 6)
     #(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:7 -> #(1 2 3 4 5 6 nil)"

    |newContents
     newSize "{ Class:SmallInteger }" 
     oldSize "{ Class:SmallInteger }" |

    oldSize := contentsArray size.
    newSize := oldSize + 1.
    newContents := Array new:newSize.
    index == 1 ifFalse:[
        newContents replaceFrom:1 to:index-1 with:contentsArray startingAt:1.
    ].
    index == newSize ifFalse:[
        newContents replaceFrom:index + 1 to:newSize with:contentsArray startingAt:index.
    ].
    contentsArray := newContents.
    lastIndex := lastIndex + 1
!

initContents:size
    contentsArray := Array new:size.
    firstIndex := 1.
    lastIndex := 0 
! !

!OrderedCollection methodsFor:'testing'!

includes:anObject
    "return true if the object is in the collection"

    |index|

    index := contentsArray indexOf:anObject startingAt:firstIndex.
    ^ index between:firstIndex and:lastIndex
!

identityIndexOf:anObject
    "return the index of the object, 0 if not in the collection"

    |index|

    index := contentsArray identityIndexOf:anObject startingAt:firstIndex.
    index < firstIndex ifTrue:[^ 0].
    index > lastIndex ifTrue:[^ 0].
    ^ index - firstIndex + 1
!

identityIndexOf:anObject startingAt:startIndex
    "return the index of the object, 0 if not in the collection"

    |index|

    index := contentsArray identityIndexOf:anObject startingAt:(startIndex + firstIndex - 1).
    index < firstIndex ifTrue:[^ 0].
    index > lastIndex ifTrue:[^ 0].
    ^ index - firstIndex + 1
!

indexOf:anObject
    "return the index of the object, 0 if not in the collection"

    |index|

    index := contentsArray indexOf:anObject startingAt:firstIndex.
    index < firstIndex ifTrue:[^ 0].
    index > lastIndex ifTrue:[^ 0].
    ^ index - firstIndex + 1
!

indexOf:anObject startingAt:startIndex
    "return the index of the object, 0 if not in the collection"

    |index|

    index := contentsArray indexOf:anObject startingAt:(startIndex + firstIndex - 1).
    index < firstIndex ifTrue:[^ 0].
    index > lastIndex ifTrue:[^ 0].
    ^ index - firstIndex + 1
! !

!OrderedCollection methodsFor:'converting'!

asOrderedCollection 
    "return the receiver as an ordered collection"

    "could be an instance of a subclass..."
    self class == OrderedCollection ifTrue:[
        ^ self
    ].
    ^ super asOrderedCollection
! !

!OrderedCollection methodsFor:'enumeration'!

do:aBlock
    "evaluate the argument, aBlock for every element in the collection."

    contentsArray from:firstIndex to:lastIndex do:aBlock
!

keysAndValuesDo:aTwoArgBlock
    "evaluate the argument, aBlock for every element in the collection,
     passing both index and element as arguments."

    firstIndex to:lastIndex do:[:index |
        aTwoArgBlock value:index value:(contentsArray at:index)
    ]
!

collect:aBlock
    "evaluate the argument, aBlock for every element in the collection
     and return a collection of the results"

    |newCollection
     index  "{ Class:SmallInteger }"
     end    "{ Class:SmallInteger }" |

    end := lastIndex.
    newCollection := (self species new).
    index := firstIndex.
    [index <= end] whileTrue:[
        newCollection add:(aBlock value:(contentsArray at:index)).
        index := index + 1
    ].
    ^ newCollection
! !