import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import static org.junit.jupiter.api.Assertions.assertEquals;
import java.util.Arrays;

import org.junit.jupiter.api.Test;

public class Lezione {

    /**
     * Metodo che prende in input un array a di interi e un intero x e restituisce la posizione di x
     * nell'array a se x appare nell'array a, -1 altrimenti.
     *
     * Scegliamo -1 come valore restituito nel caso x non venga trovato perchè -1 non è una
     * posizione valida, non verrebbe mai restituito normalmente. Un qualunque valore negativo
     * andrebbe bene, ma -1 è più standard.
     *
     * Questo metodo utilizza l'algoritmo di ricerca lineare (chiamata anche ricerca sequenziale).
     */
    public static int ricercaLineare(int[] a, int x) {
        /*
         * Scandisce l'array un elemento alla volta.. Se trova x esce immediatamente restituendo la
         * posizione in cui x è stato trovato
         */
        for (int i = 0; i < a.length; i++) {
            if (a[i] == x)
                return i;
        }
        /*
         * Se il ciclo for termina normalmente, vuol dire che x non l'abbiamo trovato e restituiamo
         * -1.
         */
        return -1;
    }

    /**
     * Metodo che prende in input un array a di interi e un intero *ORDINATO* x e restituisce la
     * posizione di x nell'array a se x appare nell'array a, -1 altrimenti.
     *
     * Scegliamo -1 come valore restituito nel caso x non venga trovato perchè -1 non è una
     * posizione valida, non verrebbe mai restituito normalmente. Un qualunque valore negativo
     * andrebbe bene, ma -1 è più standard.
     *
     * Questo metodo utilizza l'algoritmo di ricerca binaria, che è molto più efficiente di quello
     * lineare ma richiede che a sia ordinato.
     */
    public static int ricercaBinaria(int[] a, int x) {
        /*
         * Le variabili min e max contengono, in ogni momento, la posizione del primo elemento
         * dell'array e dell'ultimo elemento dell'array dove è potenzialmente possibile trovare x.
         * All'inizio x potrebbe essere ovunque.
         */
        int min = 0;
        int max = a.length - 1;
        /*
         * Finché min e minore o uguale a max, vuol dire che è possibile ancora trovare l'elemento
         * x. Se invece min > max, vuol dire che non c'è più nessuna posizione dell'array a in cui x
         * si può trovare: possiamo uscire dal ciclo e restituire -1.
         */
        while (min <= max) {
            /* Calcolo la posizione centrale tra min e max. */
            int pos = (min + max) / 2;
            /* Se ho trova l'elemento x, esco restituendo la posizione */
            if (a[pos] == x)
                return pos;
            /*
             * ...altrimenti, sfruttando il fatto che a è ordinato, modifico le variabili min e max
             * che mi dicono in quale zona dell'array posso trovare x.
             */
            else if (a[pos] > x)
                /*
                 * in particolare, se l'elemento in posizione corrente contiene un numero maggiore
                 * di x, ovviamente si deve trovare nelle posizioni antecedenti a pos, e quindi
                 * aggiorno max con pos-1.
                 */
                max = pos - 1;
            else // a[pos] < x, ma la condizione è ridondante e quindi non la mettiamo
                /**
                 * analogamente se a[pos] < x
                 */
                min = pos + 1;
        }
        return -1;
    }

    /**
     * Metodo che prende in input un array a di interi a, e ordina questo array dal numero più
     * piccolo al numero più grande. Usa l'algoritmo di ordinamento per selezione (selection sort in
     * inglese).
     */
    public static void ordina(int[] a) {
        /*
         * Questo ciclo scandisce le posizioni dell'array.
         */
        for (int i = 0; i < a.length; i++) {
            /*
             * Quando il programma raggiunge questo punto, indipendentemente dalla iterazione, vale
             * sempre questa condizione: gli elementi da a[0] ad a[i-1] sono in ordine, e sono tutti
             * più piccoli degli elementi da a[i] in poi. Questa condizione si chiama invariante del
             * ciclo.
             *
             * Compito del corpo del ciclo for è trovare l'elemento minimo negli elementi da a[i] in
             * poi, e scambiarlo con a[i], in maniera tale che alla iterazione successiva, in modo
             * che l'invarianta sia rispettato anche alla prossima iterazione.
             */

            /*
             * Il codice che segue determina la posizione in cui si trova il minimo degli elementi
             * a[i], a[i+1], .... a[a.length - 1].
             */
            int posmin = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[posmin])
                    posmin = j;
            }

            /*
             * Scambiamo a[i] con a[posmin] (ricordiamo che a[posmin] è il minimo degli elementi da
             * a[i] in poi).
             */
            int tmp = a[i];
            a[i] = a[posmin];
            a[posmin] = tmp;
        }
    }


    /**
     * Inseriamo anche dei test per provare il funzionamento del programma. Si ricordi che per far
     * funzionare i test in VSCode bisogna prima attivarli.
     */

    @Test
    void testRicercaLineare() {
        int[] v = {56, 22, 293, 122, 1, -4, 12};
        assertEquals(1, ricercaLineare(v, 22));
        assertEquals(-1, ricercaLineare(v, 3));
        assertEquals(-1, ricercaLineare(new int[0], 2));
    }

    @Test
    void testRicercaBinaria() {
        int[] v = {-4, 1, 12, 22, 56, 122, 293};
        assertEquals(3, ricercaBinaria(v, 22));
        assertEquals(-1, ricercaBinaria(v, 3));
        assertEquals(-1, ricercaBinaria(new int[0], 2));

    }

    @Test
    void testOrdinamento() {
        int[] v = {56, 22, 293, 122, 1, -4, 12};
        int[] vordinato = {-4, 1, 12, 22, 56, 122, 293};
        /*
         * Notare che il metodo ordina non restituisce nulla, ma modifica il vettore v che gli
         * viene passato in input.
         */
        ordina(v);
        assertArrayEquals(vordinato, v);
    }

}