eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'OrderedCollection':

Home

Documentation
www.exept.de
Everywhere
for:
[back]

Class: OrderedCollection


Inheritance:

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

Package:
stx:libbasic
Category:
Collections-Sequenceable
Version:
rev: 1.141 date: 2018/04/13 13:20:37
user: stefan
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:

initialization
o  initialize
the minimum size of a non-empty contentsArray

instance creation
o  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

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

o  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

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

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

Compatibility-Squeak
o  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
o  at: anInteger
return the element at index, anInteger

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

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

o  first
return the first element
usage example(s):
     (OrderedCollection withAll:#(1 2 3 4 5)) first
     (SortedCollection withAll:#(5 4 3 2 1)) first

o  firstOrNil
return the first element or nil, if empty.
usage example(s):
     (OrderedCollection withAll:#(1 2 3 4 5)) firstOrNil
     (SortedCollection withAll:#()) firstOrNil

o  last
return the last element
usage example(s):
     (OrderedCollection withAll:#(1 2 3 4 5)) last
     (SortedCollection withAll:#(5 4 3 2 1)) last

adding & removing
o  add: anObject
add the argument, anObject to the end of the collection
Return the argument, anObject.

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

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

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

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

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

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

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

o  addFirst: anObject
add the argument, anObject to the beginning of the collection.
Return the argument, anObject.

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

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

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

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

o  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

o  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

o  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

o  removeFrom: startIndex to: stopIndex
added for ST-80 compatibility.
Same as removeFromIndex:toIndex:.

o  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

o  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

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

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

o  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

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

converting
o  asArray
return the receiver as an array.

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

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

copying
o  , 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])

o  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

o  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

o  postCopy
have to copy the contentsArray too

enumerating
o  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]

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

o  do: aBlock
evaluate the argument, aBlock for every element in the collection.

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

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

o  reverseDo: aBlock
evaluate the argument, aBlock for every element in the collection
procesing elements in reverse direction (i.e. starting with the last)

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

grow & shrink
o  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.

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

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

private
o  initContents: size
setup the receiver-collection to hold size entries

o  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

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

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

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

o  setFirstIndex: newFirstIndex lastIndex: newLastIndex
set first and last index

o  setIndices
added for VW compatibility: set the indices for an empty collection

private-accessing
o  contentsArray
return the orderedCollections underlying contentsArray.
The actual elements are found here starting at firstIndex,
and ending at lastIndex.

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

o  size
return the number of elements in the collection

searching
o  identityIndexOf: anObject
return the index of anObject or 0 if not found. Compare using ==

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

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

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

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

testing
o  includes: anObject
return true if anObject is in the collection. Compare using =

o  includesIdentical: anObject
return true if anObject is in the collection. Compare using ==

o  isEmpty
return true, if the receiver has no elements

o  isEmptyOrNil
return true, if the receiver has no elements

o  isFixedSize
return true if the receiver cannot grow - this will vanish once
Arrays and Strings learn how to grow ...

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

o  notEmpty
return true, if the receiver has any elements

o  notEmptyOrNil
return true, if the receiver has any elements

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

o  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.1.0.0; WebServer 1.663 at exept.de:8081; Mon, 23 Jul 2018 11:40:53 GMT