:-use_module(library(sets)).
main(FileName,RS) :-
see(FileName),read(Deps),seen,unfold(Deps,FDs),
getAttr(FDs,R0),
splitAll(FDs,R0,RS),!.

% unfold finds all dependencies where one thing leads to two (or more) others,
% splitting that dependency into two (or more) dependencies
unfold([],[]).
% removing trivial cases i.e. A>>A
unfold([X>>X|Tail],New):- !,unfold(Tail,New).
% removing the trivial case [X,X,A]>>A. (The case [X,A,B]>>[A,B] unfolds into two of these cases)
unfold([Y>>X|Tail],New):- member(X,Y),!,unfold(Tail,New).
% biproduct of the row below, it might happen and if it does this predicate will catch it.
unfold( [_>>[] |Tail],New):- !, unfold(Tail,New).
% if splitting the dependecy works, then split it
unfold( [D>>[H2|Tail2] |Tail],Rest):- !, unfold([D>>H2, D>>Tail2 |Tail],Rest).
% otherwise, just add it as it is, assuming it's not splittable.
unfold([ (D >> H2)|Tail],[D>>H2|Rest]):-unfold(Tail, Rest).

% determines whether all elements in L1 are in L2
in([],_).
in([H1|T1],L2) :- member(H1,L2), in(T1,L2).

% returns the closure of X
% if X isn't a list and Y isn't a list
closure(X,FDs,S) :-member(Y>>Z,FDs), \+member(Z,X), Y=X, \+X=[_|_],closure([Z|[X]],FDs,S),!.
% closure(X,FDs,[Z|[X]]) :-member(Y>>Z,FDs), \+member(Z,X), Y=X, \+X=[_|_],!.
% if X is a list and Y isn't a list
closure(X,FDs,S) :-member(Y>>Z,FDs),\+member(Z,X), member(Y,X),closure([Z|X],FDs,S),!.
% if X is a list and Y is a list
closure(X,FDs,S):- member(Y>>Z,FDs), \+member(Z,X), in(Y,X),closure([Z|X],FDs,S),!.
closure(X,_,X).

% gets a list of closures written as functional dependencies
lClosures([],_,[]).
lClosures([H|T],FDs,Cl):- Cl = [H>>C|Crest],closure(H,FDs,C),lClosures(T,FDs,Crest).

% Cl must be a one to one FD list
proj(_,[],[]).
proj(R1,[X>>Y|Ct],FDs1):- member(X,R1),member(Y,R1),FDs1 = [X>>Y|P],!,proj(R1,Ct,P).
proj(R1,[_|Ct],FDs1):-!,proj(R1,Ct,FDs1).

% removes FD:s of the form a>>b b>>c a>>c where a>>c is unneccessary
% Initially Ref and the first argument are identical
purge([],_,[]).
% purge([X>>Y|T],Ref,FDs1):- member(X>>Z,Ref),member(Z>>Y,Ref),!,purge(T,Ref,FDs1) .
purge([X>>Y|T],Ref,FDs1):- leadsToInManySteps(X,Y,Ref),!,purge(T,Ref,FDs1) .
purge([H|T],Ref,FDs1):- FDs1 = [H|T2], purge(T,Ref,T2).

% wrapper for leadsTo. Finds out if X leads to Y in any case other than the trivial.
leadsToInManySteps(X,Y,Refs):-leadsTo(X,Y,Refs,[],N),N>1,!.
% checks whether X leads to Y e.g. X>>A, A>>B, B>>Y
% in at least ONE STEP
% Refs is a list of dependencies
% N is the number of steps to get to Y. N is at least 1
leadsTo(X,Y,Refs,_,1) :- member(X>>Y,Refs).
leadsTo(X,Y,Refs,Visited,N) :-write(Visited), \+member(X,Visited),member(X>>Z,Refs),V2 = [X|Visited],leadsTo(Z,Y,Refs,V2,N2),N is N2+1.

% the cases are one to one or many to one
getAttr([],[]).
% assuming that X is a list
getAttr([X>>Y|T],Attr):- X = [_|_] ,getAttr(T,A),union([Y|X],A,R),Attr = R .
getAttr([X>>Y|T],Attr):- getAttr(T,A),union([X,Y],A,R), Attr = R.

%checks if a given FD is a violation of the algorithm
violates(X>>_,FDs,R):- closure(X,FDs,C), \+subtract(R,C,[]).

split(FDs,R,R1,R2,S1,S2) :- member(X>>Y,FDs),violates(X>>Y,FDs,R),closure(X,FDs,R1),subtract(R,R1,R21),
(X=[_|_]->append(X,R21,R2);R2 = [X|R21]),
proj(R1,FDs,S1),proj(R2,FDs,S2).

splitAll(FDs,R,RS):- split(FDs,R,R1,R2,S1,S2),!,splitAll(S1,R1,RS1),splitAll(S2,R2,RS2),append(RS1,RS2,RS).
% if split didn't work, we're done.
splitAll(_,R,[R]).