:- source.

:- on_pl( swi(_V), ensure_loaded('system/swi/std') ).

:- on_pl( sicstus(_V), ensure_loaded('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)],
	List = [(Prb,[],Alts,Cont)],
	Tree = t(0,List,nil,nil),
	values( Tree, 1, 0, [], ProdPrb, ValPrbs, Vals ),
	Numb is ProdPrb.

values( _T, _Iter, _Seen, Complete, Prb, ValPrbs, Vals ) :-
	member( Prb-_Metr-Pairs, Complete ),
	% write( metric(Metr) ), nl,
	pair_list( Pairs, ValPrbs, Vals ).
values( Tree, Iter, Seen, OldComplete, Prb, ValPrbs, Values ) :-
	pick_branch( Tree, Mtrc, Branch, NbrTree ),
	% length( [H|T], Lgth ),
	length( OldComplete, Plus ),
	NxSeen is Seen + Plus,
	% write( its_sn_nds(Iter,NxSeen) ), nl,
	% write( its_sn_nds(Iter,NxSeen,Lgth) ), nl,
	expand_branch( Branch, Mtrc, Branches, Complete ),
	% collapse_branches( Branches, Collapsed ),
	list_to_tree( Branches, nil, InsTree ),
	% insert_branches_arrays( Collapsed, NxArray, NxBest, Brray, FrBest ),
	add_trees( NbrTree, InsTree, NxTree ),
	NxIter is Iter + 1,
	values( NxTree, NxIter, NxSeen, Complete, Prb, ValPrbs, Values ).

add_trees( nil, Tree, Tree ) :- !.
add_trees( Tree, nil, Tree ) :- !.
add_trees( t(Idx1,List1,L1,R1), t(Idx2,List2,L2,R2), NwTree ) :-
	( Idx1 =:= Idx2 ->
		add_trees( L1, L2, L3 ),
		add_trees( R1, R2, R3 ),
		append( List2, List1, List3 ),
		NwTree = t(Idx1,List3,L3,R3)
		;
		( Idx1 < Idx2 -> 
			add_trees( R1, t(Idx2,List2,nil,R2), R3 ),
			add_trees( t(Idx1,List1,L1,R3), L2, NwTree )
			;
			add_trees( L1, t(Idx2,List2,L2,nil), L3 ),
			add_trees( t(Idx1,List1,L3,R1), R2, NwTree )
		)
	).

pick_branch( t(Idx,List,L,R), Metric, Branch, NwTree ) :-
	!,
	( R == nil -> 
		( List = [Branch|T] -> 
			Metric = Idx,
			( T ==[] -> 
				( L == nil -> 
					NwTree = nil
					% collapse the whole branch
					;
					NwTree = L
					% bypass current node
				)
				;
				NwTree = t(Idx,T,L,R)
			)
			;
			pick_branch(L,Branch,NwTree)
			% delete current node
		)
		;
		NwTree = t(Idx,List,L,NwR),
		pick_branch( R, Metric, Branch, NwR )
	).

insert_branches_arrays( [], Array, Best, Array, Best ) :- !.
insert_branches_arrays( [Mtr-Tuples|T], Array, Best, NwArray, NwBest ) :-
	( Mtr > Best -> 
		NxBest is Mtr 
		;
		NxBest is Best
	),
	arefl( Mtr, Array, Elements ),
	append( Tuples, Elements, NwElements ),
	aset( Mtr, Array, NwElements, NxArray ),
	insert_branches_arrays( T, NxArray, NxBest, NwArray, NwBest ).

collapse_branches( Branches, Collapsed ) :-
	list_to_tree( Branches, nil, Tree ),
	tree_to_list( Tree, Collapsed, [] ).

list_to_tree( [], Tree, Tree ).
list_to_tree( [H|T], Tree, NwTree ) :-
	H = Mtr-Tuple,
	insert_to_tree( Tree, Mtr, Tuple, NxTree ),
	list_to_tree( T, NxTree, NwTree ).

insert_to_tree( nil, Idx, Val, t(Idx,[Val],nil,nil) ).
insert_to_tree( t(Cidx,Cvals,Left,Right), Idx, Val, t(Cidx,NwVals,NwL,NwR) ) :-
	( Idx < Cidx -> 
		insert_to_tree( Left, Idx, Val, NwL ),
		NwVals = Cvals, NwR = Right
		;
		( Idx =:= Cidx ->
			NwVals = [Val|Cvals],
			NwR = Right, NwL = Left
			;
			insert_to_tree( Right, Idx, Val, NwR ),
			NwVals =Cvals, NwL = Left
		)
	).

tree_to_list( nil, Collapsed, Collapsed ).
tree_to_list( t(Idx,Vals,Left,Right), List, Tail ) :-
	tree_to_list( Left, List, Tail1 ),
	Tail1 = [Idx-Vals|Tail2],
	tree_to_list( Right, Tail2, Tail ).

expand_branch( (BrPrb,List,Alts,Contin), BrMtr, Branches, Complete ) :-
	( Contin == [] ->
		reverse( List, Solution ),
		Complete = [BrPrb-BrMtr-Solution],
		Branches = []
		;
		Contin = [H|T],
		findall( NxMtr-(NxBrPrb,HList,HAlts,T1),
			(  	
				select( (HPrb,HEl), H, HRemPairs ),
				( 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 ),
				branch_probability( BrMtr, BrPrb, BestPrb, HPrb, NxMtr, NxBrPrb ),
				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 ).

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 = AccRmPrb,
		NoElH = H
	),
	clear_dmns_from_el_kp( T, El, UpdtPrb, NoElT, RmPrb ).

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

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

branch_probability( BaseMetr, BasePrb, MxAltPrb, MarginPrb, BranchMetric, BranchPrb ) :-
	% rationals_subtraction( MarginPrb, MxAltPrb, Diff ),
	rationals_multiplication( BasePrb, MarginPrb, BranchPrb ),
	% write( branchprb(BranchPrb) ), nl,
	% rationals_subtraction( BranchPrb, MxAltPrb, Diff ),
	% write( diff(Diff) ), nl,
	% rationals_to_aprox_int( Diff, 10000, Apprx ),
	% rationals_dilute( BranchPrb, Diluted, 100000 ),
	% write( diluted(Diluted) ), nl,
	% rationals_to_aprox_int( Diluted, 10000000, Apprx ),
	% rationals_inflate( BranchPrb, 100000000, DApprx ),
	% BranchMetric is min( max( integer(((BranchPrb * 10000000)-5)*100),0), 10000 ),
	% BranchMetric is min( max( integer(10+(BranchPrb-1/1000000)*1000000000), 1), 10100 ),
	% Apprx is RApprx mod 10000,
	% write( basemetric(BaseMetr) ), nl,
	Diff is MarginPrb - MxAltPrb,
	% write( diff(Diff) ), nl,
	Jump is max( -200, min( 200, integer(Diff*10000))),
	% write( jump(Jump) ),
	BranchMetric is BaseMetr + Jump.
	% write( metric(BranchMetric) ), nl,

	% BranchMetric is 10000 + BaseMetr + Apprx,
	% ( BranchMetric < 0 -> write(neg_metric(BranchMetric)), nl, abort ; true ).