"

 COPYRIGHT (c) 1989 by Claus Gittinger

 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

!

OrderedCollection comment:'

COPYRIGHT (c) 1989 by Claus Gittinger

'!

!OrderedCollection class methodsFor:'documentation'!

copyright

"

 COPYRIGHT (c) 1989 by Claus Gittinger

 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

"

"

!

documentation

"

    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

"

! !

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

    ].

    aCollection do:[:element |

    ].

    ^ newCollection

    "

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

     #(1 2 3) asSortedCollection , #(99 101 100) asSortedCollection

    "

!

copyWith:newElement

    "return a new collection consisting of a copy of the receivers elements

     plus the argument."

    |newCollection mySize newSize|

    mySize := self size.

    newSize := mySize + 1.

"/    newCollection := self species new:newSize.

    newCollection grow:newSize.

    newCollection replaceFrom:1 to:mySize with:self startingAt:1.

    newCollection at:newSize put:newElement.

    ^newCollection

    "

     #(1 2 3 4 5) copyWith:$a

     'abcdefg' copyWith:$h

     'abcdefg' copyWith:'123'    -- will fail: string cannot be stored into string

     'abcdefg' copyWith:1        -- will fail: integer cannot be stored into string

    "

!

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 |

    firstIndex > lastIndex ifTrue:[

    ].

    anObject := contentsArray at:firstIndex.

    contentsArray at:firstIndex put:nil.

    firstIndex := firstIndex + 1.

    firstIndex > lastIndex ifTrue:[

    ].

    ^ anObject

    "(OrderedCollection withAll:#(1 2 3 4 5)) removeFirst; yourself"

    "(SortedCollection withAll:#(5 4 3 2 1)) removeFirst; yourself"

    "(SortedCollection new) removeFirst"

!

removeLast

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

    |anObject |

    firstIndex > lastIndex ifTrue:[

    ].

    anObject := contentsArray at:lastIndex.

    contentsArray at:lastIndex put:nil.

    lastIndex := lastIndex - 1.

    firstIndex > lastIndex ifTrue:[

    ].

    ^ anObject

    "(OrderedCollection withAll:#(1 2 3 4 5)) removeLast; yourself"

    "(SortedCollection withAll:#(5 4 3 2 1)) removeLast; yourself"

!

removeFromIndex:startIndex to:stopIndex

    "remove the elements stored under startIndex up to and including

     the elements under stopIndex.

     return the receiver."

    |nDeleted|

    nDeleted := stopIndex - startIndex + 1.

    contentsArray replaceFrom:(firstIndex + startIndex)

    contentsArray from:(lastIndex - nDeleted + 1)

    lastIndex := lastIndex - nDeleted.

    firstIndex > lastIndex ifTrue:[

    ]

    "

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

    "

!

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:[

    ].

    ^ exceptionBlock value

!

removeAll

    "remove all elements from the collection."

    self initContents:10

!

add:anObject

    "add the argument, anObject to the end of the collection

     Return the argument, anObject."

    (lastIndex == contentsArray size) ifTrue:[

    ].

    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:[

    ].

    firstIndex := firstIndex - 1.

    contentsArray at:firstIndex put:anObject.

    ^ anObject

    "

     |c|

     c := #(1 2 3 4) asOrderedCollection.

     c addFirst:'here'.

     c

    "

    "

     |c|

     c := #() asOrderedCollection.

     c addFirst:'here'.

     c

    "

!

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.

    "

     |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 errorNotFound

    "

     |c|

     c := #(4 3 2 1) asOrderedCollection.

     c add:'here' after:3.

     c add:'here' after:5 

    "

! 

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 errorNotFound

    "

     |c|

     c := #(4 3 2 1) asOrderedCollection.

     c add:'here' before:3.

     c add:'here' before:5 

    "

! !

!OrderedCollection methodsFor:'grow & shrink'!

grow:newSize

    "grow the receiver to newSize"

    |newContents oldLast|

    newSize <= (lastIndex - firstIndex + 1) ifTrue:[

    ] ifFalse:[

    ]

! !

!OrderedCollection methodsFor:'accessing'!

at:anInteger

    "return the element at index, anInteger"

    |idx|

    idx := anInteger + firstIndex - 1.

    ((anInteger < 1) or:[idx > lastIndex]) ifTrue:[

    ] ifFalse:[

    ]

!

at:anInteger put:anObject

    "set the element at index, to be anInteger"

    |idx|

    idx := anInteger + firstIndex - 1.

    ((anInteger < 1) or:[idx > lastIndex]) ifTrue:[

    ] ifFalse:[

    ]

!

first

    "return the first element"

    firstIndex <= lastIndex ifTrue:[

    ].

    "error if collection is empty"

    "(OrderedCollection withAll:#(1 2 3 4 5)) first"

    "(SortedCollection withAll:#(5 4 3 2 1)) first"

!

last

    "return the last element"

    firstIndex <= lastIndex ifTrue:[

    ].

    "error if collection is empty"

    "(OrderedCollection withAll:#(1 2 3 4 5)) last"

    "(SortedCollection withAll:#(5 4 3 2 1)) last"

! !

!OrderedCollection methodsFor:'filling & 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:[

    ].

    ^ super replaceFrom:start to:stop with:aCollection startingAt:repStart

! !

!OrderedCollection methodsFor:'searching'!

after:anObject

    "return the element, after anObject.

     If anObject is not in the receiver, report an error."

    ^ self after:anObject ifAbsent:[self errorNotFound]

    "

     #(4 3 2 1) asOrderedCollection after:3. 

     #(4 3 2 1) asOrderedCollection after:5 

     #(4 3 2 1) asOrderedCollection after:1 

    "

!

after:anObject ifAbsent:exceptionBlock

    "return the element after the argument anObject, nil if there is none.

     If anObject is not in the receiver, return the result from evaluating exceptionBlock."

    |idx|

    idx := self indexOf:anObject.

    idx ~~ 0 ifTrue:[

    ].