% ------------------------------------------
% Logische Programmierung, ueb 3, 18.11.2002
% (c)Marc Dörflinger, Roger, Philip Iezzi
% ------------------------------------------


% ------------------------------------
% my_length(List,N)
%
% calculate the length of a list
% ------------------------------------

/*
 * Alternative 1
 * -> no accumulator needed
 * -> not tail recursive
 */

my_length([],0).
my_length([_|T],N) :-
	my_length(T,X),
	N is X + 1.
	
	
/*
 * Alternative 2
 * -> accumulator
 * -> tail recursive
 */

my_accLength(L,N) :-
	my_accLength(L,0,N).
my_accLength([],A,A).
my_accLength([_|T],A,N) :-
	A1 is A + 1,
	my_accLength(T,A1,N).



% ------------------------------------
% my_remove(Element,List,Remainder)
%
% Remove the first occurrence of an 
% element in a list.
% ------------------------------------

/*
 * Alternative 1
 * (Maya's solution)
 */

my_remove(_, [], []).

my_remove(E, [E|T], T).

my_remove(E, [H|T], [H|RestRemainder]) :-
	\+ E = H,
	my_remove(E, T, RestRemainder).


/*
 * Alternative 2
 * (using append)
 *
 * This returns all possible solution where
 * any occurence of the element has been removed 
 * from the list.
 */

my_remove2(E, X, X) :-
	\+member(E, X).  % Element is no member of the list

% Split list into pre- and post-part next to element

my_remove2(E, List, Remainder) :-
	append(Pre, [E|Post], List),
	append(Pre, Post, Remainder).


/*
 * Alternative 3
 * (without using append)
 *
 * UGLY SOLUTION - using cut!
 */

my_remove3(E,L,R) :-
	my_remove3(E,0,L,R).

my_remove3(_, _, [], []).

my_remove3(H, 0, [H|T], R) :- !,
	my_remove3(H, 1, T, R).

my_remove3(E, Done, [H|T], [H|R]) :-
	my_remove3(E, Done, T, R).




% ------------------------------------
% my_remove_all(Element,List,Remainder)
%
% Remove all occurrences of an 
% element in a list.
% ------------------------------------


/*
 * Alternative 1
 * (without using my_remove)
 */

my_remove_all(_, [], []).

my_remove_all(H, [H|T], R) :-
	my_remove_all(H, T, R).

my_remove_all(E, [H|T], [H|R]) :-
	\+ E = H,                    % or: E \== H
	my_remove_all(E, T, R).


/*
 * Alternative 2
 * (using my_remove)
 *
 * UGLY SOLUTION - using cut!
 */

my_remove_all2(_, [], []) :- !.

my_remove_all2(E, X, X) :-
	\+member(E, X),
	!.

my_remove_all2(E, L, R) :-
	my_remove(E, L, X),
	my_remove_all2(E, X, R).


% ---------------------------------
% my_sort(List, SortedList)
%
% sort a list of unsorted integers
% -> insertion sort  o(n^2)
% ---------------------------------

% my_sort requires insert

my_insert(E, [], [E]).
my_insert(E,[X|Xs],[X|L]) :-
	E > X,
	my_insert(E, Xs, L).
my_insert(E,[X|Xs],[E,X|Xs]) :-
	E =< X.


% Wenn die erste Liste List leer ist, 
% gibt es nichts zu sortieren, dann ist auch 
% die zweite Liste SortedList leer.
my_sort([], []).

% Wenn die Liste List nicht leer ist, sortiere 
% den Rumpf der Liste List und füge das Kopfelement 
% in die sortierte Liste des Rumpfes ein. (insertion sort)
my_sort([H|T], SL) :-
	my_sort(T, X),
	my_insert(H, X, SL).




% ---------------------------------
% my_flatten(List, FlattenedList)
%
% flatten a list that contains sub-
% lists
% ---------------------------------

% Wenn die Liste leer ist, dann gibt's nichts zu 'glätten'
my_flatten([],[]).

% Wenn wir ein Nicht-Listen-Element haben, dann machen 
% wir daraus eine Liste mit nur diesem Element.
my_flatten(X, [X]) :-
	\+is_list(X).

% Wenn wir eine 'normale' Liste haben, dann rufen wir 
% für den Head und den Tail rekursiv die Methode nochmals 
% auf, auf fügen die daraus resultierenden Listen zusammen.
my_flatten([H|T], L3) :-
	my_flatten(H, L1),
	my_flatten(T, L2),
	append(L1, L2, L3).