Class: SortedSet

• Inheritance
• Description
• Class protocol
  • instance creation
• Instance protocol
  • accessing
  • adding & removing
  • initialization
  • queries
• Examples

Inheritance:

   Object
   |
   +--Collection
      |
      +--Set
         |
         +--OrderedSet
            |
            +--SortedSet

Package:

stx:libbasic2

Category:

Collections-Sequenceable

Version:

rev: 1.8 date: 2023/12/21 15:07:43

user: stefan

file: SortedSet.st directory: libbasic2

module: stx stc-classLibrary: libbasic2

Description:

I am a subclass of Set whose elements are ordered in a
similar fashion to SortedCollection.
That is, I have both Set behavior (only keeping a single instance of
an element) but I also remember the sort order.

I have one additional instance variable:

order <SortedCollection>        Sorted collection of values reflecting the order 
                                in the set. 

[caveat:]
    a tree may be a better choice, 
    as although the set shows O(1) behavior when adding,
    the sortedCollection does not (especially as inserting is expensive). 
    A balanced tree would show O(lg n) behavior.

[complexity:]
    access by index:                O(1)
    insertion:                      O(n) 
    removal:          -             O(n) 
    searching:                      O(1)
    min/max:                        O(1)

copyright
COPYRIGHT (c) 2012 by eXept Software AG
             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.

Class protocol:

 sortBlock: aBlock

return a new sortedSet, 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.

Instance protocol:

 max

|s|

s := SortedSet new.
s add:15; add:3; add:-1; addAll:#(99 13 -5 101 -77).
s min.
s max.

 min

|s|

s := SortedSet new.
s add:15; add:3; add:-1; addAll:#(99 13 -5 101 -77).
s min.
s max.

 sortBlock

 addFirst: anObject

blocked; only the sort order determines the order

 addLast: anObject

blocked; only the sort order determines the order

 initializeOrder: anInteger

 setSortBlock: aBlock

 newSpeciesForAdding

used when doing collect operations.
Redefinable for collections which do not know their size in advance

Usage example(s):

(SortedSet withAll:#(1 2 3 1 2 3 4 5 6 4 5 6)) newSpeciesForAdding. SortedSet withAll:#(1 2 3 4) select:[:e | e odd] ((1 to:10) as:SortedSet) select:[:e | e even]

 newSpeciesForCollecting

used when doing collect operations.
Redefinable for collections which do not know their size in advance

Usage example(s):

(SortedSet withAll:#(1 2 3 1 2 3 4 5 6 4 5 6)) newSpeciesForCollecting. SortedSet withAll:#(1 2 3 4) collect:[:e | e * 2] ((1 to:10) as:SortedSet) collect:[:e | (e / 2) asFloat]

Examples:

        |s|

        s := SortedSet new.
        s add:'one'.
        s add:'two'.
        s add:'one'.
        s add:'two'.
        s add:'four'.
        s add:'three'.
        s size.         
        s do:[:each | Transcript showCR:each].         

        |s|

        s := SortedSet new.
        s add:'one'.
        s add:'two'.
        s add:'one'.
        s add:'two'.
        s add:'three'.
        s remove:'one'.
        s size.         
        s do:[:each | Transcript showCR:each].         

        |s|

        s := SortedSet new.
        s add:'one'.
        s add:'two'.
        s add:'three'.
        s add:'one'.
        s add:'two'.
        s add:'three'.
        s size.         
        Transcript showCR:s.         
        s removeFirst.
        Transcript showCR:s.         
        s removeFirst.
        Transcript showCR:s.         
        s removeFirst.
        Transcript showCR:s.