% =============================================================================
% Deklaratív Programozás 3. gyakorlat, rendezéssel kapcsolatos Prolog eljárások
% =============================================================================

/* Feladatok:

% rendezett(+L): L (nem feltétlenül szigorúan) monoton növő számlista.
% (A "rendezett lista" kifejezés az alábbiakban is nem feltétlenül 
%  szigorúan monoton növekedő listát jelent.)

                | ?- rendezett([]).
                yes
                | ?- rendezett([1]).
                yes
                | ?- rendezett([1,2]).
                yes
                | ?- rendezett([1,2,2,3]).
		yes
                | ?- rendezett([1,22]).
                yes
                | ?- rendezett([1,22,3]).
                no
                | ?- rendezett([4,1,2,3]).
                no

% releje(+L, -R): Az L számlista maximális nem-üres rendezett 
% kezdőszelete R.  (Determinisztikus.)

                | ?- releje([], L).
                no
                | ?- releje([4,3,1,2,3], L).
                L = [4] ? ;
                no
                | ?- releje([1,2,2,1], L).
                L = [1,2,2] ? ;
                no
                | ?- releje([1], L).
                L = [1] ? ;
                no

% elso_rresze(L, R): R az L számlista egy folytonos részlistája, mégpedig az első
% a maximális, legalább kételemű rendezett folytonos részlisták közül.
% (Determinisztikus.)

                | ?- elso_rresze([4,3,2,1,0], R).
                no
                | ?- elso_rresze([4,3,2,1,0,1,0,2,3], R).
                R = [0,1] ? ;
                no
                | ?- elso_rresze([1,0,2,3], R).
                R = [0,2,3] ? ;
                no

% rresze(L, R): R az L számlista egy olyan folytonos részlistája, amely
% legalább kételemű, rendezett és az ilyenek között maximális.
% (Nemdeterminisztikus.)

                | ?- rresze([4,3,2,1,0,1,0,2,3], R).
                R = [0,1] ? ;
                R = [0,2,3] ? ;
                no
                | ?- rresze([4,5,4,3,2,2,3,1,2,0], R).
                R = [4,5] ? ;
                R = [2,2,3] ? ;
                R = [1,2] ? ;
                no

*/


/* Megoldások */

% ---------------------------------------------------------------------------
% rendezett(+L): L (nem feltétlenül szigorúan) monoton növő számlista.
rendezett([]).
rendezett([X|L]) :-
	rendezett(L, X).

% rendezett(+L, +X): [X|L] (nem feltétlenül szigorúan) monoton növő számlista.
% Ezen segédeljárás bevezetésével elérhetjük, hogy a Prolog futás során
% nem jön létre választási pont (első arg. szerinti indexelést feltételezve).
rendezett([], _X).
rendezett([Y|L], X) :-
	X =< Y,
	rendezett(L, Y).

% ---------------------------------------------------------------------------
% releje(+L, -R): Az L nem-üres számlista maximális rendezett kezdőszelete R.
releje([X|L], R) :-
	releje(L, X, R).

% releje(+L, +X, -R): [X|L] maximális rendezett kezdőszelete R.
releje([], X, [X]).
releje([Y|L], X, [X|R]) :-
	(   X =< Y ->
	    releje(L, Y, R)
	;   R = []
	).

% ---------------------------------------------------------------------------
% elso_rresze(L, R): R az L számlista egy folytonos részlistája, mégpedig az első
% a maximális, legalább kételemű rendezett részlisták közül.
elso_rresze(L, R) :-
	L = [X|L1],
	(   L1 = [Y|_], X =< Y ->
	    releje(L, R)
	;   elso_rresze(L1, R)
	).

% ---------------------------------------------------------------------------
% rresze(L, R): R az L számlista egy olyan folytonos részlistája, amely
% legalább kételemű, rendezett és az ilyenek között maximális.

% Nem a leghatékonyabb megoldás, de a legegyszerűbb, az előző
% feladatokra építve.
rresze(L, R) :-
	releje(L, R0),
	length(R0, N),
	(   N >= 2, R = R0
	;   drop(L, N, L1),
	    rresze(L1, R)
	).

% drop(L, N, RL) :- sublist(L, 1, N, RL) % (lasd 2. gyak)

drop(L, N, RL) :-
	(   N =:= 0 -> RL = L
	;   N > 0,
	    L = [_|L1],
	    N1 is N-1,
	    drop(L1, N1, RL)
	).

:- use_module(library(lists)).

% ugyanaz, mint rresze/2, nem hatékony, de deklaratív
rresze_dekl(L, R) :-
	R = [_,_|_],               % R legalább kételemű
	append(E, L1, L),
	append(R, U, L1),          % R részlistája L-nek
	rendezett(R),              % R rendezett
	R = [R1|_],
	last(R, Rn),               % R = [R1,..., Rn]
	\+ (   last(E, Em),
	       Em =< R1
	   ),                      % R balra nem terjeszthető ki
	\+ (   U = [U1|_],
	       Rn =< U1
	   ).                      % R jobbra nem terjeszthető ki

% ugyanaz, mint rresze/2, es hatékony
rresze_hatekony(L, R) :-
	releje_maradek(L, R0, M),
	(   R0 = [_,_|_], R = R0
	;   rresze_hatekony(M, R)
	).

% releje_maradek(+L, -R, -M): Az L nem-üres számlista maximális rendezett
% kezdőszelete R,  L fennmaradó része M.
releje_maradek([X|L], R, M) :-
	releje_maradek(L, X, R, M).

% releje_maradek(+L, +X, -R, -M): [X|L] maximális rendezett kezdőszelete R,
% maradéka M.
releje_maradek([], X, [X], []).
releje_maradek(L, X, [X|R], M) :-
	L = [Y|L1],
	(   X =< Y ->
	    releje_maradek(L1, Y, R, M)
	;   R = [], M = L
	).