1:-module(interval,[]).    2% :- use_module('pac-core').
    3:- use_module(pac('expand-pac')).    4% :- expects_dialect(pac).
    5term_expansion --> pac:expand_pac.
    6:- use_module(pac(op)).    7
    8% ?- eval(interval:interval, i(1)+i(1), X).
    9% X = [i(1)]
   10% ?- eval(interval:interval, i(1)+i(1,2), X).
   11% X = [i(1)]
   12% ?- eval(interval:interval, i(1,1)+i(2,3), X).
   13% X = [i(1, 3)]
   14% ?- eval(interval:interval, i(2,3)+i(1,1), X).
   15% X = [i(1, 3)]
   16% ?- eval(interval:interval, i(3, 4)+i(1,1), X).
   17% X = [i(1, 1), i(3, 4)]
   18% ?- eval(interval:interval, i(3, 4) & i(1,1), X).
   19% X = []
   20% ?- eval(interval:interval, -( i(3, 4) & i(1,1)), X).
   21% X = [i(0)]

   25interval(A + B, C, [A, B], [A0, B0], interval:merge_interval2(A0, B0, C)).
   26interval(&(A, B), C, [-( (- A) + (- B) )], [C], true).  % de Morgan law
   27interval(-(A), C, [A], [A0], interval:complement(A0,C)).
   28interval(i(A), [i(A0)], [is::A], [A0], true).
   29interval(i(A,B), [i(A0,B0)], [is::A, is::B], [A0, B0], true).
   30interval(X, X, [], [], true).
   31
   32merge_interval2(X, Y, Z):- append(X, Y, Z0),
   33	sort_interval(Z0, Z1),
   34	merge_interval(Z1, Z).
   35
   36%%% merge intervals
   37% ?- interval:merge_interval([i(0, 9), i(10,12)], X).
   38% X = [i(0, 12)]
   39
   40merge_interval([], []).
   41merge_interval([I|Is0], Is):- merge_interval(Is0, Is1),
   42	merge_interval(I, Is1, Is).
   43
   44merge_interval(I, [], [I]).
   45merge_interval(I, [J|Js0], Js):- merge_one(I, J, I0), !,
   46	merge_interval(I0, Js0, Js).
   47merge_interval(I, Is0, [I|Is]):- merge_interval(Is0, Is).
   48
   49merge_one(i(P0, Q0), i(P1, Q1), i(P, Q)) :-
   50	(P0 =< P1 -> P1-Q0 =< 1;  P0 - Q1 =< 1),
   51	P is min(P0, P1),  Q is max(Q0, Q1).
   52merge_one(i(P0, Q0), i(P1), i(P)):-
   53	(P0 =< P1 -> P1-Q0 =< 1; true),
   54	P is min(P0, P1).
   55merge_one(i(P0), i(P1,Q1), i(P)):-
   56	(P0 =< P1 -> true; P0-Q1=<1),
   57	P is min(P0, P1).
   58merge_one(i(P0), i(P1), i(P)):- P is min(P0,P1).
   59
   60% ?- interval:sort_interval([i(3,3), i(2)], X).
   61% X = [i(2), i(3, 3)]
   62% ?- interval:complement([i(0, 3), i(6, 8), i(10)], X).
   63% X = [i(4, 5), i(9, 9)]
   64
   65% sort_interval(X, Y):- sort:predsort(interval:interval_order, X, Y).
   66sort_interval(X, Y):- predsort(interval_order, X, Y).
   67
   68complement(Is, Js):-  complement(0, Is, Ks), remove_empty(Ks, Js).
   69
   70complement(L, [], [i(L)]).
   71complement(L, [i(P)], [i(L, P0)]):- P0 is P-1.
   72complement(L, [i(P,Q)|Is], [i(L, P0)|Js]):-
   73	 P0 is P-1,
   74	 Q0 is Q+1,
   75         complement(Q0, Is, Js).
   76
   77remove_empty(X, Y):- act(cons_unless(empty), X, Y, []).
   78
   79cons_unless(P, X, Y, Y):- call(P, X), !.
   80cons_unless(_, X, [X|Y], Y).
   81
   82empty(i(P,Q)):- Q < P.
   83
   84interval_order(D, X, Y):- arg(1, X, P), arg(1, Y, Q), compare(D0, P, Q),
   85	(D0= '=' -> compare(D, X, Y); D = D0)