% ~~~~~~~~~~~~~~~~~~~~~~~~~~~
% OPERATIONS ON DEEP LISTS
% ~~~~~~~~~~~~~~~~~~~~~~~~~~~

% deepList(DL) returns true if DL is a deep list, and false otherwise.
deepList([]).
deepList([H|T]) :- atomic(H),deepList(T).

% depth(+DL,-N) binds N with the depth of deep list DL.
depth([],1). 
depth([[]|T],R) :- !,
                   depth(T,R1),
                   R is max(2,R1). 
depth([H|T],R)  :- atomic(H),!,
                   depth(T,R). 
depth([H|T],R) :-  depth(H,R1),
                   depth(T,R2),
                   R is max(R1+1,R2).

% flatten(+DL,-SL) binds SL to the shallow list produced 
% by flattening the deep list DL.
%
% This is a straightforward recursive implementation.
%
flatten([],[]).
flatten([[]|T],FL):-!,
                    flatten(T,FL).
flatten([H|T],[H|FL]):- 
                    atomic(H),!, 
                    flatten(T,FL).
flatten([H|T],FL):- flatten(H,FL1), 
                    flatten(T,FL2),
                    append(FL1,FL2,FL).

%% ~~~~~~~~~~~~~~~~~~~~~~~~~~~
%% TODO: implement heads, member1, member2
%% ~~~~~~~~~~~~~~~~~~~~~~~~~~~

% heads(+DL,L-).
heads([],[]).
heads([H|T],LH) :- compound(H),!,
    heads(H,LH1),
    heads1(T,LH2),
    append(LH1,LH2,LH).
heads([[]|T],LH) :- !,heads1(T,LH).
heads([H|T],[H|LH]):- heads1(T,LH).

% member1(?X,+DL).
member1(X,[X|_]).
member1(X,[H|_]) :- compound(H),member1(X,H).
member1(X,[_|T]):-member1(X,T).

% member2(?X,+DL).
member2(X,[H|_]) :-compound(H),member2(X,H).
member2(X,[[]|T]) :- !,member2(X,T).
member2(X,[X|_]) :- (atom(X);string(X);number(X)). 
member2(X,[_|T]) :- member2(X,T).

% ~~~~~~~~~~~~~~~~~~~~~~~~~~~
% OPERATIONS ON DIFFERENCE LISTS
% ~~~~~~~~~~~~~~~~~~~~~~~~~~~

% dAdd(+DL1,+DL2,-DL) binds DL to the difference list
% produced by appending the difference lists DL1 and DL2
%
% Remember that a difference list is dList(OL,H) where
% OL is an open list which ends with free variable H. 
% 
dAdd(dList(OL1,H1),dList(OL2,H2),dList(OL1,H2)):- H1=OL2.

% addToEnd(+DL,+E,-L) binds L to list produced by adding 
% element E at the end of the difference list DL
% 
addToEnd(dList(OL,H),E,OL):- H=[E].

% member_open(?X,+DL) holds if X is an element of the 
% difference list DL.
member_open(_,dList(OL,H)) :-
   unify_with_occurs_check(OL,H),!,fail.
member_open(X,dList([X|_],_)). 
member_open(X,dList([_|OL],H)) :-
   member_open(X,dList(OL,H)).

% go(+X,+Y,-Trail) finds a trail Trail from X to Y
% by depth-first search.
% Straightforward implementation with accumulators.

% initially, the only visited room is the initial room X 
go(X,Y,Trail) :- goAcc(X,Y,Trail,[X]).

% we move from X to Z if Z was not visited 
% and if there is a door from X to Z
goAcc(X,Y,Trail,Acc) :- 
   (door1(X,Z);door1(Z,X)),
   not(member(Z,Acc)),
   goAcc(Z,Y,Trail,[Z|Acc]).

% goV2(+X,+Y,-Trail) finds a trail Trail from X to Y
% by depth-first search.
% An more efficient implementation with difference lists.
goV2(X,Y,Trail) :- 
   goDiffList(X,Y,Trail,dList(H,H)).
goDiffList(Y,Y,Trail,DL) :- 
   addToEnd(DL,Y,Trail).
goDiffList(X,Y,Trail,DL):- 
   (door1(X,Z);door1(Z,X)), 
   not(member_open(Z,DL)), 
   dAdd(DL,dList([X|H],H),DL1), 
   goDiffList(Z,Y,Trail,DL1).

% goBF(+X,+Y,-Trail) finds a shorthest trail Trail from X to Y
% by breadth-first search.
%
goBF(X,Y,Trail) :- goBFAux([[X]],Y,R),reverse(R,Trail). 
goBFAux([[Y|Xs]|_],Y,[Y|Xs]):-!. 
goBFAux([[Lf|Xs]|Rs],Y,Trail):-
        findall([Z,Lf|Xs],
                ((door1(Lf,Z);door1(Z,Lf)),
                 not(member(Z,[Lf|Xs]))),
                ZRs),
        append(Rs,ZRs,NewRs), 
        goBFAux(NewRs,Y,Trail).

% inorder(+BT,-L) binds L to the list of integers produced
% by the traversal in inorder of the binary tree BT
%
inorder(BT,L) :- 
   dInorder(BT,dList(L,H)),
   H=[]. 
dInorder(nil,dList(H,H)). 
dInorder(bt(N,BT1,BT2),DL) :-
   dInorder(BT1,DL1), 
   dInorder(BT2,DL2), 
   dAdd(DL1,dList([N|H],H),DL3), 
   dAdd(DL3,DL2,DL).


%% ~~~~~~~~~~~~~~~~~~~~~~~~~~~
%% TODO: implement the predicates
%%   flattenV2(+DL,-SL)
%%   prerorder(+BT,-L) 
%%   postorder(+BT,-L) 
%% using difference lists

%% ~~~~~~~~~~~~~~~~~~~~~~~~~~~

% flattenV2(+DL,-SL) is the same as flatten(+DL,-SL), but
% implemented with difference lists
flattenV2(DL,SL) :- 
   flattenDiffList(DL,dList(SL,H)),
   H=[].
flattenDiffList([],dList(H,H)).
flattenDiffList([[]|T],DiffL) :- 
   flattenDiffList(T,DiffL).
flattenDiffList([H|T],DiffL) :- 
   compound(H),!,
   flattenDiffList(H,DiffL1),
   flattenDiffList(T,DiffL2),
   dAdd(DiffL1,DiffL2,DiffL).
flattenDiffList([X|T],DiffL) :-
   flattenDiffList(T,DiffL1),
   dAdd(dList([X|H],H),DiffL1,DiffL).



% preorder(+BT,-L)binds L to the list of integers produced
% by the traversal in preorder of the binary tree BT
preorder(BT,L) :- 
   dPreorder(BT,dList(L,H)),
   H=[]. 
dPreorder(nil,dList(H,H)). 
dPreorder(bt(N,BT1,BT2),DL) :-
   dPreorder(BT1,DL1), 
   dPreorder(BT2,DL2), 
   dAdd(dList([N|H],H),DL1,DL3), 
   dAdd(DL3,DL2,DL).

% postorder(+BT,-L)binds L to the list of integers produced
% by the traversal in postorder of the binary tree BT
postorder(BT,L) :- 
   dPostorder(BT,dList(L,H)),
   H=[]. 
dPostorder(nil,dList(H,H)). 
dPostorder(bt(N,BT1,BT2),DL) :-
   dPostorder(BT1,DL1), 
   dPostorder(BT2,DL2), 
   dAdd(dList(DL1,DL3,[N|H],H)), 
   dAdd(DL3,DL2,DL).
