/**
         
 * Warranty & Liability
         
 * To the extent permitted by applicable law and unless explicitly
         
 * otherwise agreed upon, XLOG Technologies AG makes no warranties
         
 * regarding the provided information. XLOG Technologies AG assumes
         
 * no liability that any problems might be solved with the information
         
 * provided by XLOG Technologies AG.
         
 *
         
 * Rights & License
         
 * All industrial property rights regarding the information - copyright
         
 * and patent rights in particular - are the sole property of XLOG
         
 * Technologies AG. If the company was not the originator of some
         
 * excerpts, XLOG Technologies AG has at least obtained the right to
         
 * reproduce, change and translate the information.
         
 *
         
 * Reproduction is restricted to the whole unaltered document. Reproduction
         
 * of the information is only allowed for non-commercial uses. Selling,
         
 * giving away or letting of the execution of the library is prohibited.
         
 * The library can be distributed as part of your applications and libraries
         
 * for execution provided this comment remains unchanged.
         
 *
         
 * Restrictions
         
 * Only to be distributed with programs that add significant and primary
         
 * functionality to the library. Not to be distributed with additional
         
 * software intended to replace any components of the library.
         
 *
         
 * Trademarks
         
 * Jekejeke is a registered trademark of XLOG Technologies AG.
         
 */
         

         
:- ensure_loaded(library(sets)).
         
:- ensure_loaded(library(lists)).
         

         
/**************************************************************/
         
/* Basic Corouting                                            */
         
/**************************************************************/
         

         
/**
         
 * deref(S, T):
         
 * The predicate succeeds in T with the value of the term S.
         
 */
         
% deref(+Term, -Term)
         
deref('$ATTR'(V,_), W) :- !, V = W.
         
deref(V, V).
         

         
/**
         
 * freeze(T, G):
         
 * The predicate delays the goal G on the term T.
         
 */
         
% freeze(+Term, +Goal)
         
freeze('$ATTR'(V,L), G) :- var(V), !, sys_freeze(L, G).
         
freeze(_, G) :- G.
         

         
% sys_freeze(+List, +Goal)
         
sys_freeze(V, G) :- var(V), !,
         
   ir_pred_site(G, H),
         
   V = [H|_].
         
sys_freeze([_|L], G) :-
         
   sys_freeze(L, G).
         

         
/**
         
 * bind(T, S):
         
 * The predicate succeeds when it can bind the term to the term T.
         
 */
         
% bind(+Term, +Term)
         
bind('$ATTR'(V,L), W) :- var(V), !,
         
   sys_bind(L, R),
         
   '$SEQ'(nothing,[V = W|R]).
         
bind(V, W) :-
         
   deref(V, W).
         

         
% sys_bind(+List, -List)
         
sys_bind(V, []) :- var(V), !.
         
sys_bind([G|L], [G|R]) :-
         
   sys_bind(L, R).
         

         
/**************************************************************/
         
/* Advanced Corouting                                         */
         
/**************************************************************/
         

         
/**
         
 * dif(S, T):
         
 * The predicate delays the goal S \== T on the terms S and T.
         
 */
         
% dif(+Term, +Term)
         
dif('$ATTR'(V,L), '$ATTR'(W,R)) :- var(V), var(W), !,
         
   sys_freeze(L, V \== W),
         
   sys_freeze(R, W \== V).
         
dif('$ATTR'(V,L), W) :- var(V), !, deref(W, J),
         
   sys_freeze(L, V \== J).
         
dif(V, '$ATTR'(W,R)) :- var(W), !, deref(V, H),
         
   sys_freeze(R, W \== H).
         
dif(V, W) :- deref(V, H), deref(W, J),
         
   H \== J.
         

         
/**
         
 * indomain(S, D):
         
 * The predicate succeeds in S with the elements of the list D.
         
 */
         
% indomain(+Term, +List)
         
indomain('$ATTR'(V,L), D) :- var(V), !,
         
   sys_bind(L, R),
         
   '$SEQ'(nothing,[member(V,D)|R]).
         
indomain(V, D) :- deref(V, H),
         
   member(H, D).
         

         
/**
         
 * all_different(L):
         
 * The predicate delays the goal that all elements of L are different.
         
 */
         
% all_different(+List)
         
all_different([]).
         
all_different([X|L]) :-
         
   maplist(dif(X), L),
         
   all_different(L).
         

         
/**
         
 * label(L, D):
         
 * The predicate binds the elements of L, left to right,
         
 * to the elements of D.
         
 */
         
% label(+List, +List)
         
label([], _).
         
label([X|L], D) :-
         
   indomain(X, D),
         
   label(L, D).
         

         
/***********************************************************/
         
/* Variable Ordering                                       */
         
/***********************************************************/
         

         
/**
         
 * labeling(L, D):
         
 * The predicate binds the elements of L, heuristically reordered
         
 * in advance, to the elements of D.
         
 */
         
% labeling(+List, +List)
         
labeling(L, D) :-
         
   sys_ahead(L, [], R),
         
   label(R, D).
         

         
/**
         
 * sys_ahead(L, P, R):
         
 * The predicate succeeds in R with the heuristically reordered
         
 * variable order L, taking into account the history P.
         
 */
         
% sys_ahead(+List, +List, +List)
         
sys_ahead([], _, []).
         
sys_ahead([X|L], P, [Y|R]) :-
         
   sys_score(X, P, S),
         
   sys_best(L, P, S, 1, 0, I),
         
   nth0(I, [X|L], Y, H),
         
   deref(Y, Z),
         
   sys_ahead(H, [Z|P], R).
         

         
/**
         
 * sys_score(X, P, S):
         
 * The predicate succeeds in S with the number of free variables
         
 * in the constraints for the attributed variable X, including
         
 * in the number the variables in the history P.
         
 */
         
% sys_score(+Term, +List, -Integer)
         
sys_score('$ATTR'(V,L), P, S) :- var(V), !,
         
   term_variables(P+L, H),
         
   length(H, S).
         
sys_score(_, _, 0).
         

         
% sys_best(+List, +List, +Integer, +Integer, +Integer, -Integer)
         
sys_best([], _, _, _, I, I).
         
sys_best([Y|L], P, S, K, _, O) :-
         
   sys_score(Y, P, T), T =< S, !,
         
   H is K+1,
         
   sys_best(L, P, T, H, K, O).
         
sys_best([_|L], P, S, K, I, O) :-
         
   H is K+1,
         
   sys_best(L, P, S, H, I, O).