program Test(Input, Output);

type 	stringa=packed array [1..8] of char;
        albero_alfabeto = ^cella_alfabeto;
	nodo_alfabeto = albero_alfabeto;
	cella_alfabeto = record
			frequenza: integer;
			figlioA, figlioC, figlioG, figlioT: nodo_alfabeto;
		end;
		
	albero_frequenza = ^cella_frequenza;
	nodo_frequenza = albero_frequenza;
	cella_frequenza = record
			elemento: stringa;
			frequenza: integer;
			sx: nodo_frequenza;
			dx: nodo_frequenza;
		end;
			
	dominio=0..3;
	percorso=array [1..8] of dominio;
		
var 	radice_alfabeto: albero_alfabeto;
	radice_frequenza: albero_frequenza;
	radice_jolly: albero_frequenza;
	livello: integer;
        parola: stringa;
	nome_file: string(100);
	ch: char;
	uscita: text;
	percorso_corrente: percorso;
	i: integer;
	maxbuffer: integer;

procedure inizializza_alfabeto(var radice: albero_alfabeto; livello: integer);
	begin
		
		radice^.frequenza := 0;
	
		if livello < 8 then
			begin
			        new (radice^.figlioA);
				inizializza_alfabeto(radice^.figlioA, livello+1);
			        new (radice^.figlioC);
				inizializza_alfabeto(radice^.figlioC, livello+1);
		                new (radice^.figlioG);
				inizializza_alfabeto(radice^.figlioG, livello+1);
				new (radice^.figlioT);
				inizializza_alfabeto(radice^.figlioT, livello+1);
			end
		else
			begin
				radice^.figlioA := nil; radice^.figlioC := nil; radice^.figlioG := nil; radice^.figlioT := nil;
		        end
	end;
	
procedure inizializza_frequenza(var radice: albero_frequenza);
	begin
		radice^.sx:=nil;
		radice^.dx:=nil;
		radice^.frequenza:=0;
	end;
	
procedure stampa_alfabeto(var radice: albero_alfabeto; var parola: stringa; livello:integer; var canale_uscita: text);
	begin
	
		if(radice^.figlioA <> nil) then
			begin
				parola[livello]:='A';
				stampa_alfabeto(radice^.figlioA, parola, livello+1, canale_uscita);
				parola[livello]:='C';
				stampa_alfabeto(radice^.figlioC, parola, livello+1, canale_uscita);
				parola[livello]:='G';
				stampa_alfabeto(radice^.figlioG, parola, livello+1, canale_uscita);
				parola[livello]:='T';
				stampa_alfabeto(radice^.figlioT, parola, livello+1, canale_uscita);
			end
	        else
	             begin
	                  {stampa parola e frequenza poiche' sono arrivato ad una foglia}
	                   if radice^.frequenza > 0 then
	                   	begin
	                   		writeln (canale_uscita, parola,'       ',radice^.frequenza);
	                   	end;
	             end        	
				
	  end;
				
procedure aggiungi_frequenza_alfabeto(var radice: albero_alfabeto; var parola: stringa; livello:integer);
	begin
		   
	      if (radice^.figlioA <> nil) then  
	         	begin
	                      if parola [livello]='A' then
			              aggiungi_frequenza_alfabeto (radice^.figlioA, parola, livello+1)
			      else
			          if parola [livello]='C' then
			              aggiungi_frequenza_alfabeto (radice^.figlioC, parola, livello+1)
			           else             
			               if parola [livello]='G' then
			                    aggiungi_frequenza_alfabeto (radice^.figlioG, parola, livello+1) 	
	                               else
				           if parola [livello]='T' then
			                        aggiungi_frequenza_alfabeto (radice^.figlioT, parola, livello+1);
			end
		else	
	     		 {sono giunto in un nodo: ho letto tutta la sequenza fino al dato nodo,ora ne incremento il campo frequenza}
	          	 radice^.frequenza:=radice^.frequenza+1;	
      	end;

procedure copia (var origine: stringa;var destinazione: stringa);
              var i: integer;
            begin
	        for i:=1 to 8 do
		     begin
		          destinazione [i]:=origine [i];
		     end;	  
	    end;
	    
procedure aggiungi_parola_frequenza(var radice: albero_frequenza; var parola: stringa; var frequenza: integer);
var tmp: nodo_frequenza;
    tmp_rad: nodo_frequenza;
    fine: boolean;
	begin
	    if frequenza < radice^.frequenza then
		begin
	          if radice^.sx <> nil then
		 	begin
		         	aggiungi_parola_frequenza (radice^.sx, parola, frequenza)
		  	end
		  else
		      begin
		             new (radice^.sx);
			     inizializza_frequenza(radice^.sx);
		             copia (parola, radice^.sx^.elemento); 
		             radice^.sx^.frequenza:=frequenza;
	              end
		 end
	    else	
	    	if frequenza > radice^.frequenza then
	    		begin      
	          	if radice^.dx <> nil then
				begin
		        		aggiungi_parola_frequenza (radice^.dx, parola, frequenza)
		  		end
			else
		      		begin
		             		new (radice^.dx);
					inizializza_frequenza(radice^.dx);
		             		copia (parola, radice^.dx^.elemento); 
		             		radice^.dx^.frequenza:=frequenza;
	              		end
		 	end
		else {frequenza = radice^.frequenza}	{ Se le due frequenze sono UGUALI metto la parola da inserire a sinistra, cosi'
	                                            	rispetto l'ordine alfabetico}
			begin
				tmp_rad := radice;
				fine:=false;
				if (tmp_rad^.sx <> nil) then
					fine := (tmp_rad^.sx^.frequenza < tmp_rad^.frequenza);
				while (tmp_rad^.sx <> nil) AND ( NOT (fine) ) do
					begin
						tmp_rad:=tmp_rad^.sx;
						fine:=true;
						if (tmp_rad^.sx <> nil) then
							fine := (tmp_rad^.sx^.frequenza < tmp_rad^.frequenza);
					end;
					
					new(tmp);
					inizializza_frequenza(tmp);
					copia (parola, tmp^.elemento);
					tmp^.frequenza:=frequenza;
					tmp^.sx:=tmp_rad^.sx;
					tmp_rad^.sx:=tmp;
					
			end;
      end;	
      
procedure aggiungi_parola_frequenza_jolly(var radice: albero_frequenza; var parola: stringa; var frequenza: integer);
var tmp: nodo_frequenza;
    tmp_rad: nodo_frequenza;
    fine: boolean;
	begin
	    if frequenza < radice^.frequenza then
		begin
	          if radice^.sx <> nil then
		 	begin
		         	aggiungi_parola_frequenza_jolly (radice^.sx, parola, frequenza)
		  	end
		  else
		      begin
		             new (radice^.sx);
			     inizializza_frequenza(radice^.sx);
		             copia (parola, radice^.sx^.elemento); 
		             radice^.sx^.frequenza:=frequenza;
	              end
		 end
	    else	
	    	if frequenza > radice^.frequenza then
	    		begin      
	          	if radice^.dx <> nil then
				begin
		        		aggiungi_parola_frequenza_jolly (radice^.dx, parola, frequenza)
		  		end
			else
		      		begin
		             		new (radice^.dx);
					inizializza_frequenza(radice^.dx);
		             		copia (parola, radice^.dx^.elemento); 
		             		radice^.dx^.frequenza:=frequenza;
	              		end
		 	end
		else {frequenza = radice^.frequenza}	{ Se le due frequenze sono UGUALI metto la parola da inserire a sinistra, cosi'
	                                            	rispetto l'ordine alfabetico}
			begin
				tmp_rad := radice;
				fine:=false;
				if (tmp_rad^.sx <> nil) then
					fine := (tmp_rad^.sx^.frequenza < tmp_rad^.frequenza);
				while (tmp_rad^.sx <> nil) AND ( NOT (fine) ) do
					begin
						tmp_rad:=tmp_rad^.sx;
						fine:=true;
						if (tmp_rad^.sx <> nil) then
							fine := (tmp_rad^.sx^.frequenza < tmp_rad^.frequenza);
					end;
					
					new(tmp);
					inizializza_frequenza(tmp);
					copia (parola, tmp^.elemento);
					tmp^.frequenza:=frequenza;
					tmp^.sx:=tmp_rad^.sx;
					tmp_rad^.sx:=tmp;
					
			end;
      end;
      
procedure stampa_frequenza(var radice: albero_frequenza; var canale_uscita: text); 
	begin
		if radice^.dx <> nil then
			begin
				stampa_frequenza(radice^.dx, canale_uscita);
			end;
			
		writeln(canale_uscita, radice^.elemento,'       ', radice^.frequenza);
		
		if radice^.sx <> nil then
			begin
				stampa_frequenza(radice^.sx, canale_uscita);
			end;	
		
	end;	

procedure costruisci_frequenza_alfabeto(var radice: albero_alfabeto; var radice_frequenza: albero_frequenza; var parola: stringa; livello:integer);
	begin
		if radice^.figlioA <> nil then
			begin
				parola[livello]:='A';
				costruisci_frequenza_alfabeto(radice^.figlioA, radice_frequenza, parola, livello+1);
				parola[livello]:='C';
				costruisci_frequenza_alfabeto(radice^.figlioC, radice_frequenza, parola, livello+1);
				parola[livello]:='G';
				costruisci_frequenza_alfabeto(radice^.figlioG, radice_frequenza, parola, livello+1);
				parola[livello]:='T';
				costruisci_frequenza_alfabeto(radice^.figlioT, radice_frequenza, parola, livello+1);
			end
	        else
	             begin
			  if radice^.frequenza > 0 then
	             	  		aggiungi_parola_frequenza(radice_frequenza, parola, radice^.frequenza);
		     end        	
				
	  end;

procedure leggi_file(nome_ingresso: string);
	var ingresso: text;
	    ch: char;
	    parola: stringa;
	    i: integer;
	    buffer: string(maxbuffer);
	    pbuffer: integer;

	begin
		i:=0;
		
		{apertura file}
		open (ingresso, nome_ingresso, OLD, RECORD_LENGTH := maxbuffer, CARRIAGE_CONTROL := NONE);
		reset(ingresso);
		
		while NOT eof (ingresso) DO
		begin
			readln(ingresso, buffer);
			pbuffer:=0;
			{writeln(buffer);
			writeln(buffer.length);
			readln(ch);}
				
		while pbuffer <= buffer.length do
			begin
				ch:=buffer[pbuffer];
				pbuffer:=pbuffer+1;
				
				if ch IN ['A','C','G','T'] then
					begin
						if(i<8) then {questo ciclo viene fatto solo all'inizio}
							begin
								i:=i+1;
								parola[i]:=ch;
								aggiungi_frequenza_alfabeto (radice_alfabeto, parola , 1);
							end
						else
							begin
								for i:=2 to 8 do
									parola[i-1]:=parola[i];
							
								parola[8]:=ch;
								aggiungi_frequenza_alfabeto (radice_alfabeto, parola , 1);
							end;
					end { if ch in a c g t }
				else
				if ch IN ['a','c','g','t'] then
					begin
						if(i<8) then {questo ciclo viene fatto solo all'inizio}
							begin
								i:=i+1;
								parola[i]:=chr(ord(ch)-32);
								aggiungi_frequenza_alfabeto (radice_alfabeto, parola , 1);
							end
						else
							begin
								for i:=2 to 8 do
									parola[i-1]:=parola[i];
							
								parola[8]:=chr(ord(ch)-32);
								aggiungi_frequenza_alfabeto (radice_alfabeto, parola , 1);
							end;
					end; { if ch in a c g t }			
			end; { while pbuffer<1024 }
		end; {while not eof}
		close(ingresso);
	end;

{mette un percorso a AAAAAAAAA}
procedure inizializza_percorso;
var i: integer;
	begin
		for i:=1 to 8 do
			percorso_corrente[i]:=0
	end;

procedure converti_e_copia(var stringa1: percorso; var parola: stringa; pos: integer);
var i: integer;
begin
	for i:=pos to 8 do
			begin
				if percorso_corrente[i-1] = 0 then
					parola[i]:='A';
				if percorso_corrente[i-1] = 1 then
					parola[i]:='C';
				if percorso_corrente[i-1] = 2 then
					parola[i]:='G';
				if percorso_corrente[i-1] = 3 then
					parola[i]:='T';
			end;
end;

	
procedure stampa_percorso;
	var tmp: stringa;
	    i: integer;
	begin
		converti_e_copia(percorso_corrente, tmp, 0);
		writeln(tmp);
	end;
	

      {prende il percorso_corrente e lo incrementa di uno}
function fornisci_percorso (lunghezza: integer): boolean;
	var riporto, i: integer;

	begin
		riporto:=1;
		if lunghezza=0 then
			fornisci_percorso:=false
		else
		begin
		fornisci_percorso:=true;
		for i:=7 downto (8-lunghezza) do
			begin
				if riporto = 1 then
					begin
					riporto:=0;
					{detect riporto incrementale}
					if percorso_corrente[i] = 3 then
						begin
							percorso_corrente[i]:=0;
							riporto:=1;
							{detect overflow}
							if i = 8-lunghezza then
								fornisci_percorso := false;
						end
					else
						percorso_corrente[i]:=percorso_corrente[i]+1;
					end; { if riporto }
			end; { ciclo for }
		end; {else}
	end; { main }
	
	
function esegui_percorso (var radice: albero_alfabeto; pos: integer):integer;
	begin	
			
		if pos < 8 then
			begin
				if percorso_corrente[pos] = 0 then
					begin
						{writeln('vado in A');}
						esegui_percorso:=esegui_percorso(radice^.figlioA, pos+1)
					end
				else
				if percorso_corrente[pos] = 1 then
					begin
						{writeln('vado in C');}
						esegui_percorso:=esegui_percorso(radice^.figlioC, pos+1)
					end
				else
				if percorso_corrente[pos] = 2 then
					begin
						{writeln('vado in G');}
				        	esegui_percorso:=esegui_percorso(radice^.figlioG, pos+1)
					end
				else
				if percorso_corrente[pos] = 3 then
					begin
						{writeln('vado in T');}
						esegui_percorso:=esegui_percorso(radice^.figlioT, pos+1);
					end
			end
		else
			begin
				esegui_percorso:= radice^.frequenza;
			end;
	end;

procedure esamina_sottoalbero (var radice:nodo_alfabeto; var albero_frequenza_jolly: albero_frequenza;
var posiz_jolly, livello:integer; var uscita_alfabeto: text; var parola: stringa);

          var somma,tmp: integer;
	
          begin	  {corpo di esamina_sottoalbero }
             parola [livello+1]:='_';
			
             { lavora nei 4 sottoalberi radicati nel nodo corrente: prendi un pattern attraverso "fornisci_percorso ( )"
               di lunghezza 8-jolly, rintraccialo nei rimanenti quattro sottoalberi radicati in figlioA, figlioC,
               filglioG, figlioT,computa la somma delle frequenze estratte dalle foglie ed inserisci nell'albero dei jolly.}

	     if posiz_jolly=8 then
	            begin
	              somma:=radice^.figlioA^.frequenza + radice^.figlioC^.frequenza+radice^.figlioG^.frequenza+radice^.figlioT^.frequenza;
		      	
		      {stampa parola con jolly e sua frequenza in ordine alfabetico}
                      {writeln ('JOLLY8 ',parola,'           ',radice^.frequenza);}
			if somma > 0 then
				begin
					writeln(uscita_alfabeto, parola,'       ',somma);
	       	      			aggiungi_parola_frequenza_jolly (albero_frequenza_jolly, parola, somma);
				end;
	           end
	     else	   	    	
	          repeat 
                        {Genera tutti i percorsi di lunghezza 8-jolly in un dominio di 4 caratteri}
			     begin	
			           somma:=0;
				   {writeln('JOLLY: A');}
			           somma:=esegui_percorso (radice^.figlioA, posiz_jolly);
				   {writeln('JOLLY: C');}	
                                   tmp:=esegui_percorso (radice^.figlioC, posiz_jolly);
			           somma:=somma+tmp;
				   {writeln('JOLLY: G');}
			           tmp:=esegui_percorso (radice^.figlioG, posiz_jolly);
			           somma:=somma+tmp;
				   {writeln('JOLLY: T');}
			           tmp:=esegui_percorso (radice^.figlioT, posiz_jolly);
			           somma:=somma+tmp;
			           {mette in parola il percorso corrente che si e' eseguito}
				
			           {stampa parola con jolly e sua frequenza in ordine alfabetico}
                                   {writeln ('fornisce percorso: ',parola,'           ',radice^.frequenza);}
			
				   if somma > 0 then
				   	begin
						converti_e_copia (percorso_corrente, parola, posiz_jolly+1);
						writeln(uscita_alfabeto, parola,'       ',somma);
			   	   		aggiungi_parola_frequenza_jolly (albero_frequenza_jolly, parola, somma);
					end;
			     end;
		  until NOT (fornisci_percorso (8-posiz_jolly));
           end;


 { Si tratta di creare un nuovo albero per la stampa in ordine di frequenza delle parole ottenute considerando il jolly.Prima di tutto devo
    conteggiare le frequenze dall'albero alfabetico. }
{ chiamala con livello zero nel main!!!}

procedure conteggia_in_albero_alfabetico (var radice:albero_alfabeto;var albero_frequenza_jolly:albero_frequenza;
var parola: stringa; posiz_jolly,livello: integer; var uscita_alfabeto: text);

{parametro albero_frequenza_jolly:albero_frequenza: albero temporaneo in cui si inseriscono le parole Jolly ordinate per frequenza }

   	{ Corpo della procedura "conteggia_in_albero_alfabetico" }
	begin
	
        if (livello< posiz_jolly-1) then
              begin
	         parola [livello+1]:='A';
	         conteggia_in_albero_alfabetico (radice^.figlioA, albero_frequenza_jolly, parola, posiz_jolly, livello+1, uscita_alfabeto);
	         parola [livello+1]:='C';
	         conteggia_in_albero_alfabetico (radice^.figlioC, albero_frequenza_jolly, parola, posiz_jolly, livello+1, uscita_alfabeto);
                 parola [livello+1]:='G';
                 conteggia_in_albero_alfabetico (radice^.figlioG, albero_frequenza_jolly, parola, posiz_jolly, livello+1, uscita_alfabeto);
	         parola [livello+1]:='T';
	         conteggia_in_albero_alfabetico (radice^.figlioT, albero_frequenza_jolly, parola, posiz_jolly, livello+1, uscita_alfabeto);
	      end
               else
		   {livello=posizione del Jolly-1: lavoro sui quattro sottoalberi}
	                 esamina_sottoalbero (radice, albero_frequenza_jolly, posiz_jolly, livello, uscita_alfabeto, parola);
	end;
	
	
procedure distruggi_albero_jolly (var radice:albero_frequenza);
      begin
      		if radice^.sx<> nil then
           		distruggi_albero_jolly ( radice^.sx);
			
		if radice^.dx<> nil then 
	   		distruggi_albero_jolly ( radice^.dx);  
		dispose (radice); 
      end;
		
{ CORPO DEL MAIN}
	
{

VER 1.0 - 15 Jen 2002
- TUTTI I REQUISITI SODDISFATTI
- UNA VOLTA INSERITO IL FILE DI INPUT VENGONO AUTOMATICAMENTE PRODOTTI I FILE DI OUTPUT CON TUTTI I JOLLY
- SE IL FILE INSERITO NON ESISTE IL PROG ESCE CON ERRORE
- SE IL FILE INSERITO NON CONTIENE NEMMENO UNA STRINGA DI 8 CARATTERI ABBIAMO SEG FAULT
- I FILE frequenza_jollyX.txt HANNO LA PARTE DOPO IL JOLLY -NON- IN ORDINE ALFABETICO
- LA LETTURA DA FILE AVVIENE CON UN BUFFER MASSIMO DI 255 CARATTERI (fase inizializza)

MODIFICHE 11 Jan 2002
- DISTRUGGI ALBERO JOLLY ORA FUNZIONA
- NELLA PROCEDURA ESAMINA SOTTOALBERO VENIVANO INSERITE ANCHE LE FREQUENZE NULLE

}
	
begin

writeln('GENOMA - VER 1.0 BETA - 15 JEN 2002 - CAMPIGOTTO/PEDROTTI');

{------ INIZIALIZZA -------------------------------------------------------------------------------}
	maxbuffer:=255;	{1..255}
	livello:=0;
	
	new (radice_alfabeto);
	inizializza_alfabeto(radice_alfabeto, livello);
	
	new (radice_frequenza);
	inizializza_frequenza(radice_frequenza);
	
	new (radice_jolly);
	inizializza_frequenza(radice_jolly);
	
	write('Inserisci nome file di input: ');
	readln(nome_file);
	
writeln('CARICAMENTO IN CORSO');

{------ CARICA IL FILE ----------------------------------------------------------------------------}
	leggi_file(nome_file);
		
writeln('CARICAMENTO TERMINATO!');
writeln('ELABORAZIONE IN CORSO');

{------ COSTRUSCE ALBERO FREQUENZA ----------------------------------------------------------------}
	{parola viene cancellata nella ricorsione}
	costruisci_frequenza_alfabeto(radice_alfabeto, radice_frequenza, parola, 1);

writeln('ELABORAZIONE TERMINATA!');
writeln('STAMPA SU FILE DEI RISULTATI');

{------ STAMPA ALFABETO ---------------------------------------------------------------------------}
	open (uscita, 'alfabeto.txt', NEW);
	rewrite(uscita);
	
	writeln('alfabeto.txt');

	stampa_alfabeto(radice_alfabeto, parola, 1, uscita);
	
        close(uscita);
	
{------ STAMPA FREQUENZA --------------------------------------------------------------------------}
	open (uscita, 'frequenza.txt', NEW);
	rewrite(uscita);
	
	writeln('frequenza.txt');

	{in questa chiamata facciamo saltare il nodo fittizio dell'albero}
	stampa_frequenza(radice_frequenza^.dx, uscita); 
	
	close(uscita);
		
{------ FASE JOLLY --------------------------------------------------------------------------------}
	
	for i:=1 to 8 do
	begin
		inizializza_percorso;
		
		nome_file:= 'alfabeto_jolly'+chr(i+ord('0'))+'.txt';
		open (uscita, nome_file, NEW);
		rewrite(uscita);	

		writeln(nome_file);

		conteggia_in_albero_alfabetico(radice_alfabeto, radice_jolly, parola, i, 0, uscita);

		close(uscita);
	
		nome_file:= 'frequenza_jolly'+chr(i+ord('0'))+'.txt';
		open (uscita, nome_file, NEW);
		rewrite(uscita);
	
		writeln(nome_file);

		stampa_frequenza(radice_jolly^.dx, uscita);
		
	     	distruggi_albero_jolly (radice_jolly^.dx);
		
		new (radice_jolly);
	        inizializza_frequenza(radice_jolly); 
		
		close(uscita);
	end;

	writeln('STAMPA TERMINATA!');
	
end.