Dalle specifiche non ho ricavato molti spunti: era chiaro quello che si doveva fare. Si trattava di calcolare il valore di una cella visitando il suo albero di valutazione costruito dal parser, individuare se le celle avessero dei riferimenti ciclici ed eventualmente marcarle come errate. Una seconda parte consisteva nel ricalcolare le celle che venivano modificate e tutte le celle che facevano riferimento a quest'ultime.
Le specifiche non suggerivano pero' il modo in cui operare. Ho percio' pensato ad ottenere buone prestazioni nel calcolo delle celle non considerando affatto l'occupazione di memoria (questo perche' Java e' gia' sufficentemente lento). Questa idea, che mi sembra tuttora la migliore, non l'ho affatto seguita inizialmente: il primo algoritmo per il calcolo delle celle occupava pochissima memoria (allocava solo una cella per volta) ma durante la fase di verifica e testing mi sono accorto che la procedura era di complessita' lineare nel caso migliore (senza contare la valutazione dell'albero) ma nel caso peggiore aveva complessita' n!.
Sono percio' ritornato alla fase di analisi per vedere di migiorare questa situazione che era inaccettabile. Della vecchia procedura ho potuto riutilizzare molto poco e percio' non ho potuto completare il ricalcola. La seconda versione dell'algoritmo procede in tempo linare sempre ma alloca molta memoria (nel caso peggiore tutte le celle che devono essere valutate) in quanto e' ricorsivo cioe' se non riesce a valutare una cella perche' dipende da un'altra si lancia il calcolo su quest'ultima.
L'algoritmo per la rilevazione di cicli e' invece molto buono perche' durante la fase di preanalisi abbiamo subito adottato una strategia (i colori) che mi ha permesso di rendere il codice efficente (tempo lineare per individuarlo e marcare le celle interessate).
Durante la fase di analisi sono stati sviluppati i seguenti documenti che sono serviti a concretizzare le idee esposte:
Diagramma delle classi
Modello funzionale per il calcolo
Modello funzionale per il ricalcolo
Gli algoritmi sono tutti molto semplici ed efficenti:
Algoritmo per il calcolo di una cella
Quando si lancia il calcolo di una cella la procedura visita l'albero partendo dalla radice (contenuto in un campo della cella) ed esegue le operazioni in esso specificate. Se si trova un riferimento ad un'altra cella si accede ad essa, si controlla il suo stato (colore): se e' Corretta si preleva il suo valore e si prosegue con la valutazione, se e' NonCalcolata si lancia la procedura di calcolo su quest'ultima, se e' Errata si marca errata anche la cella che si stava valutando. Come si vede nel caso si incontri una cella non ancora calcolata si procede al suo calcolo lasciando in sospeso quello della cella precedente ed occupando cosi' memoria in eccesso.
Tale strategia permette in contemporanea di individuare i cicli infatti quando si lancia il calcolo della sottocella si marca la cella che si stava valutando come visitata percio' se si fa di nuovo riferimento ad essa durante i vari sottocalcoli (la cella non e' ancora valutata) si trova che e' gia' stata visitata e percio' c'e' un ciclo. Al ritorno della ricorsione non si fa altro che marcare tutte le celle su questo cammino come Errate. Tutte le celle che faranno riferimento ad una cella nel ciclo sono anch'esse errate.
Algoritmo per il ricalcolo
Durante la fase di calcolo di una cella si inseriscono in una lista (Vector) i riferimenti delle celle che, per essere valutate, necessitano del risultato della cella in esame. Praticamente sono dei riferimenti al contrario: ogni cella sa quali sono le celle che dipendono da lei.
Originariamente ogni cella conteneva i riferimenti alle celle che le servivano per essere valutata ma questo comportava che per sapere quali celle si dovevano ricalcolare si dovesse scandirle tutte piu' volte. Per questo ho preferito usare i riferimenti "al contrario" che consentono di ricalcolare solo le celle che vengono effettivamente interessate dalla modifica. Se si nota il numero di riferimenti mantenuti con le due strategie e' lo stesso ma il risultato e' notevolmente diverso.
Anche questo algoritmo e' ricorsivo e si limita semplicemente a richiamare il parser sulla cella modificata e a marcare come NonCalcolata le celle che sono interessate da quest'ultima. Bastera' poi rilanciare la procedura calcola per riottenere la valutazione corretta (si poteva calcolarle subito ma questa strategia favorisce il ricalcolo manuale).
NOTA: se la cella modificata fa parte di un ciclo tutte le celle del ciclo sono marcate come da ricalcolare in quanto e' possibile che proprio questa modifica abbia interrotto il ciclo.
