%%usage of testcases: simply typing in <name>(). and it should be true
%%testcases only show that one example works, you should create more of them for yourself!
%%So there is no guarantee that these testcases ensure that your implementation is correct!

%%==========Problem 1.1===============
%TODO: implement removeDuplicates(List,ListWithoutDuplicates)
delete([],_,[]).
delete([X],X,[]).
delete([Head|Tail],Head,Result):-
	delete(Tail,Head,Result).
delete([Head|Tail],X,[Head|Result]):-
	Head \= X,
	delete(Tail,X,Result).

removeDuplicates([],[]).
removeDuplicates([Head|Tail],[Head|Tail2]):-
	delete(Tail,Head,Result),
	removeDuplicates(Result,Tail2).

%testcase
testcase_remove():-
	removeDuplicates([1,1,1,1,2,2,3,4,1,2,7],[1, 2, 3, 4, 7]).
%--------------------------------------------------------------------
%TODO: implement myReverse(List,ReversedList)

append([],List2,List2).
append([Head|Tail],List2,[Head|Result]):-
	append(Tail,List2,Result).

myReverse([],[]).
myReverse([Head|Tail],ReversedList):-
	myReverse(Tail,TempList),
	append(TempList,[Head],ReversedList).

%testcase
testcase_reverse():-
	myReverse([1,2,3,4,5],[5,4,3,2,1]).
%--------------------------------------------------------------------
%TODO: implement myPermutations(List,OnePossiblePermutationOfList)
%note: by re-evaluating the function (using the space bar or ";"), one gets all possible permutations

buildRandom(List,Element,[Element|List]).
buildRandom([Head|Tail],Element,[Head|ResultList]):-
	buildRandom(Tail,Element,ResultList).


myPermutations([],[]).
myPermutations([Head|Tail],Result):-
	myPermutations(Tail,TempList),
	buildRandom(TempList,Head,Result).

%testcase:
testcase_permut(X):-
	myPermutations([1,2,3,4],X).
%confirm yourself that your implementation outputs all 16 permutations and produces no doubles
%--------------------------------------------------------------------
%TODO: implement zip(ListA,ListB,ZippedList)
% the length difference of ListA and ListB is at most 1
% ZippedList is a list of Lists with length 2 (the last element may have length 1)
zip([X],[],[[X]]).
zip([],[X],[[X]]).
zip([A],[B],[[A,B]]).
zip([Head1|Tail1],[Head2|Tail2],Result):-
	zip(Tail1,Tail2,TempList),
	append([[Head1,Head2]],TempList,Result).




%testcase
testcase_zip():-
	zip([1,2],[3,4,5],[[1,3],[2,4],[5]]).

%%==========Problem 1.2===============
%Please see the exercise sheet for detailed instructions about what these functions do

tree(nil).
tree(_,L,R):-
	tree(L),
	tree(R).

%TODO implement construct(List,Tree)
construct(List,Tree):-
	insert(List,nil,Tree).

insert([],Tree,Tree).
insert([Head|Tail],TempTree,Tree):-
	insert_help(Head,TempTree,NewTempTree),
	insert(Tail,NewTempTree,Tree).

insert_help(X, nil, tree(X,nil,nil)).
insert_help(X,tree(Y,L,R), tree(Y,L,NewTree)):-
	X>Y,
	insert_help(X,R,NewTree).
insert_help(X,tree(Y,L,R), tree(Y,NewTree,R)):-
	X<Y,
	insert_help(X,L,NewTree).


%testcase
testcase_construct():-
	construct([5,2,4,1,3],tree(5,tree(2,tree(1,nil,nil),tree(4,tree(3,nil,nil),nil)),nil)).
%--------------------------------------------------------------------
%TODO: implement count_leaves(Tree,NumberOfLeaves)

count_leaves(nil,0).
count_leaves(tree(_,nil,nil),1):-!.
count_leaves(tree(_,L,R),Result):-
	count_leaves(L,Temp1),
	count_leaves(R,Temp2),
	Result is Temp1 + Temp2.

%testcase
testcase_count():-
	count_leaves(tree(3,tree(1,nil,tree(2,nil,nil)),nil),1).
%TODO: Use it to test how cost efficient your previous function is (in terms of the
% structure that you obtain). What can you observe for larger lists of numbers?
% Answer these questions as a comment or hand in a separate file



%--------------------------------------------------------------------
%TODO: implement symmetric(Tree) that is true, if the Tree is symmetric

%symmetric(tree(_,nil,nil)).
symmetric(tree(_,L,R)):-
	mirrored(L,R).

mirrored(nil,nil).
mirrored(tree(_,L1,R1), tree(_,L2,R2)):-
	mirrored(L1,R2),
	mirrored(R1,L2).


%testcase
testcase_symm():-
	construct([5,2,3,7,6],X),
	symmetric(X).

%=========================================
%% total test
test(X):-
	testcase_remove(),
	testcase_reverse(),
	testcase_zip(),
	testcase_construct(),
	testcase_count(),
	testcase_symm(),
	writeln("everything correct up to myPermutations,"),
	writeln("now all permutations of [1,2,3,4]:"),
	testcase_permut(X).