%
% the constraint fusing module
% fuses constraints in XCIF
%

:- module(fuse,[efuse/2,	%the explicit fuser
		ifuse/3,	%the implicit fuser
		hfuse/3,	%the hybrid fuser
		print_groups/1]	%print fused groups
	).

:- use_module('../../prolog/util/prolog_detect').

:- prolog_detect:prolog(Prolog),
	(	(Prolog=sicstus,
		use_module(library(lists))
		);
		Prolog=swi;
		(	write('*** ERROR: Unsupported Prolog system ***'),
			fail
		)
	).

:- use_module('../../prolog/util/flatten').
:- use_module('../../prolog/util/cif_util').
:- use_module('../../prolog/util/print_cif').
:- use_module(transform).

:- ['../../prolog/util/is_daplex_variable'].
:- [ifuse].				%consult ifuse.pl
:- [hfuse].				%consult hfuse.pl
:- [efuse].				%consult efuse.pl


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% SUPPORTING PREDICATES
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%-------------------------------------------------------------------
%
% sort_cif/2
%
% a more sophisticated strategy
% separate QCs into UU, UE, EU & EE
%
% sort_cif(+Cif,-Sorted)
% Cif	=	list of constraints to sort
% Sorted=	list of sorted constraints w/ UQCs going before EQCs
%
%-------------------------------------------------------------------

sort_cif(Cif,Sorted) :-
	sort_cif(Cif,Uu,Ue,Eu,Ee),
	append_cif(Uu,Ue,Temp1),
	append_cif(Eu,Ee,Temp2),
	append_cif(Temp1,Temp2,Sorted).


%
% sort_cif/3
%
% splits a list of CIF into UQCs & EQCs
% assuming all constraints in XCIF (quantified) format
%
% sort_cif(+Cif,-Uqc,-Eqc)
%
% Cif	=	list of constraints to sort
% Uqc	=	list of UQCs in Cif
% Eqc	=	list of EQCs in Cif
%
sort_cif(Cif,Uqc,Eqc) :-
	sort_cif(Cif,Uu,Ue,Eu,Ee),
	append_cif(Uu,Ue,Uqc),		%group Uu & Ue together to form Uqc
	append_cif(Eu,Ee,Eqc).		%group Eu & Ee together to form Eqc


%
% sort_cif/5
%
% further sorting strategy
% separating QC into UU, UE, EU & EE
%
sort_cif([],[],[],[],[]).

sort_cif([C|Cs],Uu,Ue,Eu,Ee) :-
	C=restrict_subquery(all(_),_,_),		%UQC
	!,
	get_all_gens(C,_,Eg),
	(	(	Eg=[],				%no EQC inside, so it is a Uu
			!,
			sort_cif(Cs,Uus,Ue,Eu,Ee),
			Uu=[C|Uus]
		);
		(	sort_cif(Cs,Uu,Ues,Eu,Ee),	%EQC inside, so it is a Ue
			Ue=[C|Ues]
		)
	).

sort_cif([C|Cs],Uu,Ue,Eu,Ee) :-
	C=restrict_subquery(some(_),_,_),
	!,
	get_all_gens(C,_,Eg),
	(	(	Eg=[],				%no EQC inside, so it is a Uu
			!,
			sort_cif(Cs,Uu,Ue,Eus,Ee),
			Eu=[C|Eus]
		);
		(	sort_cif(Cs,Uu,Ue,Eu,Ees),	%EQC inside, so it is a Ue
			Ee=[C|Ees]
		)
	).

sort_cif([_|Cs],Uu,Ue,Eu,Ee) :-
	format("*** WARNING: not UQC nor EQC in sort_cif/3, discard...~n",[]),	%unknown, discard it
	sort_cif(Cs,Uu,Ue,Eu,Ee).


%-----------------------------------
% groups_involved/4
%
% find groups involved in links
%
% groups_involved(+Links,+Groups,-Involved,-Left)
%
% Links		=	links
% Groups	=	original list of groups
% Involved	=	list of groups involved in "Links"
% Left		=	list of groups NOT involved
%
%-----------------------------------

%
% end of group list
%
groups_involved(_,[],[],[]).

%
% 1st group in list is involved
%
groups_involved(Links,[G|Gs],[G|In],Out) :-
	G=group(Vars,_),		%get list of vars in group
	member(V,Vars),			%a var in G
	member(V:_,Links),		%is involved in the match
	!,
	groups_involved(Links,Gs,In,Out).

%
% 1st group is list is NOT involved
%
groups_involved(Links,[G|Gs],In,[G|Out]) :-
	groups_involved(Links,Gs,In,Out).



%-------------------------------------------
%
% make_into_group/2
%
% make groups from a CIF
%
% make_into_group(+Cif,-Group)
%
% Cif	=	CIF of list of CIF
% Group	=	group of list of groups made
%
%-------------------------------------------

make_into_group([],[]) :-		%end of list
	!.

make_into_group([C|Cs],[G|Gs]) :-
	!,
	make_into_group(C,G),
	make_into_group(Cs,Gs).

make_into_group(G,G) :-
	G=group(_,_),			%if G is already a group, no need to make
	!.

make_into_group(Cif,G) :-
	find_vars(Cif,Vars),
	G=group(Vars,Cif).


%-------------------------------------------------------
%
% merge_groups/2
%
% merge a list of separate groups into a single group/2
%
% merge_groups(+Groups,-Merged)
%
% Groups	=	list of groups/2 to be merged
% Merged	=	merge groups in a single group/2
%
%-------------------------------------------------------

merge_groups([],[]).						%end of list

merge_groups([G|Gs],Merged) :-
	merge_groups(Gs,Gs_merged),				%recursive merge tail 1st
	(	(	Gs_merged=[],				%if nothing
			!,
			Merged=G				%then simply return group
		);
		(	G=group(G_vars,G_c),			%get vars & CIF in group
			Gs_merged=group(Gs_vars,Gs_c),		%get vars & CIF in newly merged tail
			!,
			my_union(G_vars,Gs_vars,Vars),		%combine my vars w/ its vars
			append_cif(G_c,Gs_c,C),			%append my CIF w/ its CIF
			Merged=group(Vars,C)			%this is the new group/2
		);
		(	format("*** WARNING: merge_groups/2 returns unexpected value~n",[])
		)
	).


%-------------------------------------------------------------------
%
% merge_replacement/3
%
% combine 2 replacement list into 1, thus removing intermediate vars
%
% merge_replacement(+Map1,+Map2,-Merged)
%
% Map1		=	1st replacement list in the form var1:var2
% Map2		=	2nd replacement list in the form var1:var2
% Merged	=	the merged list
%
%-------------------------------------------------------------------

%
% Map1 is empty
%
merge_replacement([],Map,Map) :-
	!.

%
% Map2 is empty
%
merge_replacement(Map,[],Map) :-
	!.

%
% scan through Map1 and remove intermediate vars
%
merge_replacement([From:Inter|Ms],Map2,[From:To|Merged]) :-
	member(Inter:To,Map2),				%there is a replacement in Map2
	!,
	delete(Map2,From:Inter,Map2_left),		%remove and skip the replacement in Map2
	merge_replacement(Ms,Map2_left,Merged).		%proceed w/ tail

merge_replacement([M|Ms],Map2,[M|Merged]) :-
	merge_replacement(Ms,Map2,Merged).		%no intermediate, just retain it and proceed



%----------------------------------------------------------
%
% get_all_gens/3
%
% get all generators, including nested one, in a constraint
%
% get_all_gens(+Cif,-U_gens,-E_gens)
%
% Cif		=	CIF to examine
% U_gens	=	list of U-gens
% E_gens	=	list of E-gens
%
%----------------------------------------------------------

%:::::::::::
% for a list
%:::::::::::

get_all_gens([],[],[]) :-
	!.

get_all_gens([C|Cs],U_gens,E_gens) :-
	!,
	get_all_gens(C,U,E),		%get gen from head
	get_all_gens(Cs,Us,Es),		%then tail
	my_union(U,Us,U_gens),		%take the union
	my_union(E,Es,E_gens).

%::::::::::::::::::
% for a fused group
%::::::::::::::::::

get_all_gens(C,U_gens,E_gens) :-
	C=group(_,Cif),				%C is a group
	!,
	get_all_gens(Cif,U_gens,E_gens).	%get gens of the CIF

%:::::::::::::::
% for constructs
%:::::::::::::::

%
% an UQC
%
get_all_gens(C,U_gens,E_gens) :-
	C=restrict_subquery(all(_),G,P),		%get G from this restrict_subquery/3
	!,
	get_all_gens(P,Nested_ug,Nested_eg),		%find nested gens in P
	append_cif(G,Nested_ug,U_gens),			%more U-gen
	E_gens=Nested_eg.				%no change for E-gen

%
% an EQC
%
get_all_gens(C,U_gens,E_gens) :-
	C=restrict_subquery(some(_),G,P),		%get G from this restrict_subquery/3
	!,
	get_all_gens(P,Nested_ug,Nested_eg),		%find nested gens in P
	append_cif(G,Nested_ug,Temp_gens),		% *** now the nested U-gens become E-gens
	append_cif(Temp_gens,Nested_eg,E_gens),		% *** because of the outtermost existential quantifier
	U_gens=[].					% *** no U-gen passing back

get_all_gens(C,U_gens,E_gens) :-
	C=generate_subquery(_,_,_,Aux1,Aux2),
	!,
	get_all_gens(Aux1,U1,E1),
	get_all_gens(Aux2,U2,E2),
	append_cif(U1,U2,U_gens),
	append_cif(E1,E2,E_gens).

get_all_gens(_,[],[]).




%-----------------------------------------------------------
%
% replace_var_in_links/3
%
% replace var-names in matching-links
%
% replace_var_in_links(+Name_map,+Orig,-New)
%
% Name_map	=	var name mappings
% Orig		=	matching links w/ original var names
% New		=	new matching
%
%-----------------------------------------------------------

%
% end of list
%
replace_var_in_links(_,[],[]).

%
% replacing
%
replace_var_in_links(Var_map,[Daplex_var:Prolog_var|Ms],[New_daplex:Prolog_var|Mapped_ms]) :-
	member(Daplex_var:New_daplex,Var_map),
	!,
	replace_var_in_links(Var_map,Ms,Mapped_ms).

%
% NOT replacing
%
replace_var_in_links(Var_map,[M|Ms],[M|Mapped_ms]) :-
	replace_var_in_links(Var_map,Ms,Mapped_ms).


%
% replace var names in a match/4 structure
%
replace_var_in_match_with_info(Replacement,Match_with_info,Replaced) :-
	Match_with_info=match(Match,Left1,Intersect,Left2),
	replace_var_in_cif(Replacement,Match,Replaced_match),
	replace_var_in_cif(Replacement,Left1,Replaced_left1),
	replace_var_in_cif(Replacement,Left2,Replaced_left2),
	replace_var_in_cif(Replacement,Intersect,Replaced_intersect),
	Replaced=match(Replaced_match,Replaced_left1,Replaced_intersect,Replaced_left2).




%----------------------------------------------------------------
%
% clone/3
%
% clone a CIF or "group" w/ different var names, providing var-map
%
% clone(+Cif,-Clone,-Map)
%
% Cif	=	CIF/group to be cloned
% Clone	=	the cloned CIF w/ new var names
% Map	=	the var map (Cif to Clone) in "replacement" style
%
%----------------------------------------------------------------

%
% end of list
%
clone([],[],[]) :-
	!.

%::::::::::::::::
% cloning a group
%::::::::::::::::

clone([C|Cs],[Clone|Clones],Whole_map) :-
	C=group(_,Cif),				%get CIF from group/2
	!,
	clone(Cif,Cif_clone,Map),		%clone the CIF
	find_vars(Cif_clone,Clone_vars),	%find vars in clone
	Clone=group(Clone_vars,Cif_clone),	%make the cloned group
	clone(Cs,Clones,Maps),			%clone the remaining list
	my_union(Map,Maps,Whole_map).		%combine the maps

%
% cloning a CIF
%
clone(Cif,Clone,Map) :-
	find_vars(Cif,Vars),						%find all vars
	generate_counter('fuse:constraint_count',Constraint_num),	%generate a count for this constraint
	name(Constraint_num,C_string),
	append(C_string,"_",Prefix_string),
	name(Prefix,Prefix_string),
	reset_daplex_counter,						%reset daplex counter before cloning a constraint
	generate_replacement_map(Vars,Prefix,Map),			%generate replacement map for all vars
	replace_var_in_cif(Map,Cif,Clone).				%replace all vars in Cif

%
% for each var in the CIF, replace it with another one
% gives replacement-map
%

generate_replacement_map([],_,[]).					%end of list

generate_replacement_map([V|Vs],Prefix,[V:New_var|Maps]) :-
	generate_daplex_variable(Prefix,New_var),			%generate a new var-name
	generate_replacement_map(Vs,Prefix,Maps).			%proceed w/ the list



%------------------------------------------------------------
%
% find_matches/3
%
% find the unifying links between vars
%
% find_matches(+Cif1,+Cif2,-Matches)
%
% Cif1		=	1st CIF to be matched
% Cif2		=	2nd CIF
% Matches	=	list of matches in the form var1:var2
%
%------------------------------------------------------------

find_matches(Cif1,Cif2,Filtered) :-
	create_template(Cif1,Template,Var_map),				%create a matching template
	Goal=(	Wanted=match(Valid_map,Left1,Intersect,Left2),
		match_cif(Template,Cif2,Left1,Intersect,Left2),		%match the template against CIF2
		filter_single_node_match(Left1,Intersect,Left2),	%filter out single-node match
		filter_var_replacement(Var_map,Valid_map)		%and filter out un-instantiated variables
		),
	findall(Wanted,call(Goal),Matches),
	filter_subset_matches(Matches,Filtered).
%	filter_single_node_matches(Subset_filtered,Filtered),

%
% filter_single_node_match/3
%
% filter out single node match of basic types
% succeeds to accept the match or fail to reject
%
% We DO NOT accept single-node match if	the match is a node
% of the basic types (i.e. integer, float, boolean & string)
% and both left behinds are not empty.
% If one CIF runs out, then it is ok.
%
% That means the following cases are accepted:
% 1)	a single-node match not involving the basic types
% 2)	a single-node match of the basic types but 1 CIF runs out.
% 3)	a non-single-node match
%
filter_single_node_match(Left1,Intersect,Left2) :-	%filter out single-node match
	Intersect=[generate(_,_)],			%intersection is a generate/2
	(	Left1=[]				%if nothing left in either 1 CIF
		;
		Left2=[]
	),
	!.						%then it's fine

filter_single_node_match(_,Intersect,_) :-		%filter out single-node match
	Intersect=[generate(Class,_)],			%if intersection is a generate/2
	member(Class,[integer,string,float,boolean]),	%1 of the 4 basic types
	!,
	fail.						%then fail

filter_single_node_match(_,_,_).			%all others are ok


/*
find_matches(Cif1,Cif2,Matches) :-
	create_template(Cif1,Template,Var_map),				%create a matching template
	Goal=(	match_cif(Template,Cif2,_,_,_),				%match the template against CIF2
		filter_var_replacement(Var_map,Valid_map),		%and filter out un-instantiated variables
		write(Valid_map),
		nl
		),
	findall(Valid_map,call(Goal),Matches).
*/

%------------------------------------------------------------
%
% find_matches_with_info/3
%
% find the unifying links between vars with extra info.
%
% find_matches_with_info(+Cif1,+Cif2,-Matches)
%
% Cif1		=	1st CIF to be matched
% Cif2		=	2nd CIF
% Matches	=	list of matches in match/4
%
%------------------------------------------------------------
find_matches_with_info(Cif1,Cif2,Matches) :-
	create_template(Cif1,Template,Var_map),				%create a matching template
	Goal=(	match_cif(Template,Cif2,Left1,Intersect,Left2),
		filter_single_node_match(Left1,Intersect,Left2),	%filter out single-node match
		filter_var_replacement(Var_map,Valid_map),		%and filter out un-instantiated variables
		Wanted=match(Valid_map,Left1,Intersect,Left2)
		),
	findall(Wanted,call(Goal),Matches).

/*
find_links(Cif1,Cif2,Links) :-
	create_template(Cif1,Template,Var_map),				%create a matching template
	Goal=(	match_cif(Template,Cif2,_,_,_),
		filter_var_replacement(Var_map,Temp_map),		%and filter out un-instantiated variables
		match_to_link(Temp_map,Valid_map)			%map the var-map into my required style
		),
	findall(Valid_map,call(Goal),Links).

%
% find all matches between 2 CIFs
%
find_matches(Cif1,Cif2,Matches) :-
	create_template(Cif1,Template,Var_map),					%create a matching template
	Match_goal=(	match_cif(Template,Cif2,Left1,Intersection,Left2),	%the goal is to find an intersection between the 2
			filter_var_replacement(Var_map,Valid_map),		%and filter out un-instantiated variables
			reinstate_var(Var_map)					%for vars w/ no match, reinstate them
			),
	findall(match(Valid_map,Left1,Intersection,Left2),call(Match_goal),Graph_matches),	%find all matches
	Matches=Graph_matches,
%	print_list(Graph_matches),
%	filter_matches(Graph_matches,Matches),			%filter un-wanted matches
%	Graph_matches=Matches,
	print_matches(Matches).
%	Matches=match(Valid_map,Left1,Intersection,Left2).
%	findall(match(Valid_map,Left1,Intersection,Left2),call(Match_goal),Matches).	%find all matches & variable unifications
*/



%----------------------------------------------------
%
% match_to_link/2
%
% map the matching list in the form Var1:Var2
% into "links" with shared Prolog var
%
% match_to_link(+Match,-Link)
%
% Match	=	list of matches in the form var1:var2
% Link	=	list of lists with shared Prolog var
%
%----------------------------------------------------

match_to_link([],[]).

match_to_link([V1:V2|Ms],[V1:Share,V2:Share|Maps]) :-
	match_to_link(Ms,Maps).



%---------------------------------------------------------------------------
%
% swap_matches/2
%
% given a list of matches in var1:var2 or match/4, swap it to var2:var1
%
% swap_matches(+Matches,-Swapped)
%
% Matches	=	the list of matches in the form var1:var2 or match/4
% Swapped	=	the returned list of swapped matches
%
%---------------------------------------------------------------------------

swap_matches(A:B,B:A).					%swap var1:var2 type match

swap_matches(Match,Swapped) :-
	Match=match(Map,Left1,Match,Left2),		%swap match/4 type match
	swap_matches(Map,Swapped_map),			%also swap the var1:var2 matching list
	Swapped=match(Swapped_map,Left2,Match,Left1).	%swap left-behinds

swap_matches([],[]).					%end of list

swap_matches([M|Ms],[S|Ss]) :-				%swap a list of matches
	swap_matches(M,S),
	swap_matches(Ms,Ss).



%
% filter out replacements with uninstantiated var
%
filter_var_replacement([],[]).

filter_var_replacement([A:B|Rest],[A:B|Filtered]) :-
	nonvar(A),				%keep replacement pair
	nonvar(B),				%if both A & B are nonvar
	!,
	filter_var_replacement(Rest,Filtered).

filter_var_replacement([_:_|Rest],Filtered) :-
	filter_var_replacement(Rest,Filtered).	%throw away replacement pair




%
% given a variable & a CIF list
% split the CIF list into the basic generator, extra conditions
% and un-related parts
%
find_generator_and_condition(_,[],[],[],[]).

find_generator_and_condition(Var,[C|Cs],[C|Gs],Cond,Remain) :-
	C=generate(_,Var),					%a basic generator
	!,
	find_generator_and_condition(Var,Cs,Gs,Cond,Remain).

find_generator_and_condition(Var,[C|Cs],G,[C|Cond],Remain) :-
	C=generate(_,_,_,_,Var),				%an extra condition
	!,
	find_generator_and_condition(Var,Cs,G,Cond,Remain).

% find_generator_and_condition(Var,[C|Cs],G,[C|Cond],Remain) :-


find_generator_and_condition(Var,[C|Cs],G,Cond,[C|Remain]) :-
	find_generator_and_condition(Var,Cs,G,Cond,Remain).	%a remaining part





%
% filter_subset_matches/2
%
% filter matches which are subset of other mathces
%
% filter_subset_matches(+Matches,-Filtered)
%
% Matches	=	list of matching instances in the form [var1:var2...]
% Filtered	=	filtered list of matching instances
%
filter_subset_matches([],[]).				%end of matching list

filter_subset_matches([G|Gs],Ms) :-
	G=match(This_var_map,_,_,_),			%get the var-map of this match
	member(match(Another_var_map,_,_,_),Gs),	%another matching instance
	my_subset(This_var_map,Another_var_map),	%this var-map is a subset of another
	!,
	filter_subset_matches(Gs,Ms).

filter_subset_matches([G|Gs],[G|Ms]) :-
	filter_subset_matches(Gs,Ms).


%
% match_cif/5
%
% given 2 CIFs, try to match them as graphs
%
match_cif(Cif1,Cif2,Left1,Intersection,Left2) :-
	cif_to_graph(Cif1,graph(Nodes1,Edges1)),				%convert CIF to graph
	cif_to_graph(Cif2,graph(Nodes2,Edges2)),				%convert CIF to graph
	match_graph(Nodes1,Edges1,Nodes2,Edges2,[],[],Left1,Intersection,Left2).




%
% THIS ONE HAS UNEXPECTED RESULT OF ORDERING
%

%
% match 2 graphs, given nodes & edges
%
match_graph(Nodes1,Edges1,Nodes2,Edges2,Nodes_matched,Edges_matched,Left1,Intersection,Left2) :-
	pick_member(Node,Nodes1,Remain_nodes1),			%pick a matching node in both graph
	pick_member(Node,Nodes2,Remain_nodes2),
	%
	% NOTE:	We DO NOT put a cut here because it inhibits the generation
	%	of different matching graphs with different starting nodes
	%	This results in losing solutions in the form of disconnected matching sub-graphs.
	%
	extend_graph(Remain_nodes1,Edges1,Remain_nodes2,Edges2,[Node|Nodes_matched],Edges_matched,Left1,Intersection,Left2).

%
% extend matching graph from matching nodes
%
extend_graph(Nodes1,Edges1,Nodes2,Edges2,Nodes_matched,Edges_matched,Left1,Intersection,Left2) :-
	pick_member(Matched_node,Nodes_matched,_),		%pick a matched node which appear in both graphs
	pick_member(New_edge,Edges1,Remain_edges1),		%pick an candidate matching edge from graph 1
	edge_emerge_from_node(New_edge,Matched_node),		%which emerges from this node
	pick_member(New_edge,Edges2,Remain_edges2),		%and this edge is also in graph 2
	pick_member(New_node,Nodes1,Remain_nodes1),		%now pick another new node from graph 1
	edge_emerge_from_node(New_edge,New_node),		%which is attached to this edge
	pick_member(New_node,Nodes2,Remain_nodes2),		%and this new node also appears in graph 2
	!,							%THIS CUT IS IMPORTANT AS IT PREVENTS FORMATION OF SMALLER SUB-GRAPH
								% REASON:	If we can extend a matching graph, then extend it.
								%		After extending it, we do not shrink back.
								%
	extend_graph(Remain_nodes1,Remain_edges1,Remain_nodes2,Remain_edges2,[New_node|Nodes_matched],[New_edge|Edges_matched],Left1,Intersection,Left2).


%
% cannot extend further
%
extend_graph(Nodes1,Edges1,Nodes2,Edges2,Nodes_matched,Edges_matched,Left1,Intersection,Left2) :-
	my_union(Nodes_matched,Edges_matched,Intersection),
	my_union(Nodes1,Edges1,Left1),
	my_union(Nodes2,Edges2,Left2).

%
% check if edge is emerging from node
%
edge_emerge_from_node(Edge,Node) :-
	Node=generate(Class,Var_in_node),		%get var from node
	nonvar(Var_in_node),
	cif_util:extract_var_with_type(Edge,Types),	%get vars w/ type from this "edge"
	member(Var_in_edge:Class,Types),
	nonvar(Var_in_edge),
	Var_in_node=Var_in_edge,
	!.
%	member(Var_in_node:Class,Types)
%	member(Var:Class,Types),			%and var is there
%	!.

%
% pick_member/3
%
% pick a member from list
%
% pick_member(-Picked,+List,-Left)
%
% Picked	=	the picked element from List
% List		=	the list of elements
% Left		=	what is left behind
%

pick_member(X,[X|T],T).

pick_member(X,[H|T],[H|Rest]) :-
	pick_member(X,T,Rest).



%
% extract all generate/2 as nodes
% all the rest as edges
%
cif_to_graph(Cif,graph(Nodes,Edges)) :-
	cif_to_graph(Cif,Nodes,Edges).

cif_to_graph([],[],[]).

cif_to_graph([C|Cs],[C|Ns],Es) :-
	C=generate(_,_),
	!,
	cif_to_graph(Cs,Ns,Es).

cif_to_graph([C|Cs],Ns,[C|Es]) :-
	cif_to_graph(Cs,Ns,Es).

/*
%
% the original matching predicate
% treating 2 CIFs as 2 sets
%
find_matches(Cif1,Cif2,Matches) :-
	create_template(Cif1,Template,Var_map),						%create a matching template
	Match_goal=(	my_intersect(Template,Cif2,Left1,Intersection,Left2),		%the goal is to find an intersection between the 2
			(	member(generate(_,_),Intersection),			%where it contains a generate/2
				!							%*** IMPORTANT: cut away alternatives in member/2 only
			),
			format("===intersection===~n",[]),
			print_cif(Intersection),
			connected_graph(Intersection),
			format("==================~n",[]),
			filter_var_replacement(Var_map,Valid_map),			%and filter out un-instantiated variables
			reinstate_var(Var_map)						%for vars w/ no match, reinstate them
			),
	findall(match(Valid_map,Left1,Intersection,Left2),call(Match_goal),Matches).	%find all matches & variable unifications
*/


%
% scan through the matching-list
% and reinstate those which do not match
%
reinstate_var([]).

reinstate_var([Daplex:Daplex|Rest]) :-	%var is changed into var, i.e. no change
	!,
	reinstate_var(Rest).		%continue w/ list

reinstate_var([_:_|Rest]) :-
	reinstate_var(Rest).		%continue w/ list

%
% check if the given CIF forms a connected graph
% with generate/2 representing nodes while generate/5 the edges
%
connected_graph(Cif) :-
	cif_util:filter_generate2(Cif,Nodes,Edges),	%extract all generate/2 as nodes
	check_nodes(Nodes,Edges).

%
% for all nodes, check if they are linked by some edges
%
check_nodes([],_).

check_nodes([G|Gs],Edges) :-
	G=generate(Class,Var),				%get var from node
	member(Edge,Edges),				%get an edge
	cif_util:extract_var_with_type(Edge,Types),	%get vars w/ type from this "edge"
	member(Var:Class,Types),			%and var is there
	check_nodes(Gs,Edges).				%proceed w/ remaining nodes




%
% cif_with_var/4
%
% split a CIF into 2 parts
%
% cif_with_var(+Vars,+Cif,-About,-Remain)
%
% Vars		=	list of Daplex vars
% Cif		=	the CIF to split
% About		=	the subset in 'Cif' that deals w/ vars directly
% Remain	=	the remaining 'Cif' which doesn't deal with vars directly
%
%

%
% with CIF is a list
%

cif_with_var(_,[],[],[]).				%end of CIF

cif_with_var(Var,[C|Cs],About,Remain) :-
	(	Var=C;					%C is a daplex var
		member(C,Var)				%Var is a list w/ C in there
	),
	!,
	cif_with_var(Var,Cs,As,Remain),			%proceed w/ tail
	About=[C|As].

cif_with_var(Var,[C|Cs],About,Remain) :-
	C =.. [_|Args],					%get args
	(	(	is_daplex_variable:is_daplex_variable(Var),		%Var is a Daplex var
			member(Var,Args)		%and is 1 of the args
		);
		(	member(X,Var),			%1 var in the list of Var
			member(X,Args)			%is 1 of the args
		);
		(	member(A,Args),			%or a 1 of the args is a term
			(	cif_with_var(Var,A,[_|_],_);	%which is concerning Var
				cif_with_var(Var,A,A,_)	%which is concerning Var
			)
		)
	),
	!,
	cif_with_var(Var,Cs,As,Remain),			%continue w/ the rest of the CIF list
	About=[C|As].

cif_with_var(Var,[C|Cs],About,[C|Remain]) :-
	!,
	cif_with_var(Var,Cs,About,Remain).		%nothing about var in C, continue w/ the list

%
% when CIF is a construct
%
cif_with_var(Var,Cif,Cif,[]) :-
	is_daplex_variable:is_daplex_variable(Cif),				%Cif is a Daplex var
	!,
	(	Var=Cif;				%which is equal to Var
		member(Cif,Var)				%or 1 of Var
	).

cif_with_var(Var,Cif,Cif,[]) :-
	Cif =.. [_|Args],				%get args
	(	(	is_daplex_variable:is_daplex_variable(Var),		%Var is a Daplex var
			member(Var,Args)		%and is 1 of the args
		);
		(	member(X,Var),			%1 var in the Var list
			is_daplex_variable:is_daplex_variable(X),		%is a Daplex var
			member(X,Args)			%which is 1 of the args
		);
		(	member(A,Args),			%an arg
			(	cif_with_var(Var,A,[_|_],_);	%is involved w/ Var
				cif_with_var(Var,A,A,_)	%is involved w/ Var
			)
		)
	).



/*
%
% cif_about_var/4
%
% split a CIF into 2 parts
%
% similar to cif_with_var/4 but take care of the
% chain-reaction-like relationship among vars
%
% 1st, we scan through the CIF and mark related vars in groups
% then we split the CIF into 2 parts accordingly
%
cif_about_var(Var,Cif,About,Remain) :-
	is_daplex_variable:is_daplex_variable(Var),			%Var is a single daplex var
	!,
	cif_about_var([Var],Cif,About,Remain).

cif_about_var(Vars,Cif,About,Remain) :-
	find_related_vars(Vars,Cif,Related_vars),	%find all related vars
	cif_with_var(Related_vars,Cif,About,Remain).	%then use cif_with_var/4
*/

%
% given a var/list of vars and a CIF
% find the list of related vars
%
find_related_vars(Var,Cif,Related_vars) :-
	build_vars_relationship(Cif,Relationship),	%build relationship among vars
	mark_vars_relationship(Var,Relationship),	%now mark those related to vars we want
	find_related_vars(Relationship,Related_vars).


find_related_vars([],[]).

find_related_vars([_:Status|Rest],Related) :-
	var(Status),
	!,
	find_related_vars(Rest,Related).

find_related_vars([Var:related|Rest],[Var|Related]) :-
	!,
	find_related_vars(Rest,Related).

find_related_vars([_:_|Rest],Related) :-
	format("WARNING: unexpected value of var status in find_related_vars/2~n",[]),
	find_related_vars(Rest,Related).


%
% scan through the list of vars and mark those related
%
mark_vars_relationship(Var,Relationship) :-
	is_daplex_variable:is_daplex_variable(Var),			%a single var
	member(Var:Status,Relationship),	%that appears in the relationship list
	!,
	Status=related.				%now they are related

mark_vars_relationship(Var,_) :-
	is_daplex_variable:is_daplex_variable(Var),			%a single var
	!.					%not found in the list, just forget it

mark_vars_relationship([],_).			%end of var list

mark_vars_relationship([V|Vs],Relationship) :-
	member(V:related,Relationship),		%a list of var, and it is found in the relationship list
	!,
	mark_vars_relationship(Vs,Relationship).

mark_vars_relationship([_|Vs],Relationship) :-
	mark_vars_relationship(Vs,Relationship).	%1st var not found, just proceed


%
% build up relationship among vars
%
build_vars_relationship(Cif,Relationship) :-
	build_vars_relationship(Cif,[],Relationship).

%
% for a list
%
build_vars_relationship([],Old,Old) :-			%end of CIF
	!.

build_vars_relationship([C|Cs],Old,New) :-
	!,
	build_vars_relationship(C,Old,Temp),		%work on the head
	build_vars_relationship(Cs,Temp,New).		%then proceed w/ the tail

%
% for an individual construct
%
build_vars_relationship(C,Old,New) :-
	get_vars_in_construct(C,Vars_in_c),		%find all vars in C
	build_common_relationship(Vars_in_c,_,Common),
%	Goal=(Relation=X:_Status,member(X,Vars_in_c)),	%they are all related
%	findall(Relation,call(Goal),Relationships),	%now they share the same relationship status
	my_union(Old,Common,New).		%more relationships added

build_common_relationship([],_,[]).
build_common_relationship([V|Vs],Status,[V:Status|Rest]) :-
	build_common_relationship(Vs,Status,Rest).




%
% find all vars in a construct
%
get_vars_in_construct(C,Vars) :-
	find_vars(C,Vars).				%we can use the more general find_vars/2 to do it









%
% gives a logical OR of the fusion states
%
states_or(States,preserved) :-
	member(preserved,States),		%if there is any 'preserved' there, info. is preserved
	!.

states_or(_,lost).				%otherwise it is lost


%
% printing a list
%
print_list([]).
print_list([H|T]) :-
	write(H),
	nl,
	print_list(T).

%
% print a list of matches
%
print_matches([]).
print_matches([M|Ms]) :-
	print_match(M),
	print_matches(Ms).

print_match(M) :-
	M=match(Map,_,_,_),
	write(Map),
	nl.


%
% print a list of groups
%
print_groups([]).
print_groups([G|Gs]) :-
	print_groups(G),
	print_groups(Gs).
print_groups(G) :-
	G=group(_,Cif),
	print_cif(Cif),
	nl.



%-----------------------------------------------
%
% refresh_vars_in_group/3
%
% given the unifying links, replace all vars
% so that unifying vars will have the same name
%
% refresh_vars_in_group(+Groups,+Links,-Refreshed)
%
% Groups	=	list of groups in group/2 format
% Links		=	list of unifying links in daplex_var:prolog_var format
% Refreshed	=	list of refreshed groups in group/2 format
%
%-----------------------------------------------

%
% an empty list, no need to refresh
%
refresh_vars_in_group([],_,[]).

%
% create a replacement list from Links
% then refresh by var replacement
%
refresh_vars_in_group(Groups,Links,Refreshed) :-
	make_replacement_list(Links,Replacement),		%from the unifying links, create a replacement list
	refresh_vars_in_group2(Groups,Replacement,Refreshed).	%refresh all vars with the replacement list

%
% refresh all vars by replacement
%
refresh_vars_in_group2([],_,[]).				%end of group list

refresh_vars_in_group2([G|Gs],Replacement,Refreshed) :-
	G=group(_,Cif),						%get CIF in group G
	replace_var_in_cif(Replacement,Cif,Refreshed_cif),	%replace vars in CIF
	find_vars(Refreshed_cif,New_vars),			%get new vars in Refreshed_cif
	Refreshed_g=group(New_vars,Refreshed_cif),		%the refreshed G
	refresh_vars_in_group2(Gs,Replacement,Refreshed_gs),	%work on the rest of list
	Refreshed=[Refreshed_g|Refreshed_gs].			%the new list



%
% from the "links", create a replacement list
%
make_replacement_list(Links,Replacement) :-
	reset_daplex_counter,					%reset counter to 1
	make_replacement_list2(Links,Replacement).		%start making the list


make_replacement_list2([],[]).					%end of links

make_replacement_list2([Daplex:Prolog|Rest],[Daplex:Prolog|New_rest]) :-
	var(Prolog),						%the Prolog var is not instantiated yet
	!,
	generate_daplex_variable(Prolog),			%create a new Daplex var for it
	make_replacement_list2(Rest,New_rest).			%go on with the list

make_replacement_list2([X|Rest],[X|New_rest]) :-
	make_replacement_list2(Rest,New_rest).			%the Prolog var in instantiated, go on


same_set(A,B) :-
	my_subset(A,B),
	my_subset(B,A).

