%                      Egy érdekes Prolog feladat
%                      ==========================

% felreforditasa(+L, -FL):
% Az L lista 2n elemű. Az ebből előállítandó FL lista szintén 2n elemű,
% első n eleme megegyezik az L első n elemével, hátsó n eleme az L utolsó n
% eleméből álló lista megfordítása.

% Egy, a lists könyvtárat használó n^2-tel arányos lépésszámú lehetséges
% megoldás (a kommentekben ++ két lista összefűzését jelöli).

felreforditasa(L, F) :-
    append(Eleje, Vege, L),       % Eleje ++ Vege = L,
    same_length(Eleje, Vege),     % Eleje és Vege azonos hosszúak
    reverse(Vege, FordVege),      % FordVege Vege megfordítása      
    append(Eleje, FordVege, F).   % Eleje ++ FordVege = F

% Írjon olyan Prolog programot, amely ezt a feladatot egy 2n hosszúságú
% bemenetre n+c redukciós lépésben (azaz ennyi eljáráshívással) oldja meg,
% ahol c egy konstans.  

% A végső cél az, hogy a megoldás teljesítse az alábbi ún. *erős*
% feltételeket: összesen 3 (azaz három) klózból álljon, ne használjon sem
% beépített, sem könyvtári eljárást (még vágót sem), továbbá se diszjunkció
% se feltételes szerkezet ne legyen benne.

% Érdemes lehet először egy *gyengített* feltételrendszer melletti
% megoldáson gondolkozni. Ebben nem korlátozzuk a klózok számát, és
% megengedjük a következő beépített predikátumokat: = /2, length/2, !/0,
% is/2, valamint az aritmetikai összehasonlító eljárásokat: < /2, =< /2,
% =:= /2 stb. Ezek hívásai nem számítanak redukciós lépésnek.  Diszjunkció
% és feltételes szerkezet is használható.


% Két fontos megjegyzés
% ---------------------

% 1. megjegyzés: A redukciók számának csökkentésére elvben lehetne
% használni a redukciós lépések összevonásának módszerét. Erre példa az
% append/3 eljárás alábbi változata, amely egyszerre 5 elemet dolgoz fel
% (ez csak összefűzésre használható, szétszedésre nem):

app5([], L, L).
app5([A,B,C,D,E|L1], L2, [A,B,C,D,E|L3]) :- !,
    app5(L1, L2, L3).
app5([A|L1], L2, [A|L3]) :-
    app5(L1, L2, L3).

% Az app5/3 eljárás a közönséges appendhez képest ötödannyi redukciós
% lépést hajt végre. Ha 5 elem helyett k elemet kezelünk egy redukciós
% lépésben, akkor a redukciós lépések számát k-ad részére lehet csökkenteni.
% Következésképpen, ha ezt a módszert a kitűzött feladatban megengedjük, 
% akkor a lépések számát nemcsak n-re, hanem n/k-ra is lehetne csökkenteni,
% ahol k tetszőlegesen nagy adott szám.

% Jelen feladat megoldásában az összevonásos módszer alkalmazását nem
% engedjük meg. Fontos megjegyezni, hogy az önmagában nem gond, ha egy
% redukciós lépésben egy lista elejéről két vagy több elemet leveszünk. Ez
% csak akkor baj, ha ezt abból a célból tesszük, hogy két vagy több
% redukciós lépést egyetlen lépésbe összevonjunk.

% 2. megjegyzés: Egy Prolog redukciós lépés futási ideje nem feltétlenül
% korlátos. Ha L1 és L2 két k hosszúságú, azonos elemekből álló lista,
% akkor az L1 = L2 hívás futtatása k-val arányos idejű (lásd a fájl végén a
% (=)/2 jelű futtatás időmérését). Így, annak ellenére, hogy egy Prolog
% hívás n redukciós lépésben lefut, futási ideje lehet n^2-tel arányos,
% vagy akár még ennél is nagyobb.

% Ezért fontos kikötnünk, hogy felreforditasa/2 eljárás futási ideje a
% bemeneti lista hosszával legyen arányos.

% Az alábbiakban a felreforditasa eljaras néhány további megvalósítását,
% egy időmérést végző segédeljárást (stat/3), valamint a
% példa-megvalósítások tesztelését végző eljárásokat mutatjuk be.  
% A program a SICStus és SWI Prolog rendszerekben is futtatható.  
% A fájl végén találhatók futási példák, időméréssel.

:- use_module(library(lists)).

felreforditasa1(L, F) :-
    length(L, Len), Len mod 2 =:= 0, N is Len//2,
    length(Eleje, N),
    append(Eleje, Vege, L),
    reverse(Vege, ForditottVege),
    append(Eleje, ForditottVege, F).

felreforditasa2(L, F) :-
    length(L, Len), Len mod 2 =:= 0, N is Len//2,
    replace_tail(N, L, Vege, F, VegeF),
    reverse(Vege, VegeF).

% replace_tail(+N, ?OldList, ?OldTail, ?NewList, ?NewTail):
%     OldList és NewList első N eleme megegyezik, 
%     OldList első N elemének elhagyása után OldTail marad,
%     NewList első N elemének elhagyása után NewTail marad.
% Egy átfogalmazás: 
%     Létezik egy olyan L N-elemű lista, hogy:
%     OldList = L ++ OldTail, és NewList = L ++ NewTail.
% Futási példák:
%     | ?- replace_tail(2, [a,b,c], OldT, NewL, NewT).
%     OldT = [c],
%     NewL = [a,b|NewT] ? ;
%     no
%     | ?- replace_tail(2, OldL, OldT, NewL, NewT).
%     OldL = [_A,_B|OldT],
%     NewL = [_A,_B|NewT] ? ;
%     no
replace_tail(0, OldList, OldTail, NewList, NewTail) :- !,
    OldList = OldTail, NewList = NewTail.
replace_tail(N, [H|L], OldTail, [H|NL], NewTail) :-
    N1 is N-1, replace_tail(N1, L, OldTail, NL, NewTail).

% Futási idő jelentést készít a Pred eljárás M hosszúságú listával való
% Rep-szeres futtatásáról.
stat(Pred, Rep, M) :-
    statistics(runtime, [_,T0]),  
                            % T0 a megelőző statistics(runtime, _) hívás
                            % óta eltelt CPU idő, ezredmásodpercekben
    T is T0*1000//Rep,
    prolog_flag(dialect, D0), dialect_name(D0, D),
    format('\nPred ~|~w,~t~16+ len =~|~t~w~9+, ~w time:~|~t~3d~10+ msec',
           [Pred,M,D,T]).

% dialect_name(System, Name): a System nevű Prolog rendszer megjelenítendő
% neve Name.
dialect_name(sicstus, 'SICStus').
dialect_name(swi, 'SWI').

:- ( prolog_flag(dialect, sicstus) -> use_module(library(between))
   ; set_prolog_flag(stack_limit, 2147483648)
   ).

% repeat(Test, Rep): A Test fajtájú eljárást SICStusban Rep-szer futtatjuk.
repeat(ff, 50).
repeat(unify, 100).

% repeat_times(Test, Rep): A Test fajtájú eljárást Rep-szer futtatjuk.
repeat_times(Test, Rep) :-
    repeat(Test, Rep0),
    (   prolog_flag(dialect, sicstus) -> Rep = Rep0
    ;   Rep is Rep0//10 % Mivel az SWI Prolog átlagosan kb. 7-szer lassabb,
                        % a futtatások számát tizedére csökkentjük.
    ).

% A felreforditasa feladatot megvalósító kétargumentumú Pred eljárást 
% 2N hosszú listára futtatja, és erről jelentést készít.
run_ff(N, Pred) :-
    M is 2*N, numlist(1, M, L),
    repeat_times(ff, Rep),           % Rep az ismételt futások száma
    statistics(runtime, _),          % Nullázzuk a relatív időmérést
    (   between(1, Rep, _),          % Rep-szer sikerül
        call(Pred, L, _),
        fail                         % meghiúsulásos ciklus folytatása
    ;   stat(Pred, Rep, M)
    ).

% Két azonos, N hosszú lista egyesítését futtatja,
% és erről jelentést készít.
run_unify(N) :-
    numlist(1, N, L1),
    numlist(1, N, L2),
    repeat_times(unify, Rep),
    statistics(runtime, _), 
    (   between(1, Rep, _),         
        L1=L2,
        fail                        
    ;   stat(= /2, Rep, N)
    ).

% Jelentést készít a felreforditasa feladatot megvalósító eljárások
% időigényéről.
run_felreforditasa :-
 (     member(N, [2000,4000,8000,16000]),    run_ff(N, felreforditasa),  fail
 ; nl, member(N, [100000,1000000,10000000]), run_ff(N, felreforditasa1), fail
 ; nl, member(N, [100000,1000000,10000000]), run_ff(N, felreforditasa2), fail
 ; true
 ).

% Jelentést készít két azonos lista egyesítésének időigényéről.
run_unify :-
    (   member(N, [100000,1000000,10000000]), run_unify(N), fail
    ;   true
    ).

run_all :-
    run_unify, nl, nl, run_felreforditasa.

end_of_file.

% A futtatások Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz processzoron,
% SICStus 4.5.0 ill. SWI 8.2.2 Prolog rendszerekkel készültek.

(=)/2,           len =   100000, SWI:     2.700 msec, SICStus:   0.920 msec
(=)/2,           len =  1000000, SWI:    27.900 msec, SICStus:   9.500 msec
(=)/2,           len = 10000000, SWI:   283.100 msec, SICStus:  94.980 msec
                                                                                     
                                                                                     
felreforditasa,  len =     4000, SWI:   192.200 msec, SICStus:  10.580 msec
felreforditasa,  len =     8000, SWI:   765.000 msec, SICStus:  41.780 msec
felreforditasa,  len =    16000, SWI:  3072.200 msec, SICStus: 165.800 msec
felreforditasa,  len =    32000, SWI: 12260.600 msec, SICStus: 658.380 msec
                                                                                     
felreforditasa1, len =   200000, SWI:    24.600 msec, SICStus:   4.020 msec
felreforditasa1, len =  2000000, SWI:   247.800 msec, SICStus:  42.140 msec
felreforditasa1, len = 20000000, SWI:  2648.200 msec, SICStus: 451.580 msec
                                                                                     
felreforditasa2, len =   200000, SWI:    20.000 msec, SICStus:   2.920 msec
felreforditasa2, len =  2000000, SWI:   201.000 msec, SICStus:  30.320 msec
felreforditasa2, len = 20000000, SWI:  2012.800 msec, SICStus: 301.680 msec
