1:- module(iboole, [i_boole/2]).    2% ?- iboole:i_normal([inf-sup, sup-inf, 3], R).
    3% ?- iboole:i_normal([3], R).
    4% ?- iboole:i_normal([3-2], R).
    5% syntax checking of intervals.
    6
    7i_normal(X, Y):- i_normal(X, X0, []),
    8	predsort(i_compare, X0, X1),
    9	i_merge(X1, Y).
   10
   11%
   12i_normal([], P, P).
   13i_normal([X|Y], P, Q):- i_check(X, P, R), i_normal(Y, R, Q).
   14
   15%
   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
   22%
   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
   27%
   28i_end(sup).
   29i_end(inf).
   30i_end(X):- integer(X).
   31
   32%
   33i_compare(C, X-Y, X-Z)  :- !, x_compare(C, Y, Z).
   34i_compare(C, X-_, Y-_)  :- x_compare(C, X, Y).
   35
   36%
   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
   44%
   45i_less(inf, X):- X\== inf.
   46i_less(X, sup):- X\== sup.
   47i_less(X, Y):- integer(X), integer(Y), X<Y.
   48
   49%
   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
   57%
   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
   65%  ?- iboole:i_on(-2, inf- sup).
   66
   67i_on(X, A-B):-   (A==inf; A =< X), !, X @=< B.
   68
   69
   70% ?- iboole:i_succ(1,X).
   71% ?- iboole:i_succ(X,2).
   72
   73i_succ(sup, sup).
   74i_succ(inf, inf).
   75i_succ(X, Y):- plus(X, 1, Y).
   76
   77%%% Boolean operations on sets of intergers represented
   78% as a list of characters
   79% and intervals of characters, e.g, [a, c-k, u, x-z].
   80% ?-  iboole:i_boole([^, 3-5],  R).
   81% ?-  iboole:i_boole(\+ ([3-5]),  R).
   82% ?-  iboole:i_boole([3-5];[4-8],  R).
   83% ?-  iboole:i_boole([1-10]&([3-5]|[4-8, 8-12]),  R).
   84%@ R = [3-10] .
   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
  104%
  105i_add([], P, P).
  106i_add([X|Xs], P, Q):- i_add_one(X, P, R),!,
  107	i_add(Xs, R, Q).
  108
  109%
  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
  115% ?- i_cap([1-10],[3-6, 8-8], R).
  116% R = [3-6,8-8] 
  117
  118i_cap(X, Y, P):- i_cap(X, Y, P, []).
  119
  120%
  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
  126%
  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
  136%  union of two intervals sets.
  137% i_cup([1-5, 7-10], [6-6], R).
  138% R = [1-10] 
  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
  145%
  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
  151%
  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
  157%
  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
  163% ?- i_subtract([1-10],[3-6], R).
  164% R = [1-2,7-10]
  165%  Remark:  i_subtract(X,Y,Z):- i_neg(Y, Y0), i_cap(X, Y0, Z).
  166i_subtract(X, Y, Z):- i_subtract(X, Y, Z, []).
  167
  168%
  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
  180% computing the complement of intervals.
  181% boole:  ?- i_neg([3-5, 7-9], R).
  182% R = [inf-2,6,10-sup] 
  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
  194% ?- iboole:i_merge([10-sup, inf- 9], X).
  195%@ X = [10-sup] .
  196% ?- iboole:i_merge([9-9, 10-10], X).
  197%@ X = [9-10] .
  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
  207% ?- i_partition([1-3], [2-2], X).
  208% X = [1-1,2-2,3-3] 
  209% ?- iboole:i_partition([1-3], [2-4], X).
  210%@ X = [1-1, 2-3] .
  211% ?- iboole:i_partition([1-3], [2-4], X).
  212% ?- iboole:i_partition([inf-sup], [-3 - -3, -2 - -2, -1 - -1],  X).
  213%@ X = [inf- -4, -3- -3, -2- -2, -1- -1, 0-sup] .
  214
  215i_partition(X, Y, Z):- i_partition(X, Y, Z, []).
  216
  217%
  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
  235% ?- m_partition([[1-5],[3-6]],R).
  236% R = [[1-2,3-5],[3-5,6-6]] 
  237% ?- iboole:m_partition([[1-2, 3-5],[3-6]],R).
  238%@ R = [[1-2, 3-5], [3-5, 6-6]] .
  239% ?- iboole:m_partition([[1-2, 4-5],[3-6]],R).
  240% ?- iboole:m_partition([[1-2, 3-5],[inf-5, 8-sup]],R).
  241%@ R = [[1-2, 3-5], [inf-0, 1-2, 3-5, 8-sup]] .
  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).
?- m_partition_one([1-5], [2-7], X, Y). X = [1-1,2-5], Y = [2-5,6-7]
  257m_partition_one(X, Y, Z, U):- m_partition_one(X, Y, Z, [], U, []).
  258
  259%
  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							
  277%
  278i_off(X, Y):- integer(X), integer(Y), !, Y > X+1.
  279i_off(inf, X):- !, X\==inf.
  280i_off(X, sup):- X\==sup.
  281
  282%
  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	  ).
?- iboole:keymerge([a-1,a-2,b-3,c-4,c-5], R). R = [a-[1,2],b-[3],c-[4,5]]
  293keymerge([], []).
  294keymerge([A-X|R],  [A-[X|P]|R0]):- keymerge(A, R, P, [], S),
  295	keymerge(S, R0).
  296%
  297keymerge(A, [A-X|R], [X|P], Q, S):- keymerge(A, R, P, Q,  S).
  298keymerge(_, R, P, P, R).
  299
  300%
  301% ?- iboole:keymerge_r([1-a,2-a,3-b,4-c,5-c], R).
  302% R = [[1,2]-a,[3]-b,[4,5]-c] 
  303
  304keymerge_r([], []).
  305keymerge_r([X-A|R],  [[X|P]-A|R0]):- keymerge_r(A, R, P, [], S),
  306	keymerge_r(S, R0).
  307%
  308keymerge_r(A, [X-A|R], [X|P], Q, S):- keymerge_r(A, R, P, Q,  S).
  309keymerge_r(_, R, P, P, R)