:- use_module(library(lists)).
:- use_module(library(apply_macros)).


% call hypothesisSelection(startNode,FinalHypothesis)
% output is a candidate hypothesis which include the current node. This hypothesis is accompanied by its properties: DL-EITIs-H. H = sets of ClaID with their coverage. 
% why EITIs, rather than EIs -- that will make the scoring even easier? -- But when you calculate the intersection with current node, EITI will make it easy. -- that is why EIs is not included, because it will be changed after computing the intersection.

hypothesisSelection(CurrentNode,BestCandidate):-
	expandNode(CurrentNode,ChildNodes),
	extractEndNode(ChildNodes,EndNodeEITIs0,NonEndChildNodes),sort(EndNodeEITIs0,EndNodeEITIs), 
	maplist(hypothesisSelection,NonEndChildNodes,ReturnedCandidates), % if NonEndChildNodes=[], then--???
	(EndNodeEITIs0==[]->
		candidateSelection(ReturnedCandidates,CurrentNode,BestCandidate);
		candidateSelection([0-EndNodeEITIs-[]|ReturnedCandidates],CurrentNode,BestCandidate)).


expandNode(CurrentNode,ChildNodes):-
	findall(Child,connect(CurrentNode,Child),ChildNodes).

extractEndNode([],[],[]).
extractEndNode([ChildNode|ChildNodes],EndNodeCoverge,NonEndNode):-
	extractEndNode(ChildNodes,PreEndNodeCoverge,PreNonEndNode),
	(ChildNode=endNode-EI-TI ->
		EndNodeCoverge=[EI-TI|PreEndNodeCoverge], NonEndNode=PreNonEndNode;	
		EndNodeCoverge=PreEndNodeCoverge, NonEndNode=[ChildNode|PreNonEndNode]
	).
	

% The returned candidate include the current node, while the scoring doesn't: when combining, don't want to include the current node repeatedly.
% score, then sort, then combine -- start from the highest score
% group is done before scoring? there is scoring and sorting within each group 
% then another scoring and sorting for those chosen from the group.

candidateSelection(ReturnedCandidates,CurrentNode,DescriptionLength-EITIs-[CurrentNode-EITIs|NewCandidate]):-
	maplist(scoreCandidateBranches(CurrentNode),ReturnedCandidates,ScoredCandidates0),
	ScoredCandidates0=ScoredCandidates, %selectlist(nonNegativeScoreBranch,ScoredCandidates0,ScoredCandidates),	% filter out those nonZero branches first before combining
	sort(ScoredCandidates,SortedScoredCandidates), 
	combine_and_competing(SortedScoredCandidates,DescriptionLength0-EITIs-NewCandidate),
	claLength(CurrentNode,CurrentNodeDescriptionLength),
	DescriptionLength is DescriptionLength0+CurrentNodeDescriptionLength.
	

nonNegativeScoreBranch(Score-DL-EIs-EITIs-CandidateBranch):- Score>=0.

	
% coverage and description length (the currentNode is only used for obtaining the intersection of coverage)
scoreCandidateBranches(CurrentNode,CandidateDescriptionLength-EITIs-Candidate,Score-CandidateDescriptionLength-NewEITIs-EITIupdated_Candidate):-	
	claNode(CurrentNode,CurrendNodeEITIs),
	ord_intersection(EITIs,CurrendNodeEITIs,NewEITIs),
	exExtraction(NewEITIs,NewEIs), 	
	length(NewEIs,NewEINum),

	ord_subtract(EITIs,NewEITIs,OtherBranchEITIs),
	maplist(removeAlones(OtherBranchEITIs),Candidate,EITIupdated_Candidate),
	Score is NewEINum-CandidateDescriptionLength.



% Input is [1-1,1-2,2-1,2-2,2-3], then the output is [1,2] 
exExtraction([],[]).
exExtraction([EI-TI|Record],EIs):- 
	exExtraction(Record,PreEIs),
	(PreEIs=[EI|Rest] ->
		EIs=PreEIs;
		EIs=[EI|PreEIs]
	).

	
identifyComputingPart(EITIs,PreEITIs,CompetingEIs):-
		exExtraction(EITIs,EIs),
		exExtraction(PreEITIs,PreEIs),
		ord_intersection(EIs,PreEIs,CompetingEIs).



	% combining from the highest score. -- for the last one, which has highest score, just 
	% competing with each other for the same example.

% Combined Candidate is DescriptionLength-EICoverage-EITIs-NewCandidate

combine_and_competing([Score-DescriptionLength-CandidateEITIs-Candidate],DescriptionLength-CandidateEITIs-Candidate).
combine_and_competing([Score-DL-EITIs-Candidate|SortedScoredCandidates],NewDL-NewEITIs-NewCandidate):-
	combine_and_competing(SortedScoredCandidates,PreDL-PreEITIs-PreCandidate),	
	identifyComputingPart(EITIs,PreEITIs,CompetingEIs),
	(CompetingEIs=[] ->
		combineTwoRecordedCandidate(EITIs-Candidate,PreEITIs-PreCandidate,NewDL-NewEITIs-NewCandidate);
		powersets(CompetingEIs,Possibles),
		maplist(getCompensatedPair(CompetingEIs),Possibles,CompensatedPairs),
		maplist(combineTwoCompetingCandidates({Candidate,PreCandidate}),CompensatedPairs,ScoredPossibleCombinations),
		sort(ScoredPossibleCombinations,SortedScoredPossibleCombinations),
		SortedScoredPossibleCombinations=[NewDL-NewEITIs-NewCandidate|Rest] % choose the head:the one with lowest DL. 
	).



getCompensatedPair(TotalSet,Set,{Set,CompensatedSet}):-
	ord_subtract(TotalSet,Set,CompensatedSet).

% another function that take in such a pair -- produce a candidate -- re-score(remove-duplicate(be careful -- they may just have different EI_Coverage)->description length -- their EI coverage remains the same -- all is comparisons about description length )	
combineTwoCompetingCandidates({Candidate1,Candidate2},{EIs1,EIs2},NewDL-CombinedEITIs-CombinedCandidate):-
	isolation(Candidate1,EIs1,RemainEITIs1-RemainCandidate1), %OverlapEITIs-CandidateOverlapPart),
	isolation(Candidate2,EIs2,RemainEITIs2-RemainCandidate2),	
	combineTwoRecordedCandidate(RemainEITIs1-RemainCandidate1,RemainEITIs2-RemainCandidate2,NewDL-CombinedEITIs-CombinedCandidate).
	


% *** when you remove certain bits, the EITI coverage is changed! -- the EITI is not simply the isolation you have now


	
% suppose there is redundancy (DAG)	
combineTwoRecordedCandidate(EITIs-Candidate,PreEITIs-PreCandidate,NewDL-NewEITIs-NewCandidate):-
			ord_union(EITIs,PreEITIs,NewEITIs),
			combineTwoCandidate(Candidate,PreCandidate,NewCandidate), 
			descriptionLength(NewCandidate,NewDL).

combineTwoCandidate([],PreCandidate,PreCandidate).
combineTwoCandidate([ClaID-ClaEITIs|Candidate],PreCandidate,NewCandidateUpdated):-
	combineTwoCandidate(Candidate,PreCandidate,NewCandidate),
	(append(PreClas,[ClaID-ClaPreEITIs|AfterClas],NewCandidate) ->
		append(ClaEITIs,ClaPreEITIs,ClaNewEITIs),
		append(PreClas,[ClaID-ClaNewEITIs|AfterClas],NewCandidateUpdated);
		NewCandidateUpdated=[ClaID-ClaEITIs|NewCandidate]		
	).



	
	


isolation(Candidate,CompetingEIs,RemainEITIs-RemainCandidate_noRedundant):-
	clasSeparation(Candidate,CompetingEIs,RemainEITIs-RemainCandidate,OverlapEITIs-CandidateOverlapPart),
	maplist(removeAlones(OverlapEITIs),RemainCandidate,RemainCandidate_noRedundant).


% you can make this part more efficient, by doing ord_union at the end, rather than every time
clasSeparation([],CompetingEIs,[]-[],[]-[]).
clasSeparation([ClaID-ClaEITIs|Candidate],CompetingEIs,RemainEITIs-RemainCandidate,OverlapEITIs-CandidateOverlapPart):-
		clasSeparation(Candidate,CompetingEIs,PreRemainEITIs-PreRemainCandidate,PreOverlapEITIs-PreCandidateOverlapPart),
		exExtraction(ClaEITIs,ClaEIs),
		(ord_subset(ClaEIs,CompetingEIs)-> 	% if it has some parts not in CompetingEIs, then it shouldn't be removed
				RemainEITIs-RemainCandidate=PreRemainEITIs-PreRemainCandidate,
				ord_union(ClaEITIs,PreOverlapEITIs,OverlapEITIs),
				CandidateOverlapPart=[ClaID-ClaEITIs|PreCandidateOverlapPart];
				OverlapEITIs-CandidateOverlapPart=PreOverlapEITIs-PreCandidateOverlapPart,
				ord_union(ClaEITIs,PreRemainEITIs,RemainEITIs),
				RemainCandidate=[ClaID-ClaEITIs|PreRemainCandidate]
		).
	
removeAlones(AloneEITIs,ClaID-EITIs,ClaID-EITIsNoAlone):-
	%nl,write({EITIs,AloneEITIs}), write('check whether they are in order'),nl,
	ord_subtract(EITIs,AloneEITIs,EITIsNoAlone). % EITIs doesn't necessarily include everything in the AloneEITIs, but  



% if a subset, then remove that clause -- update the EITI in the rest of the clauses. 
% what if the remaining become uncompressed because -- no worry, it will be removed when new branch come. -- simply check whether the remaining still has coverage -- remove the one with single coverage -- long description: e.g. two computing components -- you can't simply remove that branch, maybe the rest still worth for that -- you are allowing the flexibility to decompose the module. % no worry, you can make the selection at this step more complicated later.


% selectlist(extractCompetingCla(CompetingEIs),) % no, it is better to isolate 
% for each claID, removing those belongs -- for the competing part, it doesn't necessarily always one branch, maybe a combination. 



descriptionLength([],0).
descriptionLength([ClaID-ClaEICoverage|Candidate],DescriptionLength):-
	descriptionLength(Candidate,PreDescriptionLength),
	%claInterprete(ClaID,Cla),length(Cla,ClaDescriptionLength), -- don't worry about translate them more than once, since there is no redundant node -- probably there is (due to the DAG)
	claLength(ClaID,ClaDescriptionLength),
	DescriptionLength is PreDescriptionLength+ClaDescriptionLength.