% ---------------------------------------------------------------------------- %
% heapsort.m
% Ralph Becket <rbeck@microsoft.com>
% Tue Jan  9 14:18:19 GMT 2001
% vim: ts=4 sw=4 et tw=0 wm=0 ff=unix
%
% ---------------------------------------------------------------------------- %

:- module mytest.

:- interface.

:- import_module io.


:- pred main(io__state, io__state).
:- mode main(di, uo) is det.


:- implementation.


:- import_module float, int, array, random, list, string, require.


:- type heap == array(float).


main -->
    io__command_line_arguments(ArgV),
    (   { ArgV = [],        N = 1 }
    ;   { ArgV = [Arg],     N = string__det_to_int(Arg) }
    ;   { ArgV = [_,_|_],   error("usage: heapsort [N]") }
    ),
    { A = heapsort(N - 1, random_heap(0, seed, array__init(N, 0.0))) },
    io__format("%.10f", [f(array__lookup(A, N - 1))]),
    io__nl.


:- func random_heap(int, int, heap) = heap.
:- mode random_heap(in, in, array_di) = array_uo is det.

random_heap(I, S0, H0) = H :-
    ( if I =< array__max(H0) then
        gen_random(R, S0, S),
        H = random_heap(I + 1, S, up_heap(I, R, H0))
      else
        H = H0
    ).


:- func up_heap(int, float, heap) = heap.
:- mode up_heap(in, in, array_di) = array_uo is det.

up_heap(N, Y, H) =
    ( if 0 < N, X < Y then
        up_heap(HalfN, Y, array__set(H, N, X))
      else
        array__set(H, N, Y)
    )
 :-
    HalfN = N // 2,
    X = array__lookup(H, HalfN).


:- func heapsort(int, heap) = heap.
:- mode heapsort(in, array_di) = array_uo is det.

heapsort(N, H) =
    ( if N = 0 then H else heapsort(N - 1, remove_greatest(N, H)) ).


:- func remove_greatest(int, heap) = heap.
:- mode remove_greatest(in, array_di) = array_uo is det.

remove_greatest(N, H) = down_heap(0, N - 1, Y, array__set(H, N, X)) :-
    X = array__lookup(H, 0),
    Y = array__lookup(H, N).


:- func down_heap(int, int, float, heap) = heap.
:- mode down_heap(in, in, in, array_di) = array_uo is det.

down_heap(I, N, X, H0) = H :-
    L = I + I + 1,
    R = L + 1,
    ( if N < L then
        H = array__set(H0, I, X)
      else 
        J = ( if R < N, array__lookup(H0, R) > array__lookup(H0, L) then R
                                                                    else L ),
        Y = array__lookup(H0, J),
        ( if X > Y then
            H = array__set(H0, I, X)
          else
            H = down_heap(J, N, X, array__set(H0, I, Y))
        )
    ).


:- pred gen_random(float, int, int).
:- mode gen_random(out, in, out) is det.

gen_random(R, S0, S) :-
    S = (S0 * ia + ic) `mod` im,
    R = float(S) / float(im).

:- func im = int.   im = 139968.
:- func ia = int.   ia =   3877.
:- func ic = int.   ic =  29573.
:- func seed = int. seed =   42.