Smalltalk/X Webserver

Documentation of class 'OrderedCollection':

Class: OrderedCollection

Inheritance
Description
Class protocol
- initialization
- instance creation
Instance protocol
Examples

Inheritance:

   Object
   |
   +--Collection
      |
      +--SequenceableCollection
         |
         +--OrderedCollection
            |
            +--AutoResizingOrderedCollection
            |
            +--ChangeSet
            |
            +--Comanche::SwikiFileVersions
            |
            +--HandlerCollection
            |
            +--ImageSequence
            |
            +--List
            |
            +--SortedCollection
            |
            +--Stack
            |
            +--StringCollection
            |
            +--SunRPC::SimulatedDirectory
            |
            +--TraitComposition
            |
            +--WeakOrderedCollection
            |
            +--XML::NodeSet

Package:: stx:libbasic

Category:: Collections-Sequenceable

Version:: rev: 1.185 date: 2024/04/19 15:05:34; user: cg; file: OrderedCollection.st directory: libbasic; module: stx stc-classLibrary: libbasic

Description:

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    { InstanceVariable: firstIndex Class: SmallInteger }

    lastIndex       <SmallInteger>  index of last valid element     { InstanceVariable: lastIndex Class: SmallInteger }

[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 at the same end,
     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 in my opinion.
    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)
    access first:                   O(1)
    access last:                    O(1)
    insertion at either end:        O(1) amortized
    removal at either end:          O(1)
    insertion in the middle:        O(n)
    removal in the middle:          O(n)
    searching:                      O(n)
    min/max:                        O(n)

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

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.

new: size withAll: element

return a new collection of size, where all elements are
initialized to element.

Usage example(s):

     OrderedCollection new:10 withAll:1234

newFrom: aCollection

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

Usage example(s):

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

newLikelyToRemainEmpty

marked as obsolete by Stefan Vogel at 8-Dez-2022

** This is an obsolete interface - do not use it (it may vanish in future versions) **

newWith: aCollection from: startIndex to: endIndex

return a new OrderedCollection filled with a slice of elements from aCollection

Usage example(s):

     OrderedCollection newWith:#(10 20 30 40 50 60 70 80) from:3 to:6

newWithCapacity: size

create a new, empty OrderedCollection with a preallocated physical size.
Different from #new: and redefined for the StringCollection subclass,
where #new: allocates size empty lines.

Usage example(s):

	OrderedCollection new:10.
	StringCollection new:10.
	OrderedCollection newWithCapacity:10.
	StringCollection newWithCapacity:10.

Instance protocol:

Compatibility-Squeak

overlappingPairsCollect: aBlock
( an extension from the stx:libcompat package ): Answer the result of evaluating aBlock with all of the overlapping pairs of my elements. Override superclass in order to use addLast:, not at:put:.

accessing

at: anInteger

return the element at index, anInteger

at: anInteger ifAbsent: exceptionValue

return the element at index, anInteger.
If the index is invalid, return the value from exceptionValue

at: anInteger put: anObject

set the element at index, to be anInteger.
Return anObject (sigh).

first

return the first element

Usage example(s):

     (OrderedCollection withAll:#(1 2 3 4 5)) first
     (SortedCollection withAll:#(5 4 3 2 1)) first

firstOrNil

return the first element or nil, if empty.

Usage example(s):

     (OrderedCollection withAll:#(1 2 3 4 5)) firstOrNil
     (SortedCollection withAll:#()) firstOrNil

last

return the last element

Usage example(s):

     (OrderedCollection withAll:#(1 2 3 4 5)) last
     (SortedCollection withAll:#(5 4 3 2 1)) last

lastOrNil

return the last element or nil if I am empty

Usage example(s):

     (OrderedCollection withAll:#(1 2 3 4 5)) lastOrNil
     (OrderedCollection withAll:#(1 2 3 4 5 nil)) lastOrNil
     (OrderedCollection new) lastOrNil
     (SortedCollection withAll:#(5 4 3 2 1)) lastOrNil

adding & removing

add: anObject

add the argument, anObject to the end of the collection
Return the argument, anObject.

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here'

add: newObject after: oldObject

insert the argument, newObject after oldObject;
oldObject is searched by equality.
If oldObject is not in the receiver, report an error,
otherwise return the argument, anObject.

add: newObject afterIdentical: oldObject

insert the argument, newObject after oldObject;
oldObject is searched by identity.
If oldObject is not in the receiver, report an error,
otherwise return the argument, anObject.

add: anObject afterIndex: index

insert the argument, anObject to become located at index.
Return the receiver (sigh - ST-80 compatibility).

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' afterIndex:2

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' afterIndex:4

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' afterIndex:0

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' afterIndex:5

add: newObject before: oldObject

insert the argument, newObject before oldObject;
oldObject is searched by equality.
If oldObject is not in the receiver, report an error,
otherwise return the argument, anObject.

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' before:3.
     c      => OrderedCollection(4 'here' 3 2 1)

Usage example(s):

     |c|
     c := #(4 3.0 2 1) asOrderedCollection.
     c add:'here' before:3.
     c      => OrderedCollection(4 'here' 3.0 2 1)

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' before:3.0.
     c      => OrderedCollection(4 'here' 3 2 1)

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' before:3.
     c add:'here' before:5.
     c      => error

add: newObject beforeIdentical: oldObject

insert the argument, newObject before oldObject;
oldObject is searched by identity.
If oldObject is not in the receiver, report an error,
otherwise return the argument, anObject.

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' beforeIdentical:3.
     c      => OrderedCollection(4 'here' 3 2 1)

Usage example(s):

     |c|
     c := #(4 3.0 2 1) asOrderedCollection.
     c add:'here' beforeIdentical:3.
     c      => error not found

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' beforeIdentical:3.0.
     c      => error not found

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' beforeIdentical:3.
     c add:'here' beforeIdentical:5.
     c      => error not found

add: anObject beforeIndex: index

insert the argument, anObject to become located at index.
Return the receiver (sigh - ST-80 compatibility).

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' beforeIndex:3

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' beforeIndex:1

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c add:'here' beforeIndex:5

addAll: aCollection

add all elements of the argument, aCollection to the receiver.
Returns the argument, aCollection (sigh).

Usage example(s):

	self new addAll:#(1 2 3) asSet; yourself.
	self new addAll:#(); yourself

addAll: aCollection afterIndex: index

insert the argument, anObject to become located after index.
Return the receiver (sigh - ST-80 compatibility).

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c addAll:#(10 20 30) afterIndex:2

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c addAll:#(10 20 30) afterIndex:4

Usage example(s):

     |c|
     c := #(4 3 2 1) asOrderedCollection.
     c addAll:#(10 20 30) afterIndex:0

addAll: aCollection beforeIndex: index

insert all elements of the argument, anObject to become located at index.
The collection may be unordered, but then the order of the sliced-in elements
is undefined.
Return the receiver.

Usage example(s):

     |c|
     c := #(1 2 3 4) asOrderedCollection.
     c addAll:'here' beforeIndex:3

Usage example(s):

     |c|
     c := #(1 2 3 4) asOrderedCollection.
     c removeFirst.
     c addAll:'here' beforeIndex:3

Usage example(s):

     |c|
     c := #(1 2 3 4) asOrderedCollection.
     c addAll:'here' beforeIndex:1

Usage example(s):

     |c|
     c := #(1 2 3 4) asOrderedCollection.
     c addAll:'here' beforeIndex:5

Usage example(s):

     |c|
     c := #(1 2 3 4) asOrderedCollection.
     c addAll:('hello' asSet) beforeIndex:3

addAll: aCollection from: startIndex to: endIndex beforeIndex: index

insert elements start to stop from the argument
Return the receiver.

addAllFirst: aCollection

insert all elements of the argument, aCollection at the beginning
of the receiver. Returns the argument, aCollection.

Usage example(s):

     |c|
     c := #(1 2 3 4) asOrderedCollection.
     c addAllFirst:#(10 20 30).
     c                                    => OrderedCollection(10 20 30 1 2 3 4)

Usage example(s):

     |c|
     c := #(1 2 3 4) asOrderedCollection.
     c addAllFirst:#().
     c                                    => OrderedCollection(1 2 3 4)

Usage example(s):

     |c|
     c := #() asOrderedCollection.
     c addAllFirst:#(10 20 30).
     c                                    => OrderedCollection(10 20 30)

Usage example(s):

     |c|
     c := #() asOrderedCollection.
     c addAllFirst:#().
     c                                    => OrderedCollection()

addFirst: anObject

add the argument, anObject to the beginning of the collection.
Return the argument, anObject.

Usage example(s):

     |c|
     c := #(1 2 3 4) asOrderedCollection.
     c addFirst:'here'.
     c

Usage example(s):

     |c|
     c := #() asOrderedCollection.
     c addFirst:'here'.
     c

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.
Destructive: modifies the receiver.
Returns the receiver.

dropAllSuchThat: 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.
Destructive: modifies the receiver.
Similar to #removeAllSuchThat:, but
returns the receiver instead of a collection containing the removed elements.

Performance:
this is an O(N) algorithm (the receiver's elements are scanned once).

Usage example(s):

     |coll|

     coll := OrderedCollection withAll:(1 to:10).
     coll dropAllSuchThat:[:el | el even].
     Transcript show:'coll: '; showCR:coll

Usage example(s):

     |coll1 coll2|

     Transcript showCR:'no element removed:'.

     coll1 := OrderedCollection withAll:(1 to:1000).
     Transcript show:'  (1000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll1 copy dropAllSuchThat:[:el | el == 500] ]
	]).

     coll2 := OrderedCollection withAll:(1 to:10000).
     Transcript show:'  (10000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll2 copy dropAllSuchThat:[:el | el == 5000] ]
	]).

     coll2 := OrderedCollection withAll:(1 to:50000).
     Transcript show:'  (50000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll2 copy dropAllSuchThat:[:el | el == 25000] ]
	]).

     Transcript showCR:'small number of elements removed:'.

     coll1 := OrderedCollection withAll:(1 to:1000).
     Transcript show:'  (1000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll1 copy dropAllSuchThat:[:el | el between:500 and:550] ]
	]).

     coll2 := OrderedCollection withAll:(1 to:10000).
     Transcript show:'  (10000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll2 copy dropAllSuchThat:[:el | el between:5000 and:5050] ]
	]).

     coll2 := OrderedCollection withAll:(1 to:50000).
     Transcript show:'  (50000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll2 copy dropAllSuchThat:[:el | el between:25000 and:25050] ]
	]).

     Transcript showCR:'many elements removed:'.

     coll1 := OrderedCollection withAll:(1 to:1000).
     Transcript show:'  (1000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll1 copy dropAllSuchThat:[:el | el even] ]
	]).

     coll2 := OrderedCollection withAll:(1 to:10000).
     Transcript show:'  (10000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll2 copy dropAllSuchThat:[:el | el even] ]
	]).

     coll2 := OrderedCollection withAll:(1 to:50000).
     Transcript show:'  (50000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll2 copy dropAllSuchThat:[:el | el even] ]
	]).

dropFirst: n

remove the first n elements from the collection;
Return the receiver.
Destructive: modifies the receiver.
Similar to removeFirst:, but returns the receiver.
Use this if you are not interested in the removed elements.

Usage example(s):

     (OrderedCollection withAll:#(1 2 3 4 5)) dropFirst:2   => OrderedCollection(3 4 5)
     (OrderedCollection withAll:#(1 2 3 4 5)) removeFirst:0 => #()
     OrderedCollection new removeFirst:2                    => error
     (OrderedCollection withAll:#(1 2 3 4 5)) removeFirst:6 => error

     (SortedCollection withAll:#(5 4 3 2 1)) dropFirst:2    => SortedCollection(3 4 5)
     (SortedCollection withAll:#(5 4 3 2 1)) removeFirst:2  => #(1 2)

dropLast: n

remove the last n elements from the receiver collection.
Destructive: modifies the receiver.
Similar to removeLast:, but returns the receiver.
Use this if you are not interested in the removed elements.

Usage example(s):

     (OrderedCollection withAll:#(1 2 3 4 5)) dropLast:2    => OrderedCollection(1 2 3)
     (OrderedCollection withAll:#(1 2 3 4 5)) dropLast:0    => OrderedCollection(1 2 3 4 5)
     (OrderedCollection withAll:#(1 2 3 4 5)) dropLast:6    => error

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.
Destructive: modifies the receiver.
Uses equality compare (=) to search for the element.

Usage example(s):

     #(1 2 3 4 5) asOrderedCollection remove:9 ifAbsent:[self halt]; yourself
     #(1 2 3 4 5) asOrderedCollection remove:3 ifAbsent:[self halt]; yourself

     #(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'

removeAll

remove all elements from the collection.
Returns the receiver.
Destructive: modifies the receiver.

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.
Destructive: modifies the receiver.
Return a collection containing the removed elements.
Differs from #dropAllSuchThat:
dropAllSuchThat: returns self instead of the removed elements.

Performance:
this is an O(N) algorithm (the receiver's elements are scanned once).

Usage example(s):

     |coll|

     coll := OrderedCollection withAll:(1 to:10).
     Transcript show:'removed: '; showCR:(coll removeAllSuchThat:[:el | el even]).
     Transcript show:'coll: '; showCR:coll

Usage example(s):

     |coll1 coll2|

     Transcript showCR:'no element removed:'.

     coll1 := OrderedCollection withAll:(1 to:1000).
     Transcript show:'  (1000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll1 copy removeAllSuchThat:[:el | el == 500] ]
	]).

     coll2 := OrderedCollection withAll:(1 to:10000).
     Transcript show:'  (10000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el == 5000] ]
	]).

     coll2 := OrderedCollection withAll:(1 to:50000).
     Transcript show:'  (50000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el == 25000] ]
	]).

     Transcript showCR:'small number of elements removed:'.

     coll1 := OrderedCollection withAll:(1 to:1000).
     Transcript show:'  (1000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll1 copy removeAllSuchThat:[:el | el between:500 and:550] ]
	]).

     coll2 := OrderedCollection withAll:(1 to:10000).
     Transcript show:'  (10000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el between:5000 and:5050] ]
	]).

     coll2 := OrderedCollection withAll:(1 to:50000).
     Transcript show:'  (50000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el between:25000 and:25050] ]
	]).

     Transcript showCR:'many elements removed:'.

     coll1 := OrderedCollection withAll:(1 to:1000).
     Transcript show:'  (1000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll1 copy removeAllSuchThat:[:el | el even] ]
	]).

     coll2 := OrderedCollection withAll:(1 to:10000).
     Transcript show:'  (10000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el even] ]
	]).

     coll2 := OrderedCollection withAll:(1 to:50000).
     Transcript show:'  (50000) - '; showCR:(
	Time millisecondsToRun:[
	    100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el even] ]
	]).

removeFirst

remove the first element from the collection; return the element.
If there is no element in the receiver collection, raise an error.
Destructive: modifies the receiver

removeFirst: n

remove the first n elements from the collection;
Return a collection containing the removed elements.
Destructive: modifies the receiver

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.
Destructive: modifies the receiver

removeFrom: startIndex to: stopIndex

added for ST-80 compatibility.
Same as removeFromIndex:toIndex:.

removeFromIndex: startIndex toIndex: stopIndex

remove the elements stored under startIndex up to and including
the elements under stopIndex.
Destructive: modifies the receiver
Return the receiver.
Returning the receiver here is a historic leftover - it may change.
Please use yourself in a cascade, if you need the receiver's value
when using this method.

Usage example(s):

do not grow when doing #removeFromIndex:(size + x)

Usage example(s):

     #(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
     #(1 2 3 4 5 6 7 8 9) asOrderedCollection removeFromIndex:33 toIndex:9

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.
Destructive: modifies the receiver.
Uses identity compare (==) to search for the element.

Usage example(s):

     #(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
     #(fee) asOrderedCollection removeIdentical:#foo; yourself

removeIndices: aSortedCollectionOfIndices

remove all elements stored in any of aSortedCollectionOfIndices,
which must be sorted and sequenceable.
Destructive: modifies the receiver.
Returns a collection of removed elements.

Performance:
this is an O(N) algorithm (N being the size of the receiver).

This could be done much better, especially if the removed indices are
at either end of the receiver. However, as it is currently not heavily used,
I leave that as an exercise to the brave reader...

Usage example(s):

     |coll|

     coll := OrderedCollection withAll:(1 to:10).
     Transcript showCR:(coll removeIndices:#(1 5 7)).
     Transcript showCR:coll

removeLast

remove the last element from the collection.
Return the removed element.
Destructive: modifies the receiver

removeLast: n

remove the last n elements from the receiver collection.
Destructive: modifies the receiver.
Return a collection of removed elements.

Usage example(s):

     (OrderedCollection withAll:#(1 2 3 4 5)) removeLast:2              => #(4 5)
     (OrderedCollection withAll:#(1 2 3 4 5)) removeLast:2; yourself    => OrderedCollection(1 2 3)
     (OrderedCollection withAll:#(1 2 3 4 5)) removeLast:0              => #()
     (OrderedCollection withAll:#(1 2 3 4 5)) removeLast:0; yourself    => OrderedCollection(1 2 3 4 5)
     (OrderedCollection withAll:#(1 2 3 4 5)) removeLast:6; yourself    => error
     (SortedCollection withAll:#(5 4 3 2 1)) removeLast:2               => #(4 5)
     (SortedCollection withAll:#(5 4 3 2 1)) removeLast:2; yourself     => SortedCollection(1 2 3)
     (SortedCollection withAll:#(5 4 3 2 1)) removeLast:0               => #()
     (SortedCollection withAll:#(5 4 3 2 1)) removeLast:0; yourself     => SortedCollection(1 2 3 4 5)

removeLastIfAbsent: exceptionValue

remove the last element from the collection.
Return the removed element or the value from exceptionValue if empty.
Destructive: modifies the receiver

Usage example(s):

     OrderedCollection new removeLastIfAbsent:nil

reset

logically remove all elements from the collection.
That's almost the same as #removeAll, but keeps the contentsArray.
Returns the receiver.

converting

asArray

return the receiver as an array.

Usage example(s):

     |o rnd|

     o := OrderedCollection new.
     rnd := Random new.
     10000 timesRepeat:[
         o add:rnd next.
     ].
     Time millisecondsToRun:[o asArray]

asNewOrderedCollection

return the receiver as an ordered collection.
Make sure to return a unique new OrderedCollection

Usage example(s):

	|s|
	s := #(1 2 3 4) asOrderedCollection.
	self assert:(s ~~ s asNewOrderedCollection).
	self assert:(s = s asNewOrderedCollection).

asOrderedCollection

return the receiver as an ordered collection.
Notice: this returns the receiver. Use asNewOrderedCollection, if you intent to
modify the returned collection.

copying

, aCollection

return a new collection formed from concatenating the receiver with the argument

Usage example(s):

     #(1 2 3) asOrderedCollection , #(4 5 6) asOrderedCollection
     #(1 3 5) asSortedCollection , #(6 4 2) asSortedCollection
     #(1 3 5) asSortedCollection , #(6 4 2) asOrderedCollection
     #(1 3 5) asSortedCollection , (#(6 4 2) asSortedCollection:[:a :b| a > b])

copy

return a new OrderedCollection containing the elements of the receiver.

Usage example(s):

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

copyWithoutDuplicates

return a new orderedCollection containing my entries,
but not any duplicates

Usage example(s):

     #(7 1 2 3 2 3 4 5 2 3 6 7 3 5 1) asOrderedCollection copyWithoutDuplicates

copying-private

postCopy: have to copy the contentsArray too

enumerating

collect: aBlock

evaluate the argument, aBlock for every element in the collection
and return a collection of the results

Usage example(s):

     #(1 2 3 4) asOrderedCollection collect:[:i | i * i]
     #(1 2 3 4) asOrderedCollection collect:[:i | i even]

collect: collectBlock thenSelect: selectBlock

combination of collect followed by select;
redefined to avoid the creation of an intermediate (garbage) collection.

Usage example(s):

     #(1 2 3 4) asOrderedCollection collect:[:i | i * i] thenSelect:[:each | each > 5]
     ( #(1 2 3 4) asOrderedCollection collect:[:i | i * i]) select:[:each | each > 5]

     |coll|
     coll := #(1 2 3 4) asOrderedCollection.
     Time millisecondsToRun:[
	100000 timesRepeat:[
	    coll collect:[:i | i * i] thenSelect:[:each | each > 5]
	]
     ]

     |coll|
     coll := #(1 2 3 4) asOrderedCollection.
     Time millisecondsToRun:[
	100000 timesRepeat:[
	    ( coll collect:[:i | i * i]) select:[:each | each > 5]
	]
     ]

do: aBlock

evaluate the argument, aBlock for every element in the collection.

keysAndValuesDo: aTwoArgBlock

evaluate the argument, aBlock for every element in the collection,
passing both index and element as arguments.

Usage example(s):

     #(10 20 30 40) asOrderedCollection keysAndValuesDo:[:index :value |
	Transcript show:index; show:' '; showCR:value
     ]

Usage example(s):

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

Usage example(s):

     #(10 20 30 40) asOrderedCollection keysAndValuesReverseDo:[:index :value |
	Transcript show:index; show:' '; showCR:value
     ]

Usage example(s):

     |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
processing elements in reverse direction (i.e. starting with the last)

select: selectBlock thenCollect: collectBlock

combination of select followed by collect;
redefined to avoid the creation of an intermediate (garbage) collection.

Usage example(s):

     #(1 2 3 4 5 6 7 8) asOrderedCollection
	select:[:each | each > 5] thenCollect:[:i | i * i]
     ( #(1 2 3 4 5 6 7 8) asOrderedCollection
	select:[:each | each > 5]) collect:[:i | i * i]

     |coll|
     coll := #(1 2 3 4 5 6 7 8) asOrderedCollection.
     Time millisecondsToRun:[
	100000 timesRepeat:[
	    coll select:[:each | each > 5] thenCollect:[:i | i * i]
	]
     ]

     |coll|
     coll := #(1 2 3 4 5 6 7 8) asOrderedCollection.
     Time millisecondsToRun:[
	100000 timesRepeat:[
	    ( coll select:[:each | each > 5]) collect:[:i | i * i]
	]
     ]

filling & replacing

replaceFrom: start to: stop with: aCollection startingAt: repStart

replace elements in the receiver between index start and stop,
with elements taken from aCollection starting at repStart.
Return the receiver.
Redefined here; can be done faster as the inherited operation.

Usage example(s):

     |c1 c2|

     c1 := #(1 2 3 4 5 6) asOrderedCollection.
     c2 := #(a b c d e f) asOrderedCollection.
     c2 replaceFrom:3 to:6 with:c1.
     c2

Usage example(s):

     |c1 c2|

     c1 := #(1 2 3 4 5 6) asOrderedCollection.
     c2 := #(a b c d e f) asOrderedCollection.
     c2 replaceFrom:3 to:6 with:c1 startingAt:2.
     c2

Usage example(s):

     |c|

     c := #(1 2 3 4 5 6) asOrderedCollection.
     c replaceFrom:3 to:6 with:c startingAt:2.
     c

Usage example(s):

     |c|

     c := #(1 2 3 4 5 6) asOrderedCollection.
     c replaceFrom:3 to:5 with:c startingAt:4.
     c

grow & shrink

compress

compress the contentsArray to the minimum required size

Usage example(s):

     |oc|

     oc := OrderedCollection new.
     self assert:(oc size == 0).
     oc ensureCapacity:10.
     self assert:(oc size == 0).
     self assert:(oc asArray = #()).
     oc add:123.
     self assert:(oc size == 1).
     self assert:(oc asArray = #(123)).
     oc compress.
     self assert:(oc size == 1).
     self assert:(oc asArray = #(123)).

Usage example(s):

	self allInstances do:[:eachOc| eachOc compress].

ensureCapacity: newCapacity

ensure that the underlying container has at least newCapacity
this does NOT change the receiver's logical size, but instead ensures
that no container-allocations are needed until newCapacity elements are
logically contained (i.e. it ensures a reserve).
Use this if it is known in advance, that more elements will be added in the
near future

Usage example(s):

     |oc|

     oc := OrderedCollection new.
     self assert:(oc size == 0).
     oc ensureCapacity:10.
     self assert:(oc size == 0).
     self assert:(oc asArray = #()).
     oc add:123.
     self assert:(oc size == 1).
     self assert:(oc asArray = #(123)).
     oc ensureCapacity:100.
     self assert:(oc size == 1).
     self assert:(oc asArray = #(123)).

ensureSizeAtLeast: minSize

ensure that the size is at least minSize.
If the receiver's size is smaller, grow the receiver to minSize,
filling new slots with nil.
Otherwise, if the size is already >= minSize, leave the receiver unchanged.

Usage example(s):

     |oc|

     oc := OrderedCollection new.
     oc ensureSizeAtLeast:10.
     oc at:10 put:10.
     oc add:11.
     oc at:11.
     oc ensureSizeAtLeast:20.
     oc at:20 put:20.
     oc.

grow: newSize

grow the receiver to newSize.
This only logically changes the receiver's size;
the underlying contentsArray is kept if possible
(except if growing to a zero size, or too small for newSize)

Usage example(s):

     |oc|

     oc := OrderedCollection new.
     self assert:(oc size == 0).
     oc grow:10.
     self assert:(oc size == 10).
     self assert:(oc asArray = #(nil nil nil nil nil nil nil nil nil nil)).

possiblyShrink

e'shrink from {capacity}' _errorPrintCR.

initialization

initContents: size: setup the receiver-collection to hold size entries
initialize: this is not sent by OrderedCollection methods,
But implemented here for superclasses that do not know about #initContents:

inspecting

inspector2GraphTabUseful
( an extension from the stx:libtool package ): (comment from inherited method)
is a graph tab useful (in general for this type of collection)?

misc ui support

inspectorClass
( an extension from the stx:libtool package ): redefined to launch an OrderedCollectionInspector
(instead of the default InspectorView).

private

containerClass: the class of the underlying container.
Here Array; redefined in WeakOrderedCollection to use a WeakArray
makeRoomAtFront: grow/shift the contents for more room at the beginning.
Does not change the logical size.
i.e. the contents array is changed from:
#(1 2 3 4 5 6) -> #(nil 1 2 3 4 5 6)
and the start/stopIndices are adjusted as required
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)
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 howMany empty slots; 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; yourself -> #(1 2 nil nil 3 4 5 6)
#(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:1 for:2; yourself -> #(nil nil 1 2 3 4 5 6)
#(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:7 for:2; yourself -> #(1 2 3 4 5 6 nil nil)
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)
setFirstIndex: newFirstIndex lastIndex: newLastIndex: set first and last index
setIndices: added for VW compatibility: set the indices for an empty collection

private-accessing

contentsArray: return the orderedCollections underlying contentsArray.
The actual elements are found here starting at firstIndex,
and ending at lastIndex.
firstIndex: return the index of my first element in my underlying contentsArray.
The actual elements are found starting this index,
and ending at lastIndex.

queries

capacity: return the number of elements, that the receiver is prepared to take
without growing.
Notice, that OCs do automatically resize as required,
so knowing the capacity is of no real use.
includes: anObject: return true if anObject is in the collection. Compare using =
includesIdentical: anObject: return true if anObject is in the collection. Compare using ==
isEmpty: return true, if the receiver has no elements
isEmptyOrNil: return true, if the receiver has no elements
notEmpty: return true, if the receiver has any elements
notEmptyOrNil: return true, if the receiver has any elements
size: return the number of elements in the collection

searching

identityIndexOf: anObject

return the index of anObject or 0 if not found. Compare using ==

identityIndexOf: anObject startingAt: startIndex

return the index of anObject, starting search at startIndex.
Compare using ==; return 0 if not found in the collection

identityIndexOf: anObject startingAt: startIndex endingAt: stopIndex

return the index of anObject, starting search at startIndex,
ending at stop.
If found (within the range), return the index, otherwise return 0.
Compare using ==; return 0 if not found in the collection

Usage example(s):

     |coll|
     coll := #(1 2 3 4 5 6 7 8 9 10) asOrderedCollection.
     coll identityIndexOf:7 startingAt:2 endingAt:6.
     coll identityIndexOf:7 startingAt:2 endingAt:7.
     coll identityIndexOf:7 startingAt:2 endingAt:8.
     coll identityIndexOf:7 startingAt:2 endingAt:9.
     coll removeFirst.
     coll removeFirst.
     coll.     'now: OrderedCollection(3 4 5 6 7 8 9 10)'.
     coll identityIndexOf:7 startingAt:2 endingAt:4.
     coll identityIndexOf:7 startingAt:2 endingAt:5.
     coll identityIndexOf:7 startingAt:2 endingAt:6.
     coll identityIndexOf:7 startingAt:2 endingAt:7.

indexOf: anObject

return the index of anObject or 0 if not found in the collection.
Compare using =

Usage example(s):

     |c|

     c := OrderedCollection new:10000.
     c add:10; add:20; add:30.
     c indexOf:99

Usage example(s):

     |c|

     c := OrderedCollection new:10000.
     c add:10; add:20; add:30.
     c indexOf:30

indexOf: anObject ifAbsent: exceptionValue

return the index of anObject or 0 if not found in the collection.
Compare using =
If the receiver does not contain anElement,
return the result of evaluating the argument, exceptionBlock.

Usage example(s):

     |c|

     c := OrderedCollection new:10000.
     c add:10; add:20; add:30.
     c indexOf:99 ifAbsent:'nope'

Usage example(s):

     |c|

     c := OrderedCollection new:10000.
     c add:10; add:20; add:30.
     c indexOf:30 ifAbsent:'nope'

indexOf: anObject startingAt: startIndex

return the index of anObject, starting search at startIndex.
Compare using =; return 0 if not found in the collection

Usage example(s):

     |c|

     c := OrderedCollection new:10000.
     c add:1; add:2; add:3.
     c indexOf:4 startingAt:5

testing

isFixedSize: return true if the receiver cannot grow - this will vanish once
Arrays and Strings learn how to grow ...
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.

tuning

quickSortFrom: inBegin to: inEnd: because array-at/at:put: is much faster, this speeds up sorting by
quickSortFrom: inBegin to: inEnd sortBlock: sortBlock: because array-at/at:put: is much faster, this speeds up sorting by

Examples:

using OC as a stack:

  |stack top|

  stack := OrderedCollection new.

  1 to:10 do:[:i |
      stack add:i
  ].

  10 timesRepeat:[
      top := stack removeLast.
      Transcript showCR:top
  ]

using OC as a queue (you should use Queue right away ..):

  |queue dequeued|

  queue := OrderedCollection new.

  1 to:10 do:[:i |
      queue addLast:i
  ].

  10 timesRepeat:[
      dequeued := queue removeFirst.
      Transcript showCR:dequeued
  ]

examples to support the performance hint (see documentation) timing removal of all odd elements in a collection of 10000: (940 ms on P5/133)

      |coll time|

      coll := (1 to:10000) asOrderedCollection.
      time := Time millisecondsToRun:[
          coll removeAllSuchThat:[:el | el even]
      ].
      Transcript show:'time is '; show:time; showCR:' ms'.

tuning the removal by doing it reverse (less copying in #removeAtIndex:) speeds it up by a factor of 2:

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

rebuilding a new collection: (64 ms on P5/133)

      |coll time|

      coll := (1 to:10000) asOrderedCollection.
      time := Time millisecondsToRun:[
          coll := coll select:[:el | el odd]
      ].
      Transcript show:'time is '; show:time; showCR:' ms'.

adding at the end (fast):

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

adding at front (fast):

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

inserting in the middle (slow):

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

ST/X 7.7.0.0; WebServer 1.702 at 20f6060372b9.unknown:8081; Thu, 26 Dec 2024 14:59:23 GMT

Smalltalk/X Webserver

Documentation of class 'OrderedCollection':

Class: OrderedCollection

Inheritance:

Description:

copyright

Class protocol:

Instance protocol:

Examples: