Ricerca di un elemento in una matrice

Si realizzi un programma che lancia n thread per cercare un elemento in una matrice di n per n elementi. Ognuno dei thread cerca l'elemento in una delle righe della matrice. Non appena un thread ha trovato l'elemento cercato, rende note agli altri thread le coordinate dell'elemento e tutti i thread terminano.

La generazione della matrice su cui cercare gli elementi avviene mediante il codice:

        int [][] matrice = new int[n][n];
        Random generatore = new Random();
        for(int i=0;i<n;i++)
            for(int j=0; j<n; j++)
                matrice[i][j] = generatore.nextInt(1000);
        int ii = generatore.nextInt(n);
        int jj = generatore.nextInt(n);
        matrice[ii][jj] = 1001;

Inoltre, si realizzi il ciclo di ricerca di ogni thread con una sleep(100) all'interno di ognuna delle iterazioni, per rendere significativo il problema anche con piccoli valori di n.

Presentiamo una soluzione un cui:

• una classe Controllo supporta la terminazione dei thread
• una classe ThreadRicerca implementa la ricerca dell'elemento su una riga della matrice
• una classe Main lancia un numero di thread pari al numero di righe della matrice, dopo aver creato un sia la matrice che l'elemento Controllo.

Il codice della classe Controllo:

public class Controllo {

    public int i,j; // coordinate dell'elemento nella matrice
    private boolean trovato;

    Controllo() {
        i = -1;
        j = -1;
        trovato = false;
    }

    public synchronized boolean fine() {
        return(trovato);
    }

    public synchronized void fermalavori(int i, int j) {
        trovato = true;
        this.i = i;
        this.j = j;
    }

}

Come si vede, la classe mette a disposizione due metodi sincronizzati (e' dunque un monitor): uno per testare la codizione di terminazione e uno per settarla. Il metodo che setta la condizione di terminazione assegna anche alle variabili d'istanza gli indici dove e' stato trovato l'elemento cercato.

Il codice della classe ThreadRicerca:

public class ThreadRicerca extends Thread {

    private int indiceriga;
    private int[][] matrice;
    private int elemento;
    private Controllo flag;

    ThreadRicerca(int i, int[][] m, int e, Controllo f) {
        matrice = m;
        indiceriga = i;
        elemento = e;
        flag = f;
    }


    public void run() {
        this.setName((new Integer(indiceriga)).toString());
        int i;
        for(i=0;((i<matrice.length) && (!flag.fine()));i++) {
            System.out.println("Thread "+getName()+" cerca in "
                               +indiceriga+","+i);
            if(matrice[indiceriga][i] == elemento) {
                System.out.println("Thread "+getName()+" trovato in"
                                   +indiceriga+","+i);
                flag.fermalavori(indiceriga,i);
                return;
            }
            try {
                sleep(100);
            } catch(InterruptedException e) {}
        }
        System.out.println("Thread "+getName()+
                           " fermo dopo "+i+" iterazioni (su "+
                           matrice.length+" iterazioni previste)");
    }

}

Il ThreadRicerca viene inizializzato con i parametri che denotano la riga da ricercare, la matrice, l'elemento target e la struttura Controllo per la gestione della terminazione. Successivamente, all'esecuzione, inizializza il nome del thread con l'indice della riga su cui effettua la ricerca, e entra in un ciclo condizionato dalla lunghezza della riga e dalla condizione di terminazione. Se trova l'elemento lo segnala con una fermalavori e termina il ciclo. Altrimenti arriva in fondo alla riga.

Il codice della classe con il main:

import java.util.Random; 

public class Main {

    public static void main (String[] args) {
        int n;

        // dimensione della matrice
        try {
            n = Integer.parseInt(args[0]);
        } catch (ArrayIndexOutOfBoundsException e) {
            n = 100;
        }
        // generazione della matrice
        int [][] matrice = new int[n][n];
        Random generatore = new Random();
        for(int i=0;i<n;i++)
            for(int j=0; j<n; j++) 
                matrice[i][j] = generatore.nextInt(1000);
        int ii = generatore.nextInt(n);
        int jj = generatore.nextInt(n);
        matrice[ii][jj] = 1001;
        System.out.println("Il valore cercato sara' in posizione "+ii+","+jj);

        Controllo co = new Controllo();
        Thread[] ts = new Thread[n];
        System.out.println("Inizio");
        for(int i=0; i<n; i++) {
            ts[i] = new ThreadRicerca(i,matrice,1001,co);
            ts[i].start();
        }
        for(int i=0; i<n; i++) {
            try {
                ts[i].join();
            } catch(InterruptedException e) {}
        }
        System.out.println("Fine");
    }

}

Questo codice non fa altro che inizializzare la matrice, lanciare n thread e successivamente attendere la loro terminazione.