/*************************************************************************

         name: solveConstraint.pl
      version: Mar 10, 2002
  description: solver for clls dominance constraints 
       author: Aljoscha Burchardt
 
*************************************************************************/

:- module(solveConstraint,[solve/2]).

:- use_module(cllsLib,[hasCycle/1,idom/3,reachable/3]).

/*========================================================================
  Solver Predicates
========================================================================*/

solve(Usr,Solutions) :-
	normalize(Usr,NormalUsr),
	distribute(NormalUsr,Dist1,Dist2),
	solve(Dist1,Solutions1),
	solve(Dist2,Solutions2),
	append(Solutions1,Solutions2,Solutions).

solve(Usr,[NormalUsr]) :-
	normalize(Usr,NormalUsr),
	\+ hasCycle(NormalUsr).

% no solution results in an empty list
solve(_Usr,[]).

normalize(Usr,Normal) :-
	liftDominanceConstraints(Usr,Lifted),
	elimRedundancy(Lifted,Normal).
	

liftDominanceConstraints(Usr,Lifted) :-
	Usr = usr(Ns,LCs,DCs,BCs),
	mySelect(dom(X,Y),DCs,RestDCs),
	idom(Z,Y,Usr),!,
	liftDominanceConstraints(usr(Ns,LCs,[dom(X,Z)|RestDCs],BCs),Lifted).

liftDominanceConstraints(Usr,Usr).

elimRedundancy(usr(Ns,LCs,DCs,BCs),Irredundant) :-
	mySelect(dom(X,Y),DCs,DCsRest),
	reachable(Y,X,usr(Ns,LCs,DCsRest,BCs)),!,
	elimRedundancy(usr(Ns,LCs,DCsRest,BCs),Irredundant).

elimRedundancy(Usr,Usr).

distribute(usr(Ns,LCs,DCs,BCs),usr(Ns,LCs,[dom(X,Y)|DCs],BCs),usr(Ns,LCs,[dom(Y,X)|DCs],BCs)) :-
	member(dom(X,Z),DCs),
	member(dom(Y,Z),DCs),
	X \== Y.


/*========================================================================
   The select/3 of older SWI versions has a different order of the 
   arguments. If you have an up-to-date version, you can use select/3.
========================================================================*/

mySelect(X,[X|L],L).
mySelect(X,[Y|L1],[Y|L2]):-
   mySelect(X,L1,L2).