:- module(_, [ham/2], [assertions, regtypes, nativeprops]).

:- use_module(library(queues)).
:- use_module(library(lists)).

:- use_module(library(system)).
:- use_module(library(format), [format/2]).
:- use_module(library(between)).

:- entry ham(Number, Ss) : num * term.
:- pred ham(Number, Ss) : num * term.

ham(Number, Ss):-
	ham_(Number, Ss).

:- pred ham_(Number, Ss) : num * term => num * listnum.
ham_(Number, Ss):-
        emptyq(Twos_),
        emptyq(Threes_),
        emptyq(Fives_),
        enqueue(1, Twos_, Twos, S1),
        enqueue(1, Threes_, Threes, S2),
        enqueue(1, Fives_, Fives, S3),
        hamming(Number, Twos, Threes, Fives, S1, S2, S3, Ss).

:- pred hamming(Number, Twos, Threes, Fives, S1, S2, S3, Ss) :
	num * listnum * listnum * listnum * num * num * num * term =>
	num * listnum * listnum * listnum * num * num * num * listnum.

hamming(0, _, _, _, _, _, _, []).
hamming(N, Twos, Threes, Fives, _, _, _, [Smaller|Ss]) :-
        N > 0,
        firstq(Twos, FTwo),
        firstq(Threes, FThree),
        firstq(Fives, FFive),
        select_smaller(FTwo, FThree, FFive, Smaller),
        try_dequeue(Twos, Smaller, NewTwos),
        try_dequeue(Threes, Smaller, NewThrees),
        try_dequeue(Fives, Smaller, NewFives),
        New2 is Smaller * 2,
        New3 is Smaller * 3,
        New5 is Smaller * 5,
        enqueue(New2, NewTwos, OtherTwos, S1new),
        enqueue(New3, NewThrees, OtherThrees, S2new),
        enqueue(New5, NewFives, OtherFives, S3new),
        N1 is N - 1,
        hamming(N1, OtherTwos, OtherThrees, OtherFives, S1new, S2new, S3new, Ss).

%:- pred emptyq(A) : term => listnum.
emptyq([]).

:- pred firstq(Q, X) : listnum * term => listnum * num.
firstq(Q, X):- myappend(_, [X], Q).

:- pred enqueue(X, Q, XQ, S) : num * listnum * term * term => num * listnum * listnum * num.
enqueue(X, Q, [X|Q], S) :-
	length([X|Q],S).

:- pred dequeue(Q, W, NQ) : listnum * term * term => listnum * num * listnum.
dequeue(Q, W, NQ):-
        myappend(NQ, [W], Q).

% (particular assertion for our case)
:- pred myappend(Xs, Ys, Zs) : term * term * listnum => listnum * listnum * listnum.
myappend([], Xs, Xs).
myappend([X|Xs], Ys, [X|Zs]) :-
	myappend(Xs, Ys, Zs).

:- pred try_dequeue(Q, What, NewQ) : listnum * num * term => listnum * num * listnum.
try_dequeue(Q, What, NewQ) :- firstq(Q, What), !,
	dequeue(Q, What, NewQ).
try_dequeue(Q, _What, NewQ):-
	Q = NewQ.

:- pred select_smaller(A,B,C,Min) : num * num * num * term => num * num * num * num.
select_smaller(A, B, C, Min):-
        min(A, B, Ma),
        min(Ma, C, Min).

:- pred min(A,B,C) : num * num * term => num * num * num.
min(A, B, C):- A < B, !,
	C = A.
min(_A, B, C):-
	C = B.

:- regtype listnum/1.
listnum([]).
listnum([X|Xs]) :- num(X), listnum(Xs).



