"{ 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$'
! !