% vim: ts=4 sw=4 et ft=mercury

% mmc --make --fully-strict -E -v -O 0 --use-subdirs rodcut

% RUN: no memo statements (commented out). Output is correct.
% rodcut 494>./rodcut
% Rod Cutting. Input length rod n: 1, 2, 3, 4..., output max cut value.
% 1
% rn_main(1)=1.
% 2
% rn_main(2)=5.
% 3
% rn_main(3)=8.
% 4
% rn_main(4)=10.

%%%%%%%% If we put memo statement in, then following error is Produced.
%
% Rod Cutting. Input length rod n: 1, 2, 3, 4..., output max cut value.
% 1
% rn_main(1)=1.
%
% 2
% Uncaught Mercury exception:
% Software Error: detected need for minimal model in pred rodcut.rn_main/3

:- module rodcut.
:- interface.
:- import_module io.

:- pred main(io::di, io::uo) is cc_multi.

:- implementation.
:- import_module array, int, list, string.

:- pred main1(io::di, io::uo) is cc_multi.

:- func get_revenue(int, array(int)) = int.
get_revenue(K, P) = array.lookup(P, K-1). % K-1 because 0 based counting

% Implement rn_main, bottom of page 362 Dynamic programming, Cormen text.
% Should be implementing 15.2 rn_main = max (p_i + rn_main-i)
%                                                  1 <= i <= n, r0=0

:- pred rn_main(int, array(int), int).
:- mode rn_main(in, in, out) is multi.
:- pragma memo(rn_main/3).

rn_main(1, P, Mx) :-
    Mx = get_revenue(1, P).
rn_main(N, P, Mx) :-
    rn_aux(get_revenue(N, P), 1, N-1, P, Mx).

:- pred rn_aux(int, int, int, array(int), int).
:- mode rn_aux(in, in, in, in, out) is multi.

rn_aux(Mx, LowIndx, HighIndx, P, Max) :-
    ( if LowIndx > HighIndx then
        Max = Mx
    else
        rn_main(LowIndx, P, Lw),
        rn_main(HighIndx, P, Hg),
        NewMax = int.max(Mx, Lw + Hg),
        rn_aux(NewMax, LowIndx + 1, HighIndx -1, P, Max)
    ).

% Start with N=1, then N=2, up to N=4
:- pred doRodCut(int, int).
:- mode doRodCut(in, out) is multi.

doRodCut(N, Max) :-
    P = array.array([1, 5, 8, 9]), % array might be larger than N
    rn_main(N, P, Max).

main(!IO) :-
    io.write_string("Input length rod n: 1, 2, 3, 4... ", !IO),
    io.write_string("output max cut value.\n", !IO),
    main1(!IO).

main1(!IO) :-
    io.write_string("rod length> ", !IO),
    io.read_line_as_string(Result, !IO),
    (
        Result = eof,
        io.format("EOF, Quit\n", [], !IO)
    ;
        Result = error(Error),
        io.format("IO error: %s\n", [s(io.error_message(Error))], !IO)
    ;
        Result = ok(Nstr),
        ( if string.to_int(string.strip(Nstr), N) then
            doRodCut(N, Mx),
            io.format("rn_main(%d)=%d.\n\n", [i(N), i(Mx) ], !IO)
        else
            io.format("Input is not a number.\n", [], !IO)
        ),
        main1(!IO)
    ).