"

 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 class methodsFor:'documentation'!

copyright

"

 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.

"

!

documentation

"

    OrderedCollections (OCs) have their elements ordered as they were

    added. In addition, they provide all indexing access protocol

    and bulk copying (much like Arrays).

    Insertion and removal at both ends is possible and reasonably 

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

    [performance hint:]

      Although insertion and removal of inner elements is possible and supported,

      it may be slow, because remaining elements have to be copied.

      If many elements have to be removed out of the middle of a big OC,

      it is often faster to create a new OC from scratch.

    [beginners bug hint:]

        notice that:

            Array new:n

        is quite different from:

            OrderedCollection new:n

        The later creates an OC which is prepared to hold <n> elements,

        but has a logical size of 0 (zero). To get an OC containing <n> nils,

        use:

             (OrderedCollection new) grow:n

    [see also:]

        Array

    [author:]

        Claus Gittinger

"

!

examples

"

  using OC as a stack:

                                                                        [exBegin]

    |stack top|

    stack := OrderedCollection new.

    1 to:10 do:[:i |

        stack add:i

    ].

    10 timesRepeat:[

        top := stack removeLast.

        Transcript showCR:top

    ]

                                                                        [exEnd]

  using OC as a queue (you should use Queue right away ..):

                                                                        [exBegin]

    |queue dequeued|

    queue := OrderedCollection new.

    1 to:10 do:[:i |

        queue addLast:i

    ].

    10 timesRepeat:[

        dequeued := queue removeFirst.

        Transcript showCR:dequeued

    ]

                                                                        [exEnd]

  examples to support the performance hint (see documentation)

    timing removal of all odd elements in a collection of 10000:

    (940 ms on P5/133)

                                                                        [exBegin]

        |coll time|

        coll := (1 to:10000) asOrderedCollection.

        time := Time millisecondsToRun:[

            coll removeAllSuchThat:[:el | el even]

        ].

        Transcript show:'time is '; show:time; showCR:' ms'.

                                                                        [exEnd]

    tuning the removal by doing it reverse

    (less copying in #removeAtIndex:) speeds it up by a factor of 2:

                                                                        [exBegin]

        |coll time|

        coll := (1 to:10000) asOrderedCollection.

        time := Time millisecondsToRun:[

            coll size to:1 by:-1 do:[:index |

                (coll at:index) even ifTrue:[

                    coll removeAtIndex:index

                ]

            ]

        ].

        Transcript show:'time is '; show:time; showCR:' ms'.

                                                                        [exEnd]

    rebuilding a new collection:

    (64 ms on P5/133)

                                                                        [exBegin]

        |coll time|

        coll := (1 to:10000) asOrderedCollection.

        time := Time millisecondsToRun:[

            coll := coll select:[:el | el odd]

        ].

        Transcript show:'time is '; show:time; showCR:' ms'.

                                                                        [exEnd]

"

! !

!OrderedCollection class methodsFor:'instance creation'!

new

    "create a new, empty OrderedCollection"

    ^ (self basicNew) initContents:10

    "Modified: 19.3.1996 / 17:53:12 / cg"

!

new:size

    "create a new, empty OrderedCollection with a preallocated physical

     size. 

     NOTICE: 

        the logical size of the returned collection is 0 (i.e. it is empty).

        This may be confusing, in that it is different from what Array>>new:

        returns.

     "

    ^ (self basicNew) initContents:(size max:3)

    "Modified: 19.3.1996 / 17:53:47 / cg"

! !

!OrderedCollection methodsFor:'accessing'!

at:anInteger

    "return the element at index, anInteger"

    |idx|

    idx := anInteger + firstIndex - 1.

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

	^ self subscriptBoundsError:anInteger

    ] ifFalse:[

	^ contentsArray at:idx

    ]

!

at:anInteger put:anObject

    "set the element at index, to be anInteger.

     Return anObject (sigh)."

    |idx|

    idx := anInteger + firstIndex - 1.

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

        ^ self subscriptBoundsError:anInteger

    ] ifFalse:[

        ^ contentsArray at:idx put:anObject

    ]

    "Modified: 19.4.1996 / 11:31:16 / cg"

!

first

    "return the first element"

    firstIndex <= lastIndex ifTrue:[

	^ contentsArray at:firstIndex

    ].

    "error if collection is empty"

    ^ self emptyCollectionError

    "

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

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

    "

!

last

    "return the last element"

    firstIndex <= lastIndex ifTrue:[

	^ contentsArray at:lastIndex

    ].

    "error if collection is empty"

    ^ self emptyCollectionError

    "

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

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

    "

! !

!OrderedCollection methodsFor:'adding & removing'!

add:anObject

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

     Return the argument, anObject."

    |idx "{ Class:SmallInteger }"|

    idx := lastIndex.

    (idx == contentsArray size) ifTrue:[

        self makeRoomAtLast.

        idx := lastIndex.

    ].

    idx := lastIndex := idx + 1.

    contentsArray at:idx put:anObject.

    ^ anObject

    "

     |c|

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

     c add:'here'

    "

    "Modified: 12.4.1996 / 13:26:57 / cg"

!

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

        ^ newObject

    ].

    ^ self errorValueNotFound:oldObject

    "

     |c|

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

     c add:'here' after:3; yourself.   

    "

    "

     |c|

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

     c add:'here' after:1; yourself.   

    "

    "

     |c|

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

     c add:'here' after:5; yourself 

    "

    "Modified: 12.4.1996 / 13:51:56 / cg"

!

add:anObject afterIndex:index

    "insert the argument, anObject to become located at index.

     Return the receiver (sigh - ST-80 compatibility)."

    ^ self add:anObject beforeIndex:(index + 1)

    "

     |c|

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

     c add:'here' afterIndex:2           

    "

    "

     |c|

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

     c add:'here' afterIndex:4           

    "

    "

     |c|

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

     c add:'here' afterIndex:0           

    "

    "

     |c|

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

     c add:'here' afterIndex:5           

    "

    "Modified: 12.4.1996 / 13:52:41 / cg"

!

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.

        ^ newObject

    ].

    ^ self errorValueNotFound:oldObject

    "

     |c|

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

     c add:'here' before:3.

     c add:'here' before:5 

    "

    "Modified: 12.4.1996 / 13:25:47 / cg"

!

add:anObject beforeIndex:index

    "insert the argument, anObject to become located at index.

     Return the receiver (sigh - ST-80 compatibility)."

    |idx|

    idx := self makeRoomAtIndex:(index + firstIndex - 1).

    "/ notice: the above may change firstIndex

    contentsArray at:idx put:anObject.

    "

     |c|

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

     c add:'here' beforeIndex:3   

    "

    "

     |c|

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

     c add:'here' beforeIndex:1    

    "

    "

     |c|

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

     c add:'here' beforeIndex:5     

    "

    "Modified: 12.4.1996 / 16:47:31 / cg"

!

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 := #(1 2 3 4) asOrderedCollection.

     c addFirst:'here'.

     c

    "

    "

     |c|

     c := #() asOrderedCollection.

     c addFirst:'here'.

     c

    "

!

remove:anObject ifAbsent:exceptionBlock

    "remove the first occurrence of anObject from the collection

     and return it.

     If its not in the receiver collection, return the value of exceptionBlock."

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

    	    "/ nil it (helps GC)

	    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

    "

     #(1 2 3 4 5) asOrderedCollection remove:9 ifAbsent:[self halt]

     #(1 2 3 4 5) asOrderedCollection remove:3 ifAbsent:[self halt]

     #(1 2 3 4 5 6 7 8 9) asOrderedCollection remove:3 ifAbsent:'oops' 

     #(1 2 3 4 5) asOrderedCollection remove:9 ifAbsent:'oops' 

    "

!

removeAll

    "remove all elements from the collection.

     Returns the receiver."

    self initContents:10

    "Modified: 12.4.1996 / 13:34:19 / cg"

!

removeAllSuchThat:aBlock

    "remove all elements that meet a test criteria as specified in aBlock.

     The argument, aBlock is evaluated for successive elements and all those,

     for which it returns true, are removed.

     Return a collection containing the removed elements.

     Performance hint:

	if a big number of objects is removed this way,

        it may be better to rebuild a new collection via #select:,

        since removing elements out of the middle is somewhat slow

	due to the need to copy over remaining elements within the collection."

    "/ this is a q&d implementation (possibly slow).

    |runIndex removed element|

    removed := self species new.

    runIndex := 1.

    [runIndex <= self size] whileTrue:[

        element := self at:runIndex.

        (aBlock value:element) ifTrue:[

            removed add:element.

            self removeAtIndex:runIndex

        ] ifFalse:[