"

 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

"

    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

"

!

version

    ^ '$Header: /cvs/stx/stx/libbasic/OrderedCollection.st,v 1.37 1995-11-23 01:19:14 cg Exp $'

! !

!OrderedCollection class methodsFor:'instance creation'!

new

    "create a new OrderedCollection"

    ^ (self basicNew) initContents:10

!

new:size

    "create a new OrderedCollection"

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

! !

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

    |idx|

    idx := anInteger + firstIndex - 1.

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

	^ self subscriptBoundsError:anInteger

    ] ifFalse:[

	^ contentsArray at:idx put:anObject

    ]

!

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.

"/    lastIndex := idx.

    ^ anObject

    "

     |c|

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

     c add:'here'

    "

!

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

    ].

    self errorValueNotFound:oldObject

    "

     |c|

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

     c add:'here' after:3. 

    "

    "

     |c|

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

     c add:'here' after:1.   

    "

    "

     |c|

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

     c add:'here' after:5 

    "

!

add:anObject afterIndex:index

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

     Return the argument, anObject."

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

    "

     |c|

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

     c add:'here' afterIndex:4           

    "

!

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.

    ].

    self errorValueNotFound:oldObject

    "

     |c|

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

     c add:'here' before:3.

     c add:'here' before:5 

    "

!

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.

    "

     |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   

    "

!

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

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

    self initContents:10

!

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

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

    "/ it should be rewritten to 

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

	    runIndex := runIndex + 1

	]

    ].

    ^ removed

    "

     |coll|

     coll := OrderedCollection withAll:(1 to:10).

     Transcript showCr:(coll removeAllSuchThat:[:el | el even]).

     Transcript showCr:coll

    "

!

removeFirst

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

    |anObject |

    firstIndex > lastIndex ifTrue:[

	"error if collection is empty"

	^ self emptyCollectionError.

    ].

    anObject := contentsArray at:firstIndex.

    contentsArray at:firstIndex put:nil.

    firstIndex := firstIndex + 1.

    firstIndex > lastIndex ifTrue:[

	"reset to avoid ever growing"

	firstIndex := 1.

	lastIndex := 0 

    ].

    ^ anObject

    "

     (OrderedCollection withAll:#(1 2 3 4 5)) removeFirst; yourself

     OrderedCollection new removeFirst

     (SortedCollection withAll:#(5 4 3 2 1)) removeFirst; yourself

    "

!

removeFirst:n

    "remove the first n elements from the collection; 

     return the elements in an Array"

    |mySize ret|

    mySize := self size.

    mySize < n ifTrue:[

	"error if collection has not enough elements"

	^ self notEnoughElementsError.

    ].

    ret := Array new:n.

    ret replaceFrom:1 to:n with:contentsArray startingAt:firstIndex.

    "/

    "/ nil-out contents array, to not keep elements from being GC'd

    "/

    contentsArray from:firstIndex to:firstIndex + n - 1 put:nil.

    firstIndex := firstIndex + n.

    firstIndex > lastIndex ifTrue:[

	"reset to avoid ever growing"

	firstIndex := 1.

	lastIndex := 0 

    ].

    ^ ret

    "

     (OrderedCollection withAll:#(1 2 3 4 5)) removeFirst:2; yourself 

     (OrderedCollection withAll:#(1 2 3 4 5)) removeFirst:0; yourself 

     OrderedCollection new removeFirst:2 

     (OrderedCollection withAll:#(1 2 3 4 5)) removeFirst:6 

     (SortedCollection withAll:#(5 4 3 2 1)) removeFirst:2; yourself  

    "

!

removeFromIndex:startIndex toIndex:stopIndex

    "remove the elements stored under startIndex up to and including

     the elements under stopIndex.

     Return the receiver.

     Returning the receiver here is a historic leftover - it may change.

     Please use yourself in a cascade, if you need the receivers value

     when using this method."

    |nDeleted|

    (startIndex < 1

    or:[stopIndex > self size]) ifTrue:[

	^ self notEnoughElementsError

    ].

    nDeleted := stopIndex - startIndex + 1.

    contentsArray 

	replaceFrom:(firstIndex + startIndex - 1)

	to:(lastIndex - nDeleted)

	with:contentsArray 

	startingAt:(firstIndex + stopIndex).

    contentsArray

	from:(lastIndex - nDeleted + 1)

	to:lastIndex

	put:nil.

    lastIndex := lastIndex - nDeleted.

    firstIndex > lastIndex ifTrue:[

	"reset to avoid ever growing"

	firstIndex := 1.

	lastIndex := 0 

    ]

    "

     #(1 2 3 4 5 6 7 8 9) asOrderedCollection removeFromIndex:3 toIndex:6

     #(1 2 3 4 5) asOrderedCollection removeFromIndex:3 toIndex:6

    "

!

removeLast

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

    |anObject |

    firstIndex > lastIndex ifTrue:[

	"error if collection is empty"

	^ self emptyCollectionError.

    ].

    anObject := contentsArray at:lastIndex.

    contentsArray at:lastIndex put:nil.

    lastIndex := lastIndex - 1.

    firstIndex > lastIndex ifTrue:[

	"reset to avoid ever growing"

	firstIndex := 1.

	lastIndex := 0 

    ].

    ^ anObject

    "

     (OrderedCollection withAll:#(1 2 3 4 5)) removeLast; yourself

     OrderedCollection new removeLast

     (SortedCollection withAll:#(5 4 3 2 1)) removeLast; yourself

    "

!

removeLast:n

    "remove the last n elements from the collection; 

     return the elements in an Array"

    |mySize ret|

    mySize := self size.

    mySize < n ifTrue:[

	"error if collection has not enough elements"

	^ self notEnoughElementsError.

    ].

    ret := Array new:n.

    ret replaceFrom:1 to:n with:contentsArray startingAt:lastIndex - n + 1.

    "/

    "/ nil-out contents array, to not keep elements from being GC'd

    "/

    contentsArray from:lastIndex - n + 1 to:lastIndex put:nil.

    lastIndex := lastIndex - n.

    firstIndex > lastIndex ifTrue:[

	"reset to avoid ever growing"

	firstIndex := 1.

	lastIndex := 0