%              Deklaratív Programozás gyakorlat 2010.03.03
%     Prolog programozás: listák, feltételes szerkezetek használata
%		                MEGOLDÁSOK
% ---------------------------------------------------------------

:- use_module(library(lists), [append/3]).

% 1. feladat
% insert_ord(+RL0, +Elem, ?RL): Az RL monoton növő számlista úgy áll
% elő, hogy az RL0 szigorúan növő számlistába beszúrjuk az Elem számot,
% feltéve hogy Elem nem eleme az RL0 listának; egyébként RL = RL0.
insert_ord([], E, [E]).
insert_ord(L0, E, L) :-
	L0 = [X|L1],
	(   X > E -> L = [E|L0]
	;   X =:= E -> L = L0
	;   L = [X|L2],
	    insert_ord(L1, E, L2)
	).

% insert_ord_1(+RL0, +Elem, ?RL): ugyanaz mint
%   insert_ord(+RL0, +Elem, ?RL), de feltételes szerkezet használata
% nélkül. Kevésbé hatékony, mert választási pontot hagy maga után.
insert_ord_1([], E, [E]).
insert_ord_1([E|L0], E, [E|L0]).
insert_ord_1([X|L0], E, [E,X|L0]) :-
	X > E.
insert_ord_1([X|L0], E, [X|L]) :-
	X < E,
	insert_ord_1(L0, E, L).


% 2. feladat
% nth1_1(+N, ?L, ?E): Az L lista N. eleme E (1-től számozva az
% elemeket). 
nth1_1(N, [X|L], E) :-
	(   N =:= 1 -> E = X
	;   N > 1, N1 is N-1,
	    nth1_1(N1, L, E)
	).

% 3. feladat
% nth1_2(?N, +L, ?E): Az L lista N. eleme E (1-től számozva az
% elemeket). 
nth1_2(1, [X|_L], X).
nth1_2(N, [_|L], Y) :-
	nth1_2(N1, L, Y),
	N is N1+1.

% 4. feladat
% prefix_length(+Whole, ?Prefix, +Length): A Whole lista prefixuma a
% Prefix lista, amelynek hossza Length.
prefix_length(L, P, N) :-
	(   N =:= 0 -> P = []
	;   N > 0, N1 is N-1,
	    L = [X|L1],
	    P = [X|P1],
	    prefix_length(L1, P1, N1)
	).

% 5. feladat
% suffix_before(+Whole, ?Suffix, +Before): A Whole lista azon szuffixuma a
% Suffix lista, amelyet megelőző elemek száma Before.
suffix_before(L, S, B) :-
	(   B =:= 0 -> S = L
	;   B > 0, B1 is B-1,
	    L = [_|L1],
	    suffix_before(L1, S, B1)
	).

% 6. feladat
% sublist(+Whole, ?Part, +Before, +Length): A Whole lista azon
% (folytonos) részlistája Part, amely előtt Before számú elem áll és
% amelynek hossza Length.
sublist(Whole, Part, Before, Length) :-
	suffix_before(Whole, Suffix, Before),
	prefix_length(Suffix, Part, Length).


% 7. feladat
% sublist(+Whole, ?Part, ?Before, ?Length, ?After): A Whole lista olyan
% (folytonos) részlistája Part, amely előtt Before és amely után After
% számú elem áll, és amelynek hossza Length.
sublist(Whole, Part, Before, Length, After) :-
	append(BeforeL, PartAfterL, Whole),
	length(BeforeL, Before),
	append(Part, AfterL, PartAfterL),
	length(Part, Length),
	length(AfterL, After).

% 8. feladat
% nth1_3(?N, ?L, ?E): Az L lista N. eleme E (1-től számozva az
% elemeket). 
nth1_3(N, L, E) :-
	(   var(N) -> nth1_2(N, L, E)
	;   nth1_1(N, L, E)
	).

% 9. feladat
% insert_nth(+N, ?L0, ?E, ?L): Az L lista N. eleme E, ezt megelőző
% elemei azonosak L0 1., 2., ... N-1. elemével, ezt követő elemei
% azonosak L0 N., N+1., ... elemeivel.
insert_nth(1, L0, E, [E|L0]).
insert_nth(N, [X|L0], E, [X|L]) :-
        N > 1, N1 is N-1,
        insert_nth(N1, L0, E, L).


% :- mode insert_nth_2(+, ?, ?, ?).
insert_nth_2(N, L0, E, L) :-
        (   N =:= 1 ->  L = [E|L0]
        ;   N > 1 ->  N1 is N-1,
            L0 = [X|L1], L = [X|L2],
            insert_nth_2(N1, L1, E, L2)
        ).

% 10. feladat
% :- mode insert_nth_3(?, +, ?, ?).
insert_nth_3(N, L0, E, L) :-
        append(L1, L2, L0),
        append(L1, [E|L2], L),
        length(L1, N1),
        N is N1+1.

% 11. feladat
% :- mode insert_nth_4(?, +, ?, ?).
% :- mode insert_nth_4(?, -, ?, +).
insert_nth_4(1, L, X, [X|L]).
insert_nth_4(N, [Y|R], X, [Y|L]) :-
	insert_nth_4(N1, R, X, L),
	N is N1+1.

% :- mode insert_nth_5(?, +, ?, ?).
% :- mode insert_nth_5(?, -, ?, +).
% insert_nth_5 hatékonyan működik akkor is ha az első argumentum adott.
insert_nth_5(N, L0, X, L) :-
	(   var(N) -> insert_nth_2(N, L0, X, L)
	;   insert_nth_4(N, L0, X, L)
	).

