/*********************************************************
	container_lib

        several common list predicates
**********************************************************/

:- tap_body(container_access, [container_lib, container_access]).

:- import_pred(prolog_misc,sort/2).


:- pred append(list(T), list(T), list(@T)). 
:- pred append_sort(list(T), list(T), list(@T)).
:- pred merge(list(T), list(T), list(@T)).

% there are variants of predicate sort_cont/2 in
% the files quicksort_var.pl and  keysort_var.pl
:- pred sort_cont(container(T), container(T)).   

/*
   append(Xs,Ys,Zs) :-
         Zs is a list obtained from concatenating lists Xs and Ys
*/

:- pred append(list(T), list(T), list(@T)).
   append([],Ys,Ys).
   append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).

/*
   append_sort(Xs,Ys,Zs) :-
         Zs is a list obtained from concatenating and sorting lists Xs and Ys
*/

:- pred append_sort(list(T), list(T), list(@T)).
   append_sort(Xs,Ys,Zs) :- append(Xs,Ys,Zs_us), sort(Zs_us,Zs).   


/*
   merge(Xs,Ys,Zs) :- 
	Zs is an ordered list of integers obtained from 
	merging the ordered lists of integers Xs and Ys.
*/

:- pred merge(list(T), list(T), list(@T)).
     merge([X|Xs],[Y|Ys],[X|Zs]) :-
	X @< Y, merge(Xs,[Y|Ys],Zs).
     merge([X|Xs],[Y|Ys],[X|Zs]) :-
	X == Y, merge(Xs,Ys,Zs).
     merge([X|Xs],[Y|Ys],[Y|Zs]) :-
	X @> Y, merge([X|Xs],Ys,Zs).
     merge([],[X|Xs],[X|Xs]).
     merge(Xs,[],Xs).



:- tap_body_end(container_access).
