"

 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:'MinContentsArraySize'

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

    - therefore they can be used for queues and stacks.

    [Instance variables:]

    [performance hint:]

    [beginners bug hint:]

    [memory requirements:]

    [complexity:]

    [see also:]

    [author:]

"

!

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

initialize

    MinContentsArraySize := 4. "the minimum size of a non-empty contentsArray"

! !

!OrderedCollection class methodsFor:'instance creation'!

new

    "create a new, empty OrderedCollection"

    ^ self basicNew initContents:0

    "

	self new

	|nEmpty|

	nEmpty := 0.

	self allInstancesDo:[:e| e size == 0 ifTrue:[nEmpty := nEmpty + 1]].

	nEmpty

	|nEmpty|

	nEmpty := OrderedCollection new.

	self allInstancesDo:[:e| (e size == 0 and:[e contentsArray size ~~ 0]) ifTrue:[nEmpty add:e]].

	nEmpty

    "

    "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

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

    "

     OrderedCollection new:10 withAll:1234

    "

!

newFrom:aCollection

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

     aCollection"

    |newColl|

    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 is now obsolete and the same as new:

     as the algorithm is now clever enough to deal efficiently with this situation"

    ^ self new: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 ifAbsent:exceptionValue

    "return the element at index, anInteger.

     If the index is invalid, return the value from exceptionValue"

    |idx "{ Class: SmallInteger }"|

    idx := anInteger + firstIndex - 1.

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

	^ exceptionValue value

    ].

    ^ contentsArray basicAt:idx

!

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.

    "