Object subclass:#SequenceableCollectionSorter
	instanceVariableNames:'collection atSelector putSelector sizeSelector sortBlock'
	classVariableNames:'DefaultSortBlock'
	poolDictionaries:''
	category:'Collections-Support'
!

!SequenceableCollectionSorter class methodsFor:'documentation'!

documentation
"
    a SequenceableCollectionSorter allows for anything which responds to
    keyed at/atPut messages to be sorted just like a SequenceableCollection.
    Since the access messages can be customized, even non collections
    (or collection simulators, models etc.) can be sorted with these sorters.
    (use #atSelector: / #putSelector: and #sizeSelector: for customization).

    As with collection sorting, the sortBlock can be specified and defaults to
    a block which compares using #< messages.
"
!

examples
"
    |a sorter|

    a := #(10 5 2 17 5 99 -5).
    sorter := SequenceableCollectionSorter on:a.
    sorter sort.
    Transcript showCR:a printString
"
! !

!SequenceableCollectionSorter class methodsFor:'initialization'!

initialize
    DefaultSortBlock := [:a :b | a <= b]

    "
     SequenceableCollectionSorter initialize
    "

    "Modified: 6.2.1996 / 15:47:48 / cg"
! !

!SequenceableCollectionSorter class methodsFor:'instance creation'!

on:aCollection
    ^ self new collection:aCollection; sortBlock:DefaultSortBlock

    "Created: 6.2.1996 / 15:39:09 / cg"
    "Modified: 6.2.1996 / 16:07:36 / cg"
!

on:aCollection using:aTwoArgBlock
    ^ self new collection:aCollection; sortBlock:aTwoArgBlock

    "Created: 6.2.1996 / 15:39:32 / cg"
!

sort:aCollection
    (self new collection:aCollection; sortBlock:DefaultSortBlock) sort

    "Created: 6.2.1996 / 15:40:04 / cg"
    "Modified: 6.2.1996 / 16:07:42 / cg"
!

sort:aCollection using:aTwoArgBlock
    (self new collection:aCollection; sortBlock:aTwoArgBlock) sort

    "Created: 6.2.1996 / 15:39:58 / cg"
! !

!SequenceableCollectionSorter methodsFor:'accessing'!

atSelector:aSymbol
    "set the selector to access elements.
     If nil (the default), elements are accessed via #at:"

    atSelector := aSymbol

    "Created: 6.2.1996 / 15:35:49 / cg"
!

collection
    "return the collections being sorted."

    ^ collection

    "Created: 6.2.1996 / 15:37:02 / cg"
!

collection:aCollection
    "set the collections being sorted."

    collection := aCollection

    "Created: 6.2.1996 / 15:37:20 / cg"
!

putSelector:aSymbol
    "set the selector to access elements.
     If nil (the default), elements are accessed via #at:put:"

    putSelector := aSymbol

    "Created: 6.2.1996 / 15:36:14 / cg"
!

sizeSelector:aSymbol
    "set the selector to get the collections size.
     If nil (the default), elements are accessed via #size"

    sizeSelector := aSymbol

    "Created: 6.2.1996 / 15:36:33 / cg"
!

sortBlock
    "return the sortBlock which is used to compare two elements.
     The default sortBlock compares elements by sending the #< message."

    ^ sortBlock

    "Created: 6.2.1996 / 15:38:32 / cg"
!

sortBlock:aTwoArgBlock 
    "set the sortBlock which is used to compare two elements.
     The default sortBlock compares elements by sending the #< message."

    sortBlock := aTwoArgBlock

    "Created: 6.2.1996 / 15:38:20 / cg"
! !

!SequenceableCollectionSorter methodsFor:'sorting'!

defaultSort:inBegin to:inEnd
    "actual sort worker for sorting when the sortBlock is nil (or the default)
     and default atSelector/putSelectors are to be used.
     This will execute slightly faster, since no #perform-indirection is needed."

    |begin   "{ Class: SmallInteger }"
     end     "{ Class: SmallInteger }"
     b       "{ Class: SmallInteger }"
     e       "{ Class: SmallInteger }"
     middleElement temp1 temp2 |

    begin := inBegin.   "/ this also does a type-check
    end := inEnd.

    b := begin.
    e := end.
    middleElement := collection at:((b + e) // 2).

    [b < e] whileTrue:[
        [b < end and:[(collection at:b) <= middleElement]] whileTrue:[b := b + 1].
        [e > begin and:[middleElement <= (collection at:e)]] whileTrue:[e := e - 1].

        (b <= e) ifTrue:[
            (b == e) ifFalse:[
                temp1 := collection at:b. temp2 := collection at:e. 
                collection at:b put:temp2. collection at:e put:temp1
            ].
            b := b + 1.
            e := e - 1
        ]
    ].
    (begin < e) ifTrue:[self defaultSort:begin to:e].
    (b < end) ifTrue:[self defaultSort:b to:end]

    "Created: 6.2.1996 / 15:44:37 / cg"
    "Modified: 6.2.1996 / 18:06:23 / cg"
!

nonDefaultSort3:inBegin to:inEnd with:p
    "actual sort worker for sorting when a non default sortBlock
     with 3 args (stringSort) is used."

    |begin   "{ Class: SmallInteger }"
     end     "{ Class: SmallInteger }"
     b       "{ Class: SmallInteger }"
     e       "{ Class: SmallInteger }"
     middleElement temp1 temp2 
     atSel putSel|

    atSel := atSelector ? #at:.
    putSel := putSelector ? #at:put:.

    begin := inBegin.   "/ this also does a type-check
    end := inEnd.

    b := begin.
    e := end.
    middleElement := collection perform:atSel with:((b + e) // 2).

    [b < e] whileTrue:[
        [b < end 
        and:[sortBlock 
                value:p
                value:(collection perform:atSel with:b)
                value:middleElement]] 
        whileTrue:[b := b + 1].
        [e > begin 
        and:[sortBlock
                value:p
                value:middleElement
                value:(collection perform:atSel with:e)]] 
        whileTrue:[e := e - 1].

        (b <= e) ifTrue:[
            (b == e) ifFalse:[
                temp1 := (collection perform:atSel with:b). 
                temp2 := (collection perform:atSel with:e). 
                collection perform:putSel with:b with:temp2. 
                collection perform:putSel with:e with:temp1.
            ].
            b := b + 1.
            e := e - 1
        ]
    ].
    (begin < e) ifTrue:[self nonDefaultSort3:begin to:e with:p].
    (b < end) ifTrue:[self nonDefaultSort3:b to:end with:p]

    "Modified: / 27.10.1997 / 04:52:41 / cg"
    "Created: / 27.10.1997 / 18:54:54 / cg"
!

nonDefaultSort:inBegin to:inEnd
    "actual sort worker for sorting when a non default sortBlock
     or nonNil access selectors are used."

    |begin   "{ Class: SmallInteger }"
     end     "{ Class: SmallInteger }"
     b       "{ Class: SmallInteger }"
     e       "{ Class: SmallInteger }"
     middleElement temp1 temp2 
     atSel putSel|

    atSel := atSelector ? #at:.
    putSel := putSelector ? #at:put:.

    begin := inBegin.   "/ this also does a type-check
    end := inEnd.

    b := begin.
    e := end.
    middleElement := collection perform:atSel with:((b + e) // 2).

    [b < e] whileTrue:[
        [b < end 
        and:[sortBlock 
                value:(collection perform:atSel with:b)
                value:middleElement]] 
        whileTrue:[b := b + 1].
        [e > begin 
        and:[sortBlock
                value:middleElement
                value:(collection perform:atSel with:e)]] 
        whileTrue:[e := e - 1].

        (b <= e) ifTrue:[
            (b == e) ifFalse:[
                temp1 := (collection perform:atSel with:b). 
                temp2 := (collection perform:atSel with:e). 
                collection perform:putSel with:b with:temp2. 
                collection perform:putSel with:e with:temp1.
            ].
            b := b + 1.
            e := e - 1
        ]
    ].
    (begin < e) ifTrue:[self nonDefaultSort:begin to:e].
    (b < end) ifTrue:[self nonDefaultSort:b to:end]

    "Created: / 6.2.1996 / 16:06:46 / cg"
    "Modified: / 27.10.1997 / 04:52:41 / cg"
!

sort
    |sz|

    sizeSelector isNil ifTrue:[
        sz := collection size
    ] ifFalse:[
        sz := collection perform:sizeSelector
    ].
    self sort:1 to:sz

    "Created: 6.2.1996 / 15:41:21 / cg"
!

sort:from to:to 
    "actual sort worker for sort-messages"

    (atSelector isNil
    and:[putSelector isNil
    and:[sortBlock isNil or:[sortBlock == DefaultSortBlock]]]) ifTrue:[
        self defaultSort:from to:to 
    ] ifFalse:[
        sortBlock numArgs == 3 ifTrue:[
            self nonDefaultSort3:from to:to with:nil "p"
        ] ifFalse:[
            self nonDefaultSort:from to:to
        ]
    ].

    "Modified: / 27.10.1997 / 18:55:48 / cg"
! !

!SequenceableCollectionSorter class methodsFor:'documentation'!

version
    ^ '$Header: /cvs/stx/stx/libbasic2/SequenceableCollectionSorter.st,v 1.5 1997-10-28 19:17:02 cg Exp $'
! !
SequenceableCollectionSorter initialize!