:- use_module(library(lists),[permutation/2,permutation/3,insert/3]). 
:- ensure_loaded(type_union4).
:- ensure_loaded(utilities).


 % O'Keefe p.204: filtering the elements of a list that pass a certain
 % test, in this case lp acceptability.
 
 % compile_lp(+SubcatList,+LPrules,-ListOfSubcatLists)
 % finds all permutations of the subcat list and checks afterwards which
 % are lp acceptable  

compile_lp([],_LP,[]).
compile_lp(Subcat,LP,ValidSubcat):-
	findall(NewSubcat,
	        permutation(Subcat,NewSubcat),
		Result),
        lp_acceptable_1(Result,LP,ValidSubcat).
 
% first intermediate step
% lp_acceptable1(List,Test_LP,Sublist):-
% 	sublist(List,Test_LP,X,X,Sublist,[]).
% 
% sublist([],_LP,R0,R,R0,R).
% sublist([H|T],Test_LP,L0,L,R0,R):-
% 	filter(Test_LP,H,L0,L,M0,M),
% 	sublist(T,Test_LP,M0,M,R0,R).
% 
% filter(Test_LP,H,,M0,[H|M],M0,M):-
% 	lp_acceptable(Test_LP,H),!.
% filter(_,_,M0,M,M0,M).

% second intermediate step
% lp_acceptable1(List,Test_LP,Sublist):-
%  	sublist(List,Test_LP,Sublist).
%  
% sublist([],_LP,[]).
% sublist([H|T],Test_LP,Sublist0):-
% 	filter(Test_LP,H,Sublist0,Sublist1),
%  	sublist(T,Test_LP,Sublist1).
%  
% filter(Test_LP,H,,[H|M],M):-
%  	lp_acceptable(Test_LP,H),!.
% filter(_,_,M,M).


lp_acceptable_1(List,Test_LP,Sublist):-
  	sublist(List,Test_LP,Sublist).

sublist([],_LP,[]).
sublist([H|T],Test_LP,Sublist0):-
 	lp_acceptable(Test_LP,H),
	!,
	Sublist0 = [H|Sublist1],
  	sublist(T,Test_LP,Sublist1).
sublist([_|T],Test_LP,Sublist):-
	sublist(T,Test_LP,Sublist).


 % for comments on this code, see compile_version_1.pl

lp_acceptable([],_Subcat).
lp_acceptable(LP,[H|T]):-
	lp_acceptable_0(LP,H,T).

lp_acceptable_0([],_First,_Rest).
lp_acceptable_0([lp(FS1,FS2)|T],First,Rest):-
	lp_aux(Rest,First,FS1,FS2),
	lp_acceptable_0(T,First,Rest).


lp_aux([],_Last,_,_).
lp_aux([H|T],First,FS1,FS2):-
	(unify_fs(First,FS2,_) ->
	    lp_aux_0(T,H,FS1)
	;
	    lp_aux(T,H,FS1,FS2)
	).

lp_aux_0([],H,FS1):-
	\+ unify_fs(H,FS1,_).	
lp_aux_0([Second|T],First,FS1):-
	\+ unify_fs(First,FS1,_),
	lp_aux_0(T,Second,FS1).
