%%% version 4.6.12-8


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  The {log} standard library  %%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%   version 4.6    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%                  March 2008 - by Gianfranco Rossi
%             Extended August 2012 - by Gianfranco Rossi
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This file contains the {log} definition of a number of predicates,
% mostly dealing with sets and bags, which are not (yet) provided as 
% primitive in {log}. 
% It can be  loaded into the {log} environment by issuing the 
% goal consult_lib (provided 'setloglib.slog' is the name you 
% give to this file).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% General operations dealing with sets
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

powerset(S,PS) :-               % powerset(+S,?PS) is true if PS is the powerset 
     PS = {SS : subset(SS,S)}.  % of S (i.e., PS = 2^S)

cross_product(A,B,CP) :-        % cross_product(+A,+B,?CP) is true if CP is the 
     CP = {X : exists([Y,Z],    % Cartesian product of sets A and B
           X = [Y,Z] & Y in A & Z in B)}.

list_to_set([],{}).             % list_to_set(+L,?S) is true if S denotes the set
list_to_set([X|L],{X\S}) :-     % of all elements of the list L
     list_to_set(L,S).

int_to_set(int(A,A),{A}).       % int_to_set(+I,?S) is true if S denotes the set
int_to_set(int(A,B),{A\S}) :-   % of all elements of the interval I  
     A < B &
     A1 is A + 1 &
     int_to_set(int(A1,B),S).

dint_to_set(A,B,S) :-           % like int_to_set/2 but delayed if interal bounds are unknown
    delay(int_to_set(int(A,B),S),nonvar(A) & nonvar(B)).

diff1({X\R},X,R) :-             % diff1(?S,?X,?R) equivalent to diff(S,{X},R)
     X nin R.                   % but more efficient
diff1(S,X,S) :- 
     X nin S.

eq(T1,T2) :-                    % syntactic unification between terms T2 and T2
     prolog_call(T1 = T2).
 
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Improved implementations of primitive set constraints:
% to reduce the number of repeated equivalent solutions  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

xless(S,X,SS) :-               % remove the element X from S, if S is ground
     test(ground(S),R) &       % otherwise, remove any element X from S
    (R=true  & less(S,X,SS)! or
     R=false & less(S,X,SS)). 

xun(R,S,U) :-                  % union  (T = R \cup S)
     test(ground(R),H) &
    (H=true  & xxun(R,S,U) or
     H=false & un(R,S,U)). 
xxun('{}',X,X).                % T = R \cup S, with R ground    
xxun(R,S,{X\U}) :-
    less(R,X,RR)! &
    X nin S &
    xxun(RR,S,U).
xxun(R,S,U) :-
    less(R,X,RR)! &
    call(X in S) &
    xun(RR,S,U).

xdiff(R,S,U) :-                % difference (T = R \setminus S)
     test(ground(R),H) &
    (H=true  & xxdiff(R,S,U) or
     H=false & diff(R,S,U)). 
xxdiff({},_,{}).               % T = R \setminus S, with R ground  
xxdiff(R,S,T) :- 
    less(R,X,RR)! & 
    call(X in S) &
    xxdiff(RR,S,T).
xxdiff(R,S,{X\U}) :-
    less(R,X,RR)! &
    X nin S &
    xxdiff(RR,S,U).

xndiff(R,S,T) :-               % not difference (T = R \not\setminus S)
    xdiff(R,S,T1) & 
    T1 neq T.

xsdiff(R,S,T) :-               % symmetric difference (T = R \triangle S) 
    xdiff(R,S,A) &
    xdiff(S,R,B) & 
    xun(A,B,T). 

xsize(S,N) :-                  % cardinality (N = |S|)
    size(S,N).                 % for compatibility with previous releases

xsubset(S1,S2) :-              % subset (S1 \subseteq S2)
    subset(S1,S2).             % for compatibility with previous releases

xinters(R,S,U) :-              % intersection  (T = R \cap S)
    inters(R,S,U).             % for compatibility with previous releases
                  
test(Pred,Res) :-
    prolog_call((call(Pred),!,Res=true ; Res=false)).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Dealing with multisets 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 bag_to_set({},{}).              % bag_to_set(+M,?S) is true if S denotes the set
 bag_to_set(M,{X\S}) :-          % of all elements of the multiset M
     (M = *{X\R})! &
     bag_to_set(R,S).

 int_to_bag(int(A,A),*{A}).       % int_to_bag(+I,?M) is true if M denotes the multiset
 int_to_bag(int(A,B),*{A\M}) :-  % of all elements of the interval I   
     A < B &
     A1 is A + 1 &
     int_to_bag(int(A1,B),M).

 msize(S,N) :- in_msize(S,0,N).  % msize(?S,?N) is true if N is the cardinality 
 in_msize({},N,N).               % of the multiset S (i.e., N = |S|)
 in_msize(*{_\SS},N,M) :-
    N neq M &
    NN is N + 1 &
    in_msize(SS,NN,M).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Dealing with lists 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%prefix(P,L) true if list P is a prefix of list L
 prefix(P,L) :-
    append(P,_,L).

%sublist(Sb,L) true if list Sb is a sublist of list L
 sublist(Sb,L) :- 
    prefix(Sb,L).
 sublist(Sb,[H|T]) :- 
    Sb neq [] &
    sublist(Sb,T).

%take(N,L,NewL) true if list NewL consists of the
%first N elements of list L
 take(0,L,[ ]).
 take(N,[H|T],[H|R]) :- 
    N>0 & M is N-1 &
    take(M,T,R).

%drop(N,L,NewL) true if list NewL is L with its 
%first N elements removed
 drop(0,L,L).
 drop(N,[H|T],R) :- 
    N >0 & M is N-1 &
    drop(M,T,R).


% Redefining Prolog built-ins (for the user convenience)
 
 member(X,L) :- prolog_call(member(X,L)).

 append(L1,L2,L3) :- prolog_call(append(L1,L2,L3)).

 nth1(X,L,Y) :- prolog_call(nth1(X,L,Y)).

 length(L,N) :- prolog_call(length(L,N)).

 reverse(L,R) :- prolog_call(reverse(L,R)).

 last(L,X) :- prolog_call(last(L,X)).

    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Interactive help predicates
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 setlog_lib_help :-
   nl & 
   write('The {log} library provides a number of predicates ') & nl & 
   write('dealing with sets and bags which are not provided ') & nl &
   write('as primitive in {log}.') & nl & nl &
   write('It can be loaded into the {log} environment by issuing the ') & nl & 
   write('goal consult_lib (provided ''setloglib.slog'' is the name you ') & nl &
   write('give to the library file).') & nl.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Improved {log} set constraints, allowing intervals with
%%%% unknown bounds - user-defined predicates
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

:- prolog_call(op(700,xfx,[ein,enin])).

%%%%%%%%%%%% membership T ein S
 T ein S :-
     T in S.  
  
%%%%%%%%%%%% not membership T enin S
 T enin S :-
      T nin S.

%%%%%%%%%%%% intersection einters(S1,S2,S3) 
 einters(S1,S2,S3) :-
     inters(S1,S2,S3).

%%%%%%%%%%%% inclusion esubset(S1,S2)
 esubset(S1,S2) :-
     prolog_call(
         (nonvar(S1), nonvar(S2), 
          S1=int(A1,B1), S2=int(A2,B2), \+ground([A1,B1,A2,B2]),!,R = case1 
          ; 
          unbounded_int(S1),!,R = case2
          ;
          unbounded_int(S2),!,R = case3
          ;
          R = case4
         )
     ) &
    esubset(R,S1,S2).

 esubset(case1,I,_) :-                    % subset(empty_interval,int)
     I = {}.
 esubset(case1,I1,I2) :-                  % subset(int,int)
     eq(I1,int(A1,B1)) & eq(I2,int(A2,B2)) &
     I1 neq {} & I2 neq {} &
     A1 >= A2 & B1 =< B2.
 esubset(case2,I,S) :-                    % subset(empty_interval,set)
     eq(I,int(A,B)) &
     set(S) & A > B.
 esubset(case2,I,S) :-                    % subset(singleton_interval,set)
     eq(I,int(A,A)) &
     set(S) & A in S. 
 esubset(case2,I,S) :-                    % subset(int,set)
     eq(I,int(A,B)) &
     set(S) & A < B & 
     A in S &
     A1 is A + 1 &
     esubset(int(A1,B),S).          
 esubset(case3,{},_).                     % subset({},int)
 esubset(case3,S,I) :-                    % subset(set,int)
     eq(I,int(A,B)) &
     set(S) & S neq {} &
     smin(S,N) & smax(S,M) &
     N >= A & M =< B.
 esubset(case4,S1,S2) :-                  % subset(_AnyOther,_AnyOther)
     subset(S1,S2).
 
%%%%%%%%%%%% strict inclusion essubset(S1,S2) - TO BE COMPLETED!!
 essubset(S1,S2) :-
     prolog_call(
         (nonvar(S1), nonvar(S2), 
          S1=int(A1,B1),S2=int(A2,B2),\+ground([A1,B1,A2,B2]),!,R = case1 
          ; 
%          unbounded_int(S1),!,R = case2
%          ;
%          unbounded_int(S2),!,R = case3
%          ;
          R = case4
         )
     ) &
     essubset(R,S1,S2).

 essubset(case1,I1,I2) :-                  % ssubset(empty_int,non-empty_int)
     eq(I1,int(A1,B1)) & eq(I2,int(A2,B2)) &
     I1 = {} &
     A2 =< B2.
 essubset(case1,I1,I2) :-                  % ssubset(non-empty_int,non-empty_int)
     eq(I1,int(A1,B1)) & eq(I2,int(A2,B2)) &
     I1 neq {} & I2 neq {} &
     (A1 > A2 & B1 =< B2 or A1 >= A2 & B1 < B2).
 essubset(case4,S1,S2) :-                  % nsubset(_AnyOther,_AnyOther)
     ssubset(S1,S2).

%%%%%%%%%%%% not inclusion ensubset(S1,S2) - TO BE COMPLETED!!
 ensubset(S1,S2) :-
     prolog_call(
         (nonvar(S1), nonvar(S2), 
          S1=int(A1,B1),S2=int(A2,B2),\+ground([A1,B1,A2,B2]),!,R = case1 
          ; 
%          unbounded_int(S1),!,R = case2
%          ;
%          unbounded_int(S2),!,R = case3
%          ;
          R = case4
         )
     ) &
     ensubset(R,S1,S2).

 ensubset(case1,I1,I2) :-                  % nsubset(int,int)
     eq(I1,int(A1,B1)) & eq(I2,int(A2,B2)) &
     I1 neq {} & I2 neq {} &
     (A1 < A2 or B2 < B1).
 ensubset(case4,S1,S2) :-                  % nsubset(_AnyOther,_AnyOther)
     nsubset(S1,S2).


%%%%%%%%%%%%%% for compatibility with previous releases %%%%%%%%%%%%%% 

 dsubset(S1,S2) :- esubset(S1,S2).

 dnsubset(S1,S2) :- ensubset(S1,S2).

 dssubset(S1,S2) :- essubset(S1,S2).

 dinters(S1,S2,S3) :- einters(S1,S2,S3).

 
%%%%%%%%%%%%%%% Auxiliary predicates - Prolog code

 setlog_prolog :-
    prolog_call(assert((user:unbounded_int(I) :- nonvar(I), I=int(A,B), (var(A),! ; var(B)) ))).

:- setlog_prolog.