Class: OrderedCollection

• Inheritance
• Description
• Related information
• Class protocol
  • instance creation
• Instance protocol
  • accessing
  • adding & removing
  • converting
  • copying
  • enumerating
  • filling & replacing
  • grow & shrink
  • inspecting
  • private
  • private-accessing
  • queries
  • searching
  • testing
• Examples

Inheritance:

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

Package:

stx:libbasic

Category:

Collections-Sequenceable

Version:

rev: 1.99 date: 2009/09/28 13:25:03

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

Related information:

    Array

Class protocol:

 new

create a new, empty OrderedCollection

 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.

 new: size withAll: element

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

 newFrom: aCollection

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

Instance protocol:

 at: anInteger

return the element at index, anInteger

 at: anInteger put: anObject

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

 first

return the first element

 last

return the last element

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

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

 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.

 removeAll

remove all elements from the collection.
Returns 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.
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.

 removeFirst

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

 removeFirst: n

remove the first n elements from the collection;
Return a collection containing the removed elements.

 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.

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

 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.

 removeLast

remove the last element from the collection; return the element

 removeLast: n

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

 reset

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

 asArray

return the receiver as an array.

 asOrderedCollection

return the receiver as an ordered collection

 , aCollection

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

 copy

return a new OrderedCollection containing the elements of the receiver.

 copyEmpty

return a copy of the receiver without any elements.

 copyFrom: start to: stop

return a new OrderedCollection containing the elements
from start to stop.

 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.

 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

 collect: collectBlock thenSelect: selectBlock

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

 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.

 keysAndValuesReverseDo: aTwoArgBlock

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

 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.

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

grow the receiver to newSize

 inspectorClass

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

 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.
#(1 2 3 4 5 6) -> #(nil 1 2 3 4 5 6)

 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.
Not used by the system; added for ST-80 compatibility.

 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

 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

 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

 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.

 notEmpty

return true, if the receiver has any elements

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