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.

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

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

!

nonDefaultSort:inBegin to:inEnd

    "actual sort worker for sorting when a non default sortBlock

     or access selectors are used."

    |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 perform:atSelector with:((b + e) // 2).

    [b < e] whileTrue:[

        [b < end 

        and:[sortBlock 

                value:(collection perform:atSelector with:b)

                value:middleElement]] 

        whileTrue:[b := b + 1].

        [e > begin 

        and:[sortBlock

                value:middleElement

                value:(collection perform:atSelector with:e)]] 

        whileTrue:[e := e - 1].

        (b <= e) ifTrue:[

            (b == e) ifFalse:[

                temp1 := (collection perform:atSelector with:b). 

                temp2 := (collection perform:atSelector with:e). 

                collection perform:putSelector with:b with:temp2. 

                collection perform:putSelector 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]

    "Modified: 6.2.1996 / 15:42:51 / cg"

    "Created: 6.2.1996 / 16:06:46 / 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:[

        self nonDefaultSort:from to:to

    ].

    "Modified: 6.2.1996 / 15:51:50 / cg"

! !

!SequenceableCollectionSorter class methodsFor:'documentation'!

version

! !

SequenceableCollectionSorter initialize!