/**
 * Questa classe esegue alcuni esperimenti sugli algoritmi di ricerca e ordinamento per verificarne
 * le prestazioni.
 */
import java.util.Arrays;
import java.util.Collections;

public class Algorithms {

    /**
     * Determina se la stringa x è presente nell'array a. Restituisce la posizione in cui si trova
     * la stringa se presente, -1 se non è presente. È semplicemente una variante del metodo
     * Lezione.ricercaLineare che funziona per array di stringhe invece che per array di interi.
     */
    public static int linearSearch(String[] a, String x) {
        for (int i = 0; i < a.length; i++) {
            /* Notare l'uso del metodo equals invece di == per confrontare due stringhe. */
            if (a[i].equals(x))
                return i;
        }
        return -1;
    }

    /**
     * Determina se la stringa x è presente nell'array a. Restituisce true se è presente, false
     * altrimenti. L'array a DEVE essere ordinato. È semplicemente una variante del metodo
     * Lezione.ricercaBinaria che funziona per array di stringhe invece che per array di interi.
     */
    public static int binarySearch(String[] a, String x) {
        int min = 0;
        int max = a.length - 1;
        while (min <= max) {
            int pos = (min + max) / 2;
            /*
             * Notare l'uso del metodo compareTo invece degli operatori > e < per confrontare due
             * stringhe. L'espressione "a[pos].compareTo(x)" restituisce 0 se a[pos] è uguale ad x,
             * un numero positivo se a[pos] è maggiore di x (nel senso che a[pos] viene dopo x in
             * ordine alfabetico) e un numero negativo se a[pos] è minore di x (a[pos] viene prima
             * di x in ordine alfabetico).
             */
            int comp = a[pos].compareTo(x);
            if (comp == 0)
                return pos;
            else if (comp > 0)
                max = pos - 1;
            else if (comp < 0)
                min = pos + 1;
        }
        return -1;
    }

    /**
     * Ordina l'array a. È semplicemente una variante del metodo Lezione.ordina che funziona per
     * array di stringhe invece che per array di interi.
     */
    public static void selectionSort(String[] a) {
        for (int i = 0; i < a.length; i++) {
            int posmin = i;
            for (int j = i + 1; j < a.length; j++) {
                int comp = a[posmin].compareTo(a[j]);
                if (comp > 0)
                    posmin = j;
            }
            String tmp = a[i];
            a[i] = a[posmin];
            a[posmin] = tmp;
        }
    }

    public static void main(String[] args) throws Exception {
        /*
         * Carichiamo il dizionario (che è già in ordine alfabetico). Usiamo solo 40.000 parole,
         * altrimenti il tempo di attesa per il selections sort diventa eccessivo.
         */
        var dictionary = Dictionary.getOfflineDictionary(40_000);
        System.out.println("Letto dizionario di " + dictionary.length + " parole");

        /*
         * Parola da cercare per gli esperimenti sulla ricerca lineare e la ricerca binaria. Stiamo
         * indicardo una parola che non esiste. Se la cambiamo con una parola esistente, le
         * procedure di ricerca saranno più veloci. Non viene utilizzata
         */
        var word = "axjajdd";

        System.out.println("Ricerca lineare");
        Dictionary.timeIt(() -> {
            for (int i = 1; i <= 2000; i++)
                linearSearch(dictionary, word);
        });

        System.out.println("Ricerca binaria");
        Dictionary.timeIt(() -> {
            for (int i = 1; i <= 2000; i++)
                binarySearch(dictionary, word);
        });


        // Mischio il vettore dictionary
        Collections.shuffle(Arrays.asList(dictionary));

        System.out.println("Quick sort");
        // faccio una copia in dict1 del dizionario
        var dict1 = dictionary.clone();
        Dictionary.timeIt(() -> {
            Arrays.sort(dict1);
        });

        System.out.println("Selection sort");
        // faccio una copia in dict2 del dizionario
        var dict2 = dictionary.clone();
        Dictionary.timeIt(() -> {
            selectionSort(dict2);
        });
    }
}