Fondamenti di Informatica 1 - gr. 89
               Prova di Programmazione del 10.01.2007 - a.a. 2006 - 2007
CODA MULTIPLA
=============
L'interfaccia CQueue, allegata, definisce un contenitore di elementi
comparabili, con modalita' di accesso FIFO:

public interface CQueue  // --Interfaccia CQueue
{ boolean isEmpty();
  int size();
  void enqueue(Comparable x);
  Object dequeue() throws EmptyQueueException;
}
dove:
- boolean isEmpty() restituisce true se la coda e' vuota, false altrimenti:
- int size() restituisce il numero di elementi presenti nella coda;
- void enqueue(Comparable x): accoda l'elemento comparabile x;
- Object dequeue(): lancia l'eccezione EmptyQueueException se la coda e' vuota,
  altrimenti restituisce, estraendolo, l'elemento in testa alla coda.

La seguente classe Q realizza l'interfaccia CQueue:

public class Q implements CQueue // --Coda di Elementi Comparabili
{ // parte privata
  ...
  // parte pubblica
  public Q();
  public String toString() {...}
  public Comparable[] toSortedArray() {...}
}
dove:
- il costruttore inizializza una coda vuota;
- String toString() restituisce la descrizione testuale della coda, un elemento
  per riga, in sequenza FIFO, in modo che il primo elemento sia l'elemento in
  testa alla coda;
- Comparable[] toSortedArray() restituisce gli elementi comparabili della coda
  in un array ordinato in senso crescente, secondo il loro ordine naturale.

La Coda Multipla e' un contenitore di code disposte in sequenza. Ciascuna coda
e' associata a un numero intero non negativo, detto rango, che e' pari al
numero di code che la precedono nella sequenza. Esempio: la coda di rango 0 e'
la prima coda della sequenza (e' preceduta da zero code), mentre la coda di
rango 1 e' la seconda coda della sequenza (e' preceduta da una coda).
La seguente classe QM definisce la Coda Multipla:

public class QM // --Coda Multipla
{  //parte privata
   ...
   //parte pubblica
   public final int length;
   public QM(int n) {...}
   public void enqueue(Comparable x, int k) {...}
   public Object dequeue(int k) {...}
   public String toString(int k) {...}
   public Comparable[] toSortedArray() {...}
}
dove:
- la variabile length vale il numero di code contenute nella coda multipla;
- il costruttore QM(int n) inizializza il contenitore con n code vuote;
- enqueue(Comparable x, int k) accoda l'elemento x nella coda di rango k se
  k < length, altrimenti genera l'eccezione java.lang.IndexOutOfBoundsException;
- dequeue(int k) k < length restituisce, estraendolo, l'elemento in testa alla
  coda di rango k; altrimenti genera l'eccezione IndexOutOfBoundsException;
- toString(int k) se k < length restituisce la descrizione testuale della coda
  di rango k, altrimenti genera l'eccezione IndexOutOfBoundsException;
- toSortedArray() restituisce un array contenente tutti gli elementi della
  coda multipla, ordinati in senso crescente secondo il loro ordine naturale
  (NB: si usi il metodo toSortedArray() della classe Q).

Il candidato scriva la parte privata e completi la parte pubblica delle classi
EmptyQueueException, Q e QM.

In sede di correzione il codice sara' provato con i comandi:
   $rm *.class
   $javac ProvaQM.java
   $java ProvaQM < testo.txt
dove: testo.txt e' il file di testo allegato. La classe di prova ProvaQM,
allegata, e' la seguente:

import java.util.Scanner;
public class ProvaQM  // --Classe Di Prova
{ public static void main(String[] args)
  { QM qm = new QM(5);                //definizione di Coda Multipla con 5 code
    //acquisizione stringhe da standard input
    Scanner in = new Scanner(System.in);
    for (int k = 1; in.hasNextLine(); k++)
    { Scanner tk = new Scanner(in.nextLine());     //lettura della riga k-esima
      while (tk.hasNext())              //separazione parole della riga k-esima
        qm.enqueue(tk.next(), k - 1);   //e accodamento nella coda di rango k-1
      tk.close();
    }
    in.close();
    //stampa delle singole code della Coda Multipla
    for (int i = 0; i < qm.length; i++)                     //stampa delle code
    { System.out.println("*** STAMPA DELLA CODA DI RANGO " + i + " ***");
      System.out.println(qm.toString(i));
    }
    //stampa degli elementi della Coda Multipla in ordine crescente
    System.out.println("*** STAMPA DEGLI ELEMENTI IN ORDINE CRESCENTE***");
    Comparable[] a = qm.toSortedArray();
    for (int i = 0; i < a.length; i++)
      System.out.println(a[i]);
  }
}
ed esegue le seguenti funzioni:
- definisce una coda multipla con 5 code;
- acquisisce un insieme di righe da standard input;
- separa le parole di ciascuna riga, inserendo nella coda di rango k - 1 le
  parole contenute nella riga k;
- stampa nella sequenza FIFO le code della Coda Multipla
- stampa tutti gli elementi della Coda Multipla in ordine crescente

Nella realizzazione delle classi Q e QM non e' lecito:
- aggiungere elementi, se non privati;
- usare classi della libreria standard, ad eccezione di quelle dei package
  java.lang e java.io e delle classi java.util.Scanner e NoSuchElementException.

Alla fine della prova il candidato lascera' nella directory di lavoro i file
eventualmente prodotti: EmptyQueueException.java, Q.java, QM.java
e i file allegati dal docente: ProvaQM.java, CQueue.java, testo.txt.
I file prodotti dal candidato dovranno contenere come prima riga un commento
con nome e cognome, matricola, data, numero della postazione.

-------------------------------------------------------------------------------
Cognome   ______________________________ Nome _________________________________

Matricola _______________ Corso di Laurea _______________ Postazione __________
-------------------------------------------------------------------------------
Consegno l'elaborato che consiste dei seguenti file (contrassegnare con X):

[] Q.java        [] QM.java              Firma ________________________________
[] EmptyQueueException.java
-------------------------------------------------------------------------------
Non consegno l'elaborato e mi ritiro
dall'esame.                              Firma ________________________________
-------------------------------------------------------------------------------