Fondamenti di Informatica 1 - gr. 89 - a.a. 2005 - 2006
                    Prova di Programmazione - 16.12.2005

Coda Multipla con Rango
=======================
La coda multipla con rango (CMR) e' una sequenza di contenitori di oggetti con
modalita' di accesso FIFO (coda). Ogni coda nella CMR e' associata a un intero
non negativo, detto rango, che rappresenta il numero di code che la precedono
nella sequenza. La CMR sia definita dalla seguente classe:

public class CMR implements Container //-- Coda Multipla con Rango
{ // parte privata
  ...
  public CMR(int nc) {...}
  public void enqueueMin(Object obj) {...}
  public Object dequeueMax() throws EmptyQueueException {...}
  public void enqueue(Object obj, int k) {...}
  public Object dequeue(int k) throws EmptyQueueException {...}
  public CMR balance() {...}
  public String toString() {...}
}

Il costruttore CMR(int nc) inizializza una CMR contenente nc code vuote.
I metodi della classe eseguono le seguenti funzioni:
- enqueueMin(Object obj) accoda l'elemento obj nella coda minima (con il minor
  numero di elementi). Se piu' code sono minime, si scelga una qualsiasi;
- dequeueMax() estrae l'elemento in fronte alla coda massima (con il maggior
  numero di elementi). Se piu' code sono massime si scelga una qualsiasi.
- enqueue(Object obj, int k) accoda un elemento alla coda di rango k
- dequeue(int k) estrae e restituisce l'elemento in fronte alla coda di rango k
- balance() restituisce una CMR, con lo stesso numero di code della CMR
  originaria, le cui code contengono circa lo stesso numero di elementi
  (coda bilanciata), vuotando la CMR originaria. Piu' precisamente detti: n il
  numero di elementi e nc il numero di code nella CMR originaria, q = n/nc il
  quoziente intero e r = n%nc il resto della divisione allora:
  - r code contengono (q + 1) elementi e (nc - r) code contengono q elementi
  Esempio: se la CMR originaria contiene 7 elementi e 3 code, la CMR bilanciata
  ha 3 code di cui una contenente 3 elementi e due contenenti 2 elementi.
  Se in una coda della CMR bilanciata ci sono due elementi o1 e o2 provenienti
  da una stessa coda della CMR originaria e in questa o1 precede o2, allora
  nella coda della CMR bilanciata o1 dovra' precedere o2.
  Suggerimento per la realizzazione: sfruttare le proprieta' dei metodi
  dequeueMax() e enqueueMin().
- toString() override del metodo String toString() della classe Object;
  restituisce in una stringa il contenuto della CMR.

L'interfaccia Container sia la seguente:

public interface Container
{ boolean isEmpty();
  void makeEmpty():
}

Le code che compongono la CMR siano di classe CQueue:

public class CQueue implements Container, Comparable  // -- Coda Confrontabile
{ // parte privata
  ...
  public CQueue() {...}
  public void enqueue(Object obj) {...}
  public Object dequeue() throws EmptyQueueException {...}
  public String toString() {...}
}

Il criterio di comparazione in CQueue sia il numero di elementi delle code.
Il costruttore CQueue() inizializza una coda vuota.
Il metodo enqueue(Object obj) accoda l'elemento obj.
Il metodo dequeue() estrae e restituisce l'elemento in fronte alla coda.
Il metodo toString() restituisce una stringa contenente la descrizione testuale
degli elementi della coda.

Scrivere le parti private e pubbliche delle classi EmptyQueueExcepion, CQueue
e CMR.
All'atto della correzione il codice verra' provato nel seguente modo:
   $java TestCMR numeri.txt
dove il file numeri.txt e' allegato e la classe TestCMR e' la seguente:

import java.io.*;
import java.util.Scanner;

public class TestCMR
{ public static void main(String[] args) throws IOException
  { Scanner in = new Scanner(new FileReader(args[0]));
    CMR s = new CMR(3);

    while (in.hasNextLine())
    {  Scanner tok = new Scanner(in.nextLine());
       while (tok.hasNext())
         s.enqueue(tok.next(), 0); //inserimento nella coda di rango 0
    }
    in.close();
    System.out.println(s);  // stampa degli elementi della CMR originaria
    s = s.balance();        // bilanciamento delle code
    System.out.println(s);  // stampa degli elementi della CMR bilanciata
  }
}

Nell'esecuzione della prova si possono usare solo le classi dei pacchetti
java.lang e java.io e la classe java.util.Scanner. Non e' lecito aggiungere
metodi pubblici alle classi CQueue e CMR oltre a quelli definiti.
Alla fine della prova il candidato lascera' nella directory di lavoro i
seguenti file: CQueue.java, EmptyQueueException.java, CMR.java, Container.java,
TestCMR.java. I file dovranno contenere come prima riga un commento con nome e
cognome del candidato matricola, data, numero della postazione.

                   FONDAMENTI DI INFORMATICA I (gruppo 8-9)
                               a.a. 2004 - 2005

Cognome e Nome   ___________________________________

Matricola        ___________________________________

Corso di Laurea  ___________________________________

Postazione       ___________________________________


Consegno l'elaborato che consiste dei seguenti file:

_____________________________________________________

_____________________________________________________

_____________________________________________________


                Firma _______________________________


Non consegno l'elaborato e mi ritiro dall'esame.

                Firma _______________________________