:- cond_load( swi(_V), true, [], ['System/Swi/std'] ).

:- cond_load( sicstus(_V), true, [], ['System/Sicstus/std'] ).

% :- ensure_loaded( 'System/Swi/sicstus_ordsets' ).
:- ensure_loaded( rationals ).

% :- cond_load( sicstus(_Any), true,
% 	[ compilation_mode(consult) ],
% 	[ library(lists),
% 			% member/2
% 	  'System/Sicstus/std'
% 		] ). 


prom( Numb-ProdPrb-ValPrbs-Vals ) :-
	Vals = [_A,_B,_C,_D],
	Mtr  = 0/1,
	Prb  = 1/1,
	List = [], 
	Alts = [],
	Cont = 	[ [(3/8,a),(5/16,b),(3/16,c),(2/16,d)],
			  [(5/16,d),(4/16,c),(4/16,a),(3/16,b)],
			  [(3/7,a),(2/7,b),(1/7,d),(1/7,c)],
			  [(9/32,d),(9/32,c),(7/32,b),(7/32,a)]],
	% Cont = 	[ 1/1-[(3/8,a),(5/16,b),(3/16,c),(2/16,d)],
			  % 1/1-[(5/16,d),(4/16,c),(4/16,a),(3/16,b)],
			  % 1/1-[(3/7,a),(2/7,b),(1/7,d),(1/7,c)],
			  % 1/1-[(9/32,d),(9/32,c),(7/32,b),(7/32,a)]],
	Tree = [(Mtr,Prb,List,Alts,Cont)],
	values( Tree, 1, [], ProdPrb, ValPrbs, Vals ),
	Numb is ProdPrb.

		
mive( Numb-Prb-ValPrbs-Vals ) :-
	Vals = [_A,_B,_C,_D],
	values( [(1/1, 1/1, [],
			[ [(2/16,a),(3/16,b),(5/16,c),(3/8,d)], 
			  [(3/16,d),(4/16,c),(4/16,a),(5/16,b)], 
			  [(1/7,a),(1/7,b),(2/7,d),(3/7,c)],
			  [(7/32,d),(7/32,c),(9/32,b),(9/32,a)]]
			) 
		    ],
		1,
		[],
		Prb,
		ValPrbs,
		Vals
		), 
	Numb is Prb.
five( Numb-Prb-ValPrbs-Vals ) :-
	Vals = [_A,_B,_C,_D],
	values( [(1/1, 1/1, [],
			[ [(3/8,a),(5/16,b),(3/16,c),(2/16,d)], 
			  [(5/16,d),(4/16,c),(4/16,a),(3/16,b)], 
			  [(3/7,a),(2/7,b),(1/7,d),(1/7,c)],
			  [(9/32,d),(9/32,c),(7/32,b),(7/32,a)]]
			) 
		    ],
		1,
		[],
		Prb,
		ValPrbs,
		Vals
		), 
	Numb is Prb.
test( Prb-ValPrbs-Vals ) :-
	Vals = [_A,_B,_C],
	Branch = [ ( 0/1, 1/1, [],
				[ [(1/2,a),(1/3,b),(1/6,c)], 
				[(2/3,b),(1/6,a),(1/6,c)], 
				[(1/2,c),(1/4,a),(1/4,b)] ] ) ],
	values( Branch, 
		1,
		[],
		Prb,
		ValPrbs,
		Vals
		).

	% X1 e [a,b,c]{1/2,1/3,1/6}
	% X2 e [b,a,c]{2/3,1/6,1/6}
	% X3 e [c,a,b]{1/2,1/4,1/4}

values( _Branches, _Iter, _Seen, Complete, Prb, ValPrbs, Vals ) :-
	member( Prb-Metr-Pairs, Complete ),
	% write( metric(Metr) ), nl,
	pair_list( Pairs, ValPrbs, Vals ).
values( [H|T], Iter, Seen, OldComplete, Prb, ValPrbs, Values ) :-
	length( [H|T], Lgth ),
	length( OldComplete, Plus ),
	NxSeen is Seen + Plus,
	% write( iteration(Iter) ), write( number_of_nodes(Lgth) ), nl,
	write( its_sn_nds(Iter,NxSeen,Lgth) ), nl,
	% write( branches([H|T]) ), nl,
	expand_branch_prom( H, Branches, Complete ),
	sort_desc( Branches, Sorted ),
	% expand_branch_prom( H, Branches, Complete ),
	% expand_branch( H, Branches, Complete ),
	% expand_branch_hor( H, Branches, Complete ),
	% expand_branch_atmost( H, 3, Branches, Complete ),
	% we assume branches come out sorted, the order depends on the order of the
	% the input domains 
	% only change needed for switch between acsending / descending order is in 
	% insert_branches.
	% unsorted_branches_insert( Branches, T, NxTree ),
	insert_branches( Sorted, T, NxTree ),
	NxIter is Iter + 1,
	values( NxTree, NxIter, NxSeen, Complete, Prb, ValPrbs, Values ).

sort_desc( List, Sorted ) :-
	list_to_tree( List, nil, Tree ),
	traverse_desc( Tree, Sorted, [] ).

list_to_tree( [], Tree, Tree ).
list_to_tree( [H|T], Tree, NwTree ) :-
	insert_to_tree( Tree, H, NxTree ),
	list_to_tree( T, NxTree, NwTree ).
insert_to_tree( t(Val,Left,Right), H, t(Val,NwLeft,NwRight) ) :-
	% assume no duplicates
	( H @< Val -> 
		insert_to_tree( Left, H, NwLeft ),
		NwRight = Right
		;
		insert_to_tree( Right, H, NwRight ),
		NwLeft = Left
	).
insert_to_tree( nil, Val, t(Val,nil,nil) ).

traverse_desc( t(Val,Left,Right), Sorted, Tail ) :-
	traverse_desc( Right, Sorted, Tail1 ),
	Tail1 = [Val|Tail2],
	traverse_desc( Left, Tail2, Tail ).
traverse_desc( nil, Sorted, Sorted ).
	

expand_branch_hor( (BrMtr,BrPrb,List,Contin), Branches, Complete ) :-
	% length( List, Lgth ),
	( singleton(Contin,Single) -> 
		findall( SolPrb-Solution,
			( member( (ElPrb,El), Single ),
			  insert_progressive( List, [(ElPrb,El)], 1/1, Solution, _ReAddedPrb ),
			  rationals_multiplication( BrPrb, ElPrb, SolPrb ) ),
			Complete ),
		Branches = []
		;
		% dont test for Contin = []
		findall( (NxMtr,NxBrPrb,HList,T1),
			( 	nth1(Nth1,Contin,[(HPrb,HEl)|_Umn],OtherCs),
				clear_dmns_from_el( OtherCs, HEl, T1 ),
				new_branch_probability( BrMtr, BrPrb, _Lgth, HPrb, NxMtr, NxBrPrb ),
				HList = [Nth1-(HPrb,HEl)|List] ),
			Branches ),
			Complete = []
	).

% expand_branch_prom( (BrMtr,BrPrb,List,Alts,[RmPrb-H|T]), Branches, Complete ) :-
% expand_branch_prom( (BrMtr,BrPrb,List,Alts,[H|T]), Branches, Complete ) :-
% expand_branch_prom( Branch, Tree, Branches, Complete, NwTree ) :-
% 	expand_branch_prom_1( Branch, Branches, Complete ),
% 	sort_branches( Branches, Sorted ), 
% 	sorted_to_tree( Sorted, Tree, NwTree ).
% sort_branches( 

expand_branch_prom( (BrMtr,BrPrb,List,Alts,Contin), Branches, Complete ) :-
	% length( List, Lgth ),
	( Contin == [] ->
		% findall( SolPrb-SMtr-Solution,
			% (	member((HPrb,HEl),H),
				% % SolPrb is HPrb * BrPrb,
				% % rationals_multiplication( BrPrb, HPrb, SolPrb ),
				% ( selects((MxPrb,HEl),Alts,MidAlts) -> 
					% true
					% ;
					% % MxPrb = 0/1, MidAlts = Alts
					% MxPrb = 0/1, MidAlts = Alts
				% ),
				% new_new_branch_probability( BrMtr, BrPrb, MxPrb, HPrb, SMtr, SolPrb ),
				 % reverse( [(HPrb,HEl)|List], Solution )
				 reverse( List, Solution ),
			% ),
			% Complete ),
		Complete = [BrPrb-BrMtr-Solution],
		Branches = []
		;
		Contin = [H|T],
		findall( (NxMtr,NxBrPrb,HList,HAlts,T1),
			(  	select( (HPrb,HEl), H, HRemPairs ),
				% NxBrPrb is HPrb * BrPrb,
			   	% rationals_multiplication( BrPrb, HPrb, NxBrPrb ),
				( select((MxPrb,HEl),Alts,MidAlts) -> 
					true
					;
					MxPrb = 0/1, MidAlts = Alts
				),
				clear_dmns_from_el_kp( T, HEl, 0/1, T1, RmvdPrb ),
				rat_max( RmvdPrb, MxPrb, BestPrb ),
				new_new_new_branch_probability( BrMtr, BrPrb, BestPrb, HPrb, NxMtr, NxBrPrb ),
				% write( new_metric(NxMtr) ), nl,
				HList = [(HPrb,HEl)|List],
				refresh_alts( HRemPairs, MidAlts, HAlts )
			),
			Branches ),
		Complete = []
	).
				
refresh_alts( [], Alts, Alts ).
refresh_alts( [(HPrb,HEl)|T], Alts, [(NwHElPrb,HEl)|TNwAlts] ) :-
	( select((AltHElPrb,HEl),Alts,NxAlts) -> 
		( HPrb > AltHElPrb -> 
			NwHElPrb = HPrb
			;
			NwHElPrb = AltHElPrb
		)
		;
		NwHElPrb = HPrb,
		NxAlts = Alts
	),
	refresh_alts( T, NxAlts, TNwAlts ).

expand_branch( (BrMtr,BrPrb,List,[H|T]), Branches, Complete ) :-
	length( List, Lgth ),
	( T == [] ->
		findall( SolPrb-Solution,
			(	member((HPrb,HEl),H),
				% SolPrb is HPrb * BrPrb,
				% rationals_multiplication( BrPrb, HPrb, SolPrb ),
				new_branch_probability( BrMtr, BrPrb, Lgth, HPrb, _SMtr, SolPrb ),
				reverse( [(HPrb,HEl)|List], Solution )
			),
			Complete ),
		Branches = []
		;
		findall( (NxMtr,NxBrPrb,HList,T1),
			(  	member( (HPrb,HEl), H ),
				% NxBrPrb is HPrb * BrPrb,
			   	% rationals_multiplication( BrPrb, HPrb, NxBrPrb ),
				new_branch_probability( BrMtr, BrPrb, Lgth, HPrb, NxMtr, NxBrPrb ),
				HList = [(HPrb,HEl)|List],
				clear_dmns_from_el( T, HEl, T1 )
			),
			Branches ),
		Complete = []
	).
				
expand_branch_atmost( (BrMtr,BrPrb,List,[H|T]), AtM, Branches, Complete ) :-
	length( List, Lgth ),
	( T = [] -> 
		proliferate_solutions( H, AtM, BrMtr, BrPrb, List, Lgth, T, Branches, Complete )
		;
		proliferate_branches( H, AtM, BrMtr, BrPrb, List, Lgth, T, Branches ),
		Complete = []
	).


proliferate_solutions( [], _AtM, _BrMtr, _BrPrb, _List, _MrgMtr, _Contin, [], [] ).
proliferate_solutions( [(HPrb,HEl)|T], AtM, BrMtr, BrPrb, List, MrgMtr, Contin, Branches, Complete ) :-
	% member((HPrb,HEl),Pool),
	% SolPrb is HPrb * BrPrb,
	% rationals_multiplication( BrPrb, HPrb, SolPrb ),
	( AtM < 1 -> 
		Branches = [(BrMtr,BrPrb,List,[[(HPrb,HEl)|T]|Contin])],
		Complete = []
		;
		new_branch_probability( BrMtr, BrPrb, MrgMtr, HPrb, _SMtr, SolPrb ),
		reverse( [(HPrb,HEl)|List], Solution ),
		NxAtm is AtM - 1,
		Complete = [SolPrb-Solution|TComplete],
		proliferate_solutions( T, NxAtm, BrMtr, BrPrb, List, MrgMtr, Contin, Branches, TComplete )
	).

% proliferate_top( [], _AtM, _BrMtr, _BrPrb, _List, _Lgth, _Contin, [] ).
% proliferate_top( [(HPrb,HEl)|T], AtM, BrMtr, BrPrb, List, MrgMtr, Contin, Branches ) :-

proliferate_branches( [], _AtM, _BrMtr, _BrPrb, _List, _Lgth, _Contin, [] ).
proliferate_branches( [(HPrb,HEl)|T], AtM, BrMtr, BrPrb, List, MrgMtr, Contin, Branches ) :-
	( AtM < 1 -> 
		Branches = [(BrMtr,BrPrb,List,[[(HPrb,HEl)|T]|Contin])]
		;
		new_branch_probability( BrMtr, BrPrb, MrgMtr, HPrb, NxMtr, NxBrPrb ),
		clear_dmns_from_el( Contin, HEl, ThisContin ),
		Branches = [(NxMtr,NxBrPrb,[(HPrb,HEl)|List],ThisContin)|TBranches],
		NxAtm is AtM - 1,
		proliferate_branches( T, NxAtm, BrMtr, BrPrb, List, MrgMtr, Contin, TBranches )
	).

clear_dmns_from_el_kp( [], _El, RmPrb, [], RmPrb ).
clear_dmns_from_el_kp( [H|T], El, AccRmPrb, [NoElH|NoElT], RmPrb ) :-
	( select( (PrbEl,El), H, NoElH ) -> 
		rat_max( AccRmPrb, PrbEl, UpdtPrb )
		;
		UpdtPrb = RmPrb,
		NoElH = H
	),
	clear_dmns_from_el_kp( T, El, UpdtPrb, NoElT, RmPrb ).

rat_max( RmPrb, PrbEl, UpdtPrb ) :-
	( RmPrb < PrbEl -> 
		UpdtPrb = PrbEl
		;
		UpdtPrb = RmPrb
	).

clear_dmns_from_el( [], _El, [] ).
clear_dmns_from_el( [RmPrb-H|T], El, [UpdRmPrb-NoElH|NoElT] ) :-
% clear_dmns_from_el( [H|T], El, [NoElH|NoElT] ) :-
	% maybe we could use the discarded probability as a metric.
	% for weighting the branch.
	% ( selects( (_Prb,El), H, NoElH ) -> 
	( select( (PrbEl,El), H, NoElH ) -> 
		% green and red cut, this is healthy as far as H contains at most
		% one occurance of El.
		% true
		% rationals_addition( RmPrb, PrbEl, UpdRmPrb )
		rationals_multiplication( RmPrb, PrbEl, UpdRmPrb )
		;
		UpdRmPrb = RmPrb,
		NoElH = H
	),
	clear_dmns_from_el( T, El, NoElT ).

unsorted_branches_insert( [], Tree, Tree ).
unsorted_branches_insert( [H|T], Tree, NwTree ) :-
	% H = (BrMtr,_BrPrb,_List,_Contin),
	H = (BrMtr,_BrPrb,_List,_Alt,_Contin),
	merge_branches( Tree, BrMtr, H, [], NxTree ),
	unsorted_branches_insert( T, NxTree, NwTree ).

insert_branches( [], Tree, Tree ).
insert_branches( [H|T], Tree, NxTree ) :-
	H = (BrMtr,_BrPrb,_List,_Alt,_Contin),
	% H = (BrMtr,_BrPrb,_List,_Contin),
	merge_branches( Tree, BrMtr, H, T, NxTree ).

merge_branches( [], _InsPrb, InsBranch, InsBrs, [InsBranch|InsBrs] ).
merge_branches( [(NdMtr,NdPrb,NdList,NdContin)|Tree], InsMtr, InsBranch, InsBrs, NxTree ) :-
	( NdMtr =< InsMtr -> 
	% ( NdMtr >= InsMtr ->  % for ascending order
		NxTree = [InsBranch|TailTree],
		insert_branches( InsBrs, [(NdMtr,NdPrb,NdList,NdContin)|Tree], TailTree )
		;
		NxTree = [(NdMtr,NdPrb,NdList,NdContin)|TailTree],
		merge_branches( Tree, InsMtr, InsBranch, InsBrs, TailTree )
	).

pair_list( [], [], [] ).
pair_list( [(A,B)|T], [A|T1], [B|T2] ) :-
	pair_list( T, T1, T2 ).

new_new_new_branch_probability( BaseMetr, BasePrb, MxAltPrb, MarginPrb, BranchMetric, BranchPrb ) :-
	rationals_subtraction( MarginPrb, MxAltPrb, Diff ),
	rationals_to_aprox_int( Diff, 1000000, Apprx ),
	BranchMetric is BaseMetr + Apprx,
	rationals_multiplication( BasePrb, MarginPrb, BranchPrb ).

new_new_branch_probability( BaseMetr, BasePrb, MxAltPrb, MarginPrb, BranchMetric, BranchPrb ) :-
	% rationals_addition( BasePrb, MarginPrb, Sum1 ),
	rationals_addition( BaseMetr, MarginPrb, Sum1 ),
	rationals_subtraction( Sum1, MxAltPrb, BranchMetric ),
	rationals_multiplication( BasePrb, MarginPrb, BranchPrb ).
	% rationals_multiplication( BasePrb, MarginPrb, BranchPrb ),
	% rationals_to_aprox_int( BranchMetricFull, 1000000, BranchMetric ).
	% rationals_dilute( BranchMetricFull, BranchMetric, 10000 ).
	
new_branch_probability( BaseMetr, BasePrb, RemPrb-MxAltPrb, MarginPrb, BranchMetric, BranchPrb ) :-
	% rationals_invert( RemPrb, InvRemPrb ),
	% rationals_invert
	% rationals_multiplication( BaseMetr, MarginPrb, BranchPrb ),

	% rationals_addition( BaseMetr, MarginPrb, Sum1 ),
	% rationals_subtraction( Sum1, RemPrb, Sum2 ),
	% rationals_subtraction( Sum2, MxAltPrb, BranchMetric ),
	rationals_multiplication( BaseMetr, MarginPrb, Prod1 ),
	rationals_multiplication( RemPrb, MxAltPrb, Prod2 ),
	rationals_subtraction( Prod1, Prod2, BranchMetric ),
	rationals_multiplication( BasePrb, MarginPrb, BranchPrb ).

	
% new_branch_probability( BaseMetr, _BasePrb, _MarginMetr, MarginPrb, BranchMetric, BranchPrb ) :-
% 	rationals_multiplication( BaseMetr, MarginPrb, BranchPrb ),
% 	rationals_addition( BaseMetr, MarginPrb, BranchMetric ).
	
old_new_branch_probability( BaseMetr, BasePrb, MarginMetr, MarginPrb, BranchMetric, BranchPrb ) :-
	rationals_multiplication( BasePrb, MarginPrb, BranchPrbProp ),
	rationals_dilute( BranchPrbProp, BranchPrb, 10000 ),
	% currently the metric is the length of partial solution 'on' this branch
	% BranchMetric = (BaseMetric * (MarginMetric -1) + MarginPrb) * MarginMetr
	% not cerain if it is better to distribute...
	PlusMM is MarginMetr + 1, % expect it to work properly for MarginMetric = 1
	rationals_multiplication( BaseMetr, MarginMetr/1, Factor ),
	rationals_addition( Factor, MarginPrb, Additive ),
	rationals_multiplication( Additive, 1/PlusMM, BranchMetricProp ),
	rationals_dilute( BranchMetricProp, BranchMetric, 10000 ).