%
% the hybrid fuser
% will be consulted by fuse.pl
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% hfuse/3
%
% hybrid fusion
% CIF may be combined and unifying links are found
% the CIF itself may be changed as fusing with EQCs involves cloning
%
% hfuse(+Cif,-Groups,-Links)
%
% Cif		=	list of CIF to be fused
% Groups	=	a list of groups as a result of fusion (clones may be created)
% Links		=	list of unifications found
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

hfuse(Cif,Groups,Links) :-
	sort_cif(Cif,Sorted_cif),					%sort CIF so that UQCs go before EQCs
	hfuse_into_group(Sorted_cif,fused(_,link(Uu,Eu),Groups)),	%fuse it
	my_union(Uu,Eu,Links).						%combine UU-links w/ EU-links


%
% hfuse_into_group/2
%
% fuse constraints into a "fused/3" structure
% unifying links are found and CIF may be changed because of cloning
%
% hfuse_into_group(+Cif,-Fused)
%
% Cif	=	list of CIF to be fused
% Fused	=	the fused CIF in a "fused/3" structure
%
hfuse_into_group([],fused(gen([],[]),link([],[]),group([]))).	%end of CIF, no more gen & links

hfuse_into_group([C|Cs],Fused) :-
	hfuse_into_group(Cs,Temp_fused),			%fuse the tail 1st
	hfuse_into_group(C,Temp_fused,Fused).			%then fuse head into the fused-tail



%
% hfuse_into_group/3
%
% hfuse_into_group(+C,+Fused,-New_fused)
%
% C	=	a QC to be fused into Fused
% Fused	=	a fused CIF in a "fused/3" structure
% New_fused	=	the new result as a fused/3
%

%
% no U-gen nor E-gen in "Fused", no fusion needed
% just return C1 as a group in fused/3
%
hfuse_into_group(C1,fused(gen([],[]),link(_,_),group(_)),Fused) :-
	C1=restrict_subquery(_,_,_),						%C1 is a QC
	!,
	get_all_gens(C1,Ug_of_c1,Eg_of_c1),					%get all gens in C1
	make_into_group(C1,C1_group),						%make C1 into a group
	Fused=fused(gen(Ug_of_c1,Eg_of_c1),link([],[]),[C1_group]).		%compose the fused structure

%
% something in gen, possible fusion
%
hfuse_into_group(C1,Fused,New_fused) :-
	C1=restrict_subquery(_,_,_),						%C1 is a QC
	!,
	get_all_gens(C1,Ug_of_c1,Eg_of_c1),					%get gens in C1
	%
	% STEP 1:	look for UU-fusion
	%
	hfuse_into_group_step1(C1,Ug_of_c1,Eg_of_c1,Fused,Temp_fused_1,Uu_flag),
/*
	Temp_fused_3=Temp_fused_1,
	Ue_flag=not_added,
	Eu_flag=not_added,
*/
	%
	% STEP 2:	find EU-links between C1's UQCs  & fused's EQCs
	%
	hfuse_into_group_step2(C1,Ug_of_c1,Eg_of_c1,Temp_fused_1,Temp_fused_2,Ue_flag),
	%
	% STEP 3:	find EU-links between C1's EQCs & fused's UQCs
	%
	hfuse_into_group_step3(C1,Ug_of_c1,Eg_of_c1,Temp_fused_2,Temp_fused_3,Eu_flag),
	(	(	Uu_flag=not_added,					%if there is no fusion taken place
			Ue_flag=not_added,					%put C1 into the result
			Eu_flag=not_added,
			!,
			Temp_fused_3=fused(gen(Temp_ug3,Temp_eg3),Temp_link_3,Temp_groups_3),
			append_cif(Ug_of_c1,Temp_ug3,New_ug),			%more U-gen
			append_cif(Eg_of_c1,Temp_eg3,New_eg),			%more E-gen
			New_gens=gen(New_ug,New_eg),				%the new gen
			New_link=Temp_link_3,					%no change in links
			make_into_group(C1,C1_group),				%make C1 into a group
			New_groups=[C1_group|Temp_groups_3],			%add C1's group
			New_fused=fused(New_gens,New_link,New_groups)		%the new fused structure
		);
		(	New_fused=Temp_fused_3					%otherwise C1 must be put in
		)
	).



%
% step 1:	find UU-links and potential explicit fusion
%
hfuse_into_group_step1(C1,Ug_of_c1,_,Fused,New_fused,Flag) :-
	Fused=fused(gen(Ug,_),_,_),
	find_matches(Ug_of_c1,Ug,Uu_matches),				%find match between C1's U-gen & the current fused structure
	(	(	Uu_matches=[],					%no UU-link found
			!,
			Flag=not_added,					%no match found
			New_fused=Fused					%no change being made
		);
		(
			Flag=found,					%match(es) found
			hfuse_update_fused_from_uu_matches(C1,Fused,Uu_matches,New_fused)
		)
	).


%
% step 2:	find UE-links between C1 & Fused
%		potential cloning of C1 possible
%
hfuse_into_group_step2(C1,Ug_of_c1,_,Fused,New_fused,Flag) :-
	Fused=fused(gen(_,Eg),_,_),
	find_matches(Ug_of_c1,Eg,Ue_matches),					%find UE-matches
	%
	% NOTE: no matter there is a UE-match or not, we don NOT add C1
	%
	(	(	Ue_matches=[],						%if no match found
			!,
			Flag=not_added,						%no match found, C1 not added
			New_fused=Fused						%no change at all
		);
		(	%
			% Now given this "bag" of UE-matches, we try to clone C1 (as many as needed)
			% and get the UE-links between these cloned-C1s & fused's EQCs
			% As C1 is being cloned, more vars are created and we have to
			% update U-gen & E-gen as well
			%
			Flag=not_added,						%match(es) found
			hfuse_update_fused_from_ue_matches(C1,Fused,Ue_matches,New_fused)
		)
	).

%
% step 3:	find EU-links between C1 & Fused
%		some groups in Fused may be cloned
%
hfuse_into_group_step3(C1,_,Eg_of_c1,Fused,New_fused,Flag) :-
	Fused=fused(gen(Ug,_),_,_),
	find_matches(Eg_of_c1,Ug,Eu_matches),					%find EU-matches
	%
	% NOTE:	no matter there is a EU-match or not, we don NOT add C1
	%
	(	(	Eu_matches=[],						%if no match found
			!,
			Flag=not_added,						%no match found, C1 not added
			New_fused=Fused						%no change at all
		);
		(	%
			% with the bag of EU-matches, we try to clone those matching groups in Fused
			%
			Flag=not_added,						%match(es) found
			hfuse_update_fused_from_eu_matches(C1,Fused,Eu_matches,New_fused)
		)
	).



%
% hfuse_update_fused_from_uu_matches/4
%
% update fused structure according to UU-match instances
%

hfuse_update_fused_from_uu_matches(C1,Fused,Matches,New_fused) :-
	%
	% NOTE:	calling ifuse here!!!
	%
	ifuse_update_fused_from_uu_matches_prepare_to_fuse(C1,Fused,Matches,[],To_fuse),	%prepare a list of to_fuse structure
	hfuse_update_fused_from_to_fuse(Fused,To_fuse,New_fused).


hfuse_update_fused_from_ue_matches(C1,Fused,Matches,New_fused) :-
	ifuse_update_fused_from_ue_matches_prepare_to_fuse(C1,Fused,Matches,[],To_fuse),	%prepare a list of to_fuse structure
	hfuse_update_fused_from_to_fuse(Fused,To_fuse,New_fused).


hfuse_update_fused_from_eu_matches(C1,Fused,Matches,New_fused) :-
	ifuse_update_fused_from_eu_matches_prepare_to_fuse(C1,Fused,Matches,[],To_fuse),	%prepare a list of to_fuse structure
	hfuse_update_fused_from_to_fuse(Fused,To_fuse,New_fused).





%
% hfuse_update_fused_from_to_fuse/3
%
% update fused/3 according to the list of to_fuse/6
%
% hfuse_update_fused_from_to_fuse(+Old,+Updates,-New)
%
% Old		=	old fused structure in fused/3
% Updates	=	the list of updates in to_fuse/6
% New		=	the returned fused structure in fused/3
%

%
% end of update list
%
hfuse_update_fused_from_to_fuse(Fused,[],Fused).					%no change


hfuse_update_fused_from_to_fuse(Fused,[To|Tos],New_fused) :-
	To=to_fuse(Match_with_info,More_uu,More_eu,_,_,To_add_group),			%get the matching part
	Fused=fused(Gens,Links,Groups),							%get components of the current fused structure
	my_union(More_uu,More_eu,More_links),						%get a union of all links
	groups_involved(More_links,Groups,Involved,Left),				%find groups involved in this match
	hfuse_fuse_explicitly(Match_with_info,Links,To_add_group,Involved,Temp_involved),	%add group explicitly into the involved groups
	!,
	%
	% if explicit fusion succeeds, do this
	%
	append_cif(Temp_involved,Left,Temp_group),					%put the left-behind back
	Temp_gen=Gens,
	Temp_link=Links,
	Temp_fused=fused(Temp_gen,Temp_link,Temp_group),				%the updated fused/3 structure
	hfuse_update_fused_from_to_fuse(Temp_fused,Tos,New_fused).			%work on remaining changes


%
% a non-perfect match
% fuse it implicitly
%
hfuse_update_fused_from_to_fuse(Fused,[To|Tos],New_fused) :-
	To=to_fuse(_,More_uu,More_eu,To_add_ug,To_add_eg,To_add_group),
        Fused=fused(gen(Ug,Eg),link(Uu,Eu),Current_groups),             %the current fused structure
        %
        % update gens
        %
        append_cif(To_add_ug,Ug,Temp_ug),                               %more U-gen
        append_cif(To_add_eg,Eg,Temp_eg),                               %more E-gen
        Temp_gen=gen(Temp_ug,Temp_eg),                                  %the temp gen structure
        %
        % update links
        %
        my_union(More_uu,Uu,Temp_uu),                                   %more UU-links
        my_union(More_eu,Eu,Temp_eu),                                   %more UU-links
        Temp_link=link(Temp_uu,Temp_eu),
        %
        % update groups
        %
        my_union(More_uu,More_eu,Links),                                %get all links in this match
        groups_involved(Links,Current_groups,Involved,Left),            %find involved groups & left-behind in C2
        flatten([To_add_group|Involved],To_merge),                      %put all related groups into a list
        merge_groups(To_merge,Merged_group),                            %merge the 2 groups
        Temp_group=[Merged_group|Left],                                 %put back those left-behind
        Temp_fused=fused(Temp_gen,Temp_link,Temp_group),                %the current fused structure
        ifuse_update_fused_from_to_fuse(Temp_fused,Tos,New_fused).



%
% hfuse_fuse_explicitly/4
%
% fuse explicitly into a list of groups
% returning the list of groups with the fused constraint
% succeeds if an explicit fusion is found, fails otherwise
%
% hfuse_fuse_explicitly(+Match,+Links,+To_add,+Groups,-New_groups)
%
% Match		=	match-with-info in match/4
% Links		=	current links among variables
% To_add	=	a list of to-add in group/2 or CIF
% Groups	=	a list of groups in group/2
% New_groups	=	the returned list of groups with To_add added
%


%
% To_add is an empty-list
%
hfuse_fuse_explicitly(_,_,[],C2,C2) :-
	!.

%
% To_add is a list
%
% NOTE:	This caters for whether To_add is a list of group/2 or CIF
%	and succeeds only if ALL "Adds" can be fused explicitly.
%	So if the tail doesn't fail, then it still fails
%
hfuse_fuse_explicitly(Match_with_info,Links,[Add|Adds],C2,New_c2) :-
	!,
	hfuse_fuse_explicitly(Match_with_info,Links,Add,C2,Temp_c2),		%fuse 1st "to-add" into C2 explicitly
	hfuse_fuse_explicitly(Match_with_info,Links,Adds,Temp_c2,New_c2).	%then the rest
/*
%
% C2 is an empty-list
%
hfuse_fuse_explicitly(_,_,_,[],[]) :-
	!.
*/

%
% C2 is a list
%
hfuse_fuse_explicitly(Match_with_info,Links,To_add,[C|Cs],[New_c|New_cs]) :-
	!,
	hfuse_fuse_explicitly(Match_with_info,Links,To_add,C,New_c),			%fuse explicitly into head
	(	hfuse_fuse_explicitly(Match_with_info,Links,To_add,Cs,New_cs);	%if it can also fuse with tail, then it's fine
		New_cs=Cs							%even if it doesn't, we still got it into the head
	).

%
% To_add is a group
%
hfuse_fuse_explicitly(Match_with_info,Links,To_add,C2,New_c2) :-
	To_add=group(_,Cif),							%get the CIF out of it
	!,
	hfuse_fuse_explicitly(Match_with_info,Links,Cif,C2,New_c2).	%call again to add

%
% To_add is a restrict_subquery/3
% C2 is a group/2
%
hfuse_fuse_explicitly(Match_with_info,Links,To_add,C2,New_c2) :-
	To_add=restrict_subquery(_,_,_),					%To_add is a QC
	C2=group(_,Cif),							%get the list of Cif in this group
	!,
	hfuse_fuse_explicitly(Match_with_info,Links,To_add,Cif,New_cif),	%fuse To_add into CIF of group
	find_vars(New_cif,New_vars),
	New_c2=group(New_vars,New_cif).
%	make_into_group(New_cif,New_c2).					%make new CIF into a group

%
% To_add is a UQC in restrict_subquery/3
% C2 is NOT a group/2, is and supposed to be a restrict_subquery/3
% and C2 is the matching one
%
% NOTE:	if C2 is a list, it will be handled by previous cases
%
hfuse_fuse_explicitly(match(Match,_,_,_),Links,To_add,C2,New_c2) :-
	To_add=restrict_subquery(all(_),_,_),					%To_add is a UQC
	C2=restrict_subquery(Q2,G2,P2),
	same_generator(To_add,C2,Match,Links,Var_map),				%To_add & C2 have the same generator
%	same_set(G1,G2),							%G1 & G2 are the same
	!,
	replace_var_in_cif(Var_map,To_add,Replaced_to_add),			%use C2's var names in To_add's G
	Replaced_to_add=restrict_subquery(all(_),_,P1),				%get G & P of To_add
	append_cif(P1,P2,New_p),						%fuse the P1 into P2
	New_c2=restrict_subquery(Q2,G2,New_p).					%use the new P, Q & G remains the same as we use C2's var names

/*
%
% To_add is a EQC in restrict_subquery/3
% C2 is a UQC in restrict_subquery/3
%
hfuse_fuse_explicitly(match(Match,_,_,_),Links,To_add,C2,New_c2) :-
	To_add=restrict_subquery(some(_),_,_),					%To_add is a UQC
	C2=restrict_subquery(all(V2),G2,P2),
	same_generator(To_add,C2,Match,Links,Var_map),				%To_add & C2 have the same generator
	!,
	replace_var_in_cif(Var_map,To_add,Replaced_to_add),			%use C2's var names
	Replaced_to_add=restrict_subquery(all(_),G1,P1),			%get G & P of To_add
	subtract(G1,G2,[]),							%G1 & G2 are the same
	!,
	append_cif(P1,P2,New_p),						%fuse the P1 into P2
	New_q=some(V2),
	New_c2=restrict_subquery(New_q,G2,New_p).				%use the new P, Q & G remains the same as we use C2's var names
*/

/*
%
% other cases
% i.e. C2 is not the matching one or others
%
hfuse_fuse_explicitly(_,C2,C2).
*/

%
%
%
same_generator(C1,C2,Match,Links,C1_to_c2_map) :-
	C1=restrict_subquery(_,G1,_),
	C2=restrict_subquery(_,G2,_),
	%
	% match G1 against G2
	%
	create_template(G1,Template,C1_to_c2_map),		%create a template from G1
	my_intersect(Template,G2,[],_,[]),
%	match_cif(Template,G2,_,_,_),				%must have nothing left in both Gs
	Links=link(Uu_links,Eu_links),
	my_union(Uu_links,Eu_links,All_links),
	match_is_feasible(C1_to_c2_map,Match,All_links).

match_is_feasible([],_,_).

match_is_feasible([V1:V2|Rest],Match,Links) :-
	member(V1:V2,Match),
	!,
	match_is_feasible(Rest,Match,Links).

match_is_feasible([V1:V2|Rest],Match,Links) :-
	member(V1:Intermediate_var,Match),
	member(Intermediate_var:Shared_var1,Links),
	member(V2:Shared_var2,Links),
	Shared_var1==Shared_var2,
	!,
	match_is_feasible(Rest,Match,Links).



