:- module(cif_util,[	find_var_types/2,			%find all vars in CIF with types
			find_vars/2,				%find all vars in CIF
			replace_var_in_cif/3,			%replace vars in CIF
			initialize_counter/1,			%create & init a counter from 1
			initialize_counter/2,			%init counter from a certain no.
			clear_counter/1,			%remove a counter
			generate_counter/2,			%get counter value & increment it
			generate_counter/3,			%get counter value & increment it with prefix
			generate_daplex_variable/1,		%generate a daplex var
			generate_daplex_variable/2,		%generate a daplex var, with prefix
			reset_daplex_counter/0,
			is_skolem/1,				%check for skolem constant/function
			is_skolem_constant/1,
			is_skolem_function/1,
			is_daplex_var/1,
			find_generator/3,
			extract_generator/4,
			create_template/3,			%create template from CIF
			append_cif/3,
			my_union/3,
			refresh_vars/2,				%refresh all var names
			fill_in_implicit_generator/2,		%fill in implicit generators
			my_intersect/5				%find intersection of 2 lists
		]).
:- use_module(library(lists)).

:- dynamic(counter/2).



%---------------------
% find all vars in CIF
%---------------------

find_vars(Cif,Vars) :-
	find_var_types(Cif,[],Types),
	findall(X,member(X:_,Types),Vars).


%---------------------------------------
% given a CIF construct or a list of CIF
% find all vars w/ types
%---------------------------------------
find_var_types(Cif,Types) :-
	find_var_types(Cif,[],Types).			%start with an empty list of types

%
% end of CIF list
%
find_var_types([],Bindings,Bindings) :-
	!.

%
% run through list of CIF
%
find_var_types([P|Ps],Old_bindings,New_bindings) :-
	!,
	extract_var_with_type(P,Vars_with_type),			%find var w/ types in a construct
	add_var_with_type(Vars_with_type,Old_bindings,Temp_bindings),	%combine with existing one
	find_var_types(Ps,Temp_bindings,New_bindings).			%proceed with the rest

%
% a single CIF construct
%
find_var_types(Cif,Old_bindings,Bindings) :-
	extract_var_with_type(Cif,Vars_with_type),			%find var w/ types in a construct
	add_var_with_type(Vars_with_type,Old_bindings,Bindings).		%combine with existing one


%
% generate/2
%
extract_var_with_type(P,Filtered) :-
	P=generate(Class,Var),
	!,
	Vars_with_type=[Var:Class],
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% generate/3
%
extract_var_with_type(P,Filtered) :-
	P=generate(Class,_,Var),
	!,
	Vars_with_type=[Var:Class],
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% generate/5
%
extract_var_with_type(P,Filtered) :-
	P=generate(_,Arg_types,Args,Class,Var),		%a function call
	!,
	findall(X,(	nth0(N,Arg_types,Type),		%find list of args w/ type
			nth0(N,Args,Arg),
			X=Arg:Type
			),
		Args_with_type),
	Vars_with_type=[Var:Class|Args_with_type],	%the overall list
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% restrict/4
%
% *** Note: restrict/4 is removed in CIF
%
extract_var_with_type(P,[]) :-
	P=restrict(_,_,_,_),
	!,
	write('ERROR: restrict/4 is removed in CIF'),
	nl,
	fail.


%
% relative/3
%
extract_var_with_type(P,Filtered) :-
	P=relative(Class,Instance,Var),
	!,
	Vars_with_type=[Instance:_,Var:Class],
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% expression/3
%
extract_var_with_type(P,Filtered) :-
	P=expression(Gen,Req,Pattern),
	!,
	findall(X,(	member(V,[Gen|Req]),
			X=V:_
			),
		Bindings_1),
	extract_var_with_type(Pattern,Bindings_2),
	append(Bindings_1,Bindings_2,Vars_with_type),
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% expr/1
%
extract_var_with_type(P,Filtered) :-
	P=expr(Var),
	!,
	Vars_with_type=[Var:_],
	filter_non_daplex_var(Vars_with_type,Filtered).


%
% expr/3 w/ op '='
%
extract_var_with_type(P,Filtered) :-
	P=expr(=,V1,V2),
	!,
	Vars_with_type=[V1:Class,V2:Class],
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% expr/3 w/ other operators
%
extract_var_with_type(P,Filtered) :-
	P=expr(_,V1,V2),
	!,
	Vars_with_type=[V1:_,V2:_],
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% int_set/3
%
extract_var_with_type(P,Filtered) :-
	P=int_set(_,_,Var),
	!,
	Vars_with_type=[Var:integer],
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% expression/4
%
extract_var_with_type(P,Filtered) :-
	P=expression(Gen,Req,_,Set),
	!,
	findall(X,(	member(V,[Gen|Req]),
			X=V:_
			),
		Bindings_1),
	find_var_types(Set,Bindings_2),			%find vars in the set-code
	append(Bindings_1,Bindings_2,Vars_with_type),	%join them together
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% restrict_subquery/3
%
extract_var_with_type(P,Filtered) :-
	P=restrict_subquery(Quantifier,Set_cif,Pred_cif),
	!,
	(	(	Quantifier =.. [Functor,Var],
			member(Functor,[all,some,no]),
			Bindings_1=[Var:_]
		);
		(	Quantifier =.. [Functor,Var,Num],
			integer(Num),
			member(Functor,[least,most,exactly]),
			Bindings_1=[Var:_]
		)
	),
	find_var_types(Set_cif,Bindings_2),
	find_var_types(Pred_cif,Bindings_3),
	append(Bindings_1,Bindings_2,Temp),
	append(Temp,Bindings_3,Vars_with_type),
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% restrict_subquery/4 (extended CIF)
%
extract_var_with_type(P,Filtered) :-
	P=restrict_subquery(All,Some,Set,Pred),
	!,
	All=all(Us),
	findall(X,(	member(U,Us),
			X=U:_),
		Bindings_1),
	Some=some(Es),
	findall(Y,(	member(E,Es),
			Y=E:_),
		Bindings_2),
	find_var_types(Set,Bindings_3),
	find_var_types(Pred,Bindings_4),
	append(Bindings_1,Bindings_2,Temp1),
	append(Temp1,Bindings_3,Temp2),
	append(Temp2,Bindings_4,Vars_with_type),
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% restrict_subquery/2 (extended CIF)
%
extract_var_with_type(P,Filtered) :-
	P=restrict_subquery(Quantifier,Pred_cif),
	!,
	(	(	Quantifier =.. [Functor,Vars],
			member(Functor,[all,some,no]),
			findall(X,	(member(V,Vars),
					X=V:_),
				Bindings_1)
		);
		(	Quantifier =.. [Functor,Vars,Num],
			integer(Num),
			member(Functor,[least,most,exactly]),
			findall(X,	(member(V,Vars),
					X=V:_),
				Bindings_1)
		)
	),
	find_var_types(Pred_cif,Bindings_2),
	append(Bindings_1,Bindings_2,Vars_with_type),
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% generate_subquery/5
%
extract_var_with_type(P,Filtered) :-
	P=generate_subquery(Type,Var,Sub,Aux1,Aux2),
	!,
	Bindings_1=[Var:Type],
	find_var_types(Sub,Bindings_sq),
	find_var_types(Aux1,Bindings_a1),
	find_var_types(Aux2,Bindings_a2),
	flatten([Bindings_1,Bindings_sq,Bindings_a1,Bindings_a2],Vars_with_type),
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% the/1
%
extract_var_with_type(P,Filtered) :-
	P=the(Code),
	!,
	find_var_types(Code,Vars_with_type),
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% any/3
%
extract_var_with_type(P,Filtered) :-
	P=any(Card,Set,Var),
	!,
	find_var_types(Card,Bindings_1),
	find_var_types(Set,Bindings_2),
	flatten([[Var:_],Bindings_1,Bindings_2],Vars_with_type),
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% set/2
%
extract_var_with_type(P,Filtered) :-
	P=set(Var,Set),
	!,
	find_var_types(Set,Bindings_1),
	Vars_with_type=[Var:_|Bindings_1],
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% logical_or/2 or logical_and/2
%
extract_var_with_type(P,Filtered) :-
	(	P=logical_or(Lhs,Rhs);
		P=logical_and(Lhs,Rhs)
	),
	!,
	find_var_types(Lhs,Bindings_1),
	find_var_types(Rhs,Bindings_2),
	append(Bindings_1,Bindings_2,Vars_with_type),
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% logical_or/1 or logical_and/1 (extended CIF)
%
extract_var_with_type(P,Filtered) :-
	(	P=logical_or(Cifs);
		P=logical_and(Cifs)
	),
	!,
	find_var_types(Cifs,Filtered).



%
% logical_not/1
%
extract_var_with_type(P,Filtered) :-
	P=logical_not(Code),
	!,
	find_var_types(Code,Vars_with_type),
	filter_non_daplex_var(Vars_with_type,Filtered).

%
% all other patterns
%
extract_var_with_type(P,Vars) :-
	marker,
	format("WARNING: non-Icode construct~n",[]),
	P =.. [_|Args],
	findall(X:_,(	X=var(_),
			member(X,Args)
		),
		Vars).

/*
extract_var_with_type(_,[]).
*/


%
% add a var:class pair (or a list of pairs)
% into the var:class binding list
% avoiding duplicate
%

%
% a list of pairs
%
add_var_with_type([],Old,Old) :-
	!.

add_var_with_type([B|Bs],Old,New) :-
	!,
	add_var_with_type(B,Old,Temp),
	add_var_with_type(Bs,Temp,New).

%
% a single pair
%
add_var_with_type(Var:Class,Old,Old) :-
	member(Var:Class,Old),		%var w/ class already in list
	!.				%ok

add_var_with_type(Var:_,Old,Old) :-
	member(Var:_,Old),		%var in list
	!,
	fail.				%but class doesn't match

add_var_with_type(Var:Class,Old,New) :-
	New=[Var:Class|Old],
	!.


%
% given a list of variable replacement in the form From:To
% replace variables in a CIF
%
replace_var_in_cif([],Cif,Cif) :-				%no replacement at all
	!.

replace_var_in_cif(Replacements,Old_cif,New_cif) :-
	is_list(Old_cif),					%if CIF is a list
	!,
	replace_var_in_list(Replacements,Old_cif,New_cif).	%proceed with list

replace_var_in_cif(Replacements,Old_cif,New_cif) :-
	replace_var_in_list(Replacements,[Old_cif],[New_cif]).	%CIF is not a list, just a construct


replace_var_in_list(_,[],[]).					%end of CIF list

replace_var_in_list(Replacements,[From|Rest],[To|New_rest]) :-
	member(From:To,Replacements),				%1st element is in replacement list
	!,
	replace_var_in_list(Replacements,Rest,New_rest).	%proceed with the rest

replace_var_in_list(Replacements,[Head|Rest],[New_head|New_rest]) :-
	is_list(Head),						%1st element is a list
	!,
	replace_var_in_cif(Replacements,Head,New_head),		%recursively work on 1st element
	replace_var_in_list(Replacements,Rest,New_rest).	%and rest of list

replace_var_in_list(Replacements,[Head|Rest],[Head|New_rest]) :-
	functor(Head,_,0),					%1st element is an atom
	!,
	replace_var_in_list(Replacements,Rest,New_rest).	%proceed with list

replace_var_in_list(Replacements,[Term|Rest],[New_term|New_rest]) :-
	Term =.. List,						%1st element is a term
	replace_var_in_list(Replacements,List,New_list),	%work on all arguments
	New_term =.. New_list,
	!,
	replace_var_in_list(Replacements,Rest,New_rest).	%proceed with list


%
% in a X:Type binding list,
% filter out those non-Daplex variables
%
filter_non_daplex_var([],[]).

filter_non_daplex_var([X:Type|Rest],[X:Type|Filtered_rest]) :-
	is_daplex_var(X),
	!,
	filter_non_daplex_var(Rest,Filtered_rest).

filter_non_daplex_var([X:Type|Rest],[X:Type|Filtered_rest]) :-
	is_skolem(X),
	!,
	filter_non_daplex_var(Rest,Filtered_rest).

filter_non_daplex_var([_|Rest],Filtered_rest) :-
	filter_non_daplex_var(Rest,Filtered_rest).



%
% general purpose counter management
%

initialize_counter(Counter) :-
	retractall(counter(Counter,_)),			%retract existing value
	!,
	asserta(counter(Counter,1)).			%and set it to 1

initialize_counter(Counter) :-
	asserta(counter(Counter,1)).			%if no current value exists, just set it

initialize_counter(Counter,Count) :-
	retractall(counter(Counter,_)),			%retract existing value
	!,
	asserta(counter(Counter,Count)).		%and set it to the value specified

initalize_count(Counter,Count) :-
	asserta(counter(Counter,Count)).		%if no current value exists

%
% remove a counter
%
clear_counter(Counter) :-
	retractall(counter(Counter,_)).



%
% get the value of a counter and advances it
%
generate_counter(Counter,Count) :-
	retract(counter(Counter,Count)),		%retract old one
	!,
	Next is Count+1,				%increment it
	asserta(counter(Counter,Next)).			%and save for next use

generate_counter(Counter,Count) :-
	initialize_counter(Counter),			%no value exist, just create a new one
	generate_counter(Counter,Count).		%and get value

%
% return a counter with prefix
%
generate_counter(Counter,Prefix,Count_with_prefix) :-
	generate_counter(Counter,Count),
	name(Prefix,Prefix_string),
	name(Count,Count_string),
	append(Prefix_string,Count_string,String),
	name(Count_with_prefix,String).

%
% generate a Daplex variable
%
generate_daplex_variable(X) :-
	generate_counter(daplex,Count),			%get counter for daplex
	X=var(Count).

%
% generate a Daplex variable w/ prefix
%
generate_daplex_variable(Prefix,X) :-
	generate_counter(daplex,Count),
	name(Prefix,Prefix_string),
	name(Count,Count_string),
	append(Prefix_string,Count_string,String),
	name(Count_with_prefix,String),
	X=var(Count_with_prefix).


reset_daplex_counter :-
	initialize_counter(daplex).			%initialize it


%
% check for skolem/constant/function
%
is_skolem(X) :-
	is_skolem_constant(X).

is_skolem(X) :-
	is_skolem_function(X).

is_skolem_constant(skolem(_)).
is_skolem_function(skolem(_,_)).


%
% check for daplex var
%
is_daplex_var(var(X)) :-
	is_list(X),
	!,
	fail.

is_daplex_var(var(X)) :-
	integer(X).

is_daplex_var(var(X)) :-
	atom(X).


%
% create a CIF template by replacing all Daplex
% variables by Prolog variables
%
create_template(Cif,Template,Replacements) :-
	find_var_types(Cif,Vtypes),
	findall(X,(	member(Var:_,Vtypes),
			X=Var:_),
		Replacements),
	replace_var_in_cif(Replacements,Cif,Template),
	!.


%----------------------------------------------
% find_generator/3
%
% given a list of generators, find the relevant
% one for a particular variable
%
%----------------------------------------------
find_generator(_,[],[]).

find_generator(Var,[C|Cs],[C|Gens]) :-
	C=generate(_,Var),
	find_generator(Var,Cs,Gens).

find_generator(Var,[C|Cs],[C|Gens]) :-
	C=generate(_,_,_,_,Var),
	find_generator(Var,Cs,Gens).

%
% cater for a list of vars
%
find_generator(Vars,[C|Cs],[C|Gens]) :-
	C=generate(_,V),
	member(V,Vars),
	find_generator(Vars,Cs,Gens).

find_generator(Vars,[C|Cs],[C|Gens]) :-
	C=generate(_,_,_,_,V),
	member(V,Vars),
	find_generator(Vars,Cs,Gens).

find_generator(Vars,[_|Cs],Gens) :-
	find_generator(Vars,Cs,Gens).


%
% find generator but also remove them from original list
%

extract_generator(_,[],[],[]).				%end of input list

extract_generator(Var,[C|Cs],Gen,Leftover) :-
	C=generate(_,Var),				%var matches generator/2
	extract_generator(Var,Cs,G,Leftover),
	!,
	(	(	member(C,G),
			Gen=G
		);
		Gen=[C|G]
	).

extract_generator(Var,[C|Cs],Gen,Leftover) :-
	C=generate(_,_,_,_,Var),
	extract_generator(Var,Cs,G,Leftover),
	!,
	(	(	member(C,G),
			Gen=G
		);
		Gen=[C|G]
	).

extract_generator(Vars,[C|Cs],Gen,Leftover) :-
	C=generate(_,V),				%var matches generator/2
	member(V,Vars),
	extract_generator(Vars,Cs,G,Leftover),
	!,
	(	(	member(C,G),
			Gen=G
		);
		Gen=[C|G]
	).

extract_generator(Vars,[C|Cs],Gen,Leftover) :-
	C=generate(_,_,_,_,V),
	member(V,Vars),
	extract_generator(Vars,Cs,G,Leftover),
	!,
	(	(	member(C,G),
			Gen=G
		);
		Gen=[C|G]
	).

extract_generator(Var,[C|Cs],Gen,[C|Leftover]) :-	%C doesn't match, it's a leftover
	extract_generator(Var,Cs,Gen,Leftover).


%--------------------------------
% append 2 cif/construct together
%--------------------------------
append_cif(C1,C2,Cif) :-
	my_union(C1,C2,Cif).


%
% a union/3 that works with list/single element
%

my_union(X,Y,Z) :-
	is_list(X),
	is_list(Y),
	!,
	union(X,Y,Z).
my_union(X,Y,Z) :-
	is_list(Y),
	!,
	union([X],Y,Z).
my_union(X,Y,Z) :-
	is_list(X),
	!,
	union(X,[Y],Z).
my_union(X,Y,Z) :-
	union([X],[Y],Z).


%
% normal union/3
%
union([],X,X).
union([H|T],X,Z) :-
	member(H,X),
	!,
	union(T,X,Z).
union([H|T],X,Z) :-
	union(T,[H|X],Z).

%
% change all variable names
%
refresh_vars(Cif,Refreshed) :-
	find_var_types(Cif,Types),
	findall(X,	(	member(Old_name:_,Types),
				generate_daplex_variable(New_name),
				X=Old_name:New_name
			),
		Replacement),
	replace_var_in_cif(Replacement,Cif,Refreshed).



%------------------------------------------------------
% fill in implicit generators at the appropriate places
%------------------------------------------------------
/*
%
% fill_implicit/2
%

fill_implicit(Cif,Filled) :-
	find_var_types(Cif,Types),			%find all var types
	fill_implicit(Cif,Types,Filled).		%then start


%
% fill_implicit/3
% the main predicate for filling in implicit generators
%

fill_implicit([],_,[]) :-
	!.					%end of list

fill_implicit([C|Cs],Types,Filled) :-
	!,
	fill_implicit(C,Types,F),			%work on every element in the list
	fill_implicit(Cs,Types,Fs),
	append_cif(F,Fs,Filled).


fill_implicit(C,Types,Filled) :-
	find_and_fill_implicit(C,Types,New_c,Needed),
	generate_implicit(Needed,Gens),
	append_cif(New_c,Gens,Filled).

%
% if you have a list, just summarize their "needs"
%
find_and_fill_implicit([],_,[],[]) :-
	!.

find_and_fill_implicit([C|Cs],Types,New,Needed) :-
	!,
	find_and_fill_implicit(C,Types,New_c,C_needed),
	find_and_fill_implicit(Cs,Types,New_cs,Cs_needed),
	append_cif(New_c,New_cs,New),
	my_union(C_needed,Cs_needed,Needed).



%
% generate/2
%
% no change & no need
%
find_and_fill_implicit(C,Types,C,[]) :-
	C=generate(Class,Var),
	member(Var:Class,Types),
	!.

find_and_fill_implicit(C,_,C,[]) :-
	C=generate(_,_),
	format("WARNING: find_and_fill_implicit/4 generate/2 unmatch var-type~n",[]).

%
% generate/5
%
% no change to C but has a need
%
find_and_fill_implicit(C,Types,C,[Var:Class]) :-
	C=generate(_,_,_,Class,Var),
	member(Var:Class,Types),
	!.

find_and_fill_implicit(C,_,C,[]) :-
	C=generate(_,_,_,_,_),
	!,
	format("WARNING: find_and_fill_implicit/4 generate/5 unmatch var-type~n",[]).

%
% restrict_subquery/3
%
% may change G & P but no need
%
find_and_fill_implicit(C,Types,Filled,[]) :-
	C=restrict_subquery(Q,G,P),
	!,
	find_and_fill_implicit(G,Types,New_g,G_needed),
	find_and_fill_implicit(P,Types,New_p,P_needed),
	generate_implicit(G_needed,G_gens),
	generate_implicit(P_needed,P_gens),
	append_cif(New_g,G_gens,Temp_g),
	append_cif(Temp_g,P_gens,Final_g),
	Filled=restrict_subquery(Q,Final_g,New_p).

%
% all others
%
find_and_fill_implicit(C,Types,Filled,Needed) :-
	C =.. [Functor|Args],
	find_and_fill_implicit(Args,Types,Filled_args,Needed),
	Filled =.. [Functor|Filled_args].


%----------------------------------------------------
% given a list of Var:Type, generate those generate/2
%----------------------------------------------------

generate_implicit([],[]).

generate_implicit([Var:Type|Rest],[generate(Type,Var)|Gs]) :-
	generate_implicit(Rest,Gs).

*/

%------------------------------------------
% scan a CIF and fill in missing generate/2
%------------------------------------------



fill_in_implicit_generator(Cif,Filled) :-
	find_var_types(Cif,Types),				%find all vars w/ types
	fill_in_implicit_generator(Cif,Types,Filled).		%fill in missing generators

fill_in_implicit_generator([],_,[]) :-
	!.

fill_in_implicit_generator([C|Cs],Types,Filled) :-
	fill_in_implicit_generator(C,Types,Filled_c),		%handle the head
	fill_in_implicit_generator(Cs,Types,Filled_cs),		%then the tail
	append_cif(Filled_c,Filled_cs,Filled),			%append them together
	!.

%
% handling individual CIF construct
%

%
% generate/2
%
fill_in_implicit_generator(C,Types,C) :-
	C=generate(Class,Var),
	member(Var:Class,Types),		%appear in the var-type list
	!.

fill_in_implicit_generator(C,_,C) :-
	C=generate(_,_),
	format("WARNING: generate/2 does not match var-type list.~n",[]),	%cannot find it in var-type list
	!.

%
% generate/5
%
fill_in_implicit_generator(C,Types,Filled) :-
	C=generate(_,_,_,Class,Var),				%a generate/5
	member(Var:Class,Types),				%find it in the var-type list
	!,
	Filled=[generate(Class,Var),C].				%fill int the missing generate/2

fill_in_implicit_generator(C,_,C) :-
	C=generate(_,_,_,_,_),					%a generate/5
	format("WARNING: generate/5 does not match var-type list.~n",[]),
	!.

%
% restrict_subquery/3
%
fill_in_implicit_generator(C,Types,Filled) :-
	C=restrict_subquery(Q,G,P),
	fill_in_implicit_generator(G,Types,Filled_g),			%recursively work on G
	fill_in_implicit_generator(P,Types,Filled_p),			%and P
	Filled=restrict_subquery(Q,Filled_g,Filled_p).


fill_in_implicit_generator(C,_,C) :-
	functor(C,_,0),
	!.

%
% all other term
%
fill_in_implicit_generator(C,Types,Filled) :-
	C =.. [F|Args],
	fill_in_implicit_generator_in_args(Args,Types,Filled_args),
	Filled =.. [F|Filled_args],
	!.

fill_in_implicit_generator_in_args([],_,[]).
fill_in_implicit_generator_in_args([A|As],Types,[F|Fs]) :-
	fill_in_implicit_generator(A,Types,F),
	fill_in_implicit_generator_in_args(As,Types,Fs).

%
% my_intersect(List1,List2,L1_left,Match,L2_left)
%
% List1=	1st list
% List2=	2nd list
% L1_left=	remain part of L1
% Match=	matching part of the 2 lists
% L2_left=	remain part of L2
%
% match 2 lists against each other
% return the overlapping & non-overlapping part in both lists
%
my_intersect([],L,[],[],L) :-				%end of 1st list
	!.

my_intersect(L,[],L,[],[]) :-				%end of 2nd list
	!.

my_intersect([T|Ts],C,Left,[T|Match],Right) :-
	member(T,C),					%T matches something in C
	delete(C,T,C_rest),				%find the rest of C
	my_intersect(Ts,C_rest,Left,Match,Right).	%carry on

my_intersect([T|Ts],C,[T|Left],Match,Right) :-
	not(member(T,C)),
	my_intersect(Ts,C,Left,Match,Right).		%T doesn't match anything in C

