1:-module(interval,[]). 3:- use_module(pac('expand-pac')). 5term_expansion --> pac:expand_pac.
6:- use_module(pac(op)). 7
25interval(A + B, C, [A, B], [A0, B0], interval:merge_interval2(A0, B0, C)).
26interval(&(A, B), C, [-( (- A) + (- B) )], [C], true). 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
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
64
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)