"{ Encoding: utf8 }"

"
 COPYRIGHT (c) 1996 by Claus Gittinger
              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 }"

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

!SequenceableCollectionSorter class methodsFor:'documentation'!

copyright
"
 COPYRIGHT (c) 1996 by Claus Gittinger
              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
"
    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 argumentCount == 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$'
! !


SequenceableCollectionSorter initialize!