1:- module(path_count6, [zdd0/1, co_compare/3]).    2
    3:- use_module(library(apply)).    4:- use_module(library(apply_macros)).    5:- use_module(library(clpfd)).    6:- use_module(library(statistics)).    7:- use_module(zdd('zdd-array')).    8:- use_module(util(math)).    9:- use_module(util('pac-meta')).   10:- use_module(pac(basic)).   11:- use_module(pac(meta)).   12:- use_module(util(misc)).   13:- use_module(pac('expand-pac')). % For the kind block.
   14:- use_module(zdd('zdd-misc')).   15:- use_module(zdd(zdd)).   16:- use_module(zdd('mqp-update2')).   17:- use_module(pac(op)).   18
   19
   20:- set_prolog_flag(stack_limit, 10_200_147_483_648).   21
   22 :- op(1060, xfy, ~).		% equivalence
   23 :- op(1060, xfy, #).		% exor
   24 :- op(1060, xfy, <->).		% equivalence
   25 :- op(1050, yfx, <-).   26 :- op(1060, xfy, <=> ).	% equivalence
   27 :- op(1040, xfy, \/).		% OR
   28 :- op(1030, xfy, /\).		% AND
   29 :- op(1020, fy, \).		% NOT
   30 :- op(700, xfx, :=).		% Assignment
   31 :- op(1000, xfy, &).   32
   33% for pac query.
   34 :- pac:op(1000, xfy, &).   35 :- pac:op(700, xfx, :=).   36
   37term_expansion --> pac:expand_pac.
   38
   39% ?- zdd0((true)).
   40% ?- zdd0((X<<pow([a,b]),  psa(X))).
   41
   42:- meta_predicate zdd0(:).   43zdd0(X):- zdd((set_compare(co_compare),
   44   				   set_pred(admissibility, admissible_qp_link),
   45				   X)).
   46
   47% ?- admissible_qp(u-v, a-b).  % false.
   48% ?- admissible_qp(a-b, l-m).
   49
   50admissible_qp(X, Y):- X = (_-_),
   51	(inadmissible_qp(X, Y) -> false ; true).
   52
   53
   54% ?- admissible_qp_link(p(2,0)-p(3,0),  p(3,3)-p(3,4)).
   55% ?- admissible_qp_link(p(1,0)-p(2,0),  p(3,3)-p(3,4)).  % false
   56
   57admissible_qp_link(p(I, _)-p(J, _), p(A, B)-p(C, B)):- !, U is min(A, C),
   58	I >= U,
   59	J >= U.
   60admissible_qp_link(p(I, _)-p(J, _), p(A, _)-p(A, _)):- U is A - 1,
   61	I >= U,
   62	J >= U.
   63
   64% ?- inadmissible_qp(l-m, a-x).
   65% ?- inadmissible_qp(3-5, 3-3).	% false.
   66inadmissible_qp(A-B, P-Q):-min(A, B, M),
   67	(P @< M ; Q @< M), !.
   68
   69% ?- test_mqp_update.
   70test_mqp_update:-
   71	forall(	mqp_query(Mqp, Links),
   72			zdd0((X<<Mqp,
   73				 nl,
   74				 format("Links = ~w, mqp = ~w\n", [Links, Mqp]),
   75				 mqp_update_links(Links, X, Y),
   76				 sets(Y, Y0),
   77				 maplist(writeln, Y0)))).
   78%
   79mqp_query({[]},  [a-b]).
   80mqp_query({[a-a, b-b]}, [a-b]).
   81mqp_query({[a-a, b-b]}, [b-a]).
   82mqp_query({[a-a, b-b], [a-a, c-c]}, [a-b]).
   83mqp_query({[a-a, b-b], [a-a, b-b, c-c]}, [a-b]).
   84mqp_query({[a-a, b-b], [a-a, b-b, c-c]}, [c-d]).
   85mqp_query({[a-a, b-c], [a-a, b-b, c-c]}, [c-b]).
   86mqp_query({[a-a, b-c], [a-a, b-b, c-c]}, [a-b, c-b]).
   87mqp_query({[a-a, b-c], [a-a, b-b, c-c]}, [a-b, c-a]).
   88mqp_query({[a-a, b-b]}, [a-b]).
   89mqp_query({[a-a, b-b]}, [b-a]).
   90mqp_query({[a-a, b-b, c-c]},[a-b, b-c]).
   91mqp_query({[a-a, b-b, c-c]}, [b-a, c-b]).
   92
   93% ?- co_compare(C, c-d, c->d).
   94% ?- co_compare(C, c->d, c->d).
   95% ?- co_compare(C, c->d, c-d).
   96% ?- co_compare(C, c-d, c-d).
   97% ?- predsort(co_compare, [a->b, b->a], R).
   98% ?- predsort(co_compare, [a-b, b-a], R).
   99% ?- predsort(co_compare, [b->a, a->b, a-b, a->b, c-b, a-b, b-a], R).
  100% ?- zdd((set_compare(co_compare), zdd_compare(C, a-b, c-d))).
  101% ?- zdd((set_compare(co_compare), zdd_compare(C, c-d, c->d))).
  102% ?- zdd((set_compare(co_compare), zdd_compare(C, c->d, c-d))).
  103% ?- zdd((set_compare(co_compare), zdd_insert_atoms([a-b, c-d], 1, X))).
  104% ?- zdd((set_compare(co_compare), zdd_insert_atoms([a->b, c-d], 1, X), psa(X))).
  105
  106co_compare(C, X, Y):- compare(C0, X, Y),
  107	(	C0 = (=)  -> C = (=)
  108	;	functor(X, Fx, _),
  109		functor(Y, Fy, _),
  110		(	Fx == Fy
  111		-> 	(	Fx = (-)
  112			->  ( C0 = (<) -> C = (>) ; C = (<) )
  113			;	C = C0
  114			)
  115		;	(	Fx = (-) -> C = (<) ; C = (>) )
  116		)
  117	).
  118
  119% ?- predsort(co_compare, [a->b, b->a, a-b, a->b, c-b, b-a, a-b ], R).
  120% ?- predsort(co_compare, [a->b, b->a], R).
  121
  122% some tiny.
  123% x(p(X, _), X).
  124% y(p(_, Y), Y).
  125link_symbol(_->_).
  126change_symbol(A-B, A->B).
  127%
  128touch(A-_, _-A):-!.
  129touch(_-A, A-_).
  130% ?- connect_pairs(a-b, [b-c, d-a], W).
  131% ?- connect_pairs(a-b, [a-c, a-b], W).  % false
  132
  133connect_pairs(X-Y, [U-X, Y-V], U-V):-!.
  134connect_pairs(X-Y, [Y-V, U-X], U-V).
  135
  136% ?- zdd0((X<<{[p(0,0)-p(2,1)], [p(1,1)-p(2,3), p(2,2)-p(2,2)]},
  137%	E = p(2,1)-p(3,1),
  138%	prune_frontier(X, E, p(0,0), Y), psa(Y))).
  139
  140% ?- zdd0((X<<{[p(0,0)-p(2,1)], [p(1,1)-p(1,1), p(2,2)-p(2,2)]},
  141%	E = p(2,1)-p(3,1),
  142%	prune_frontier(X, E, p(0,0), Y), psa(Y))).
  143
  144% ?- zdd0((X<<{[p(0,0)-p(2,1)], [p(1,1)-p(1,1), p(2,2)-p(2,3)]},
  145%	E = p(2,1)-p(3,1),
  146%	prune_frontier(X, 2, p(0,0), Y), psa(Y))).
  147
  148prune_frontier(F, E, P, F0):- @(prune_frontier(F, E, P, F0)).
  149%
  150prune_frontier(F, _, _, F, _):- F<2, !.
  151prune_frontier(F, E, P, F0, S):- s_cofact(F, t(A, L, R), S),
  152	prune_frontier(L, E, P, L0, S),
  153	(	(	A = (X-X)
  154		;	A = (P-_)
  155		; 	admissible_qp(E, A)
  156		)
  157	->	prune_frontier(R, E, P, R0, S)
  158	;	R0 = 0
  159	),
  160	s_cofact(F0, t(A, L0, R0), S).
  161
  162%
  163prune_frontier_by_level(F, K, P, F0):- @(prune_frontier_by_level(F, K, P, F0)).
  164%
  165prune_frontier_by_level(F, _, _, F, _):- F<2, !.
  166prune_frontier_by_level(F, K, P, F0, S):- s_cofact(F, t(A, L, R), S),
  167	prune_frontier_by_level(L, K, P, L0, S),
  168	(	(	A = (X-X)
  169		;	A = P - p(K,_)
  170		; 	A = p(K, _)-p(K, _)
  171		)
  172	->	prune_frontier_by_level(R, K, P, R0, S)
  173	;	R0 = 0
  174	),
  175	s_cofact(F0, t(A, L0, R0), S).
  176
  177
  178
  179
  180		/****************
  181		*     bridge    *
  182		****************/
  183
  184% ?- zdd0((count_path(p(0,0), p(0, 1), C))).
  185% ?- zdd0((count_path(p(0,0), p(1, 0), C))).
  186% ?- zdd0((count_path(p(0,0), p(1,1), C))).
  187% ?- zdd0((count_path(p(0,0), p(2,2), C))).
  188% ?- zdd0((count_path(p(0,0), p(3,3), C))).
  189% ?- zdd0((count_path(p(1,1), p(2,1), C))).
  190% ?- zdd0((count_path(p(1,2), p(3,2), C))).
  191% ?- zdd0((count_path(p(1,2),p(10,2), C))).
  192% ?- zdd0((count_path(p(1,2),p(12,2), C))).
  193% ?- zdd0((count_path(p(1,2),p(13,2), C))).
  194% ?- zdd0((count_path(p(1,2),p(14,2), C))).
  195% ?- zdd0((count_path(p(1,2),p(100,2), C))).
  196% ?- time(zdd0((count_path_line(p(1,2),p(1000, 2), C)))).
  197%@ % 4,691,349 inferences, 0.982 CPU in 1.154 seconds
  198% ?- time(zdd0((count_path_line(p(1,2),p(10000,2), C)))).
  199%@ % 61,745,569 inferences, 59.803 CPU in 60.290 seconds
  200
  201% ?- zdd0((count_path(p(0,0), p(1,1), Z, U),  psa(U))).
  202
  203count_path(X, Y, Z, U):- @(count_path(X, Y, Z, U)).
  204%
  205count_path(p(I, J), p(_K, L), Bridge, Col, S):-
  206	initial_bridge(I, J, L, Bridge),
  207	initial_column(I, J, L, Col, S).
  208
  209
  210% ?- bridge_shift(h, [p(1,1)-p(1,1)], X).
  211% ?- bridge_shift(v, [p(1,1)-p(1,1)], X).
  212bridge_shift(F, X, Y):- maplist(shift_link(F), X, Y).
  213
  214% ?- zdd((convert_to_col([[1-2], [3-4]], Col, 0),
  215%	map_h_shift(Col, Col0))).
  216map_h_shift(X, Y):- @(map_h_shift(X, Y)).
  217%
  218map_h_shift([], [], _).
  219map_h_shift([X|Y], [X0|Y0], S):- h_shift(X, X0, S),
  220	map_h_shift(Y, Y0, S).
  221
  222% ?- zdd((convert_to_row([[1-2], [3-4]], Row, 0),
  223%	map_v_shift(Row, Row0))).
  224map_v_shift(X, Y):- @(map_v_shift(X, Y)).
  225%
  226map_v_shift([], [], _).
  227map_v_shift([X|Y], [X0|Y0], S):- v_shift(X, X0, S),
  228	map_v_shift(Y, Y0, S).
  229
  230%
  231h_shift(X, Y):- @(h_shift(X, Y)).
  232%
  233h_shift(X, X, _):- X < 2, !.
  234h_shift(X, Y, S):- cofact(X, t(p(I, J)-p(I, K), L, R), S),
  235	I0 is I + 1,
  236	h_shift(L, L0, S),
  237	h_shift(R, R0, S),
  238	cofact(Y, t(p(I0, J)-p(I0, K), L0, R0), S).
  239
  240% ?- zdd((qp_along_line(1, 2, X), convert_to_row(X, Y, 3),
  241%	maplist(v_shift, Y, Y0),
  242%	forall(member(M, Y0), (qp_list(M, L), writeln(L))))).
  243
  244v_shift(X, Y):- @(v_shift(X, Y)).
  245%
  246v_shift(X, X, _):- X < 2, !.
  247v_shift(X, Y, S):- cofact(X, t(p(I, J)-p(K, J), L, R), S),
  248	v_shift(L, L0, S),
  249	v_shift(R, R0, S),
  250	J0 is J + 1,
  251	cofact(Y, t(p(I, J0)-p(K, J0), L0, R0), S).
  252
  253% ?- spy(solve_rect).
  254% ?- zdd((solve_rect(p(0,0),p(1,0), Z))).
  255% ?- zdd((solve_rect(p(0,0),p(1,1), Z))).
  256% ?- zdd((solve_rect(p(0,0),p(2,2), Z))).
  257% ?- zdd((solve_rect(p(0,0),p(3,3), Z))).
  258% ?- call_with_time_limit(300, zdd((solve_rect(p(0,0),p(4,4), Z)))).
  259
  260% ?- zdd0((solve_rect(p(0,0),p(1,1), Z, C))).
  261% ?- zdd0((solve_rect(p(0,0),p(1,0), Z, C))).
  262% ?- zdd0((solve_rect(p(0,0),p(2,0), Z, C))).
  263% ?- zdd0((solve_rect(p(0,0),p(32,0), Z, C))).
  264% ?- zdd0((solve_rect(p(0,0),p(1,1), Z, C), psa(Z))).
  265% ?- zdd0((solve_rect(p(0,0),p(3,3), Z, C))).
  266% ?- zdd0((solve_rect(p(0,0),p(3,4), Z, C))).
  267% ?- zdd0((solve_rect(p(0,0),p(3,1), Z, C))).
  268% ?- zdd0((solve_rect(p(0,0),p(20,1), Z, C))).
  269% ?- zdd0((solve_rect(p(0,0),p(4,4), Z, C))).
  270% ?- zdd0((solve_rect(p(0,0),p(5,5), Z, C))).
  271% ?- zdd0((solve_rect(p(0,0),p(6,6), Z, C))).
  272% ?- time(zdd0((solve_rect(p(0,0),p(7,7), Z, C)))).
  273% ?- zdd0((solve_rect(p(0,0),p(8,8), Z, C))).
  274% ?- zdd0((solve_rect(p(0,0),p(9,9), Z, C))).
  275% ?- zdd0((solve_rect(p(0,0),p(10,10), Z, C))).
  276% ?- zdd0((solve_rect(p(0,0),p(13,13), Z, C))).
  277% ?- zdd0((solve_rect(p(0,0),p(15,15), Z, C))).
  278% ?- zdd0((solve_rect(p(0,0),p(20,20), Z, C))).
  279% ?- zdd0((solve_rect(p(0,0),p(30,30), Z, C))).
  280
  281% ?- zdd0((solve_rect(p(0,0),p(2,2), Z, C))).
  282% ?- zdd0((solve_rect(p(0,0),p(3,3), Z, C))).
  283% ?- zdd0((solve_rect(p(0,0),p(4,4), Z, C))).
  284% ?- zdd0((solve_rect(p(0,0),p(5,5), Z, C))).
  285% ?- zdd0((solve_rect(p(0,0),p(6,6), Z, C))).
  286% ?- zdd0((solve_rect(p(0,0),p(7,7), Z, C))).
  287% ?- zdd0((solve_rect(p(0,0),p(8,8), Z, C))).
  288
  289solve_rect(X, Y, Z, C):- @(solve_rect(X, Y, Z, C)).
  290%
  291solve_rect(p(I, J), p(I, L), Z, 1, S):-!, initial_column(I, J, L, Z, S).
  292solve_rect(p(I, J), p(K, L), Z, C, S):-
  293	initial_col_bridge(I, J, L, Col, B, S),
  294	N is (K-I),
  295	repeat_bridge(N, Col, I, p(I,J), Col, B, Z, S),
  296	card(Z, C, S).
  297
  298s_psa(X):- @(s_psa(X)).
  299
  300s_psa(X, @(S,_,_)):-!, psa(X, S).
  301s_psa(X, S):- psa(X, S).
  302%
  303repeat_bridge(0, X, _, _, _, _, X, _):-!, writeln(0).
  304repeat_bridge(N, X, K, P, C, B, Y, S):- writeln(N),
  305	prune_frontier_by_level(X, K, P, X0, S),
  306	mqp_shift(h, C, C0, S),
  307	s_zdd_merge(X0, C0, X1, S), % s_psa(X0, S), s_psa(X1, S),
  308	s_mqp_update_links(B, X1, Y0, S), % nl, writeln(B), s_psa(Y0, S),
  309	maplist(shift_link(h), B, B0),
  310	K0 is K + 1,
  311	N0 is N - 1,
  312	repeat_bridge(N0, Y0, K0, P, C0, B0, Y, S).
  313
  314% ?- zdd0((initial_col_bridge(0, 0, 3, C, B))).
  315% ?- time(zdd0((initial_col_bridge(0, 0, 15, C, B)))).
  316initial_col_bridge(I, L, H, C, B):-	@(initial_col_bridge(I, L, H, C, B)).
  317%
  318initial_col_bridge(I, L, H, C, B, S):- initial_column(I, L, H, C, S),
  319	initial_bridge(I, L, H, B).
  320
  321
  322% ?- zdd0((initial_column(1, 2, 4, Col), psa(Col))).
  323% ?- zdd0((initial_column(1, 0, 10, Col), card(Col, C))).
  324% ?- zdd0((initial_column(1, 0, 3, Col), card(Col, C))).  % seems good.
  325% ?- zdd0((initial_column(1, 0, 3, Col),
  326%	mqp_shift(h, Col, Col1),
  327%	mqp_shift(v, Col1, Col2),
  328%	card(Col, C),
  329%	card(Col1, C1),
  330%	card(Col2, C2))).
  331
  332initial_column(I, Low, Hi, Col):- @(initial_column(I, Low, Hi, Col)).
  333%
  334initial_column(I, Low, Hi, Col, S):-
  335	mqp_linear_grid(Low, Hi, X, S),
  336	mqp_lift(x(I), X, Col, S).
  337
  338% ?- initial_bridge(0, 1, 4, Bridge), maplist(writeln, Bridge).
  339initial_bridge(I, Low, Hi, Bridge):- J is I + 1,
  340	findall(A,
  341			(	member(A, [p(I, V)-p(J, V), p(J, V)-p(I, V)]),
  342				between(Low, Hi, V)
  343			),
  344			Bridge0),
  345	sort(Bridge0, Bridge).
  346
  347		/****************
  348		*     prune     *
  349		****************/
  350
  351% ?- zdd((qp_along_line(1, 13, X), length(X, L), convert_to_col(X, Y, 3),
  352%	prune_by_column(Y, 3, p(3,1)-p(3,1), Y0), length(Y, Ly))).
  353
  354prune_by_column(F, X, P, F0):- @(prune_by_column(F, X, P, F0)).
  355%
  356prune_by_column([], _, _, [], _).
  357prune_by_column([Q|F], X, P, [Q|F0], S):- admissible_qp(Q, X, P, S), !,
  358	prune_by_column(F, X, P, F0, S).
  359prune_by_column([_|F], X, P, F0, S):-
  360	prune_by_column(F, X, P, F0, S).
  361%
  362admissible_qp(Q, X, P):- @(admissible_qp(Q, X, P)).
  363%
  364admissible_qp(Q, X, P, S):- qp_list(Q, List, S),
  365	admissible_qp_list(List, X, P).
  366
  367% ?- admissible_qp_list([p(0,0)-p(2,1), p(3,1)-p(3,1)], 2, p(0,0)).
  368admissible_qp_list([], _, _):-!.
  369admissible_qp_list([P-p(X, _)|List], X, P):-!,
  370	admissible_qp_list(List, X, P).
  371admissible_qp_list([p(X, _)-p(X, _)|List], X, P):- !,
  372	admissible_qp_list(List, X, P).
  373admissible_qp_list([p(Z, _)-_|_], X, _):- Z>X, !.
  374admissible_qp_list([P-P|List], X, P):- admissible_qp_list(List, X, P).
  375
  376% ?- rect((qp_along_line(1,1, Ls), maplist_qp(Ls, Q))).
  377% ?- rect((qp_along_line(1,10, Ls), maplist_qp(Ls, Q))).
  378% ?- time(rect((qp_along_line(1, 15, Ls), maplist_qp(Ls, Q)))).
  379%@ % 99,784,517 inferences, 8.136 CPU in 8.371 seconds (97% CPU, 12264944 Lips)
  380
  381
  382% ?- spy(mqp_linear_grid).
  383% ?- I = 0, zdd0((mqp_linear_grid(0,I,X), psa(X))).
  384% ?- I = 1, zdd0((mqp_linear_grid(0,I,X), psa(X))).
  385% ?- I = 2, zdd0((mqp_linear_grid(0,I,X), psa(X))).
  386% ?- I = 3, zdd0((mqp_linear_grid(0,I,X), psa(X))).
  387% Checked by hand.
  388
  389% ?- forall(between(0, 20, I), zdd0((mqp_linear_grid(0,I,X), card(X, C), format("count(~w) = ~w\n", [I, C])))).
  390
  391% simple line quasi path
  392mqp_linear_grid(X, Y, Z):- @(mqp_linear_grid(X, Y, Z)).
  393
  394mqp_linear_grid(E, X, Y, S):-
  395	open_state(M, [hash_size(128)]),
  396	get_key(admissibility, Pred, S),
  397	s_mqp_linear_grid(E, X, Y, @(S, M, Pred)),
  398	close_state(M).
  399%
  400s_mqp_linear_grid(I, I, P, S):-!, s_zdd_singleton(I-I, P, S).
  401s_mqp_linear_grid(I, J, Q, S):-
  402	M is (I+J)//2,
  403	M0 is M+1,
  404	s_mqp_linear_grid(I, M, R, S),
  405	s_mqp_linear_grid(M0, J, R0, S),
  406	s_zdd_merge(R, R0, Q0, S),
  407	s_mqp_update_links([M-M0, M0-M], Q0, Q, S).
  408
  409
  410% ?- I = 3, zdd0((mqp_linear_grid(0,I,X), mqp_lift(y(0), X, Y), card(Y, C))).
  411%
  412mqp_lift(F, X, Y):- @(mqp_lift(F, X, Y)).
  413%
  414mqp_lift(F, X, Y, S):-open_state(M, [hash_size(128)]),
  415	mqp_lift(F, X, Y, S, M),
  416	close_state(M).
  417%
  418mqp_lift(_, X, X, _, _):- X<2, !.
  419mqp_lift(F, X, Y, S, M):- memo(mqp_lift(X)-Y, M),  % F dropped.
  420	(	nonvar(Y)-> true
  421	;	s_cofact(X, t(A, L, R), S),
  422		mqp_lift(F, L, L0, S, M),
  423		mqp_lift(F, R, R0, S, M),
  424		lift_link(F, A, B),
  425		s_cofact(Y, t(B, L0, R0), S)
  426	).
  427
  428% ?- I = 3, zdd0((mqp_linear_grid(0,I,X), mqp_lift(y(0), X, Y), card(Y, C))).
  429% ?- I = 3, zdd0((mqp_linear_grid(0,I,X), mqp_lift(y(0), X, Y), card(Y, C),
  430%	mqp_shift(v, Y, Z), psa(Z), card(Z, D))).
  431% ?- I = 3, zdd0((mqp_linear_grid(0,I,X), mqp_lift(y(0), X, Y),
  432%	mqp_shift(v, Y, Z), mqp_shift(v, Z, U), psa(U), card(U, C))).
  433
  434%
  435mqp_shift(F, X, Y):- @(mqp_shift(F, X, Y)).
  436%
  437mqp_shift(F, X, Y, S):-
  438	open_state(M, [hash_size(128)]),
  439	mqp_shift(F, X, Y, S, M),
  440	close_state(M).
  441
  442%
  443mqp_shift(_, X, X, _, _):- X<2, !.
  444mqp_shift(F, X, Y, S, M):- memo(mqp_shift(X)-Y, M),  % F dropped.
  445	(	nonvar(Y)-> true
  446	;	s_cofact(X, t(A, L, R), S),
  447		mqp_shift(F, L, L0, S, M),
  448		mqp_shift(F, R, R0, S, M),
  449		shift_link(F, A, B),
  450		s_cofact(Y, t(B, L0, R0), S)
  451	).
  452
  453
  454% ?- lift_point(3, x(2), R).
  455% ?- lift_point(3, y(2), R).
  456%
  457lift_point(J, x(I), p(I, J)):-!.
  458lift_point(J, y(I), p(J, I)).
  459
  460% ?- lift_link(x(2), 4-5, R).
  461lift_link(Ctr, A-B, P-Q):-!, lift_point(A, Ctr, P),
  462	lift_point(B, Ctr, Q).
  463% ?- lift_link(x(2), 4->5, R).
  464lift_link(Ctr, A->B, P->Q):- lift_point(A, Ctr, P),
  465	lift_point(B, Ctr, Q).
  466%
  467shift_link(h, A, B):-!, h_shift_link(A, B).
  468shift_link(v, A, B):- v_shift_link(A, B).
  469
  470% ?- h_shift_point(p(1,1), R).
  471% ?- h_shift_point(-1, p(1,1), R).
  472h_shift_point(p(I, J), p(I0, J)):- I0 is I + 1.
  473h_shift_point(K, p(I, J), p(I0, J)):- I0 is I + K.
  474%
  475v_shift_point(p(I, J), p(I, J0)):- J0 is J + 1.
  476v_shift_point(K, p(I, J), p(I, J0)):- J0 is J + K.
  477
  478%
  479h_shift_link(P-Q, P0-Q0):-!, h_shift_point(P, P0),
  480	h_shift_point(Q, Q0).
  481h_shift_link(P->Q, P0->Q0):- h_shift_point(P, P0),
  482	h_shift_point(Q, Q0).
  483%
  484v_shift_link(P-Q, P0-Q0):-!, v_shift_point(P, P0),
  485	v_shift_point(Q, Q0).
  486v_shift_link(P->Q, P0->Q0):- v_shift_point(P, P0),
  487	v_shift_point(Q, Q0).
  488
  489% ?- simple_bridge(1-2, [1-1], [2-2], R).
  490% ?- simple_bridge(2-1, [1-1], [2-2], R).
  491% ?- simple_bridge(2-3, [1-1], [2-2], R).
  492simple_bridge(A-B, L, M, N):-	% assuming qp  X < qp Y
  493	(	select(B-V, M, M0),
  494		select(U-A, L, L0)
  495	;	select(B-V, L, L0),
  496		select(U-A, M, M0)
  497	),
  498	!,
  499	(	U @> V
  500	-> 	ord_union(L0, [U-V|M0], N)
  501	; 	ord_union([U-V], M0, M1),
  502		ord_union(L0, M1, N)
  503	).
  504simple_bridge(_, _, _, []).
  505
  506%
  507simple_bridge_links([], _, _, Z, Z).
  508simple_bridge_links([E|Es], X, Y, Z, U):-
  509	simple_bridge_link(X, E, Y, Z, Z0),
  510	simple_bridge_links(Es, X, Y, Z0, U).
  511%
  512simple_bridge_link([], _, _, Z, Z).
  513simple_bridge_link([X|Xs], E, Y, Z, U):-
  514	simple_bridge_basic(Y, X, E, Z, Z0),
  515	simple_bridge_link(Xs, E, Y, Z0, U).
  516%
  517simple_bridge_basic([], _, _, Z, Z).
  518simple_bridge_basic([Y|Ys], X, E, Z, U):- simple_bridge(E, X, Y, V),
  519	(	V = []
  520	->	Z0 = Z
  521	;	Z  = [V|Z0]
  522	),
  523	simple_bridge_basic(Ys, X, E, Z0, U).
  524
  525% ?- Q = [a-a], Q0=[b-b], Q1 = [c-c],
  526%	simple_prod_union([Q, Q0], [Q1], Z).
  527
  528%
  529simple_prod_union(X, Y, Z):- simple_prod_union(X, Y, Z, []).
  530%
  531simple_prod_union([], _, U, U).
  532simple_prod_union([L|Y], Z, U, V):-
  533	simple_union(Z, L, U, U0),
  534	simple_prod_union(Y, Z, U0, V).
  535%
  536simple_union([], _, U, U).
  537simple_union([M|As], L, [N|U], V):-
  538	ord_union(L, M, N),
  539	simple_union(As, L, U, V).
  540
  541%% test basics.
  542% ?- zdd((
  543%	qp_list(X, [a-a]), qp_list(Y, [b-b]),
  544%	qp_joint([a-b, b-a], [X], [Y], Z),
  545%	maplist(pred(([U]:-qp_list(U, List), writeln(List))), Z))).
  546% ?- zdd((
  547%	qp_list(X, [a-a]), qp_list(Y, [b-b]),
  548%	qp_joint([a-b, b-a], [X], [Y], Z),
  549%	zdd_join(X, Y, A),
  550%	memo(qp_suc(A)-L), writeln(qp_suc(A)-L),
  551%	maplist(pred(([U]:-qp_list(U, List), writeln(List))), Z))).
  552% ?- zdd((
  553%	qp_list(X, [a-a]), qp_list(Y, [b-b]),
  554%	qp_joint([a-b, b-a], [X], [Y], Z),
  555%	zdd_join(X, Y, A),
  556%	memo(qp_suc(A)-L), writeln(qp_suc(A)-L),
  557%	maplist(pred(([U]:-qp_list(U, List), writeln(List))), Z))).
  558
  559qp_joint(X, Y, Z, U):-@(qp_joint(X, Y, Z, U)).
  560%
  561qp_joint(X, Y, Z, U, S):- map_prod_sum(Y, Z, V, [], S),
  562	qp_bridge_links(X, Y, Z, U, V, S).
  563
  564% ?- zdd((qp_list(X, [a-a]), qp_list(Y, [b-b]),
  565%	qp_bridge(a-b, X, Y, Z), qp_list(Z, U))).
  566% ?- zdd((qp_list(X, [a-a]), qp_list(Y, [b-b]),
  567%	qp_bridge(b-a, X, Y, Z), qp_list(Z, U))).
  568
  569qp_bridge(E, X, Y, Z):- @(qp_bridge(E, X, Y, Z)).
  570%
  571qp_bridge(A-B, X, Y, Z, S):- % assuming qp  X < qp Y
  572	qp_list(X, L, S),
  573	qp_list(Y, M, S),
  574	(	select(U-A, L, L0),
  575		select(B-V, M, M0)
  576	;	select(B-V, L, L0),
  577		select(U-A, M, M0)
  578	),
  579	!,
  580	ord_union(L0, M0, N0),
  581	ord_union([U-V], N0, N),
  582	qp_list(Z, N, S).
  583qp_bridge(_, _, _, 0, _).
  584
  585%
  586qp_bridge_links(X, Y, Z, U, V):- @(qp_bridge_links(X, Y, Z, U, V)).
  587%
  588qp_bridge_links([], _, _, Z, Z, _).
  589qp_bridge_links([E|Es], X, Y, Z, U, S):-
  590	qp_bridge_link(X, E, Y, Z, Z0, S),
  591	qp_bridge_links(Es, X, Y, Z0, U, S).
  592%
  593qp_bridge_link([], _, _, Z, Z, _).
  594qp_bridge_link([X|Xs], E, Y, Z, U, S):-
  595	qp_bridge_basic(Y, X, E, Z, Z0, S),
  596	qp_bridge_link(Xs, E, Y, Z0, U, S).
  597%
  598qp_bridge_basic([], _, _, Z, Z, _).
  599qp_bridge_basic([Y|Ys], X, E, Z, U, S):- qp_bridge(E, X, Y, V, S),
  600	(	V = 0
  601	->	Z0 = Z
  602	;	Z  = [V|Z0],
  603		select_goto(E, X, Y, V, S)
  604	),
  605	qp_bridge_basic(Ys, X, E, Z0, U, S).
  606%
  607select_goto(E, X, Y, Z):- @(select_goto(E, X, Y, Z)).
  608%
  609select_goto(A-B, X, Y, Z, S):-
  610	G = (A-B)-Z,
  611	( A@<B -> W = X ; W = Y ),
  612	getmemo(qp_suc(W)-U, V, S),
  613	(	var(V) -> V = [] ; true ),
  614	add_new(G, V, U).
  615
  616		/***********************
  617		*     end of bridge    *
  618		***********************/
  619
  620% ?-  belong(3, 3, 4).
  621% ?-  belong(3, 4, 1).
  622belong(X, I, J):- I @=< J, !, I @=< X, X @=< J.
  623belong(X, I, J):- J @=< X, X @=< I.
  624%
  625sub_interval(I, J, X, Y):- belong(I, X, Y), belong(J, X, Y).
  626%
  627disjoint_interval(I, J, X, Y):- \+ belong(I, X, Y), \+ belong(J, X, Y).
  628
  629% ?- compatible_interval(1, 2, 3, 4).
  630% ?- compatible_interval(1, 3, 2, 4). % false
  631% ?- compatible_interval(2, 4, 5, 7).
  632% ?- compatible_interval(7, 5, 2, 4).
  633
  634compatible_interval(I, J, X, Y):- disjoint_interval(I, J, X, Y), !.
  635compatible_interval(I, J, X, Y):- sub_interval(I, J, X, Y), !.
  636compatible_interval(I, J, X, Y):- sub_interval(X, Y, I, J).
  637
  638
  639% go
  640% ?- spy(s_mqp_update_links).
  641% ?- rect_dg(rect(1,1), X, Y), findall(A-A, member(A,  X), Init), reverse(Y, Y0),
  642%	zdd0(( zdd_insert_atoms(Init, 1, Init0), psa(Init0), s_mqp_update_links(Y0, Init0, R), psa(R))).
  643% ?- rect_dg(rect(1,1), X, Y), findall(A-A, member(A,  X), Init), reverse(Y, Y0),
  644%	zdd0(( zdd_insert_atoms(Init, 1, Init0), psa(Init0), s_mqp_update_links(Y0, Init0, R), psa(R))).
  645
  646% ?- rect_dg(rect(2,2), X, Y), findall(A-A, member(A,  X), Init),
  647%	zdd0(( zdd_insert_atoms(Init, 1, Init0), psa(Init0), s_mqp_update_links(Y, Init0, R))).
  648% ?- rect_dg(rect(3,3), X, Y), findall(A-A, member(A,  X), Init),
  649%	zdd0(( zdd_insert_atoms(Init, 1, Init0), s_mqp_update_links(Y, Init0, R))).
  650
  651
  652% ?- rect_dg(rect(0,1), X, Y).
  653% ?- rect_dg(rect(0,0), X, Y).
  654
  655rect_dg(rect(W, H), Nodes, Links):-
  656	rect_nodes(W, H, Nodes),
  657	rect_links(W, H, Nodes, Links).
  658% ?- rect_nodes(4,5,Ns), length(Ns, L).
  659
  660rect_nodes(W, H, Nodes):-
  661	findall(p(I, J),
  662			(	between(0, W, I),
  663				between(0, H, J)
  664			),
  665			Nodes0),
  666	sort(Nodes0, Nodes).
  667
  668%
  669rect_links(W, H, Ns, Links):-
  670	findall(P-Q,
  671			(	member(P, Ns),
  672				P = p(I, J),
  673				(	Q = p(I, J1),
  674					(	J1 is J-1,
  675						J1 >= 0
  676					;	J1 is J+1,
  677						J1 =< H
  678					)
  679				;   Q = p(I1, J),
  680					(	I1 is I-1,
  681						I1 >= 0
  682					;	I1 is I+1,
  683						I1 =< W
  684					)
  685				)
  686			),
  687			Links0),
  688	sort(Links0, Links).
  689
  690		/********************
  691		*   frontier based  *
  692		********************/
  693
  694% ?- zdd(path_count(rect(0,0), C)).
  695% ?- zdd(path_count(rect(1,0), C)).
  696% ?- zdd(path_count(rect(0,1), C)).
  697% ?- zdd(path_count(rect(1,1), C)).
  698% ?- zdd(path_count(rect(2, 1), C)).
  699% ?- zdd(path_count(rect(3, 1), C)).
  700% ?- zdd(path_count(rect(1, 3), C)).
  701% ?- zdd(path_count(rect(4, 1), C)).
  702% ?- zdd(path_count(rect(2, 3), C)).
  703% ?- zdd(path_count(rect(4,3), C)).
  704%@ C = 976 .
  705% ?- zdd(path_count(rect(4,4), C)).
  706%@ C= 8512
  707% ?- call_with_time_limit(360, zdd(path_count(rect(5, 5), C))).
  708
  709path_count(Rect, C):- @(path_count(Rect, C)).
  710
  711%
  712path_count(rect(0,0), 1, _):-!.
  713path_count(Rect, C, S):-
  714	rect_dg(Rect, Ns, Links),
  715	findall(A-A, member(A, Ns), Ids),
  716	Rect = rect(W, H),
  717	set_key(final, p(W, H), S),
  718	qp_list(Q, Ids, S),
  719	memo(qp_suc(Q)-[], S),
  720	frontier(Links, [Q], FinalQs, S),
  721	fold_qp_memo_final(FinalQs, S),
  722	path_tree(Q, Tree, S),
  723	card(Tree, C, S).
  724
  725%
  726frontier([], Qs, Qs, _).
  727frontier([E|Es], Qs, Qs0, S):-
  728	frontier_link(E, Qs, Qs1, Qs, S),
  729	prune_frontier(Qs1, E, Qs2, S),
  730	frontier(Es, Qs2, Qs0, S).
  731
  732%
  733frontier_link(_, [], Qs, Qs, _):-!.
  734frontier_link(E, [X|Qs], Qs0, Qs1, S):- X<2, !,
  735 	frontier_link(E, Qs, Qs0, Qs1, S).
  736frontier_link(E, [Q|Qs], Next, Qs1, S):-
  737	qp_update(E, Q, Q0, S),
  738	(	Q0 < 2
  739	->	Next = Qs0
  740	;	qp_memo_final(Q0, S),
  741		Next = [Q0|Qs0]
  742	),
  743	qp_update_succs(E-Q0, Q, S),
  744	frontier_link(E, Qs, Qs0, Qs1, S).
  745
  746% ?- zdd((qp_list(Q, [a]), qp_list(Q0, [b]), qp_list(Q1, [c]),
  747%	map_prod_sum([Q, Q0], [Q1], Z),
  748%	maplist(pred([A, M]:-qp_list(A, M)), Z, W))).
  749%
  750map_prod_sum(X, Y, Z):- map_prod_sum(X, Y, Z, []).
  751%
  752map_prod_sum(X, Y, Z, U):- @(map_prod_sum(X, Y, Z, U)).
  753
  754map_prod_sum([], _, U, U, _).
  755map_prod_sum([Q|Y], Z, U, V, S):- qp_list(Q, L, S),
  756	map_qp_sum(Z, L, U, U0, S),
  757	map_prod_sum(Y, Z, U0, V, S).
  758%
  759map_qp_sum([], _, U, U, _).
  760map_qp_sum([Q|As], L, [Q0|U], V, S):-qp_list(Q, M, S),
  761	ord_union(L, M, N),
  762	qp_list(Q0, N, S),
  763	map_qp_sum(As, L, U, V, S).
  764
  765
  766% ?- zdd((path_count(rect(1,0), C))).
  767% ?- zdd((path_count(rect(0,1), C))).
  768% ?- zdd((path_count(rect(1,1), C))).
  769% ?- zdd((path_count(rect(3,1), C))).
  770% ?- time(zdd((path_count(rect(1,8), C)))).   % take time.
  771%@ % 86,018,490 inferences, 10.604 CPU in 11.323
  772% ?- time(zdd((path_count(rect(8,1), C)))).
  773%@ % 9,254,518 inferences, 3.089 CPU in 4.850
  774% ?- zdd((path_count(rect(2,3), C))).
  775% ?- zdd((path_count(rect(3,2), C))).
  776% ?- time(zdd((path_count(rect(3,3), C)))).
  777%@ % 50,584,360 inferences, 7.362 CPU in 9.480
  778%@ C = 184 .
  779% ?- time(zdd((path_count(rect(4,4), C)))).
  780%@ % 9,474,429,287 inferences, 1256.779 CPU in 1433.734 seconds (88% CPU, 7538660 Lips)
  781%@ C = 8512 .
  782
  783qp_update(E, X, Y):- @(qp_update(E, X, Y)).
  784%
  785qp_update(_, X, 0, _):- X < 2.
  786qp_update(E, X, Y, S):- qp_list(X, U, S),
  787	memo(qp_update(E, X)-Y, S),
  788	(	nonvar(Y)  ->	true
  789	;	select_touch(E, [A, B], U, U0)
  790	->	connect_pairs(E, [A, B], W),
  791		ord_union([W], U0, V),
  792		qp_list(Y, V, S)
  793	;	Y = 0
  794	).
  795qp_update(_, _, 0,  _).
  796
  797% ?- zdd((qp_list(X, [a-a, b-b]), memo(qp_suc(X)-[]))).
  798qp_update_succs(G, Q):- @(qp_update_succs(G, Q)).
  799
  800% ?- zdd(qp_update_succs(a, 1)).
  801qp_update_succs(G, Q, S):- getmemo(qp_suc(Q)-U, V, S),
  802	G = E-Q0,
  803	(	var(V) -> U = [E-Q0]
  804	;	add_new(E-Q0, V, U)
  805	).
  806
  807qp_admissible(L):-
  808	forall((select(A-B, L, L0), select(C-D, L0, _)),
  809		   compatible_interval(A, B, C, D)).
  810
  811% ?- compatible_interval(1, 2, 3, 4).
  812% ?- compatible_interval(1, 3, 2, 4). % false
  813% ?- compatible_interval(2, 4, 5, 7).
  814% ?- compatible_interval(7, 5, 2, 4).
  815
  816
  817% compatible_interval(I, J, X, Y):- disjoint_interval(I, J, X, Y), !.
  818% compatible_interval(I, J, X, Y):- sub_interval(I, J, X, Y), !.
  819% compatible_interval(I, J, X, Y):- sub_interval(X, Y, I, J).
  820%@ true.
  821%@ path-count4.pl qcompiled.
  822
  823% ?- select_touch(a-b, [A, B], [a-a, b-b], X).
  824% ?- select_touch(a-b, [A, B], [a-a, b-b], X),
  825%	connect_pairs(a-b, [A, B], Y).
  826%@ false.
  827
  828% ?- select_touch(a-b, [A, B], [a-a, b-c], X),
  829%	connect_pairs(a-b, [A, B], Y).
  830% ?- select_touch(a-b, [A, B], [a-a, c-b], X).
  831
  832select_touch(_, [], V, V).
  833select_touch(E, [A|As], [A|U], V):- touch(E, A), !,
  834	select_touch(E, As, U, V).
  835select_touch(E, As, [A|U], [A|V]):-select_touch(E, As, U, V).
  836
  837% ?- add_new(a,[b,c,a], X).
  838add_new(X, Y, Y):- memberchk(X, Y), !.
  839add_new(X, Y, [X|Y]).
  840
  841% ?- zdd((qp_list(Q, [p(0,0)-p(1,0)]), qp_list(Q, L))).
  842%@ L = [p(0, 0)-p(1, 0)].
  843%
  844qp_list(Q, List):- @(qp_list(Q, List)).
  845%
  846qp_list(0, 0, _):-!.
  847qp_list(1, [], _):-!.   

 ???

  848qp_list(Q, List, S):- var(Q), !,
  849	zdd_insert_atoms(List, 1, Q, S),
  850	memo(qp_suc(Q)-U, S),
  851	(	var(U) -> U = []
  852	;	true			% Already registered.
  853	).
  854qp_list(Q, [A|As], S):- cofact(Q, t(A, 0, R), S),
  855	qp_list(R, As, S).
  856
  857%
  858qp_memo_final(X):- @(qp_memo_final(X)).
  859%
  860qp_memo_final(Q, S):-  memoq(qp_final(Q)-true, S), !.
  861qp_memo_final(Q, S):- qp_list(Q, List, S),
  862	get_key(final, F, S),
  863	(	qp_final(List, F)
  864	->	memo(qp_final(Q)-true, S)
  865	;	true
  866	).
  867%
  868fold_qp_memo_final([], _).
  869fold_qp_memo_final([Q|Qs], S):- qp_memo_final(Q, S),
  870	fold_qp_memo_final(Qs, S).
  871
  872%
  873path_tree(Q, T):- @(path_tree(Q, T)).
  874%
  875
  876path_tree(X, 0,  _):- X<1, !.
  877path_tree(Q, 1, S):- memoq(qp_final(Q)-true, S), !.
  878path_tree(Q, T, S):- memo(path_tree(Q)-T, S),
  879	(	nonvar(T) -> true
  880	;	memo(qp_suc(Q) - L, S),		% writeln(qp_suc(Q)-L),
  881		path_tree_list(L, 0, T, S)
  882	).
  883%
  884path_tree_list([], C, C, _).
  885path_tree_list([E-Q|Qs], C0, C, S):-
  886	path_tree(Q, A, S),
  887	zdd_insert(E, A, A0, S),
  888	zdd_join(C0, A0, C1, S),
  889	path_tree_list(Qs, C1, C, S).
  890
  891% ?- qp_final([p(0,0)-p(2,3),p(0,3)-p(0,3),p(1,3)-p(1,3)], p(2,3)).
  892
  893qp_final([X-Y|R], X, Y):-!, qp_all_id(R).
  894qp_final([A-A|R], X, Y):- qp_final(R, X, Y).
  895
  896qp_final([p(0,0)-F|R], F):-!, qp_all_id(R).
  897qp_final([A-A|R], F):- qp_final(R, F).
  898
  899%
  900qp_all_id([]).
  901qp_all_id([A-A|R]):- qp_all_id(R).
  902
  903%
  904dag_card(Q, C):- @(dag_card(Q, C)).
  905%
  906dag_card(Q, C, S):- open_state(M),
  907	dag_card(Q, C, S, M),
  908	close_state(M).
  909%
  910dag_card(Q, 0,  _, _):- Q<2, !.
  911dag_card(Q, 1, S, _):- memoq(qp_final(Q)-true, S), !.
  912dag_card(Q, C, S, M):- memo(dag_card(Q)-C, M),
  913	(	nonvar(C) -> true
  914	;	memo(qp_suc(Q) - L, S),
  915		dag_card_list(L, 0, C, S, M)
  916	).
  917%
  918dag_card_list([], C, C, _, _).
  919dag_card_list([_-Q|Qs], C0, C, S, M):-
  920	dag_card(Q, A, S, M),
  921	C1 is C0 + A,
  922	dag_card_list(Qs, C1, C, S, M).
  923
  924
  925		/***************
  926		*     debug    *
  927		***************/
  928%
  929snap_qp_update(E, X, Y, S):- qp_update(E, X, Y, S),
  930	qp_list(X, X0, S),
  931	qp_list(Y, Y0, S),
  932	format("~w\n~w\n~w\n\n", [qp_update(E, X, Y), X0, Y0]).
  933%
  934dump_frontier(Qs, S):- maplist(pred(S,
  935	([Q]:- qp_list(Q, U, S), writeln(U))), Qs).
  936%
  937dump_qp(X, _):-  X<2, !, writeln(X).
  938dump_qp(X, S):-  qp_list(X, L, S),
  939	writeln(X=L).
  940
  941%
  942delta_star([], Q, Q, _).
  943delta_star([E|Es], Q,  Q0, S):-  memo(qp_suc(Q)-L, S),
  944	writeln(E),
  945	memberchk(E-Q1, L),
  946	dump_qp(Q1, S),
  947	delta_star(Es, Q1, Q0, S).
  948
  949%
  950mirror(X, Y):- @(mirror(X, Y)).
  951%
  952mirror(X, X, _):- X<2, !.
  953mirror(X, Y, S):- cofact(X, t(p(I,J)-p(K,L), Lx, Rx), S),
  954	mirror(Lx, MLx, S),
  955	mirror(Rx, MRx, S),
  956	zdd_insert(p(J, I)-p(L, K), MRx, MRx0, S),
  957	zdd_join(MLx, MRx0, Y, S).
  958
  959%
  960rect_path_tree(Rect, T):-@(rect_path_tree(Rect, T)).
  961
  962rect_path_tree(Rect, T, S):-
  963	sort_links_by_rank(Rect, Rs, Ids),
  964	Rect = rect(W, H),
  965	set_key(final, p(W, H), S),
  966	qp_list(Q, Ids, S),
  967	repeat_frontier(Rs, [Q], FinalQs, S),
  968	fold_qp_memo_final(FinalQs, S),
  969	path_tree(Q, T, S).
  970
  971% ?- spy(remove_end_links).
  972% ?- remove_end_links([1-[c-a]], R0, a-d).
  973% ?- remove_end_links([1-[c-a, d-c, a-d]], R0, a-d).
  974
  975remove_end_links(R, R0, ST):- maplist(pred(ST,
  976	(	[J-Es, J-Es0]:- foldl(
  977		pred([ST, Es, Es0],
  978			 ( [P-Q, U, V]:- ST = S-T,
  979					(	( Q==S; P==T)
  980					->  V = U
  981					;	U = [P-Q|V]
  982					))),  Es,  Es0, []))),  R, R0).
  983
  984%
  985rest(Q, X, Y, S):- memo(qp_suc(Q)-L, S),
  986	(	select(Q, X, X0)-> true
  987	;	X0 = X
  988	),
  989	rest_list(L, X0, Y, S).
  990%
  991rest_list([], X, X, _).
  992rest_list([_-Q|Qs], X, Y, S):-
  993	rest(Q, X, X0, S),
  994	rest_list(Qs, X0, Y, S).
  995
  996
  997% ?- zdd((dbg_qp_update(p(0,0)-p(1,0), [p(0,0)-p(0,0),p(1,0)-p(1,0)], L))).
  998% ?- spy(dbg_qp_update).
  999% ?- zdd((dbg_qp_update(p(2,2)-p(2,3), [p(0,0)-p(2,2),p(0,3)-p(0,3), p(1,3)-p(1,3), p(2,3)-p(2,3)], L))).
 1000
 1001dbg_qp_update(E, X, Y):- @(dbg_qp_update(E, X, Y)).
 1002%
 1003dbg_qp_update(E, X, Y, S):- qp_list(Q, X, S),
 1004	qp_update(E, Q, Q0, S),
 1005	qp_list(Q0, Y, S).
 1006
 1007
 1008% ?- zdd((rect_path_tree(rect(3,2), T), card(T, C),
 1009%   zdd_insert_atoms([p(0,0)-p(2,3),p(0,3)-p(0,3),p(1,3)-p(1,3)], 1, W),
 1010%	mirror(T, MT), card(MT, CMT),
 1011%	rect_path_tree(rect(2,3), T0), card(T0, C0), mirror(T0, MT0),
 1012%	card(MT0, CM0),
 1013%	zdd_subtr(T, MT0, D), card(D, CD), psa(D)
 1014%)).
 1015
 1016
 1017% Test to show getmemo/2,3 works well.
 1018% ?- time((numlist(1, 10000, Ns),
 1019%	zdd((maplist( pred([A]:- getmemo(a(A)-A, _)), Ns),
 1020%		 maplist( pred(([A]:- getmemo(a(A)-B, Old), B is 2*Old)),  Ns),
 1021%		 foldl( pred(([I, B, C]:- getmemo(a(I)-J, J),
 1022%							 C is B + J)), Ns, 0, Sum))))).
 1023%@ % 938,719 inferences, 0.074 CPU in 0.075 seconds (99% CPU, 12701698 Lips)
 1024%@ Ns = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
 1025%@ Sum = 100010000.