"

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

	contentsArray   <Array>         the actual contents

	firstIndex      <SmallInteger>  index of first valid element

	lastIndex       <SmallInteger>  index of last valid element

    [performance hint:]

	They overallocate a few slots to make insertion at either end often O(1),

	but sometimes O(n), where n is the current size of the collection

	(i.e. they have reallocate the underlying element buffer and therefore copy the

	 elements into a new one. However, this reallocation is not done on every insert,

	 and if elements are deleted and others reinserted, the buffer is usually already able

	 to hold the new element)

	Insertion in the middle is O(n), and therefore slower, because elements have to be

	shuffled towards either end, in order to make space for the new element.

	Therefore, it is often cheaper, to instantiate a new object, and copy over the

	elements.

	see SegmentedOrderedCollection for a collection, which is specialized for this

	kind of usage with many elements.

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

    [complexity:]

	access by index: O(1)

	insertion at either end: mostly O(1)

	removal at either end: O(1)

	insertion in the middle: O(n)

	searching: O(n)

	min/max: O(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]

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

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

    "

    "

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