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 collection (or
collection simulators) can be sorted with this.
(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 < 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]
"Modified: 6.2.1996 / 15:42:51 / cg"
"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
^ '$Header: /cvs/stx/stx/libbasic2/SequenceableCollectionSorter.st,v 1.1 1996-02-06 17:49:00 cg Exp $'
! !
SequenceableCollectionSorter initialize!