%% translated into AR by N.F. Zhou, March 2006

%% Optimization 0:

/*
Constraints are indexed on arguments that are involved in equality tests in the guard of a rule. For example, p(..X..),q(..Y..) <=> X=Y,GRest | B.
*/

%% Optimization 1:

/*
For a rule with symmetric patterns (P,P' <=> G | B). Only one agent is created for P and P'.
*/
%% Optimization 2:

/*
No channeling variable is used for single-headed rules if the rules are never re-tried because of 
variable instantiations.
*/
%% Optimization 3:

/*
No history is necessary if it is known that a propagation rule can be applied at most once.
*/
%% Optimization 4:

/*
No id needs to be created and used for a constraint if (1) no history is managed; and (2) events are 
never re-posted.
*/

/*
fib(N,M1), fib(N,M2) <=> M1 = M2, fib(N,M1).

fib(0,M) ==> M = 1.

fib(1,M) ==> M = 1.

fib(N,M) ==> N > 1 | N1 is N-1, fib(N1,M1), N2 is N-2, fib(N2,M2), M is M1 + M2.
*/

main :-
	main(22).

main(N):-
	cputime(X),
	fib(N,_),
	cputime( Now),
	Time is Now-X,
	write(bench(fib ,N,Time, 0,bp_ar)),write('.'), nl.
                 
:-mod fib(+,-).
fib(N,M):-
    Constr=fib(Flag,N,M),
    global_heap_get(fib_2(N),C), % channeling variable C shared by all fib(N,..) constraints

    post_event(C,Constr), % early posting

    fib_r1(C,Flag,N,M),
    fib_r234(Flag,N,M).

/* generated from CHR rules assuming the first argument nonvar */
:-determinate fib/2.
%%% fib(N,M1), fib(N,M2) <=> M1 = M2, fib(N,M1).

fib_r1(C,Flag,N,M),var(Flag),{event(C,Fib)}=>
    Fib=fib(FlagQ,N1,M1),
    (var(FlagQ)->
       (N==N1-> % this test can even be removed

         FlagQ=1,
         Flag=1,
         M=M1,
         fib(N,M)  % the body is the same as the first atom on the LHS 

	;
         true
       )
     ;
       true
     ).
fib_r1(C,Flag,N,M) => true.

%%% fib(0,M) ==> M = 1.

%%% fib(1,M) ==> M = 1.

%%%fib(N,M) ==> N > 1 | N1 is N-1, fib(N1,M1), N2 is N-2, fib(N2,M2), M is M1 + M2.


fib_r234(Flag,0,M),var(Flag) => M=1.
fib_r234(Flag,1,M),var(Flag) => M=1.
fib_r234(Flag,N,M),var(Flag),N>1 =>
     N1 is N-1, 
%     writeln((fib(N,M)=>fib(N1,M1),fib(N2,M2))),

     fib(N1,M1), 
     N2 is N-2, 
     fib(N2,M2), 
     M is M1 + M2.
fib_r234(Flag,N,M) => true.