"

 COPYRIGHT (c) 1989-93 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-93 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

%W% %E%

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:'testing'!

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

reverse

    "return a new collection with all elements of the receiver

     in reverse order"

    |newCollection

     size     "{ Class:SmallInteger }"

     dstIndex "{ Class:SmallInteger }" |

    size := self size.

    newCollection := self species new:size.

    newCollection setFirstIndex:firstIndex lastIndex:lastIndex.

    dstIndex := size.

    1 to:size do:[:srcIndex |

        newCollection at:dstIndex put:(self at:srcIndex).

        dstIndex := dstIndex - 1

    ].

    ^ newCollection

!

, 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

! !

!OrderedCollection methodsFor:'adding & removing'!

removeFirst

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

    |anObject |

    anObject := contentsArray at:firstIndex.

    firstIndex := firstIndex + 1.

    ^ anObject

!

removeLast

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

    |anObject |

    anObject := contentsArray at:lastIndex.

    lastIndex := lastIndex - 1.

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

            lastIndex := lastIndex - 1.

            ^ anObject

        ].

        index := index + 1

    ].

    ^ exceptionBlock value

!

add:anObject

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

     Return the argument, anObject."

    ^ self addLast:anObject

!

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

!

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

!

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

! !

!OrderedCollection methodsFor:'grow & shrink'!

grow:newSize

    "return the number of elements in the collection"

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

    ((anInteger < 1) or:[(anInteger + firstIndex - 1) > lastIndex])

    ifTrue:[

        self errorNoSuchElement

    ] ifFalse:[

        ^ contentsArray at:(anInteger + firstIndex - 1)

    ]

!

at:anInteger put:anObject

    "set the element at index, to be anInteger"

    ((anInteger < 1) or:[(anInteger + firstIndex - 1) > lastIndex])

    ifTrue:[

        self errorNoSuchElement

    ] ifFalse:[

        ^ contentsArray at:(anInteger + firstIndex - 1) put:anObject

    ]

! !

!OrderedCollection methodsFor:'private'!

errorNoSuchElement

    self error:'indexing non existing element'

!

setFirstIndex:newFirstIndex lastIndex:newLastIndex

    firstIndex := newFirstIndex.

    lastIndex := newLastIndex.

!

makeRoomAtLast

    "grow the contents for more room at the end"

    |newContents 

     oldSize "{ Class:SmallInteger }" |

    oldSize := contentsArray size.

    newContents := Array new:(oldSize * 2).

    newContents replaceFrom:1 to:oldSize with:contentsArray.

    contentsArray := newContents

!

makeRoomAtFront

    "grow the contents for more room at the beginning"

    |newContents

     oldSize "{ Class:SmallInteger }" |

    oldSize := contentsArray size.

    newContents := Array new:(oldSize * 2).

    newContents replaceFrom:(oldSize + 1) to:(oldSize * 2)

                       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.

    ^ index between:firstIndex and:lastIndex

!

identityIndexOf:anObject

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

    |index|

    index := contentsArray identityIndexOf:anObject.

    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.

    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:'enumeration'!

do:aBlock

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

    contentsArray from:firstIndex to:lastIndex do:aBlock

!

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

! !