:- ensure_loaded(typeops_meta).

:- import(prolog_arith).
:- import_type(prolog_types,list(T)).


:- suptype numexpr > posint.


%++++++++++++++++++++++++++ predicates ++++++++++++++++++++++++++

:- import_pred(prolog_meta, fcall/3).
:- import_pred(prolog_meta, [!/0, (\+)/1, '='/2]).



:- pred sort(meta((trmName(list(@T), list(@T)) of mpred)),
	           list(T), list(T)).
sort(Algorithm, Xs, Ys) :- fcall(Algorithm, Xs,Ys).


:- pred bubblesort_up(list(T), list(T)).         % TAP: not generic
bubblesort_up(Xs, Ys)   :- bubblesort(<, Xs, Ys).   % ill-typed

:- predl bubblesort_down(list(T), list(T)).      % TAP: use of predl
bubblesort_down(Xs, Ys) :- bubblesort(>=, Xs, Ys).



:- pred bubblesort(meta((trmName(T, T) of mpred)), list(T), list(T)).
bubblesort(_Operator, [],[]).
bubblesort(Operator, [X|Xs],[Bubble|Zs]) :- 
	sink(Operator, X, Xs, Bubble, Ys), 
	bubblesort(Operator,Ys,Zs).

:- pred sink(meta((trmName(T, T) of mpred)), T, list(T), T, list(T)).
sink(_Operator,X,[],X,[]).
sink(Operator,X, [Y|Ys], Bubble, [Z|Zs]) :- fcall(Operator,X,Y), !,
	Z = Y, sink(Operator, X, Ys,  Bubble, Zs).
sink(Operator, X, [Y|Ys], Bubble, [Z|Zs]) :- \+ fcall(Operator,X,Y), !,
	Z = X, sink(Operator, Y, Ys, Bubble, Zs).


%----

:- pred mergesort(list(T), list(T)).
mergesort(Xs, Ys) :- partition(Xs, Xss), merge(Xss, Ys).

:- pred partition(list(T), list(list(T))).
partition([], []).
partition([X | Xs], [[Z] | Zs]) :- Z = X, partition(Xs, Zs).

:- pred merge(list(list(T)), list(T)).
merge([], []).
merge([Xs],Xs).
merge(Xss, Ys) :- merge2(Xss,Zss), merge(Zss, Ys).

:- pred merge2(list(list(T)), list(list(T))).
merge2([], []).
merge2([Xs], [Xs]).
merge2([X1s, X2s | Xss], [Zs | Zss]) :-
         merge_lists(X1s, X2s, Zs),
	 merge2(Xss, Zss).

:- predl merge_lists(list(T), list(T), list(T)).     % TAP: use of predl
merge_lists([], X2s, X2s).
merge_lists(X1s, [], X1s).
merge_lists([X1 | X1s], [X2 | X2s], [Z | Zs]) :-
         X1 < X2,
	 Z = X1,
	 merge_lists(X1s, [X2 | X2s], Zs).
merge_lists([X1 | X1s], [X2 | X2s], [Z | Zs]) :-
         X1 >= X2,
	 Z = X2,
	 merge_lists([X1 | X1s], X2s, Zs).



%+++++++++++++++++++++++++  tests ++++++++++++++++++++++++++

?- bubblesort(>=, [5,9,3,1], X).
?- bubblesort(<,[5,9,3,1], X).

?- sort(bubblesort_up,   [745,73,58,26,46], X).
?- sort(bubblesort_down, [745,73,58,26,46], X).
?- sort(mergesort,       [745,73,58,26,46], X).

?- sort(bubblesort, [745,73,58,26,46], X).   % ill-typed,  wrong meta predicate


