La documentazione qui prodotta presenta il progetto dell'esame "Prova Finale - Progetto di Algoritmi e Strutture dati" del Politecnico di Milano, Anno Accademico 2019/2020.
L'obiettivo del progetto è quello di implementare un semplice editor di testo eseguibile da terminale, con le classiche funzionalità di aggiunta/rimozione di righe, la visualizzazione dell'intero documento (o parte di esso) e l'esecuzione di altri comandi, come undo e redo.
Il codice sorgente è stato sottoposto da un verificatore online a numerosi test, ciascuno focalizzato su specifiche funzionalità del programma. Obiettivo di questi test è quello di valutare la complessità dell'algoritmo sviluppato, in termini di utilizzo della memoria e di tempo di esecuzione.
A seguito di questi test è stato attribuito al progetto la valutazione di 30 e Lode.
I comandi, necessari per poter interagire con il programma, sono forniti al terminale tramite tastiera (stdin). Ciascun comando, per poter essere interpretato correttamente dall'editor di testo, deve rispettare la sintassi di seguito mostrata:
Il comando change cambia il contenuto delle righe di testo con indice compreso tra ind1 e ind2. Le (ind2-ind1)+1 righe devono essere inserite assicurandosi prima di essere andati a capo nel terminale. Se gli indici delle righe indicate non esistono ancora nel documento, il programma provvederà a inserire queste nuove righe in coda. Per terminare il comando è necessario inserire un punto '.' dopo aver scritto su terminale il contenuto di tutte le righe da modificare/aggiungere.
Esempio di utilizzo
1,3c
Prima riga del file di testo
Seconda riga del file di testo
Terza riga del file di testo
.
Il documento contiene ora le righe appena inserite.
Il comando delete cancella tutte le righe comprese tra ind1 e ind2 (estremi inclusi), modificando e portando a ind1 l'indice delle righe successive.
Esempio di utilizzo
2,3d
Il documento contiene ora una sola riga (Prima riga del file di testo).
Il comando print stampa a video (attraverso stdout) il contenuto delle righe comprese tra ind1 e ind2 (estremi inclusi). Se le righe non esistono queste vengono visualizzate con un punto '.'
Esempio di utilizzo
1,3p
Supponendo di aver già eseguito i comandi degli esempi precedenti, l'output sarà il seguente:
Prima riga del file di testo
.
.
(I punti visualizzati indicano che le righe 2 e 3 non esistono nel documento, poichè eliminate)
Il comando undo annulla l'effetto di un certo numero, indicato da number, di comandi di tipo change o delete precedentemente eseguiti. Se il numero indicato di comandi da annullare è superiore a quelli precedenemente eseguiti, vengono allora annullati tutti i passi ed il documento diventa vuoto.
Esempio di utilizzo
1u
Il documento, per effetto di una undo, contiene anche le due righe precedentemente eliminate.
Il comando redo annulla l'effetto di un certo numero di undo precedentemente eseguiti, indicato da number. Non è possibile eseguire la redo di comandi precedenti all'inserimento, modifica o cancellazione di righe nel file di testo.
Esempio di utilizzo
1r
Il documento, per effetto della redo, rettifica l'effetto della undo precedente ed elimina di nuovo le due righe che erano state ripristinate.
Il comando quit termina l'esecuzione dell'editor.
Durante la fase di progettazione e stesura del codice sono state considerate numerose strategie implementative, ciascuna di esse con diversi punti di forza e criticità.
E' stata individuata quindi una soluzione che ha consentito un buon bilanciamento tra complessità temporale e spaziale, attraverso l'utilizzo di una lista doppiamente concatenata (lista bidirezionale) e di due pile:
- Una prima lista concatenata Row serve per implementare la struttura logica delle righe di un documento;
- Due pile pilaUndo e pilaRedo di tipo Command per implementare le rispettive funzionalità di undo e redo di comandi.
L'algoritmo, in maniera molto semplificata, segue questi passi:
- Viene ricevuto da terminale il comando desiderato dall'utente, che viene decodificato individuandone il tipo di comando richiesto (c,d,p,u,r,q) ed eventuali parametri(ind1, ind2, number);
- Nel caso di un comando di tipo change o delete viene istanziato un nodo di tipo Command nella pila pilaUndo, che contiene al suo interno riferimenti ad eventuali righe aggiunte, modificate o eliminate. In questo modo risulta estremamente semplice effetuare una operazione di undo, nel caso in cui questa venga richiesta in futuro;
- Nel caso di un comando di tipo undo, viene preso dalla pila un determinato numero di nodi di tipo Command dalla pila pilaUndo, vengono processate le informazioni al loro interno e viene ripristinata la situazione desiderata dall'utente. I comandi precedentemente estratti da pilaUndo vengono poi inseriti, in ordine inverso nella seconda pila pilaRedo;
- Analogamente, viene eseguito il medesimo processo nel caso di un comando di tipo redo;
- Se il comando richiesto è di tipo print, infine, vengono stampate le righe richieste dall'utente procedendo con uno scorrimento sequenziale partendo dagli estremi del documento, arrivando all'indice di inizio desiderato.
L'utilizzo di una lista doppiamente concatenata permette l'accesso alle righe del documento partendo da due possibili estremi: un primo, che corrisponde all'inizio del documento; un secondo, che corrisponde invece all'ultima riga. In base alla posizione (indice) della riga desiderata è possibile decidere da dove iniziare lo scorrimento della lista, permettendo un notevole risparmio dei tempi di esecuzione nel caso in cui righe selezionate siano vicine agli estremi del documento.
Per compilare il programma è sufficiente scaricare il file Progetto.c nel proprio PC, raggiungere da terminale la directory in cui il file è salvato ed eseguire il seguente comando:
/usr/bin/gcc -DEVAL -std=gnu11 -O2 -pipe -static -s -o progetto progetto.c -lm
Infine, è possibile eseguire il programma digitando su linea di comando:
./progetto
Il progetto presenta tutte le funzionalità richieste dal documento di specifica. Non è stato possibile implementare funzionalità aggiuntive in quanto queste avrebbero potuto alterare l'output del programma, con conseguente fallimento dei test generati del verificatore.
Data la natura del verificatore non si è reso necessario il caricamento/salvataggio dei documenti da/in memoria di massa.
Il verificatore online, implementato dai docenti, ha effettuato test utilizzando input di ~250 MB e richiedendo un tempo massimo di esecuzione di 2,100s. Il progetto, nei worst case scenario, ha impegato al massimo 1,575 secondi per eseguire i comandi richiesti.
Per informazioni dettagliate su come è stata richiesta l'implementazione delle funzionalità del programma (ed il comportamento da seguire nei numerosi corner case) si veda il documento di specifica.