Alternate Pony Sort

gistfile1.txt

// Library code

interface val SortFunction[B: Any #read]
  new val create()
  fun lt(first: B, second: B): Bool

primitive ComparableSortFunction[B: Comparable[B] #read]
  fun lt(first: B, second: B): Bool => first < second
    //iftype B <: Comparable[B] then first < second else false end

type ComparableSort[A: Seq[B] ref, B: Comparable[B] #read] is Sort[A, B, ComparableSortFunction[B] val]

primitive Sort[A: Seq[B] ref, B: Any #read, C: SortFunction[B] val]
  fun apply(a: A, f: C = C): A^ =>
    try _sort(a, f, 0, a.size().isize() - 1)? end
    a

  fun _sort(a: A, f: C, lo: ISize, hi: ISize) ? =>
    if hi <= lo then return end
    // choose outermost elements as pivots
    if f.lt(a(hi.usize())?, a(lo.usize())?) then _swap(a, lo, hi)? end
    (var p, var q) = (a(lo.usize())?, a(hi.usize())?)
    // partition according to invariant
    (var l, var g) = (lo + 1, hi - 1)
    var k = l
    while k <= g do
      if f.lt(a(k.usize())?, p) then
        _swap(a, k, l)?
        l = l + 1
      elseif f.lt(q, a(k.usize())?) then
        while f.lt(q, a(g.usize())?) and (k < g) do g = g - 1 end
        _swap(a, k, g)?
        g = g - 1
        if f.lt(a(k.usize())?, p) then
          _swap(a, k, l)?
          l = l + 1
        end
      end
      k = k + 1
    end
    (l, g) = (l - 1, g + 1)
    // swap pivots to final positions
    _swap(a, lo, l)?
    _swap(a, hi, g)?
    // recursively sort 3 partitions
    _sort(a, f, lo, l - 1)?
    _sort(a, f, l + 1, g - 1)?
    _sort(a, f, g + 1, hi)?

  fun _swap(a: A, i: ISize, j: ISize) ? =>
    a(j.usize())? = a(i.usize())? = a(j.usize())?

// ---

// User code

primitive StringSizeSortFunction
  """
  Sort by string size.
  """
  fun lt(first: String, second: String): Bool => first.size() < second.size()

actor Main
  new create(env: Env) =>
    var array = [ "third"; "second"; "first" ]
    var sorted_array = ComparableSort[Array[String], String](array)
    for e in sorted_array.values() do
      env.out.print(e) // prints "first \n second \n third"
    end
    env.out.print("---")
    array = [ "eleven"; "three"; "one" ]
    sorted_array = Sort[Array[String], String, StringSizeSortFunction](array)
    for e in sorted_array.values() do
      env.out.print(e) // prints "one \n three \n eleven"
    end