2° compitino laboratorio II 24/25

[peppescala]

Si utilizzi la struttura

typedef struct terna {
int x,y,z;
struct terna *left, *right;
} terna;
per rappresentare il nodo di un albero binario di ricerca (ABR) contenente una terna di interi nei campi x, y, e z.

Importante: il vostro codice deve utilizzare le funzioni base per la manipolazione delle terne contenute in terne.c e terne.h. In particolare l'ABR deve usare come funzione di ordinamento terna_confronta che confronta gli elementi delle terne nell'ordine z, y, x. Quindi la terna 10 3 1 precede la terna 1 2 3 in quanto la componente z della prima terna è più piccola. Se le componenti z sono uguali si confronta la componente y (quindi 20 2 13 è minore di 2 3 13) e se anche le componenti y sono uguali si confronta la componente x (quindi 2 10 20 è minore di 3 10 20).

Non importa in quale modo organizzate i file sorgenti e il makefile ma è obbligatorio che usiate le funzioni definite in terne.c e non altre, e che la compilazione venga fatta con le opzioni std=c11 -Wall -O -g.

L'albero binario di ricerca per le terne deve supportare le funzioni di inserimento ricerca e visita in in-order più eventuali altre funzioni necessarie per lo svolgimento dell'esercizio. Dovete seguire la convenzione fatta a lezione che nell'abero non vengono mai inseriti elementi duplicati (cioè terne uguali).

Il makefile deve essere scritto in modo che scrivendo

makefile pitagora
venga generato l'eseguibile pitagora che svolge le seguenti operazioni. Scrivendo sulla linea di comando

pitagora nomefile s1 s2... sk

dove s1 s2... sk sono dei valori interi, il programma deve leggere le terne contenute in nomefile e memorizzarle nell'ABR. Successivamente deve: * stampare su stdout il numero di nodi dell'albero ottenuto * per i=1..k stampare su stdout il numero di terne nell'albero la cui somma è uguale all'intero si

Questi valori devono essere stampati uno per riga senza frasi esplicative; ad esempio se si esegue comando pitagora small 10 12 14 16 su stdout deve essere scritto

7
0
2
1
0
in quanto il file small contiene 7 terne distinte, di cui nessuna ha somma 10, due terne hanno somma 12, una terna ha somma 14 e nessuna ha somma 16.

Successivamente, il programma deve scrivere nel file nomefile.pit l'elenco delle terne dell'ABR che sono terne pitagoriche, cioè per cui vale
𝑥2+𝑦2=𝑧2
Importante: per calcolare il quadrato di una variabile x scrivete x*x, NON x**2 o x^2 (la seconda espressione compila ma calcola un'operazione bitwise che non c'entra con il quadrato).

Le terne devono essere stampate in ordine crescente: in pratica dovete fare una visita dell'albero in in-order e scrivere su file solo le terne pitagoriche. Anche in questo caso scrivete una terna per riga (usando la funzione terna_stampa in terne.c) senza commenti. Ad esempio, quando viene passato come argomento il file small il corrispondete file small.pit dovrebbe contenere solamente le due righe

3 4 5
12 5 13
che sono le terne pitagoriche contenute in small (si noti l'ordine: 3 4 5 precede 12 5 13 in quanto 5<13).

Il programma deve scrivere su stdout solamente i valori indicati sopra: ogni altra informazione e i messaggi di debug devono essere scritti su stderr. Prima di terminare il programma deve chiudere tutti i file e deallocare tutta la memoria utilizzata (usare valgrind, per la verifica).

Lettura delle terne. Le terne sono memorizzate in file di testo in un formato particolare:

ogni linea del file può memorizzare una singola terna
i valori delle terne sono espressi con sequenze del carattere - separate da un numero arbitrario di caratteri : o ; e tali caratteri possono apparire anche prima o dopo le sequenze di -. Ad esempio le linee :-:--:--:, -:;;:--;--:;, -;--;::-- sono tre modi possibili per esprimere la terna 1 2 2
se una linea contiene dei caratteri diversi da -, :, ;, e naturalmente \n, tale linea va ignorata
l'ultima regola è che se una linea contiene un numero di sequenze di - diverso da 3 (ad esempio :-;-- o -;-;-;-) tale linea va ignorata.
Tenuto conto di queste regole, consiglio di leggere le terne con la seguente procedura

usare getline per leggere una linea alla volta
eseguire una scansione della linea e se si trovano caratteri diversi da -:;\n passare alla linea successiva
utilizzare la funzione strtok per tokenizare la linea in modo che ogni token consista in una sequenza del solo carattere - e utilizzare strlen per ottenere il valore rappresentato da quella sequenza (si noti che i valori nelle terne saranno tutti positivi). Se effettuando la tokenizzazione risulta che ci sono meno un numero di sequenze diverso da 3, passare alla linea successiva.
Utilizzare i file small, t5, e t20 per testare il vostro codice. L'output che deve essere inviato su stdout si trova nei file con estensione .out e le terne pitagoriche da scrivere nei file .pit si trovano nei file .ris. Questi test vengono fatti automaticamente dando il comando python3 terne_test.py.