Class: OrderedSet

• Inheritance
• Description
• Related information
• Class protocol
  • instance creation
• Instance protocol
  • accessing
  • adding & removing
  • converting
  • copying-private
  • enumerating
  • initialization
  • searching
  • testing
• Examples

Inheritance:

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

Package:

stx:libbasic

Category:

Collections-Sequenceable

Version:

rev: 1.41 date: 2019/05/27 13:03:48

user: cg

file: OrderedSet.st directory: libbasic

module: stx stc-classLibrary: libbasic

Author:

Claus Gittinger

Description:

I am a subclass of Set whose elements are ordered in a
similar fashion to OrderedCollection.
That is, I have both Set behavior (only keeping a single instance of
an element) but I also remember the original order, in which elements
were added.
Therefore, this combines fast access/check/add via hashing with a defined 
order when enumerating.

[instance variables:]
    order <OrderedCollection>       Ordered collection of values reflecting the order 
                                    in the set. 

Related information:

    OrderedCollection
    Dictionary
    OrderedDictionary
    Set
    Bag

Class protocol:

 new: anInteger

Instance protocol:

 at: index

return the indexed instance variable with index, anInteger.
Report an error, if the index is wrong.

 at: index ifAbsent: exceptionalValue

return the indexed instance variable with index, anInteger.
If not present, return the value from exceptionalValue.

 atIndex: index

 atIndex: index ifAbsent: exceptionalValue

return an element at a given index

 order

returns the values in the order of their appearance

 add: anObject

Add anObject to the receiver (if not already included).
Also, remember in the order (i.e. add to the end)
If anObject is already present in the set,
the order will not be changed. (See also: #addLast:)

usage example(s):

self new add:1; add:2; add:nil; add:1; yourself

 addFirst: anObject

Add anObject to the receiver (if not already included).
Also, remember in the order (i.e. add to the beginning)

usage example(s):

self new addFirst:1; addFirst:nil; yourself

 addLast: anObject

Add anObject to the receiver (if not already included).
Also, remember in the order (i.e. add to the end)
If anAssociation is already present in the receiver,
it will be moved to the end. (See also: #add:)

usage example(s):

self new addLast:1; addLast:nil; yourself

 addOrReplace: anObject

Add the argument, anObject to the receiver.
If it is already included, replace it by anObject.
Return nil, if anObject was not present in the receiver,
otherwise the element that has been replaced.

Also, remember in the order (i.e. add to the end)
If anObject is already present in the set,
the order will not be changed.

usage example(s):

Note that 1 is replaced by 1.0, but 1.0 is still at the beginning: self new addOrReplace:1; addOrReplace:2; addOrReplace:nil; addOrReplace:1.0; yourself

 clearContents

remove all elements from the receiver, but do not shrink. Returns the receiver.

 remove: oldObject ifAbsent: exceptionValueProvider

remove oldObject from the collection and return it.
If it was not in the collection return the value of exceptionValueProvider.

WARNING: do not remove elements while iterating over the receiver.

usage example(s):

OrderedSet new remove:nil

 removeAll

remove all elements from the receiver. Returns the receiver.

 removeFirst

remove the first object from the collection and return it.
If it was not in the collection, raise an error.

WARNING: do not remove elements while iterating over the receiver.

 removeFirstIfAbsent: exceptionalValue

remove the first object from the collection and return it.
If it was not in the collection, return the value from exceptionalValue.

WARNING: do not remove elements while iterating over the receiver.

 removeIdentical: oldObject ifAbsent: exceptionValueProvider

remove oldObject from the collection and return it.
If it was not in the collection return the value of exceptionValueProvider.

WARNING: do not remove elements while iterating over the receiver.

 removeLast

remove the last object from the collection and return it.
If it was not in the collection, raise an error.

WARNING: do not remove elements while iterating over the receiver.

 removeLastIfAbsent: exceptionalValue

remove the last object from the collection and return it.
If it was not in the collection, return the value from exceptionalValue.

WARNING: do not remove elements while iterating over the receiver.

 safeRemove: oldObject ifAbsent: exceptionValueProvider

remove the element, oldObject from the collection.
Return the element
(could be non-identical to oldObject, since I hash on equality, not on identity).
If it was not in the collection return the value of exceptionValueProvider.

In contrast to #remove:, this does not resize the underlying collection
and therefore does NOT rehash & change the elements order.
Therefor this can be used while enumerating the receiver,
which is not possible if #remove: is used.

WARNING: since no resizing is done, the physical amount of memory used
by the container remains the same, although the logical size shrinks.
You may want to manually resize the receiver using #emptyCheck.
(after the loop)

 testAndAdd: anObject

Test, if the element is present in the receiver.
Answer true, if the element did already exist in the collection,
false otherwise.
If the element does not exist, add it to the collection.
Also, remember in the order (i.e. add to the end)
If anObject is already present in the set,
the order will not be changed. (See also: #addLast:)

 asNewOrderedSet

make sure to return a unique new set

 asOrderedSet

make sure to return a unique new set

 postCopy

have to copy the keyArray too

 do: aBlock

Evaluate aBlock for each of the sets's values
in the order they have been added.

 doWithIndex: aBlock

Squeak/V'Age compatibility;
Evaluate aBlock for each of the sets's values and index
in the order they have been added.

 reverseDo: aBlock

Evaluate aBlock for each of the sets's values
in the reverse order they have been added.

 withIndexDo: aBlock

evaluate the argument, aBlock for every element in the collection,
passing both element and index as arguments.
Same as doWithIndex:, due to parallel evolution of different Smalltalk dialects

 initializeOrder: count

 findFirst: aBlock ifNone: exceptionValue

find the index of the first element, for which evaluation of the argument, aBlock returns true;
return its index or the value from exceptionValue if none detected.
This is much like #detect:ifNone:, however, here an INDEX is returned,
while #detect:ifNone: returns the element.

 findLast: aBlock ifNone: exceptionValue

find the index of the last element, for which evaluation of the argument, aBlock returns true.
Return its index or the value from exceptionValue if none detected.

 indexOf: anObject

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

 isOrdered

(comment from inherited method)
return true, if the receiver's elements are ordered.
Redefined to return false here, because the order of keys (and values in dictionaries)
may change due to rehashing, when elements are added/removed

Examples:

        |s|

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

        |s|

        s := OrderedSet 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 := OrderedSet new.
        s add:'one'.
        s addFirst:'two'.
        s addFirst:'three'.
        s add:'one'.
        s add:'two'.
        s add:'three'.
        s size.         
        s do:[:each | Transcript showCR:each].