"

 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.

"

"{ Package: 'stx:libbasic' }"

"{ NameSpace: Smalltalk }"

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 also 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 to make space in the middle.

      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 or to use another collection class

      (see SegmentedOrderedCollection) which is specialized for this kind of usage.

    [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

        or the syntactic sugar for that:

             OrderedCollection newWithSize:n

        I know, this is confusing for beginners and was a bad semantic decision.

        However, that's the way the standard was defined and how all Smalltalk's behave,

        so we can't change that here.

    [memory requirements:]

        OBJ-HEADER + (3 * ptr-size)

                   + (size-roundedUpToNextPowerOf2 * ptr-size)

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

    adding at the end (fast):

                                                                        [exBegin]

        |coll time|

        coll := OrderedCollection new.

        time := TimeDuration toRun:[

            (1 to:100000) do:[:el | coll add:el].

        ].

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

        self assert:(coll = (1 to:100000)).

        self assert:(coll asBag = (1 to:100000) asBag).

                                                                        [exEnd]

    adding at front (fast):

                                                                        [exBegin]

        |coll time|

        coll := OrderedCollection new.

        time := TimeDuration toRun:[

            (1 to:100000) reverseDo:[:el | coll addFirst:el].

        ].

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

        self assert:(coll = (1 to:100000)).

        self assert:(coll asBag = (1 to:100000) asBag).

                                                                        [exEnd]

    inserting in the middle (slow):

                                                                        [exBegin]

        |coll time|

        coll := OrderedCollection new.

        time := TimeDuration toRun:[

            (1 to:100000) do:[:el | coll add:el beforeIndex:(coll size // 2)+1 ].

        ].

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

        self assert:(coll asBag = (1 to:100000) asBag).

                                                                        [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. However, that's the way OrderedCollections work in every other

        Smalltalk, so here it should as well.

     See also newWithSize:, which might do what you really want.        

     "

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

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

!

new:size withAll:element

    "return a new collection of size, where all elements are

     initialized to element."

    |newCollection|

    newCollection := self newWithSize:size.

    newCollection atAllPut:element.

    ^ newCollection

    "

     OrderedCollection new:10 withAll:1234  

    "

!

newFrom:aCollection

    "return a new OrderedCollection filled with all elements from the argument,

     aCollection"

    |newColl|

    newColl := self new:(aCollection size).

    newColl addAll:aCollection.

    ^ newColl

    "

     OrderedCollection newFrom:#(1 2 3 4)

     OrderedCollection newFrom:(Set with:1 with:2 with:3)

    "

!

newLikelyToRemainEmpty

    "create a new, empty OrderedCollection, for which we already know

     that it is very likely to remain empty.

     Use this for collections which may sometimes get elements added, but usually not.

     This creates an initial contents array of size 0 in contrast to the default new:0,

     which preserves space for 3 elements."

    ^ (self basicNew) initContents:0

    "

     self newLikelyToRemainEmpty size

     self newLikelyToRemainEmpty add:1; size

     self newLikelyToRemainEmpty addAll:#(1 2); size

    "

! !

!OrderedCollection methodsFor:'accessing'!

at:anInteger

    "return the element at index, anInteger"

    |idx "{ Class: SmallInteger }"|

    idx := anInteger + firstIndex - 1.

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

        ^ self subscriptBoundsError:anInteger

    ].

    ^ contentsArray basicAt:idx

    "Modified: / 12.11.1997 / 17:56:05 / cg"

!

at:anInteger put:anObject

    "set the element at index, to be anInteger.

     Return anObject (sigh)."

    |idx "{ Class: SmallInteger }"|

    idx := anInteger + firstIndex - 1.

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

        ^ self subscriptBoundsError:anInteger

    ].

    ^ contentsArray basicAt:idx put:anObject

    "Modified: / 12.11.1997 / 17:56:32 / 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.

    ].

    lastIndex := idx := idx + 1.

    contentsArray basicAt:idx put:anObject.

    ^ anObject

    "

     |c|

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

     c add:'here'

    "

    "Modified: / 12.11.1997 / 17:49:47 / 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 physicalIndex|

    physicalIndex := index + firstIndex - 1.

    physicalIndex > lastIndex ifTrue:[

        "can only add to the end of the collection"

        physicalIndex == (lastIndex+1) ifTrue:[

            idx := lastIndex.

            (idx == contentsArray size) ifTrue:[

                self makeRoomAtLast.

                idx := lastIndex.

            ].

            lastIndex := idx := idx + 1.

        ] ifFalse:[

            ^ self subscriptBoundsError:index.

        ]

    ] ifFalse:[