Fondamenti di Informatica 1 - a.a. 2005 - 2006
Simulazione della Prova di Programmazione - 28.11.2005

Pila Multipla con Rango
=======================
La pila multipla con rango e' una sequenza ordinata di contenitori di oggetti
con modalita' di accesso LIFO (stack).
Ogni stack nella pila multipla e' associato a un intero non negativo, detto
rango, che rappresenta il numero di stack che lo precedono nella sequenza.
La pila multipla con rango sia definita dalla seguente classe:

public class PMR implements Container //--Pila Multipla con Rango
{
  // parte privata
  ...
  
  public PMR(int k) {...}
  public void pushMin(Object obj) {...}
  public Object popMax() throws EmptyStackException {...}
  public void push(Object obj, int k) {...}
  public Object pop(int k) throws EmptyStackException {...}
  public PMR balance() {...}
  public String toString() {...}
}

Il costruttore PMR(int ns) inizializza una pila multipla composta da ns stack.
Ciascun stack e' inizialmente vuoto.
I metodi della classe eseguano le seguenti funzioni:
- pushMin(Object obj) inserisce l'elemento obj nello stack minimo ovvero lo
  stack con il minor numero di elementi. Se vi sono piu' stack minimi si
  scelga uno qualsiasi fra quelli minimi.
- popMax() estrae e restituisce l'elemento in cima allo stack massimo, ovvero
  lo stack con il maggior numero di elementi.  Se vi sono piu' stack masimi si
  scelga uno qualsiasi fra quelli massimi.
- push(Object obj, int k) inserisce un elemento in cima allo stack di rango k
- pop(int k) estrae e restituisce l'elemento in cima allo stack di rango k
- balance() restituisce una pila multipla, con lo stesso numero di stack della
  pila originaria (parametro implicito), i cui stack contengono tutti lo
  stesso numero di elementi (pila bilanciata), vuotando la pila originaria.
  Piu' precisamente detti: n il numero di elementi e ns il numero di stack
  nella pila multipla originaria, q = n/ns il quoziente intero e r = n%ns il
  resto della divisione n/ns allora:
  - r stack contengono (q + 1) elementi
  - (ns - r) stack contengono q elementi
  Gli elementi in ciascun stack della pila multipla bilanciata devono rispettare
  l'ordine di inserimento nella pila multipla originaria (parametro implicito).
  Esempio se la pila multipla originaria contiene 7 elementi e 3 stack, la pila
  multipla bilanciata e' formata dallo stesso numero di stack tre stack di cui
  uno contenente 3 elementi e due contenenti due elementi.
  Infatti q = 7/3 = 2, r = 7%3 = 1.
  Suggerimento: sfruttare le proprieta' dei metodi popMax() e pushMin().
  Attenzione all'ordine degli elementi negli stack bilanciati
- toString() override del metodo String toString() della classe Object.
  restituisce in una stringa il contenuto degli stack.
L'interfaccia Container sia la seguente:

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

Gli stack che compongono la pila multipla con rango siano di classe CStack,
cosi' definita:

public class CStack implements Container, Comparable  // --Stack Confrontabile
{
  // parte privata
  ...

  public CStack() {...}
  public void push(Object obj) {...}
  public Object pop() throws EmptyStackException {...}
  public String toString() {...}
}

Il criterio di comparazione degli oggetti della classe CStack sia il numero di
elementi contenuto negli stack stessi
Il costruttore CStack() inizializza uno stack vuoto
Il metodo push(Object obj) inserisce l'elemento obj in cima allo stack
Il metodo pop() estrae e restituisce l'elemento in cima allo stack
Il metodo toString() restituisce una stringa contenente la descrizione
testuale degli elementi dello stack.

Completare le classi PMR e CStack con le parti private e scrivere il codice
delle parti pubbliche.

All'atto della correzione il codice verra' provato nel seguente modo:
   $java TestPMR numeri.txt

La classe TestPMR e' riportata di seguito e il file numeri.txt e' allegato:

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

public class TestPMR  //--classe di prova
{ public static void main(String[] args) throws IOException
  { Scanner in = new Scanner(new FileReader(args[0]));
    PMR s = new PMR(3);

    while (in.hasNextLine())
    {  Scanner tok = new Scanner(in.nextLine());
       while (tok.hasNext())
         s.push(tok.next(), 0); //inserimento nello stack di rango 0
    }
    in.close();
    System.out.println(s);  // stampa degli elementi della pila multipla
    s = s.balance();        // bilanciamento degli stack
    System.out.println(s);  // stampa elementi della pila multipla bilanciata
  }
}

Nell'esecuzione della prova si possono usare solo le classi del pacchetto
java.io e la classe java.util.Scanner. Nelle classi CStack e PMRNon e' lecito
aggiungere  metodi pubblici oltre a quelli definiti.
Alla fine della prova lo studente dovra' lasciare nella directory di lavoro
i seguenti file:
- PMR.java
- CStack.java
- EmptyStackException.java
- Container.java
- TestPMR.java