% =====================================
% Operations on Lists:
% 
% Iterators:
% - iter
% - iter_rev
% - iter_every_2nd
% - iter_nth
% - iter_odd
% - iter_even
% 
% Metadata:
% - len
% - count (occurances of element)
% - indexof
% - sum (sum list of integers)
% - member (test if a element is in a list)
% 
% Manipulation/Access:
% - nth (get N-th element) 
% - remove (remove element by value)
% - del (remove element at index)
% - del_last
% - del_first
% - insert (insert at index)
% - add (append)
% - merge
% - repeat 
% 
% =====================================

% what to do on each iteration
do_sth(X):-writeln(X).

% iterate over list in sucessive order
% prints each element
%
% example: iter_nth([1,2,3,4,5,6,7,8,9])
% output: [1,2,3,4,5,6,7,8,9]
iter([]).
iter([H|T]):-do_sth(H), iter(T).

% iterate over list in reverse order
% prints each element
%
% example: iter_nth([1,2,3,4,5,6,7,8,9])
% output: [9,8,7,6,5,4,3,2,1]
iter_rev([A]):-do_sth(A).
iter_rev([H|T]):-iter_rev(T), do_sth(H).

% prints every 2nd element from the supplied list
iter_every_2nd([]).
iter_every_2nd([_|[H2|T]]):-do_sth(H2), iter_every_2nd(T).

% iterate over every nth element in the list
%
% example: iter_nth([1,2,3,4,5,6,7,8,9], 3)
% output: [3, 6, 9]
iter_nth([], _, _).
iter_nth([H|T], E, 0):-
    R is E - 1,
    iter_nth(T, E, R),
    do_sth(H).

iter_nth([_|T], E, L):-
    R is L - 1,
    iter_nth(T, E, R).

iter_nth(L, N):-
    R is N - 1,
    iter_nth(L, N, R).

% iterate over all elements with an even index
iter_even(L):-iter_nth(L, 2).

% iterate over all elements with an odd index
iter_odd(L):-iter_nth(L, 2, 0).

% counts the amount of items in the supplied list
%
% example: len([1,2,3,4,5,6], X)
% output: X = 6
len([], L):-L is 0.
len([_|T], L):-
    len(T, Tmp),
    L is Tmp + 1.

% count the amounts an element `E` is present in the supplied list
%
% example: count([a,b,c,a], a, X)
% output: X = 2
count([], _, L):-L is 0.
count([H|T], E, L):-
    H == E,
    count(T, E, R),
    L is R + 1.
count([_|T], E, L):-
    count(T, E, R),
    L is R.

% return the nth element of the supplied list.
% indexing starts with 0
%
% example: nth([a,b,c,d,e], 3, X)
% output: X = d
nth([],_).
nth([H|_], 0, O):-O is H.
nth([_|T], C, O):-
    C1 is C - 1,
    nth(T,C1, K),
    O is K.

% return the index of the first occurance of the element
% in a list
% indexing starts with 0
%
% example: indexof([0,1,3,4,5,6,7,8,9], 3, X)
% output: X = 2
indexof([],_,_).
indexof([H|_],E,C):-
    H == E,
    C is 0.
indexof([_|T],E,C):-
    indexof(T,E,R),
    C is R + 1.

% removes all elements of Tar from the list
%
% example: remove([a,b,c,d], a, X)
% output: X = [b,c,d]
remove([],_,[]).
remove([Head|Tail], Head, Res):-
    remove(Tail, Head, Res).
remove([Head|Tail], Tar, [Head|Res]):-
    remove(Tail, Tar, Res).

% removes the last element
%
% example: del_last([1,2,3,4], X)
% output: X = [1, 2, 3]
del_last(List, Res):-
    len(List, Len),
    Tmp is Len - 1,
    del(List, Tmp, Res).

% removes the first element
%
% example: del_first([1,2,3,4], X)
% output: X = [2, 3, 4]
del_first([_|Tail], Tail).

% append an element to the right end of the list
%
% example: add([a,b,c,d], a, X)
% output: X = [a,b,c,d,a]
add([], Elem, [Elem]).
add([Head|Tail], Elem, [Head|Tail2]):-
    add(Tail, Elem, Tail2).

% insert an element into the list at a certain index
%
% example: insert([a,b,c,d], k, 2, X)
% output: X = [a, b, k, c, d]
insert([], _, _, []).
insert([Head|Tail], Elem, 0, [Elem|[Head|Tail]]).
insert([Head|Tail], Elem, Idx, [Head|Res]):-
    Idx2 is Idx - 1,
    insert(Tail, Elem, Idx2, Res).

% remove an element at the specified index from the list
%
% example: del([a,b,c,d], 2, X)
% output: X = [a, b, d]
del([], _, _, []).
del([_|Tail], 0, Tail).
del([Head|Tail], Idx, [Head|Res]):-
    Idx2 is Idx - 1,
    del(Tail, Idx2, Res).    

% merge to lists together
%
% example: merge([a,b], [3,4], X)
% output: X = [a, b, 3, 4]
merge(List, [], List).
merge(List,[Head|Tail],Res):-
    add(List, Head, Tmp),
    merge(Tmp, Tail, Res).    

% sum a list of values
%
% example: sum([1,2,3,4], X)
% value: X = 10
sum([], 0).
sum([Head|Tail], Res):-
    sum(Tail, Tmp),
    Res is Tmp + Head.

% detect whether an elemenz is part of a given list
%
% example: member([1,2,3,4], 4)
% output: true
%
% example: member([1,2,3,4], 9)
% output: false
member([Elem|_], Elem).
member([_|Tail], Elem):-member(Tail, Elem).

% repeat sth N-times
%
% example: repeat(a, 5, X).
% output: X = [a,a,a,a,a]
repeat(_, 0, []).
repeat(Elem, N, [Elem|Tmp]):-
    N1 is N - 1,
    repeat(Elem, N1, Tmp).