Class: OrderedCollection

• Inheritance
• Description
• Related information
• Class protocol
  • initialization
  • instance creation
• Instance protocol
  • Compatibility-Squeak
  • accessing
  • adding & removing
  • converting
  • copying
  • copying-private
  • enumerating
  • filling & replacing
  • grow & shrink
  • misc ui support
  • private
  • private-accessing
  • queries
  • searching
  • testing
  • tuning
• Examples

Inheritance:

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

Package:

stx:libbasic

Category:

Collections-Sequenceable

Version:

rev: 1.148 date: 2019/05/27 13:03:53

user: cg

file: OrderedCollection.st directory: libbasic

module: stx stc-classLibrary: libbasic

Author:

Claus Gittinger

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

    lastIndex       <SmallInteger>  index of last valid element

[performance hint:]
    They overallocate a few slots to make insertion at either end often O(1),
    but sometimes O(n), where n is the current size of the collection
    (i.e. they have reallocate the underlying element buffer and therefore copy the
     elements into a new one. However, this reallocation is not done on every insert,
     and if elements are deleted and others reinserted, the buffer is usually already able
     to hold the new element)

    Insertion in the middle is O(n), and therefore slower, because elements have to be
    shuffled towards either end, in order to make space for the new element.
    Therefore, it is often cheaper, to instantiate a new object, and copy over the
    elements.
    see SegmentedOrderedCollection for a collection, which is specialized for this
    kind of usage with many elements.

[beginners bug hint:]
    notice that:
        Array new:n
    is quite different from:
        OrderedCollection new:n

    The later creates an OC which is prepared to hold <n> elements,
    but has a logical size of 0 (zero). To get an OC containing <n> nils,
    use:
         (OrderedCollection new) grow:n
    or the syntactic sugar for that:
         OrderedCollection newWithSize:n

    I know, this is confusing for beginners and was a bad semantic decision.
    However, that's the way the standard was defined and how all Smalltalk's behave,
    so we can't change that here.

[memory requirements:]
    OBJ-HEADER + (3 * ptr-size)
               + (size-roundedUpToNextPowerOf2 * ptr-size)

[complexity:]
    access by index: O(1)
    insertion at either end: mostly O(1)
    removal at either end: O(1)
    insertion in the middle: O(n)
    searching: O(n)
    min/max: O(n)

Related information:

    Array

Class protocol:

 initialize

the minimum size of a non-empty contentsArray

 new

create a new, empty OrderedCollection

usage example(s):

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

 new: size

create a new, empty OrderedCollection with a preallocated physical
size.
NOTICE:
the logical size of the returned collection is 0 (i.e. it is empty).
This may be confusing, in that it is different from what Array>>new:
returns. However, that's the way OrderedCollections work in every other
Smalltalk, so here it should as well.
See also newWithSize:, which might do what you really want.

 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

create a new, empty OrderedCollection, for which we already know
that it is very likely to remain empty.
Use this for collections which may sometimes get elements added, but usually not.
This is now obsolete and the same as new:
as the algorithm is now clever enough to deal efficiently with this situation

usage example(s):

self newLikelyToRemainEmpty size self newLikelyToRemainEmpty add:1; size self newLikelyToRemainEmpty addAll:#(1 2); size

Instance protocol:

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

 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

 add: anObject

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

 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.

 add: anObject afterIndex: index

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

 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.

 add: anObject beforeIndex: index

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

 addAll: aCollection

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

 addAll: aCollection afterIndex: index

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

 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.

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

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

 addFirst: anObject

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

 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.

 dropLast: n

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

usage example(s):

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

 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.

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

 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

usage example(s):

(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

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

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

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

 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; 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 (SortedCollection withAll:#(5 4 3 2 1)) removeLast:0; yourself (SortedCollection withAll:#(5 4 3 2 1)) removeLast:0

 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.

 asArray

return the receiver as an array.

 asNewOrderedCollection

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

 asOrderedCollection

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

 , 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

 postCopy

have to copy the contentsArray too

 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 ]

 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 ]

 reverseDo: aBlock

evaluate the argument, aBlock for every element in the collection
procesing 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] ] ]

 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.

 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.

 grow: newSize

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

 inspectorClass
( an extension from the stx:libtool package )

redefined to launch an OrderedCollectionInspector
(instead of the default InspectorView).

 containerClass

the class of the underlying container.
Here Array; redefined in WeakOrderedCollection to use a WeakArray

 initContents: size

setup the receiver-collection to hold size entries

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

 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

 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.

 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

 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

 indexOf: anObject

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

 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.

 indexOf: anObject startingAt: startIndex

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

 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.

 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:

  |stack top|

  stack := OrderedCollection new.

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

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

  |queue dequeued|

  queue := OrderedCollection new.

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

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

      |coll time|

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

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

      |coll time|

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

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

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

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