%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%     Programma per la ricerca di percorsi stradali su mappa
%     letta da file
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% leggi_lista_str(L,F): legge dal file F (fino a EOF) una sequenza  
% di stringhe, terminate da "spazio" o "a capo", e memorizza gli 
% atomi corrispondenti nella lista L
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

leggi_lista_str(L,F) :-
      see(F),
      leggi_lista_str(L),
      seen.

leggi_lista_str([S|R]) :-
      leggi_stringa(S),
      S \== end_of_file, !,
      leggi_lista_str(R).
leggi_lista_str([]).

leggi_stringa(end_of_file) :-
      at_end_of_stream, !.  % vero se si e' raggiunto l'end_of_file 
                            % sul file di input corrente
leggi_stringa(S) :-
      leggi_lista_car2(L),
      name(S,L).

leggi_lista_car2([C|R]) :-
      get0(C),
      C \== 10, C \== 32, C \== -1, !,
      leggi_lista_car2(R).
leggi_lista_car2([]).

% Goal d'esempio:
%
% Si supponga che il file 'prova.txt' contenga:
% parma reggio_emilia
% modena
%
% ?- leggi_lista_str(L,'prova.txt').
% L = [parma, reggio_emilia, modena] ;
% no


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% crea_terne(L,LT): vero se L e' una lista e LT e' la lista che 
% contiene gli stessi elementi di L raggruppati tre a tre (ciascuna 
% terna e' realizzata come una sottolista di tre elementi). Gli 
% eventuali elementi in eccesso in L vengono ignorati.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

crea_terne([],[]).
crea_terne([_X],[]).
crea_terne([_X,_Y],[]).
crea_terne([X,Y,Z|R],[[X,Y,Z]|RT]) :-
      crea_terne(R,RT).

% Goal d'esempio:
%
% ?- crea_terne([a,b,c,d,e,f,g],LT).
% LT = [[a,b,c],[d,e,f]] 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ccamm_p(G,X,Y,C,P): vero se C e' un cammino dal nodo X al nodo Y 
% con peso P. G puo' essere ciclico
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

ccamm_p(G,X,Y,Cammino,P) :-
      ccamm_p(G,X,Y,[],RCammino,P),
      reverse(RCammino,Cammino).

ccamm_p(G,X,Y,Visitati,[Y,X|Visitati],P) :- 
      (member([X,Y,P],G) ; member([Y,X,P],G)),
      \+member(Y,Visitati).
ccamm_p(G,X,Y,Visitati,VisitatiNuovi,P) :-
      (member([X,Z,P1],G) ; member([Z,X,P1],G)),
      \+member(Z,Visitati),
      ccamm_p(G,Z,Y,[X|Visitati],VisitatiNuovi,P2),
      P is P1 + P2.  


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% "Programma principale"
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

start :-
      leggi_lista_str(L,'mappa.txt'),
      crea_terne(L,G),
      write('Dai punto di partenza:  '),
      leggi_stringa(Partenza),   %read(Partenza),
      write('Dai punto di arrivo:  '),
      leggi_stringa(Arrivo),   %read(Arrivo),
      ccamm_p(G,Partenza,Arrivo,Percorso,Distanza),
      write('Partenza:  '),write(Partenza),nl,
      write('Arrivo:  '),write(Arrivo),nl,
      write('Percorso:  '),write(Percorso),nl,
      write('Distanza:  '),write(Distanza),nl,
      write('Altre alternative? (y/n): '),
      get0(C),get0(_C),
      continua(C).
continua(121) :- nl,fail.
continua(110).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Predicati ausiliari
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% member(X,L): vero se X e' un elemento della lista L

  member(X,[X|_R]).
  member(X,[_Y|R]) :- 
      member(X,R).

% append(L1,L2,L3): vero se la lista L3 e' la concatenazione
% delle liste L1 ed L2

  append([],L2,L2).
  append([X|R1],L2,[X|R3]) :-
      append(R1,L2,R3).

% reverse(L1,L2): vero se la lista L2 coincide con la lista L1 ma
% con gli elementi in ordine inverso

  reverse([],[]).
  reverse([X|R1],L2) :-
      reverse(R1,RR1),
      append(RR1,[X],L2).

