How to merge two sorted lists using streams

Leandro Caniglia caniglia at dm.uba.ar
Wed Apr 6 23:57:32 UTC 2005


OrderedCollection >> merge: aCollection sortBlock: sortBlock
"Implementation note: the second condition in the #whileTrue: avoids an 
endless
loop in strict orders."
| answer first last a b swap |
self isEmpty ifTrue: [^aCollection asOrderedCollection].
aCollection isEmpty ifTrue: [^self asOrderedCollection].
answer := OrderedCollection new: self size + aCollection size.
first := self readStream.
last := aCollection readStream.
a := first next.
b := last next.
[true] whileTrue: [
[(sortBlock value: a value: b) or: [(sortBlock value: b value: a) not]]
whileTrue: [
answer addLast: a.
first atEnd
ifTrue: [^answer addLast: b; addAllLast: last upToEnd; yourself].
a := first next].
swap := first.
first := last.
last := swap.
swap := a.
a := b.
b := swap]
"
(#('a' 'a' 'b' 'c' 'c') asSortedCollection: [:x :y | x asString < y 
asString]) merge: #(a c)
"


----- Original Message ----- 
From: "Brent Pinkney" <brent.pinkney at aircom.co.za>
To: "The general-purpose Squeak developers list" 
<squeak-dev at lists.squeakfoundation.org>
Sent: Wednesday, April 06, 2005 4:45 PM
Subject: How to merge two sorted lists using streams


> Hi,
>
> Does anyone have the One True Algorithm to merge two sorted
> OrderedCollections using streams ?
>
> Thanks
>
> Brent
> 




More information about the Squeak-dev mailing list