Class: SortedCollection

• Inheritance
• Description
• Class protocol
  • Compatibility-Dolphin
  • initialization
  • instance creation
• Instance protocol
  • adding & removing
  • blocked
  • converting
  • copying
  • enumerating
  • instance protocol
  • private
  • queries
  • searching
  • statistical functions
• Examples

Inheritance:

   Object
   |
   +--Collection
      |
      +--SequenceableCollection
         |
         +--OrderedCollection
            |
            +--SortedCollection
               |
               +--ParseTreeIndex

Package:

stx:libbasic

Category:

Collections-Sequenceable

Version:

rev: 1.90 date: 2019/02/10 13:51:33

user: cg

file: SortedCollection.st directory: libbasic

module: stx stc-classLibrary: libbasic

Author:

Claus Gittinger

Description:

I keep my elements sorted. The sort order is defined by a sortblock,
a two-argument block which, when given two elements of the collection,
should return true if the element given as first arg has to come before the
element given as second arg.

Equal elements may occur multiple times.

SortedCollection uses quickSort to resort and a binary search when adding/removing elements.
Because insertion/removal may require that remaining elements have to
be shifted within the container, adding many individual elements will be faster above a
particular number of added elements by creating a completely new collection from the
unsorted elements.
(see examples)

A sortblock, given arguments a,b should return true, if a is to be shown before b.
A sortBlock of [:a :b | a < b] defines ascending sort-order,
while [:a :b | a > b] defines descening order.
The default sortBlock for SortedCollections is the first one (i.e. sorting in ascending order).

Compatibility Warning:
    VW seems to use a default sortBlock which compares a<=b, whereas ST/X uses a<b.
    That means, that elements which are compared MUST understand #< in ST/X
    while the minumum protocol is #<= in VW.
    This may be changed in a future release of ST/X
    (it is not yet, to not confuse existing applications ...
     ... be aware, that the sortBlock has an effect on a few algorithms
     found here; especially #indexForInserting is critical.)

[caveat:]
    a balanced tree may be a better choice, as inserting may be slow when
    elements have to be shifted. See the performance measurements in AATree.

Class protocol:

 sortBlock: aBlock withAll: aCollection

 initialize

setup the default sortBlock.
Use #<, since this is the base method in Magnitude.

usage example(s):

SortedCollection initialize

 forStrings

this is supposed to return a sortedCollection, which sorts using
the current locales collating sequence. For now, simply use a
normal string compare.
This will change

 forStrings: size

this is supposed to return a sortedCollection, which sorts using
the current locales collating sequence. For now, simply use a
normal string compare.
This will change

 forStrings: size collatedBy: aCollationPolicy

Create & return a SortedCollection that sorts the receiver's
elements according to the specified locales collating policy.
This is currently not really supported - strings are sorted
without caring for the locale.

 new

return a new sortedCollection, the sorting is done using
a compare for a < b, in ascending order

 new: size

return a new sortedCollection with preallocated size.
The sorting is done using a compare for a < b, in ascending order

 sortBlock: aBlock

return a new sortedCollection, whe the sort order is defined
by aBlock.
This must be a two-argument block which returns true if its arg1 has to come before
its arg2 in the collection.

 withAll: aCollection sortBlock: aBlock

initialize from aCollection and set the sort-block

usage example(s):

SortedCollection withAll:#(1 2 3 4 5 6 7 8 9 0) sortBlock:[:a :b | a > b]

Instance protocol:

 add: anObject

add the argument, anObject at the proper place in the receiver.
Returns the argument, anObject (sigh).

usage example(s):

#(7 3 9 10 99) asSortedCollection add:5; yourself #(7 3 9 10 99) asSortedCollection add:1; yourself #(7 3 9 10 99) asSortedCollection add:1000; yourself #(7 3 9 10 99) asSortedCollection add:1; yourself

 addAll: aCollection

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

usage example(s):

#(7 3 9 10 99) asSortedCollection addAll:#(77 0 1 16 5); yourself ( #(7 3 9 10 99) asSortedCollection:[:a :b | a > b]) addAll:#(77 0 1 16 5); yourself #(7 3 9 10 99) asSortedCollection addAll:( #(77 0 1 16 5) asSortedCollection:[:a :b | a > b]); yourself (#(7 3 9 10 99) asSortedCollection:[:a :b | a > b]) addAll:( #(77 0 1 16 5) asSortedCollection:[:a :b | a < b]); yourself

 mergeSorted: aSortedCollection

add all elements of the argument, aSortedCollection to the receiver.
This leads to an error, if the argument is not sorted.

This should be used when a number of elements is to be added.
Notice, that quicksort degenerates to a veeery slow bubble-like
sort when a collection of already sorted elements is given to it.
Therefore, adding chunks is better done by sorting the chunk and merging
it in, instead of resorting the receiver.

aSortedCollection must be sorted by the same sortBlock as myself!

usage example(s):

#(7 3 9 10 99) asSortedCollection mergeSorted:#(77 0 1 16 5) asSortedCollection #(7 3 9 10 99) asSortedCollection mergeSorted:#(77 0 3 1 98 99 16 5) asSortedCollection #() asSortedCollection mergeSorted:#(77 0 3 1 98 99 16 5) asSortedCollection #(7 3 9 10 99) asSortedCollection mergeSorted:#() asSortedCollection

 add: newObject after: oldObject

catch this - its not allowed for sortedCollections

 add: newObject before: oldObject

catch this - its not allowed for sortedCollections

 addFirst: anObject

catch this - its not allowed for sortedCollections

 addLast: anObject

catch this - its not allowed for sortedCollections

 asSortedCollection

return the receiver as a sorted collection

 asSortedCollection: aSortBlock

return the receiver as a sorted collection, using aSortBlock.
Return the receiver, if it's a sortedCollection and the sortBlock
is the same as the argument-sortBlock

 copyEmpty: size

return a copy of the receiver with no elements, but
the same size. This method has been be redefined to
preserve the sortBlock.

 postCopyFrom: anOriginal

sent after a copy or when a new collection species has been created.
The new collection should have the same sortBlock as the original.

 collect: aBlock

evaluate the argument, aBlock for every element in the collection
and return a collection of the results. Redefined to return an OrderedCollection;
see X3J20 spec. (SortedCollection>>collect: should return an OrderedCollection)

 sort: aSortBlock

redefined from superclass to change the sortBlock

 sortBlock

return the block used for sorting

 sortBlock: aSortBlock

change the sort criteria for a sorted collection, resort the elements of
the collection, and return the receiver. The argument, aSortBlock must
be a two-argument block which returns true if its arg1 has to come before
its arg2 in the collection.

usage example(s):

#(9 8 7 6 5 4 3) asSortedCollection #(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a < b] #(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a > b] #($f $G $z $Y $o $H) asSortedCollection #($f $G $z $Y $o $H) asSortedCollection sortBlock:[:a : b | a asUppercase < b asUppercase]

 indexForInserting: anObject

search the index at which to insert anObject.
Can also be used to search for an existing element
by checking if the element at the returned index is the one we look for.
Uses a binarySearch since we can depend on the elements being in sorted order.
The returned index is a physical one, for accessing contentsArray.

usage example(s):

#(1 2 3 4 7 99 1313 981989 898989898) asSortedCollection indexForInserting:50 #(1.0 2.0 3 4 7 49.0 51.0 99 1313 981989 898989898) asSortedCollection indexForInserting:50

 setSortBlock: aSortBlock

set the sortblock without resorting - private only

 includes: anObject

return true, if the argument, anObject is in the collection.
Redefined, since due to being sorted, the inclusion check can
be done with log-n compares i.e. much faster.

usage example(s):

#(7 3 9 10 99) asSortedCollection includes:50 #(7 3 9 10 99) asSortedCollection includes:10

 isSorted

return true. if my elements are sorted

 isSortedBy: aBlock

return true, if my elements are sorted (already) by the given criterion (sortBlock).

 isSortedCollection

return true. if I am a sorted collection

 occurrencesOf: anObject

return how many times the argument, anObject is in the collection.
Redefined, since due to being sorted, the range of checked objects
can be limited i.e. it can be done much faster.
Uses #= (i.e. equality) compare.

usage example(s):

#(7 3 9 10 99) asSortedCollection occurrencesOf:50 #(7 3 9 10 99) asSortedCollection occurrencesOf:10 #(7 10 3 10 9 10 10 10 10 10 10 10 10 99) asSortedCollection occurrencesOf:10

 speciesForCollecting

Redefined to return an OrderedCollection;
see X3J20 spec. (SortedCollection>>collect: should return an OrderedCollection)

 after: anObject ifAbsent: exceptionBlock

return the element after the argument, anObject; or nil if there is none.
If anObject is contained multiple times in the collection, return the
the first element which is non-equal to anObject.
If the receiver does not contain anObject, return the result from evaluating
exceptionBlock.

usage example(s):

#(7 3 9 10 99) asSortedCollection after:50 #(7 3 9 10 99) asSortedCollection after:3 #(7 3 9 10 99) asSortedCollection after:1 #(7 3 9 10 99) asSortedCollection after:10 #(7 3 9 10 99) asSortedCollection after:7 #(7 3 9 10 99) asSortedCollection after:99 #(7 10 3 10 9 10 10 99) asSortedCollection after:9 #(7 10 3 10 9 10 10 99) asSortedCollection after:10

 before: anObject ifAbsent: exceptionBlock

return the element before the argument, anObject; or nil if there is none.
If the receiver does not contain anObject, return the result from evaluating
exceptionBlock.

usage example(s):

#(7 3 9 10 99) asSortedCollection before:50 #(7 3 9 10 99) asSortedCollection before:3 #(7 3 9 10 99) asSortedCollection before:1 #(7 3 9 10 99) asSortedCollection before:10 #(7 3 9 10 99) asSortedCollection before:7 #(7 3 9 10 99) asSortedCollection before:99 #(7 10 3 10 9 10 10 99) asSortedCollection before:9 #(7 10 3 10 9 10 10 99) asSortedCollection before:10

 indexOf: anObject

return the index of the anObject or 0 if anObject is not in the collection.
Redefined, since due to being sorted,
this can be done with log-n compares i.e. much faster.

usage example(s):

#(7 3 9 10 99) asSortedCollection indexOf:50 #(7 3 9 10 99) asSortedCollection indexOf:10 #('aa' 'bb' 'cc' 'dd') asSortedCollection indexOf:'bb' #('aa' 'bb' 'cc' 'dd' 'aa' 'bb' 'cc' 'dd') asSortedCollection indexOf:'bb' |allSyms indices| allSyms := Symbol allInstances asSortedCollection. Time millisecondsToRun:[ indices := allSyms collect:[:el | allSyms indexOf:el]. ]. indices = (1 to:allSyms size)

 indexOf: anElement ifAbsent: exceptionBlock

Return the index of anElement within the receiver.
If the receiver does not contain anElement,
return the result of evaluating the argument, exceptionBlock.

 largest: n

return a collection containing the n largest elements, largest last.
Raises an exception, if the receiver does not contain at least n elements

usage example(s):

#(10 35 20 45 30 5) asSortedCollection largest:3 (#(10 35 20 45 30 5) asSortedCollection:[:a :b | a > b]) largest:3 #(10 35 20 45 30 5) asSortedCollection largest:6 #(10 35 20 45 30 5) asSortedCollection largest:7

 max

return the maximum value in the receiver collection,
redefined, since this can be easily computed.
Raises an error, if the receiver is empty.

usage example(s):

#(10 35 20 45 30 5) asSortedCollection max #(10 35 20 45 30 5) max #() asSortedCollection max

 min

return the minimum value in the receiver collection,
redefined, since this can be easily computed.
Raises an error, if the receiver is empty.

usage example(s):

#(10 35 20 45 30 5) asSortedCollection min #(10 35 20 45 30 5) min

 minMax

return the minimum and maximum values in the receiver collection
as a two element array, using #< to compare elements.
Raises an error, if the receiver is empty.

usage example(s):

#(10 35 20 45 30 5) asSortedCollection minMax #(10 35 20 45 30 5) minMax

 smallest: n

return a collection containing the n smallest elements, largest last.
Raises an exception, if the receiver does not contain at least n elements

usage example(s):

#(10 35 20 45 30 5) asSortedCollection smallest:3 (#(10 35 20 45 30 5) asSortedCollection:[:a :b | a > b]) smallest:3 #(10 35 20 45 30 5) asSortedCollection smallest:6 #(10 35 20 45 30 5) asSortedCollection smallest:7

 median

Return the middle element, or as close as we can get.

usage example(s):

#(10 35 20 45 30 5) asSortedCollection median #(10 35 20 45 30 5) median

Examples: