/*
 * Bandiera.java - questo programma risolve il problema 4.7 p. 116 di
 * Demetrescu, Finocchi, Italiano, "Algoritmi e strutture dati"
 * (seconda edizione), McGraw-Hill, 2008.
 *
 * Il problema della bandiera nazionale e' definito nel modo seguente:
 * Sia A un array di dimensione n, i cui elementi possono assumere
 * solo uno di tre possibili colori: bianco, verde e rosso. Vogliamo
 * ordinare l'array in modo che tutti gli elementi verdi precedano
 * quelli bianchi, e gli elementi bianchi precedano quelli
 * rossi. L'algoritmo deve richiedere tempo O(n) nel caso peggiore,
 * puo' solo scambiare elementi e non deve usare altri array
 * temporanei di appoggio. Non puo' nemmeno utilizzare contatori per
 * tenere traccia del numero di elementi di un certo colore presenti
 * (quindi non si puo' usare una variante dell'algoritmo counting
 * sort, che vedremo a lezione). L'algoritmo, infine, deve ordinare
 * gli elementi facendo una singola scansione dell'array. Assicurarsi
 * che l'algoritmo funzioni anche se mancano elementi di qualcuno dei
 * colori.
 *
 * Version 0.3 del 2009/11/25
 * Autore: Moreno Marzolla (marzolla (at) cs.unibo.it)
 *
 * This file has been released by the author in the Public Domain
 */
public class Bandiera {

    public static final int VERDE = 1;
    public static final int BIANCO = 2;
    public static final int ROSSO = 3;

    /**
     * Scambia tra di loro gli elementi A[i] e A[j]. Attenzione:
     * nessun controllo viene effettuato circa la validita' degli
     * indici i e j.
     */
    protected static void swap( int[] A, int i, int j ) 
    {
	System.out.println("Scambia "+i+" con "+j);
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }

    /**
     * Stampa a video il contenuto dell'array A
     */
    public static void stampa( int[] A )
    {
        for( int i=0; i<A.length; ++i ) {
            System.out.print(A[i]);
            System.out.print(" ");
        }
        System.out.println();
    }

    /**
     * Risolve il problema della bandiera nazionale: ordina l'array
     * A[] (che puo' contenere solo i valori 1=VERDE, 2=BIANCO,
     * 3=ROSSO) in una unica passata. 
     *
     * Questo metodo ha complessita' Theta(n).
     */
    public static void ordina( int[] A )
    {
        int n = A.length; // numero elementi de
        int v = 0; // Prima posizione in cui si puo' inserire un elemento verde
        int i = 0; // Prima posizione in cui si puo' inserire un elemento bianco
        int r = A.length-1; // Prima posizione in cui si puo' inserire un elemento rosso

        /**
         * L'algoritmo mantiene le seguenti invarianti:
         *
         * 1. Gli elementi A[0]...A[v-1] sono verdi (se v=0, non ci
         * sono elementi verdi);
         *
         * 2. Gli elementi A[v]..A[i-1] sono bianchi (se i==v, non ci
         * sono elementi bianchi);
         *
         * 3. Gli elementi A[r+1]..A[n-1] sono rossi (se r==n-1, non
         * ci sono elementi rossi);
         *
         * 4. Gli elementi A[i]...A[r] possono essere di qualsiasi colore
         *
         * Ad ogni iterazione, l'algoritmo esamina A[i], effettuando
         * opportuni scambi per spostare l'elemento nella posizione
         * corretta. Ad ogni iterazione, i viene incrementato OPPURE r
         * viene decrementato. Cio' assicura che sia garantita la
         * terminazione dell'algoritmo.
         */
        while( i<= r ) {
	    if ( BIANCO == A[i] ) {
		i++;
	    } else {
		if ( VERDE == A[i] ) {
		    swap( A, v, i );
		    v++;
		    i++;
		} else { // A[i] e' rosso 
		    swap( A, i, r );
		    r--;
		} 
	    }
	}
    }

    public static void main( String[] args )
    {
        int p1[] = {1, 2, 3, 1, 3, 1, 2, 3, 3, 1, 1, 2, 3, 1, 1 };
	Bandiera.ordina(p1);
	Bandiera.stampa(p1);
	int p2[] = {1, 1, 1, 1};
	Bandiera.ordina(p2);
	Bandiera.stampa(p2);
	int p3[] = {2, 2, 2, 2};
	Bandiera.ordina(p3);
	Bandiera.stampa(p3);
	int p4[] = {3, 3, 3, 3};
	Bandiera.ordina(p4);
	Bandiera.stampa(p4);
	int p5[] = {3, 1, 1, 3, 1, 3};
	Bandiera.ordina(p5);
	Bandiera.stampa(p5);
        int p6[] = {3, 3, 3, 2};
        Bandiera.ordina(p6);
        Bandiera.stampa(p6);
    }
}