:- [task14part1].
	
% Adding a variable for the current path.
extractDiagnoses(HSTree,Diagnoses):-
	extractDiagnoses2(HSTree, Diagnoses, []).	

% Set path in set and end recursion when leaf had been reached
extractDiagnoses2(leaf, [PathEnd], PathEnd).
% Finished clearing empty node
extractDiagnoses2(node([], []), [], _). 
extractDiagnoses2(node([CsHead|CsTail], [CsHeadBranch|CsTailBranches]),
		DiagnosesSet, CurrentPath) :-
	% Add new visited conflict item to the visited path 
	append(CurrentPath, [CsHead], NewPath),
	% Recursively collects all paths from the recursive calls into the depth
	% and the width and puts them into the DiagnosesSet
	append(DepthPaths, WidthPaths, DiagnosesSet), 
	% Continues into the depth of the branch
	extractDiagnoses2(CsHeadBranch,DepthPaths,NewPath),
	% Calls on all conflict items in the width of the branch
	extractDiagnoses2(node(CsTail, CsTailBranches), WidthPaths, CurrentPath). 

% Computes length of smallest diagnosis
getLengthSmallestSet([Diagnosis], DiagnosisLength):-
	% Calls length single diagnosis
	length(Diagnosis,DiagnosisLength). 
getLengthSmallestSet([HeadDiagnosis|RestOfDiagnoses], Minimal):-
	% Recursively gets the length of tail.
	getLengthSmallestSet(RestOfDiagnoses, RestLength),
	% Initialises length of the head diagnosis.
	length(HeadDiagnosis,HeadLength),
	% Gets minimal length of diagnoses.
	Minimal is min(HeadLength, RestLength).

filterLength(X,Y):-
	length(Y, LengthY),
	%Checks if the set isn't bigger than the smallest set.
	X \== LengthY. 


getSubsetMinimalDiagnoses(DiagnosesSets, MinimalDiagnosesSets):- 
	%Gets the length of the smallest set to prune the diagnoses. 
	%Break so that there will be no backtracking if something goes wrong.
	getLengthSmallestSet(DiagnosesSets,Length),!,
	% Excludes sets that are bigger than the smallest set
	exclude(filterLength(Length), DiagnosesSets, MinimalDiagnosesSets).

% Function that returns minimal hitting sets from a problem.
subsetMinimalDiagnoses(SD, COMP, OBS, HsTree, DiagnosesSets, MinimalDiagnosesSets) :-
	% Generate hitting tree.
	generateHittingSetTree(SD, COMP, OBS, [], HsTree),
	write(HsTree),
	% Get diagnoses out of the hitting tree.
	extractDiagnoses(HsTree, DiagnosesSets),
	write(DiagnosesSets),
	% Determine smallest diagnoses.
	getSubsetMinimalDiagnoses(DiagnosesSets, MinimalDiagnosesSets).
