/**
 * Binary decision diagrams.
 *
 * The following structure is used:
 *    Tree = (Variable -> Tree; Tree) | [] | false.
 *
 * Copyright 2012, XLOG Technologies GmbH, Switzerland
 * Jekejeke Prolog 0.9.7 (a fast and small prolog interpreter)
 */

/*********************************************************************/
/* Boolean Operations                                                */
/*********************************************************************/

% invert(+Tree, -Tree)
invert([], false).
invert(false, []).
invert((V -> S;T), (V -> A;B)) :-
   invert(S, A),
   invert(T, B).

% union(+Tree, +Tree, -Tree)
union([], _, []) :- !.
union(_, [], []) :- !.
union(false, X, X) :- !.
union(X, false, X) :- !.
union((V -> S;T), (V -> P;Q), R) :- !,
   union(S, P, A),
   union(T, Q, B),
   make(V, A, B, R).
union((V -> S;T), (W -> P;Q), R) :- V @< W, !,
   union(S, (W -> P;Q), A),
   union(T, (W -> P;Q), B),
   make(V, A, B, R).
union((V -> S;T), (W -> P;Q), R) :-
   union((V -> S;T), P, A),
   union((V -> S;T), Q, B),
   make(W, A, B, R).

% inter(+Tree, +Tree, -Tree)
inter(false, _, false) :- !.
inter(_, false, false) :- !.
inter([], X, X) :- !.
inter(X, [], X) :- !.
inter((V -> S;T), (V -> P;Q), R) :- !,
   inter(S, P, A),
   inter(T, Q, B),
   make(V, A, B, R).
inter((V -> S;T), (W -> P;Q), R) :- V @< W, !,
   inter(S, (W -> P;Q), A),
   inter(T, (W -> P;Q), B),
   make(V, A, B, R).
inter((V -> S;T), (W -> P;Q), R) :-
   inter((V -> S;T), P, A),
   inter((V -> S;T), Q, B),
   make(W, A, B, R).

/*********************************************************************/
/* Helper Predicates                                                 */
/*********************************************************************/

% make(+Variable, +Tree, +Tree, -Tree)
make(_, A, A, A) :- !.
make(V, A, B, (V -> A;B)).