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


 % compile_lp(+SubcatList,+LPrules,-ListOfSubcatLists)
 % finds all permutations of the subcat list that are lp acceptable 

compile_lp([],_LP,[]).
compile_lp(Subcat,LP,Result):-
	(findall(NewSubcat,
	        (permutation(Subcat,NewSubcat),
		 lp_acceptable(LP,NewSubcat)),
		Result) ->
	    true
	    ;
	    Result = []).

 
 % lp_acceptable(+ListOfLPRules,+SubcatList)
 % recurses down the lp list
 %
 % lp_acceptable([],_Subcat).
 % lp_acceptable([LPrule|T],Subcat):-
 % 	lp_aux(Subcat,LPrule),
 % 	lp_acceptable(T,Subcat).
 %
 % 
 % lp_aux(+SubcatList,+LPRule)
 % recurses through the subcat list
 %
 % lp_aux([_],_).
 % lp_aux([H|T],LP):-
 % 	lp_aux1(T,H,LP),
 % 	lp_aux(T,LP).
 %
 % 
 % lp_aux1(+RestList,+FirstOfList,+LPrule)
 % checks whether First and some elemnt from Rest unify with the
 % elements of the lp rule. If both do in a certain way, we have a
 % violation of this lp rule.
 % 
 % lp_aux1([],_,_LP).
 % lp_aux1([Next|T],H,lp(Fs1,Fs2)):-
 % 	\+ (unify_fs(Fs1,Next,_),
 % 	    unify_fs(Fs2,H,_)),
 % 	lp_aux1(T,H,lp(Fs1,Fs2)).
 % 

 % Improved by lagging to use first argument indexing since the old
 % lp_aux/2 was not deterministic
 % 
 % lp_aux([H|T],LPrule):-
 % 	lp_aux_0(T,H,LPrule).
 % 
 % lp_aux_0([],_Last,_LP).
 % lp_aux_0([Second|T],First,LP):-
 % 	lp_aux_1(T,First,Second,LP),
 % 	lp_aux_0(T,Second,LP).
 % 
 % lp_aux_1([],First,Second,lp(Fs1,Fs2)):-
 % 	\+ (unify_fs(Fs1,Second,_),
 % 	    unify_fs(Fs2,First,_)).
 % lp_aux_1([Next|T],First,Second,lp(Fs1,Fs2)):-
 % 	\+ (unify_fs(Fs1,Second,_),
 % 	    unify_fs(Fs2,First,_)),
 % 	lp_aux_1(T,First,Next,lp(Fs1,Fs2)).
 % 


 % Improved by unpacking the lp rule and testing whether it is worth
 % trying to find a violation at all.
 % 	
 % lp_acceptable([],_Subcat).
 % lp_acceptable([lp(FS1,FS2)|T],Subcat):-
 % 	lp_aux(Subcat,FS1,FS2),
 %   	lp_acceptable(T,Subcat).
 % 
 % lp_aux([],_,_).
 % lp_aux([H|T],FS1,FS2):-
 % 	(unify_fs(H,FS2,_) ->
 % 	    lp_aux_0(T,H,FS1,FS2)
 % 	;
 % 	    lp_aux(T,FS1,FS2)
 % 	).
 % 
 % lp_aux_0([],_Last,_LP).
 % lp_aux_0([Second|T],First,LP):-
 % 	lp_aux_1(T,First,Second,LP),
 % 	lp_aux_0(T,Second,LP).
 % 
 % lp_aux_1([],First,Second,lp(Fs1,Fs2)):-
 % 	\+ (unify_fs(Fs1,Second,_),
 % 	    unify_fs(Fs2,First,_)).
 % lp_aux_1([Next|T],First,Second,lp(Fs1,Fs2)):-
 % 	\+ (unify_fs(Fs1,Second,_),
 % 	    unify_fs(Fs2,First,_)),
 % 	lp_aux_1(T,First,Next,lp(Fs1,Fs2)).
 % 
 % 

 % further improvement by case analysis. Only if the first element of
 % the list matches the second part of the lp statement, we have to 
 % check whether nothing else in the list does.
 % Also improved by further lagging to stop lp_aux/4 as early as
 % possible (only one element left).

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).


