"{ Encoding: utf8 }"

"

 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.

"

"{ Package: 'stx:libbasic2' }"

"{ NameSpace: Smalltalk }"

OrderedSet subclass:#SortedSet

	instanceVariableNames:''

	classVariableNames:''

	poolDictionaries:''

	category:'Collections-Sequenceable'

!

!SortedSet class methodsFor:'documentation'!

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.

"

!

documentation

"

    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.

    [author:]

        Claus Gittinger

    [see also:]

        OrderedCollection 

        Dictionary OrderedDictionary

        Set Bag

"

!

examples

"

                                                                    [exBegin]

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

                                                                    [exEnd]

                                                                    [exBegin]

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

                                                                    [exEnd]

                                                                    [exBegin]

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

                                                                    [exEnd]

"

! !

!SortedSet class methodsFor:'instance creation'!

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

    ^ self new setSortBlock:aBlock

    "Created: / 06-08-2012 / 12:34:29 / cg"

! !

!SortedSet methodsFor:'accessing'!

sortBlock

    ^ order sortBlock

! !

!SortedSet methodsFor:'adding & removing'!

addFirst:anObject 

    "blocked; only the sort order determines the order"

    self shouldNotImplement

    "Modified: / 06-08-2012 / 12:37:23 / cg"

!

addLast:anObject 

    "blocked; only the sort order determines the order"

    self shouldNotImplement

    "Modified: / 06-08-2012 / 12:37:30 / cg"

! !

!SortedSet methodsFor:'enumerating'!

collect:aBlock

    "for each element in the receiver, evaluate the argument, aBlock

     and return a new collection with the results"

    |newCollection|

    newCollection := self speciesForAdding new.

    newCollection setSortBlock:self sortBlock.

    self do:[:element | newCollection add:(aBlock value:element)].

    ^ newCollection

    "

     #(1 2 3 4) collect:[:e | e odd]   

     (1 to:10) collect:[:e | e even]     

    "

    "Modified: / 07-08-2010 / 16:26:40 / cg"

!

select:aBlock

    "return a new collection with all elements from the receiver, for which

     the argument aBlock evaluates to true.

     See also: #removeAllFoundIn: and #removeAllSuchThat:"

    |newCollection|

    newCollection := self speciesForAdding new.

    newCollection setSortBlock:self sortBlock.

    self do:[:each |

        (aBlock value:each) ifTrue:[newCollection add:each].

    ].

    ^ newCollection

    "

     #(1 2 3 4) select:[:e | e odd]   

     (1 to:10) select:[:e | e even]     

    "

    "Modified: / 07-08-2010 / 16:26:40 / cg"

! !

!SortedSet methodsFor:'initialization'!

initializeOrder:anInteger

    order := SortedCollection new:anInteger

    "Created: / 06-08-2012 / 12:33:31 / cg"

!

setSortBlock:aBlock

    order sortBlock:aBlock

    "Created: / 06-08-2012 / 12:35:07 / cg"

! !

!SortedSet class methodsFor:'documentation'!

version

    ^ '$Header$'

!

version_CVS

    ^ '$Header$'

! !