%% 031201 finite-domain solver
%% 031209 (still with errors: pyramid does not finish)
%% 050109 finally corrected (Marc)

:- use_module(library(chr)).
:- use_module(library(lists)).

handler fd.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% FD constraint solver
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% domain constraints: X in [..]
operator(700,xfy,'in').

constraints in/2.

%% empty
empty @ X in [] <=> fail.

%% keep lists short: sort (sort also removes duplicates)
short @ X in L <=> sort(L,L1), L \= L1 | X in L1.

%% (generalised) idempotency
idem  @ X in L1 \ X in L2 <=> sublist(L1, L2) | true.

%% intersection
intersection @ X in L1, X in L2 <=> intersection(L1,L2,L), X in L.

%% auxiliary predicate for intersection/ linear scan
intersection([], _, []).
intersection(_, [], []).
intersection([X|Tail1], [X|Tail2], [X|Tail3]) :-
	intersection(Tail1, Tail2, Tail3).

intersection([X|Tail1], [Y|Tail2], Tail3) :-
	 X < Y -> intersection(Tail1, [Y|Tail2], Tail3) ; intersection([X|Tail1], Tail2, Tail3).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%