1:- module(iboole, [i_boole/2]). 6
7i_normal(X, Y):- i_normal(X, X0, []),
8 predsort(i_compare, X0, X1),
9 i_merge(X1, Y).
10
12i_normal([], P, P).
13i_normal([X|Y], P, Q):- i_check(X, P, R), i_normal(Y, R, Q).
14
16i_check(X, _, _):- var(X), throw(iterval(variable(X))).
17i_check(X-Y, P, Q):- nonvar(X), nonvar(Y), i_end(X), i_end(Y), !,
18 i_check(X, Y, P, Q).
19i_check(X, [X-X|P], P):- integer(X), !.
20i_check(X, _, _):- throw(interval(unknown(X))).
21
23i_check(inf, inf, P, P).
24i_check(sup, sup, P, P).
25i_check(X, Y, P, Q):- i_add_one(X-Y, P, Q).
26
28i_end(sup).
29i_end(inf).
30i_end(X):- integer(X).
31
33i_compare(C, X-Y, X-Z) :- !, x_compare(C, Y, Z).
34i_compare(C, X-_, Y-_) :- x_compare(C, X, Y).
35
37x_compare(=, X, X).
38x_compare(<, _,sup).
39x_compare(>, sup,_).
40x_compare(>, _,inf).
41x_compare(<, inf,_).
42x_compare(C, X, Y):- compare(C, X, Y).
43
45i_less(inf, X):- X\== inf.
46i_less(X, sup):- X\== sup.
47i_less(X, Y):- integer(X), integer(Y), X<Y.
48
50i_max(_, sup, sup).
51i_max(sup, _, sup).
52i_max(inf, X, X).
53i_max(X, inf, X).
54i_max(X, Y, X):- X > Y.
55i_max(_, Y, Y).
56
58i_min(X, sup, X).
59i_min(sup, X, X).
60i_min(_, inf, inf).
61i_min(inf, _, inf).
62i_min(X, Y, X):- X<Y,!.
63i_min(_, Y, Y).
64
66
67i_on(X, A-B):- (A==inf; A =< X), !, X @=< B.
68
69
72
73i_succ(sup, sup).
74i_succ(inf, inf).
75i_succ(X, Y):- plus(X, 1, Y).
76
85
86
87i_boole(normal(X), Y):- i_normal(X, Y).
88i_boole(dot(X), Y):- i_boole(X, Y).
89i_boole(out(X), Y):- i_boole(X, X0), i_neg(X0, Y).
90i_boole(^(X), Y):- i_boole(out(X), Y).
91i_boole(\+(X), Y):- i_boole(out(X), Y).
92i_boole((X|Y), Z):- i_boole(X, X0),
93 i_boole(Y, Y0),
94 i_cup(X0, Y0, Z).
95i_boole((X;Y), Z):- i_boole((X|Y), Z).
96i_boole(&(X,Y), Z):- i_boole(X, X0),
97 i_boole(Y, Y0),
98 i_cap(X0, Y0, Z).
99i_boole(\(X,Y), Z):- i_boole(X, X0),
100 i_boole(Y, Y0),
101 i_subtract(X0, Y0, Z).
102i_boole(X, X).
103
105i_add([], P, P).
106i_add([X|Xs], P, Q):- i_add_one(X, P, R),!,
107 i_add(Xs, R, Q).
108
110i_add_one(X-Y, P, P):- integer(X), integer(Y), Y < X.
111i_add_one(_-inf, P, P).
112i_add_one(sup-_, P, P).
113i_add_one(X, [X|P], P).
114
117
118i_cap(X, Y, P):- i_cap(X, Y, P, []).
119
121i_cap([], _, P, P).
122i_cap(_, [], P, P).
123i_cap([X|Xs],[Y|Ys], P, Q):- i_cap(X, Y, NXs, Xs, NYs, Ys, P, R), !,
124 i_cap(NXs, NYs, R, Q).
125
127i_cap(LX-RX, LY-RY, P, Q, R, S, T, U):-
128 i_max(LX, LY, Min),
129 i_min(RX, RY, Max),
130 i_succ(RY, Y0),
131 i_succ(RX, X0),
132 i_add_one(Y0-RX, P, Q),
133 i_add_one(X0-RY, R, S),
134 i_add_one(Min-Max, T, U).
135
139
140i_cup([], Y, Y).
141i_cup(X, [], X).
142i_cup(X, Y, Z):- select_smaller(S, X, Y, X0, Y0),
143 i_cup(S, X0, Y0, Z).
144
146i_cup(X, [], Y, Z):- i_cup_one(X, Y, Z).
147i_cup(X, Y, [], Z):- i_cup_one(X, Y, Z).
148i_cup(X, As, Bs, Z):- select_smaller(Y, As, Bs, Cs, Ds),
149 i_cup(X, Y, Cs, Ds, Z).
150
152i_cup(X-X0, Y-Y0, As, Bs, [X-X0|Z]):- i_off(X0, Y), !,
153 i_cup(Y-Y0, As, Bs, Z).
154i_cup(X-X0, _-Y0, As, Bs, Z):- i_max(X0, Y0, M),
155 i_cup(X-M, As, Bs, Z).
156
158i_cup_one(X, [], [X]).
159i_cup_one(X-X0, [Y-Y0|Ys], [X-X0, Y-Y0|Ys]):- i_off(X0, Y), !.
160i_cup_one(X-X0, [_-Y0|Ys], Z):- i_max(X0, Y0, M),
161 i_cup_one(X-M, Ys, Z).
162
166i_subtract(X, Y, Z):- i_subtract(X, Y, Z, []).
167
169i_subtract([], _, P, P).
170i_subtract(X, [], P, Q):- append(X, Q, P).
171i_subtract([LX-RX|Xs], [LY-RY|Ys], P, Q):-
172 i_succ(RY, RY0),
173 i_succ(LY0, LY),
174 i_succ(RX, RX0),
175 i_add_one(LX-LY0, P, R),
176 i_add_one(RY0-RX, NXs, Xs),
177 i_add_one(RX0-RY, NYs, Ys),
178 i_subtract(NXs, NYs, R, Q).
179
183
184i_neg(X, Y):- i_neg(inf, X, Y, []).
185
186i_neg(W, [], P, Q):- i_add_one(W-sup, P, Q).
187i_neg(W, [X-Y|Z], P, Q):-
188 i_succ(X0, X),
189 i_succ(Y, Y0),
190 i_add_one(W-X0, P, R),
191 i_neg(Y0, Z, R, Q).
192
193
198
199i_merge([], []).
200i_merge([X], [X]).
201i_merge([X-X0, Y-Y0|Z], [X-X0|U]):- i_off(X0, Y), !,
202 i_merge([Y-Y0|Z], U).
203i_merge([X-X0, _-Y0|Z], U):- i_max(X0, Y0, M),
204 i_merge([X-M|Z], U).
205
206
214
215i_partition(X, Y, Z):- i_partition(X, Y, Z, []).
216
218i_partition([], _, P, P).
219i_partition(X, [], P, Q):- append(X, Q, P).
220i_partition([LX-RX|Xs], [_-RY|Ys], P, Q):- i_less(RY, LX), !,
221 i_partition([LX-RX|Xs], Ys, P, Q).
222i_partition([LX-RX|Xs], [LY-RY|Ys], [LX-RX|P], Q):- i_less(RX, LY), !,
223 i_partition(Xs, [LY-RY|Ys], P, Q).
224i_partition([LX-RX|Xs], [LY-RY|Ys], P, Q):-
225 i_max(LX, LY, L),
226 i_min(RX, RY, R),
227 i_succ(L0, L),
228 i_add([LX-L0, L-R], P, P0),
229 i_succ(RX, RX0),
230 i_add_one(RX0-RY, NYs, Ys),
231 i_succ(RY, RY0),
232 i_add_one(RY0-RX, NXs, Xs),
233 i_partition(NXs, NYs, P0, Q).
234
242
243m_partition([], []).
244m_partition([X|Y], [X0|Z]):- m_partition(Y, Z0),
245 m_partition(X, Z0, X0, Z).
246
247m_partition(X, [], X, []).
248m_partition(X, [Y|Z], X1, [Y0|V]):-
249 m_partition_one(X, Y, X0, Y0),
250 m_partition(X0, Z, X1, V).
257m_partition_one(X, Y, Z, U):- m_partition_one(X, Y, Z, [], U, []).
258
260m_partition_one([], Y, P, P, Q, R):- append(Y, R, Q).
261m_partition_one(X, [], P, Q, R, R):- append(X, Q, P).
262m_partition_one([LX-RX|Xs], [LY-RY|Ys], P, Q, [LY-RY|U], V):- i_less(RY, LX), !,
263 m_partition_one([LX-RX|Xs], Ys, P, Q, U, V).
264m_partition_one([LX-RX|Xs], [LY-RY|Ys], [LX-RX|P], Q, U, V):- i_less(RX, LY), !,
265 m_partition_one(Xs, [LY-RY|Ys], P, Q, U, V).
266m_partition_one([LX-RX|Xs], [LY-RY|Ys], P, Q, U, V):- i_max(LX, LY, L),
267 i_min(RX, RY, R),
268 i_succ(L0, L),
269 i_add([LX-L0, L-R], P, P0),
270 i_succ(RX, RX0),
271 i_add_one(RX0-RY, NYs, Ys),
272 i_succ(RY, RY0),
273 i_add_one(RY0-RX, NXs, Xs),
274 i_add([LY-L0, L-R], U, U0),
275 m_partition_one(NXs, NYs, P0, Q, U0, V).
276
278i_off(X, Y):- integer(X), integer(Y), !, Y > X+1.
279i_off(inf, X):- !, X\==inf.
280i_off(X, sup):- X\==sup.
281
283select_smaller(C, [A|As], [B|Bs], X, Y) :- i_compare(P, A, B),
284 ( P == (=) -> C=A, X=As, Y=Bs
285 ; P == (<) -> C=A, X=As, Y=[B|Bs]
286 ; C = B, X = [A|As], Y = Bs
287 ).
293keymerge([], []).
294keymerge([A-X|R], [A-[X|P]|R0]):- keymerge(A, R, P, [], S),
295 keymerge(S, R0).
297keymerge(A, [A-X|R], [X|P], Q, S):- keymerge(A, R, P, Q, S).
298keymerge(_, R, P, P, R).
299
303
304keymerge_r([], []).
305keymerge_r([X-A|R], [[X|P]-A|R0]):- keymerge_r(A, R, P, [], S),
306 keymerge_r(S, R0).
308keymerge_r(A, [X-A|R], [X|P], Q, S):- keymerge_r(A, R, P, Q, S).
309keymerge_r(_, R, P, P, R)