Implementazione del File System tramite una coda circolare

• Implementare una coda con un buffer circolare È possibile implementare una coda tramite un array circolare nel seguente modo. Il buffer circolare è costituito da un array e due variabili intere che tengono rispettivamente traccia della prima posizione libera (la prossima ad essere occupata a seguito di un'inserzione) e della prima occupata (la prossima ad essere liberata a seguito di un'estrazione); le due variabili si chiamano rispettivamente head e tail. Ricordiamo che la coda è una struttura con gestione FIFO (first in first out), quindi il primo elemento ad essere inserito è anche il primo ad essere estratto.
  Cerchiamo di capire -in modo intuitivo- come deve essere gestito il buffer circolare. Nelle figure successive, l'array è arrotolato a mo' di ciambella per vedere come i due indici scorrono lungo il medesimo e a tratti apparentemente si invertono; i numeri corrispondono agli indici delle diverse caselle.

  

  Quando il buffer è vuoto, head e tail concidono (figura in alto a sinistra).
  Quando si inserisce il primo elemento, head viene fatto avanzare di una posizione (figura in alto a destra), dimodoché continui a puntare ad una casella vuota.
  Quando si cancella un elemento, l'indice tail viene fatto avanzare di una posizione.

  In un generico istante di utilizzo della coda, a seguito di alcune inserzioni ed alcune estrazioni, potremo avere la seguente situazione:

  

  solo una porzione dell'array è occupata; genericamente si tratterà di una porzione interna all'array (cioè gli estremi non coincideranno con gli estremi del vettore).
  Supponiamo che ad un certo punto la situazione sia la seguente:

  

  e che desideriamo inserire un ulteriore elemento. Ciò deve essere possibile, in quanto l'array è parzialmente vuoto. In particolare head punta ad una casella libera, la posizione 7. Quale valore assumerà head a seguito dell'inserzione? L'idea che deve essere implementata è che esso diventi uguale a 0 (zero) perché nella gestione circolare tale posizione segue la posizione numero 7 (in generale, gli estremi del vettore sono immaginati essere successivi). Praticamente questo risultato può essere ottenuto utilizzando l'operatore modulo (simbolo: %) rispetto alla dimensione dell'array. Nel caso in esame il risultato sarà:

  

  In generale sarà quindi lecita anche la seguente situazione:

  

  in cui head vale 2 e tail vale 6!! La vostra implementazione deve quindi essere in grado di gestire questa configurazione.

• Implementazione :
  La struttura descritta dovrà essere implementata in una classe chiamata FileSystemQueue.
  Si tratterà di una coda di istanze della classe FileDescriptor, già realizzata in un precedente esercizio.

  La classe FileSystemQueue deve prevedere le seguenti variabili d'istanza:
  

  • private FileDescriptor [] coda: array di oggetti della classse FileDescriptor (il buffer)
  • private int dim: dimensione dell'array -non obbligatoria perché si può risalire al suo valore in altro modo-
  • private int head: indice all'elemento in testa alla coda
  • private int tail: indice all'elemento in coda alla struttura

  Deve inoltre fornire i seguenti metodi:
  

  • public boolean isEmpty(): restituisce true se la coda è vuota
  • public boolean isFull(): restituisce true se la coda è piena
  • public void add(FileDescriptor el): inserisce l'oggetto el in testa alla coda (nella posizione identificata da head).
    N.B.: l'inserzione può avvenire solo se c'è una casella libera a disposizione;
  • public FileDescriptor getHead(): consente l'accesso all'elemento in testa alla coda (posizione identificata dall'indice head - 1) senza rimuoverlo da essa;
  • public FileDescriptor remove(): estrae e restituisce l'elemento in fondo alla coda;
  • public void print(): stampa a video la coda (da tail a head).
• Gestire le eccezioni

  Nella classe FileSystemQueue i metodi che possono fallire devono sollevare eccezioni, ad es.:

  throw new QueueEmptyException(...) quando si riscontra un tentativo di accedere agli elementi di una coda vuota.

  In particolare occorre definire le seguenti eccezioni:

  • QueueEmptyException: per poter gestire i casi di coda vuota
  • QueueFullException: per poter gestire i casi di coda piena