"
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' }"
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
[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]
"
! !
!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"
!
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)
"
! !
!OrderedCollection methodsFor:'accessing'!
after:anObject ifAbsent:exceptionBlock
"return the element after the argument anObject, nil if there is none.
If anObject is not in the receiver, return the result from evaluating exceptionBlock."
|idx|
idx := self indexOf:anObject.
idx ~~ 0 ifTrue:[
idx == lastIndex ifTrue:[^ nil].
^ self at:(idx + 1).
].
^ exceptionBlock value
"
#(4 3 2 1) asOrderedCollection after:3.
#(4 3 3 1) asOrderedCollection after:3. <- what should be returned here ?
#(4 3 2 1) asOrderedCollection after:5
#(4 3 2 1) asOrderedCollection after:1
"
"Modified: 10.5.1996 / 14:07:28 / cg"
!
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"
!
before:anObject ifAbsent:exceptionBlock
"return the element before the argument anObject, nil if there is none.
If anObject is not in the receiver, return the result from evaluating exceptionBlock."
|idx|
idx := self indexOf:anObject.
idx ~~ 0 ifTrue:[
idx == firstIndex ifTrue:[^ nil].
^ self at:(idx - 1).
].
^ exceptionBlock value
"
#(4 3 2 1) asOrderedCollection before:3.
#(4 3 2 1) asOrderedCollection before:5
#(4 3 2 1) asOrderedCollection before:1
#(4 2 1 1) asOrderedCollection before:1
#(4 3 2 1) asOrderedCollection before:4
"
"Modified: 10.5.1996 / 14:07:55 / 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:[
physicalIndex == (lastIndex+1) ifTrue:[
self addLast:anObject.
^ self
].
^ self subscriptBoundsError:index
].
idx := self makeRoomAtIndex:physicalIndex.
"/ notice: the above may change firstIndex
contentsArray basicAt: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: / 28.1.1998 / 17:17:48 / cg"
!
addAll:aCollection
"add all elements of the argument, aCollection to the
receiver. Returns the argument, aCollection."
self addAll:aCollection beforeIndex:(1 + self size).
^ aCollection
!
addAll:aCollection beforeIndex:index
"insert all elements of the argument, anObject to become located at index.
The collection may be unordered, but then order of the sliced-in elements
is undefined.
Return the receiver."
|idx count|
aCollection isSequenceable ifTrue:[
"/ we are lucky - that thing can count & do bulk copies
count := aCollection size.
idx := self makeRoomAtIndex:(index + firstIndex - 1) for:count.
"/ notice: the above may change firstIndex
contentsArray replaceFrom:idx to:(idx + count - 1) with:aCollection startingAt:1.
^ self
].
idx := index.
aCollection do:[:element |
self add:element beforeIndex:idx.
idx := idx + 1.
].
"
|c|
c := #(1 2 3 4) asOrderedCollection.
c addAll:'here' beforeIndex:3
"
"
|c|
c := #(1 2 3 4) asOrderedCollection.
c removeFirst.
c addAll:'here' beforeIndex:3
"
"
|c|
c := #(1 2 3 4) asOrderedCollection.
c addAll:'here' beforeIndex:1
"
"
|c|
c := #(1 2 3 4) asOrderedCollection.
c addAll:'here' beforeIndex:5
"
"
|c|
c := #(1 2 3 4) asOrderedCollection.
c addAll:('hello' asSet) beforeIndex:3
"
"Modified: 15.4.1997 / 12:43:59 / cg"
!
addFirst:anObject
"add the argument, anObject to the beginning of the collection.
Return the argument, anObject."
|idx "{ Class:SmallInteger }"|
(idx := firstIndex) == 1 ifTrue:[
self makeRoomAtFront.
idx := firstIndex.
].
firstIndex := idx := idx - 1.
contentsArray basicAt:idx put:anObject.
^ anObject
"
|c|
c := #(1 2 3 4) asOrderedCollection.
c addFirst:'here'.
c
"
"
|c|
c := #() asOrderedCollection.
c addFirst:'here'.
c
"
"Modified: / 12.11.1997 / 17:58:05 / cg"
!
addLast: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.4.1996 / 13:26:57 / cg"
"Created: / 12.11.1997 / 17:46:29 / cg"
!
clearContents
"remove all elements from the collection but keep the contentsArray.
Useful for huge lists, if the contents will be rebuild soon (using #add:)
to a size which is similar to the lists current size.
Returns the receiver."
"/ clear those references, to give the garbage collector
"/ a chance ...
firstIndex >= lastIndex ifTrue:[
contentsArray from:firstIndex to:lastIndex put:nil.
].
firstIndex := 1.
lastIndex := 0.
"/ this is the same as:
"/ self initContents:(self size)
"Modified: 12.4.1996 / 13:34:19 / cg"
!
remove:anObject ifAbsent:exceptionBlock
"remove the first element which is equal to anObject;
if found, remove and return it;
if not, return the value from evaluating exceptionBlock.
Uses equality compare (=) to search for the element."
|index retVal|
index := contentsArray indexOf:anObject startingAt:firstIndex endingAt:lastIndex.
index ~~ 0 ifTrue:[
retVal := contentsArray at:index.
index := index - firstIndex + 1.
self removeFromIndex:index toIndex:index.
^ retVal
].
^ 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'
#(1.0 2.0 3.0 4.0 5.0) asOrderedCollection remove:4 ifAbsent:'oops'
#(1.0 2.0 3.0 4.0 5.0) asOrderedCollection removeIdentical:4 ifAbsent:'oops'
"
"Modified: 8.2.1997 / 19:17:19 / cg"
!
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 large number of objects is to be 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 sz|
removed := self species new.
runIndex := 1.
sz := self size.
[runIndex <= sz] whileTrue:[
element := self at:runIndex.
(aBlock value:element) ifTrue:[
removed add:element.
self removeAtIndex:runIndex.
sz := sz - 1.
] ifFalse:[
runIndex := runIndex + 1
]
].
^ removed
"
|coll|
coll := OrderedCollection withAll:(1 to:10).
Transcript showCR:(coll removeAllSuchThat:[:el | el even]).
Transcript showCR:coll
"
"Modified: 8.2.1997 / 19:19:00 / cg"
!
removeFirst
"remove the first element from the collection; return the element.
If there is no element in the receiver collection, raise an error."
|anObject
fI "{ Class: SmallInteger }" |
fI := firstIndex.
fI > lastIndex ifTrue:[
"error if collection is empty"
^ self emptyCollectionError.
].
anObject := contentsArray basicAt:fI.
"/ nil it out, to allow GC to reclaim it.
contentsArray basicAt:fI put:nil.
fI := fI + 1.
fI > lastIndex ifTrue:[
"reset to avoid ever growing"
fI := 1.
lastIndex := 0
].
firstIndex := fI.
^ anObject
"
(OrderedCollection withAll:#(1 2 3 4 5)) removeFirst; yourself
OrderedCollection new removeFirst
(SortedCollection withAll:#(5 4 3 2 1)) removeFirst; yourself
"
"Modified: / 5.2.1999 / 23:22:58 / cg"
!
removeFirst:n
"remove the first n elements from the collection;
Return a collection containing the removed elements."
|mySize ret newFirstIndex|
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
"/
newFirstIndex := firstIndex + n.
contentsArray from:firstIndex to:newFirstIndex - 1 put:nil.
newFirstIndex > lastIndex ifTrue:[
"reset to avoid ever growing"
newFirstIndex := 1.
lastIndex := 0
].
firstIndex := newFirstIndex.
^ 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
"
"Modified: 8.2.1997 / 19:20:18 / cg"
!
removeFirstIfAbsent:exceptionBlock
"remove the first element from the collection; return the element.
If there is no element in the receiver collection, return the value from
exceptionBlock."
|anObject fI "{ Class: SmallInteger }" |
fI := firstIndex.
fI > lastIndex ifTrue:[
"error if collection is empty"
^ exceptionBlock value.
].
anObject := contentsArray basicAt:fI.
"/ nil it out, to allow GC to reclaim it.
contentsArray basicAt:fI put:nil.
fI := fI + 1.
fI > lastIndex ifTrue:[
"reset to avoid ever growing"
fI := 1.
lastIndex := 0
].
firstIndex := fI.
^ anObject
"
(OrderedCollection withAll:#(1 2 3 4 5)) removeFirst; yourself
OrderedCollection new removeFirst
(SortedCollection withAll:#(5 4 3 2 1)) removeFirst; yourself
"
"Modified: / 12.11.1997 / 17:58:43 / cg"
"Created: / 30.7.1998 / 13:19:42 / cg"
!
removeFrom:startIndex to:stopIndex
"added for ST-80 compatibility.
Same as removeFromIndex:toIndex:."
^ self removeFromIndex:startIndex toIndex:stopIndex
"Created: 15.4.1997 / 12:39:00 / cg"
!
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 "{ Class: SmallInteger }"
fI "{ Class: SmallInteger }"
lI "{ Class: SmallInteger }"
newLastIndex sz|
sz := self size.
(startIndex < 1 or:[stopIndex > sz]) ifTrue:[
^ self notEnoughElementsError
].
nDeleted := stopIndex - startIndex + 1.
nDeleted < 0 ifTrue:[
"/ mhmh - what should be done here ?
^ self error:'bad index range'
].
nDeleted == 0 ifTrue:[^ self].
fI := firstIndex.
lI := lastIndex.
"/
"/ can be done faster, when removing the first elements
"/
startIndex == 1 ifTrue:[
"/ nil out (helps GC)
contentsArray
from:fI
to:fI + nDeleted - 1
put:nil.
firstIndex := fI := fI + nDeleted
] ifFalse:[
"/
"/ can be done faster, when removing the last elements
"/
stopIndex == sz ifTrue:[
"/ nil out (helps GC)
contentsArray
from:lI - nDeleted + 1
to:lI
put:nil.
lastIndex := lI := lI - nDeleted
] ifFalse:[
"/
"/ must shuffle
"/ TODO:
"/ for big collections, try to copy the smallest
"/ possible number of elements
newLastIndex := lI - nDeleted.
contentsArray
replaceFrom:(fI + startIndex - 1)
to:newLastIndex
with:contentsArray
startingAt:(fI + stopIndex).
"/ nil out rest (helps GC)
contentsArray
from:(newLastIndex + 1)
to:lI
put:nil.
lastIndex := lI := newLastIndex.
]
].
fI > lI 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 6 7 8 9) asOrderedCollection removeFromIndex:6 toIndex:8
#(1 2 3 4 5 6 7 8 9) asOrderedCollection removeFromIndex:1 toIndex:3
#(1 2 3 4 5 6 7 8 9) asOrderedCollection removeFromIndex:6 toIndex:9
#(1 2 3 4 5) asOrderedCollection removeFromIndex:3 toIndex:6
"
"Modified: / 5.2.1999 / 23:22:07 / cg"
!
removeIdentical:anObject ifAbsent:exceptionBlock
"remove the first element which is identical to anObject;
if found, remove and return it;
if not, return the value from evaluating exceptionBlock.
Uses identity compare (==) to search for the element."
|index|
index := contentsArray identityIndexOf:anObject startingAt:firstIndex endingAt:lastIndex.
index ~~ 0 ifTrue:[
index := index - firstIndex + 1.
self removeFromIndex:index toIndex:index.
^ anObject
].
^ exceptionBlock value
"
#(1.0 2.0 3.0 4.0 5.0) asOrderedCollection remove:4 ifAbsent:'oops'
#(1.0 2.0 3.0 4.0 5.0) asOrderedCollection remove:4 ifAbsent:'oops'; yourself
#(1.0 2.0 3.0 4.0 5.0) asOrderedCollection removeIdentical:4 ifAbsent:'oops'
#(fee foo bar baz) asOrderedCollection removeIdentical:#fee; yourself
#(fee foo bar baz) asOrderedCollection removeIdentical:#foo; yourself
#(fee foo bar baz) asOrderedCollection removeIdentical:#baz; yourself
#(fee) asOrderedCollection removeIdentical:#fee; yourself
"
"Modified: 8.2.1997 / 18:57:43 / cg"
!
removeLast
"remove the last element from the collection; return the element"
|anObject
idx "{ Class: SmallInteger }" |
idx := lastIndex.
firstIndex > idx ifTrue:[
"error if collection is empty"
^ self emptyCollectionError.
].
anObject := contentsArray basicAt:idx.
"/ nil it (helps GC)
contentsArray basicAt:idx put:nil.
lastIndex := idx := idx - 1.
firstIndex > idx 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
"
"Modified: / 12.11.1997 / 17:58:57 / cg"
!
removeLast:n
"remove the last n elements from the collection;
Return a collection of removed elements."
|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
].
^ ret
"
(OrderedCollection withAll:#(1 2 3 4 5)) removeLast:2; yourself
(OrderedCollection withAll:#(1 2 3 4 5)) removeLast:0; yourself
(OrderedCollection withAll:#(1 2 3 4 5)) removeLast:6; yourself
(SortedCollection withAll:#(5 4 3 2 1)) removeLast:2; yourself
"
"Modified: 12.4.1996 / 13:39:12 / cg"
!
reset
"logically remove all elements from the collection.
Thats almost the same as #removeAll, but keeps the contentsArray.
Returns the receiver."
firstIndex := contentsArray size // 3 max: 1.
lastIndex := firstIndex - 1
! !
!OrderedCollection methodsFor:'converting'!
asArray
"return the receiver as an array."
^ contentsArray copyFrom:firstIndex to:lastIndex
"/ |newArray sz|
"/
"/ sz := self size.
"/ newArray := Array new:sz.
"/ newArray replaceFrom:1 to:sz with:contentsArray startingAt:firstIndex.
"/ ^ newArray
"
OrderedCollection new asArray
OrderedCollection new add:1;add:2;asArray
OrderedCollection new add:1;removeFirst;asArray
"
"
|o rnd|
o := OrderedCollection new.
rnd := Random new.
10000 timesRepeat:[
o add:rnd next.
].
Time millisecondsToRun:[o asArray]
"
"Modified: 13.4.1996 / 12:10:56 / cg"
!
asOrderedCollection
"return the receiver as an ordered collection"
"could be an instance of a subclass..."
self class == OrderedCollection ifTrue:[
^ self
].
^ super asOrderedCollection
! !
!OrderedCollection methodsFor:'copying'!
, aCollection
"return a new collection formed from concatenating the receiver with
the argument"
|newCollection|
newCollection := self copyEmpty:(self size + aCollection size).
self do:[:element |
newCollection add:element
].
aCollection do:[:element |
newCollection add:element
].
^ newCollection
"
#(1 2 3) asOrderedCollection , #(4 5 6) asOrderedCollection
#(1 2 3) asSortedCollection , #(99 101 100) asSortedCollection
"
!
copy
"return a new OrderedCollection containing the elements of the receiver."
"redefinition is a consequence of the implementation with a
separate array - otherwise we get a shallow copy of the
contents array, which is not what we want here"
^ self copyFrom:1 to:self size
!
copyEmpty
"return a copy of the receiver without any elements."
^ self copyEmpty:10
!
copyFrom:start to:stop
"return a new OrderedCollection containing the elements
from start to stop."
|newCollection sz|
sz := stop - start + 1.
newCollection := self copyEmptyAndGrow:sz. "must grow, otherwise replace fails"
newCollection replaceFrom:1 to:sz with:self startingAt:start.
^ newCollection
!
copyWith:newElement
"return a new collection containing the receivers elements
and the single new element, newElement.
This is different from concatentation, which expects another collection
as argument, but equivalent to copy-and-addLast."
|newCollection mySize newSize|
mySize := self size.
newSize := mySize + 1.
newCollection := self copyEmptyAndGrow:newSize. "must grow, otherwise replace fails"
newCollection replaceFrom:1 to:mySize with:self startingAt:1.
newCollection at:newSize put:newElement.
^newCollection
"
#(1 2 3 4 5) copyWith:$a
'abcdefg' copyWith:$h
'abcdefg' copyWith:'123' -- will fail: string cannot be stored into string
'abcdefg' copyWith:1 -- will fail: integer cannot be stored into string
"
!
postCopy
"have to copy the contentsArray too"
contentsArray := contentsArray shallowCopy
! !
!OrderedCollection methodsFor:'enumerating'!
collect:aBlock
"evaluate the argument, aBlock for every element in the collection
and return a collection of the results"
|newCollection
start "{ Class:SmallInteger }"
stop "{ Class:SmallInteger }" |
newCollection := self copyEmpty:(self size).
stop := lastIndex.
start := firstIndex.
start to:stop do:[:index |
newCollection add:(aBlock value:(contentsArray at:index)).
].
^ newCollection
"
#(1 2 3 4) asOrderedCollection collect:[:i | i * i]
#(1 2 3 4) asOrderedCollection collect:[:i | i even]
"
!
do:aBlock
"evaluate the argument, aBlock for every element in the collection."
contentsArray from:firstIndex to:lastIndex do:aBlock
!
keysAndValuesDo:aTwoArgBlock
"evaluate the argument, aBlock for every element in the collection,
passing both index and element as arguments."
|start "{ Class:SmallInteger }"
stop "{ Class:SmallInteger }"
idx "{ Class:SmallInteger }" |
stop := lastIndex.
start := firstIndex.
idx := 1.
start to:stop do:[:index |
aTwoArgBlock value:idx value:(contentsArray at:index).
idx := idx + 1.
]
"
#(10 20 30 40) asOrderedCollection keysAndValuesDo:[:index :value |
Transcript show:index; show:' '; showCR:value
]
"
"
|oc|
oc := #(10 20 30 40 50 60 70 80) asOrderedCollection.
oc removeFirst; removeFirst.
oc keysAndValuesDo:[:index :value |
Transcript show:index; show:' '; showCR:value
]
"
!
keysAndValuesReverseDo:aTwoArgBlock
"evaluate the argument, aBlock for every element in the collection,
passing both index and element as arguments."
|start "{ Class:SmallInteger }"
stop "{ Class:SmallInteger }"
idx "{ Class:SmallInteger }"|
stop := lastIndex.
start := firstIndex.
idx := (stop - start + 1).
stop to:start by: -1 do:[:index |
aTwoArgBlock value:idx value:(contentsArray at:index).
idx := idx - 1.
]
"
#(10 20 30 40) asOrderedCollection keysAndValuesReverseDo:[:index :value |
Transcript show:index; show:' '; showCR:value
]
"
"
|oc|
oc := #(10 20 30 40 50 60 70 80) asOrderedCollection.
oc removeFirst; removeFirst.
oc keysAndValuesReverseDo:[:index :value |
Transcript show:index; show:' '; showCR:value
]
"
!
reverseDo:aBlock
"evaluate the argument, aBlock for every element in the collection
procesing elements in reverse direction (i.e. starting with the last)"
contentsArray from:firstIndex to:lastIndex reverseDo:aBlock
! !
!OrderedCollection methodsFor:'filling & replacing'!
replaceFrom:start to:stop with:aCollection startingAt:repStart
"replace elements in the receiver between index start and stop,
with elements taken from replacementCollection starting at repStart.
Return the receiver.
Redefined here; can be done faster as the inherited operation."
|end|
end := stop + firstIndex - 1.
((start >= 1) and:[end <= lastIndex]) ifTrue:[
aCollection class == self class ifTrue:[
contentsArray
replaceFrom:(start + firstIndex - 1)
to:end
with:aCollection contentsArray
startingAt:(repStart + aCollection firstIndex - 1).
] ifFalse:[
contentsArray
replaceFrom:(start + firstIndex - 1)
to:end
with:aCollection
startingAt:repStart.
].
^ self
].
^ super replaceFrom:start to:stop with:aCollection startingAt:repStart
"
|c|
c := #(1 2 3 4 5 6) asOrderedCollection.
c replaceFrom:3 to:6 with:c startingAt:2.
c
"
"
|c|
c := #(1 2 3 4 5 6) asOrderedCollection.
c replaceFrom:3 to:5 with:c startingAt:4.
c
"
"Modified: / 28.1.1998 / 16:49:31 / cg"
! !
!OrderedCollection methodsFor:'grow & shrink'!
grow:newSize
"grow the receiver to newSize"
|oldSize newContents oldLast newLast|
oldSize := lastIndex - firstIndex + 1.
newSize ~~ oldSize ifTrue:[
newLast := firstIndex + newSize - 1.
newSize < oldSize ifTrue:[
oldLast := lastIndex.
lastIndex := newLast.
"
nil out rest, to give GC a chance to reclaim things
"
contentsArray from:lastIndex + 1 to:oldLast put:nil.
] ifFalse:[
newLast <= contentsArray size ifTrue:[
lastIndex := newLast.
^ self
].
newContents := Array basicNew:newSize.
newContents replaceFrom:1 to:oldSize with:contentsArray startingAt:firstIndex.
contentsArray := newContents.
firstIndex := 1.
lastIndex := newSize
]
]
! !
!OrderedCollection methodsFor:'inspecting'!
inspectorClass
"redefined to launch an OrderedCollectionInspector
(instead of the default InspectorView)."
^ OrderedCollectionInspectorView
"
(OrderedCollection withAll:#(3 2 1)) inspect
(OrderedCollection withAll:#(3 2 1)) removeFirst; yourself; inspect
#(0 8 15 3 99 2) asSortedCollection inspect
"
! !
!OrderedCollection methodsFor:'private'!
initContents:size
"setup the receiver-collection to hold size entries"
contentsArray := Array basicNew:size.
firstIndex := 1.
lastIndex := 0
!
makeRoomAtFront
"grow/shift the contents for more room at the beginning.
Does not change the logical size.
i.e.
#(1 2 3 4 5 6) -> #(nil 1 2 3 4 5 6)"
|newContents
oldSize "{ Class:SmallInteger }"
newSize "{ Class:SmallInteger }"
startIndex "{ Class:SmallInteger }"
sz "{ Class:SmallInteger }"|
oldSize := contentsArray size.
sz := lastIndex - firstIndex + 1.
((oldSize == 0) or:[sz == 0]) ifTrue:[
contentsArray := Array basicNew:3.
firstIndex := 2. lastIndex := 1.
^ self
].
"
if there is lots of room at the end (> 50%),
shift instead of growing. This helps collections
which get elements removed at the end and added at front.
"
oldSize > (sz * 2) ifTrue:[
startIndex := oldSize // 4.
startIndex > 1 ifTrue:[
contentsArray
replaceFrom:startIndex
to:startIndex + sz - 1
with:contentsArray
startingAt:1.
contentsArray from:1 to:(startIndex - 1) put:nil.
firstIndex := startIndex.
lastIndex := startIndex + sz - 1.
^ self
]
].
newSize := oldSize * 2.
newSize == 0 ifTrue:[ newSize := 3].
newContents := Array basicNew:newSize.
newContents
replaceFrom:(oldSize + 1)
to:newSize
with:contentsArray
startingAt:1.
contentsArray := newContents.
firstIndex := firstIndex + oldSize.
lastIndex := lastIndex + oldSize
"Created: 8.11.1995 / 12:47:49 / cg"
!
makeRoomAtIndex:whereToMakeEmptySlot
"grow the contents for inserting at whereToMakeEmptySlot.
The whereToMakeEmptySlot argument must be a physical index within the contentsArray.
If there is (plenty of) room at either end, elements are shifted inplace to create
an empty slot; otherwise, a new contentsArray is allocated.
Since this changes the logical size, the modified index is returned.
i.e.
#(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:3 -> #(1 2 nil 3 4 5 6)
#(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:1 -> #(nil 1 2 3 4 5 6)
#(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:7 -> #(1 2 3 4 5 6 nil)"
|newContents
newSize "{ Class:SmallInteger }"
oldSize "{ Class:SmallInteger }"
oneFourthOfSize "{ Class:SmallInteger }"
first "{ Class:SmallInteger }"
last "{ Class:SmallInteger }"
index "{ Class:SmallInteger }"
shiftLeft shiftRight|
oldSize := contentsArray size.
oneFourthOfSize := oldSize // 4.
index := whereToMakeEmptySlot.
first := firstIndex.
last := lastIndex.
((first > 1) and:[first > oneFourthOfSize]) ifTrue:[
"there is room (>25%) at the beginning"
shiftLeft := true.
index == first ifFalse:[
"/ so, we'd have to copy all elements before that index
"/ one slot towards the containers beginning ...
"/ if there is also space at the end, AND the number of
"/ elements after the index is smaller than the number before,
"/ copy the remaining elements. To copy the least possible number.
(last - index) < (index - first) ifTrue:[
last < (oneFourthOfSize * 3) ifTrue:[
shiftLeft := false.
shiftRight := true.
]
]
]
] ifFalse:[
last < (oneFourthOfSize * 3) ifTrue:[
shiftRight := true
]
].
shiftLeft == true ifTrue:[
"there is room (>25%) at the beginning"
index == first ifFalse:[
contentsArray
replaceFrom:(first - 1)
to:(index - 2)
with:contentsArray
startingAt:first.
contentsArray at:index-1 put:nil.
].
firstIndex := first - 1.
^ index - 1
].
shiftRight == true ifTrue:[
"there is room (>25%) at the end"
last := last + 1.
index == last ifFalse:[
contentsArray
replaceFrom:(index + 1)
to:last
with:contentsArray
startingAt:index.
contentsArray at:index put:nil
].
lastIndex := last.
^ index
].
newSize := oldSize * 2.
newContents := Array basicNew:newSize.
index ~~ first ifTrue:[
newContents
replaceFrom:1
to:index - first
with:contentsArray
startingAt:first.
].
index <= last ifTrue:[
newContents
replaceFrom:index - first + 2
to:(last - first + 2)
with:contentsArray
startingAt:index.
].
contentsArray := newContents.
firstIndex := 1.
lastIndex := last - first + 2.
"/ return the modified index
^ index - (first - firstIndex).
"Modified: 12.4.1996 / 17:18:58 / cg"
!
makeRoomAtIndex:whereToMakeEmptySlots for:howMany
"grow the contents for inserting at whereToMakeEmptySlot.
The whereToMakeEmptySlot argument must be a physical index within the contentsArray.
If there is (plenty of) room at either end, elements are shifted inplace to create
an empty slot; otherwise, a new contentsArray is allocated.
Since this changes the logical size, the modified index is returned.
i.e.
#(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:3 for:2 -> #(1 2 nil nil 3 4 5 6)
#(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:1 for:2 -> #(nil nil 1 2 3 4 5 6)
#(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:7 for:2 -> #(1 2 3 4 5 6 nil nil)"
|newContents
newSize "{ Class:SmallInteger }"
oldSize "{ Class:SmallInteger }"
oneFourthOfSize "{ Class:SmallInteger }"
first "{ Class:SmallInteger }"
last "{ Class:SmallInteger }"
index "{ Class:SmallInteger }"
shiftLeft shiftRight|
oldSize := contentsArray size.
oneFourthOfSize := oldSize // 4.
index := whereToMakeEmptySlots.
first := firstIndex.
last := lastIndex.
shiftLeft := shiftRight := false.
((first > howMany) and:[first > oneFourthOfSize]) ifTrue:[
"there is room (>25%) at the beginning"
shiftLeft := true.
] ifFalse:[
((last + howMany) <= oldSize
and:[last < (oneFourthOfSize * 3)]) ifTrue:[
shiftRight := true
]
].
shiftLeft == true ifTrue:[
"there is room at the beginning"
index == first ifFalse:[
contentsArray
replaceFrom:(first - howMany)
to:(index - howMany - 1)
with:contentsArray
startingAt:first.
contentsArray from:index-howMany to:index-1 put:nil.
].
firstIndex := first - howMany.
^ index - howMany
].
shiftRight == true ifTrue:[
"there is room at the end"
last := last + howMany.
index == last ifFalse:[
contentsArray
replaceFrom:(index + howMany)
to:last
with:contentsArray
startingAt:index.
contentsArray from:index to:index+howMany-1 put:nil
].
lastIndex := last.
^ index
].
newSize := oldSize * 2.
[newSize < (oldSize+howMany)] whileTrue:[
newSize := newSize * 2
].
newContents := Array basicNew:newSize.
index > first ifTrue:[
newContents
replaceFrom:1
to:index - first
with:contentsArray
startingAt:first.
].
index <= last ifTrue:[
newContents
replaceFrom:index - first + howMany + 1
to:(last - first + howMany + 1)
with:contentsArray
startingAt:(index).
].
contentsArray := newContents.
firstIndex := 1.
lastIndex := last - first + howMany + 1.
"/ return the modified index
^ index - (first - firstIndex).
"Modified: 15.4.1997 / 12:34:16 / cg"
!
makeRoomAtLast
"grow/shift the contents for more room at the end.
Does not change the logical size.
i.e.
#(1 2 3 4 5 6) -> #(1 2 3 4 5 6 nil)"
|newContents
oldSize "{ Class:SmallInteger }"
newSize "{ Class:SmallInteger }"
startIndex "{ Class:SmallInteger }"
sz "{ Class:SmallInteger }"|
oldSize := contentsArray size.
sz := lastIndex - firstIndex + 1.
"
if there is lots of room at the beginning (> 50%),
shift instead of growing. This helps collections which get
elements removed at front and added at the end.
"
oldSize > (sz * 2) ifTrue:[
startIndex := firstIndex // 4.
startIndex == 0 ifTrue:[
startIndex := 1
].
contentsArray
replaceFrom:startIndex
to:startIndex + sz - 1
with:contentsArray
startingAt:firstIndex.
contentsArray from:startIndex + sz to:lastIndex put:nil.
firstIndex := startIndex.
lastIndex := startIndex + sz - 1.
^ self
].
newSize := oldSize * 2.
newSize == 0 ifTrue:[newSize := 3].
newContents := Array basicNew:newSize.
newContents
replaceFrom:1
to:oldSize
with:contentsArray
startingAt:1.
contentsArray := newContents
!
setFirstIndex:newFirstIndex lastIndex:newLastIndex
"set first and last index"
firstIndex := newFirstIndex.
lastIndex := newLastIndex.
! !
!OrderedCollection methodsFor:'private accessing'!
contentsArray
"return the orderedCollections underlying contentsArray.
The actual elements are found here starting at firstIndex,
and ending at lastIndex."
^ contentsArray
!
firstIndex
"return the index of my first element in my underlying contentsArray.
The actual elements are found starting this index,
and ending at lastIndex."
^ firstIndex
! !
!OrderedCollection methodsFor:'queries'!
capacity
"return the number of elements, that the receiver is
prepared to take.
Not used by the system; added for ST-80 compatibility."
^ contentsArray size
!
isEmpty
"return true, if the receiver has no elements"
^ lastIndex < firstIndex
!
isFixedSize
"return true if the receiver cannot grow - this will vanish once
Arrays and Strings learn how to grow ..."
^ false
!
notEmpty
"return true, if the receiver has any elements"
^ lastIndex >= firstIndex
!
size
"return the number of elements in the collection"
^ lastIndex - firstIndex + 1
! !
!OrderedCollection methodsFor:'searching'!
identityIndexOf:anObject
"return the index of anObject or 0 if not found. Compare using =="
|index|
index := contentsArray
identityIndexOf:anObject
startingAt:firstIndex
endingAt:lastIndex.
index == 0 ifTrue:[^ 0].
^ index - firstIndex + 1
"Modified: 12.4.1996 / 17:58:25 / cg"
!
identityIndexOf:anObject startingAt:startIndex
"return the index of anObject, starting search at startIndex.
Compare using ==; return 0 if not found in the collection"
|index|
index := contentsArray
identityIndexOf:anObject
startingAt:(startIndex + firstIndex - 1)
endingAt:lastIndex.
index == 0 ifTrue:[^ 0].
^ index - firstIndex + 1
"Modified: 12.4.1996 / 17:58:19 / cg"
!
indexOf:anObject
"return the index of anObject or 0 if not found in the collection.
Compare using ="
|index|
index := contentsArray
indexOf:anObject
startingAt:firstIndex
endingAt:lastIndex.
index == 0 ifTrue:[^ 0].
^ index - firstIndex + 1
"
|c|
c := OrderedCollection new:10000.
c add:1; add:2; add:3.
c indexOf:99
"
"Modified: 12.4.1996 / 17:57:54 / cg"
!
indexOf:anObject startingAt:startIndex
"return the index of anObject, starting search at startIndex.
Compare using =; return 0 if not found in the collection"
|index|
index := contentsArray
indexOf:anObject
startingAt:(startIndex + firstIndex - 1)
endingAt:lastIndex.
index == 0 ifTrue:[^ 0].
^ index - firstIndex + 1
"
|c|
c := OrderedCollection new:10000.
c add:1; add:2; add:3.
c indexOf:4 startingAt:5
"
"Modified: 12.4.1996 / 17:58:53 / cg"
! !
!OrderedCollection methodsFor:'testing'!
includes:anObject
"return true if anObject is in the collection. Compare using ="
^ (contentsArray
indexOf:anObject
startingAt:firstIndex
endingAt:lastIndex) ~~ 0
"Modified: 12.4.1996 / 17:57:27 / cg"
!
includesIdentical:anObject
"return true if anObject is in the collection. Compare using =="
^ (contentsArray
identityIndexOf:anObject
startingAt:firstIndex
endingAt:lastIndex) ~~ 0
"Modified: 12.4.1996 / 17:57:09 / cg"
!
isOrderedCollection
"return true, if the receiver is some kind of ordered collection (or list etc);
true is returned here - the method is only redefined in Object."
^ true
! !
!OrderedCollection class methodsFor:'documentation'!
version
^ '$Header: /cvs/stx/stx/libbasic/OrderedCollection.st,v 1.74 2000-06-19 14:52:17 ps Exp $'
! !