For my merge sort demonstration, I wanted a factory object producing snapshots of progressive sorting in an array of integers. It would essentially be a (partial) function with the signature
(Array[Int]) ⇒ RepeatingIterator[Int].
The argument to the factory is an array of integers that represents the initial state, before sorting.
The class RepeatingIterator is derived from Iterator. It repeats infinitely by yielding the first item after the last, and so on.
object SortStates {
def apply (init: Array[Int]) = {
Create stages
Define conversion function
new RepeatingIterator(Seq(init) ++
(stages map convFn))
}
}
Create stages
The states of partial to complete ordering are mapped from an instance of Stages (which is a structure that will be described in part 3; suffice to say that it provides a method def map (f: List[Int] ⇒ Array[Int])).
val size = init.size
val stages = new Stages(size)
Define conversion function
The function passed to map is an object whose apply method takes two arguments: a copy of the initial state, and one of the stages mapped over.
val convFn = StateFunc(init take size) _
The StateFunc object
This object is a function (Array[Int])(List[Int]) ⇒ Array[Int] that takes as its first argument the previous state of the values. The second argument is a list that describes one stage in the merging process. After building a state with buildState, it is written back to the data parameter and finally returned.
object StateFunc {
Define merge method
Define splitMerge method
Define buildState method
def apply (data: Array[Int])(stage: List[Int]) = {
val state =
buildState(data, stage).flatten.toArray
for (i ← 0 until data.size)
data(i) = state(i)
state
}
}
Define buildState method
The buildState method builds a new state by merging the sorted lists of the previous state. One merge operation is done for each element of the stage data structure. During each merge operation, the following constants are defined:
- n
- the length of the resulting sublist
- s
- the total length of the sublists that are already merged
- r
- a list of n values past the s first values of data
If the sublist length (n) is 1, it is already sorted and r is simply added to the result. Otherwise, r is passed to the method splitMerge.
private def buildState (data: Array[Int], stage: List[Int]) = {
for {
i ← 0 until stage.size
n = stage(i)
s = (stage take i sum)
r = (data drop s take n).toList
} yield if (n == 1) r else splitMerge(r)
}
Define splitMerge method
The splitMerge method splits its parameter (which has n values) into two sublists with n / 2 and n - n / 2 values, respectively. The subroutine merge is then applied to the two lists.
private def splitMerge (r: List[Int]) = {
val n = r.size
val n_2 = n / 2
val xs1 = r take n_2
val xs2 = r drop n_2 take (n - n_2)
merge(xs1, xs2)
}
Define merge method
The merge method is the same as in the mergeSort function in part 1.
private def merge (a: List[Int], b: List[Int]): List[Int] =
(a, b) match {
case (_, Nil) ⇒ a
case (Nil, _) ⇒ b
case (ah :: at, bh :: _) if (ah <= bh) ⇒
ah :: merge(at, b)
case (_, bh :: bt) ⇒ bh :: merge(a, bt)
}
And that's it for SortStates and StateFunc. In the final part I will show Stages and RepeatingIterator.
