import java.util.*;

public class EserciziSuStringhe {

	public static void scambiaElementi (String v[], int i, int j) {
		String temp = v[i];
		v[i] = v[j];
		v[j] = temp;
	}

	public static void bubbleSort ( String a[] ) {
		boolean scambi = true;
		int border = a.length - 1;
		while ( scambi && border > 0 ) {
			scambi = false;
			for ( int j = 0; j < border; j++) {
				if (a[j].compareTo(a[j+1]) > 0) {
					scambiaElementi(a,j,j+1);
					scambi = true;
				}
			}
			border--;
		}
	}
	
	public static String eliminaSpaziEstremi(String s){
		int i=0, f=s.length()-1;
		
		while(s.charAt(i)==' ' && i<s.length())
			i++;
		while(s.charAt(f)==' ' && f>=0)
			f--;

		String ris="";
		for(int k=i; k<=f; k++)
			ris += s.charAt(k);
		return ris;
		
//		In alternativa:
//		return s.substring(i, f+1);
	}
	
	public static String eliminaSpazi(String s){
		String ris="";
		for(int i=0; i<s.length(); i++)
			if(s.charAt(i)!=' ')
				ris += s.charAt(i);
		return ris;
	}
	
	public static String eliminaSpaziRipetuti(String s){
		String ris="";
		int i=0;

		while(i<s.length()){
			ris += s.charAt(i);
			if(s.charAt(i)==' ')
				while(i<s.length() && s.charAt(i)==' ')
					i++;
			else
				i++;
		}
		return ris;
	}
	
	public static int ricercaBinariaIterativa(String[] v, String elem){
	    int min = 0;
	    int max = v.length-1;
	    int mezzo = (max+min)/2;
	    boolean trovato = false;
	    while(!trovato && min <= max) {
	        mezzo = (max+min)/2;
	        if(v[mezzo].equals(elem)) 
	        	trovato=true; 
	        if(v[mezzo].compareTo(elem) < 0) 
	        	min = mezzo + 1;
	        else max = mezzo - 1;
	    }
	    if(trovato) 
	    	return mezzo;
	    return -1;
	}
	
	public static int ricercaBinariaRicorsiva (String v[], String elem, int inf, int sup) {
		if( sup < inf )
			return -1;
	
		int med = (inf + sup)/2;
		if (elem.equals(v[med]))
			return med;
		if (elem.compareTo(v[med]) < 0)
			return ricercaBinariaRicorsiva(v, elem, inf, med-1);
		return ricercaBinariaRicorsiva(v, elem, med+1, sup);
	}

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in); 

		System.out.println("Inserisci una frase:");
		String frase = input.nextLine();
		
		String fraseSenzaSpaziEstremi = eliminaSpaziEstremi(frase);
		System.out.println("La tua frase senza gli spazi iniziali e finali:");
		System.out.println(fraseSenzaSpaziEstremi);
		System.out.println("Risultato ottenuto con trim:");
		System.out.println(frase.trim());
		
		String fraseSenzaSpazi = eliminaSpazi(frase);
		System.out.println("La tua frase senza nessuno spazio:");
		System.out.println(fraseSenzaSpazi);
		System.out.println("Risultato ottenuto con replaceAll:");
		System.out.println(frase.replaceAll(" ", ""));
		
		String fraseSenzaSpaziRipetuti = eliminaSpaziRipetuti(frase);
		System.out.println("La tua frase con non pił di uno spazio di seguito:");
		System.out.println(fraseSenzaSpaziRipetuti);
		
		// Ottieni array di parole
		String[] parole = eliminaSpaziRipetuti(frase.trim()).split(" ");
		// Ordina l'array
		bubbleSort(parole);
		// Stampa frase ordinata
		System.out.println("Frase con parole in ordine lessicografico:");
		String fraseOrdinata = "";
		for(int i=0; i<parole.length; i++)
			fraseOrdinata += (parole[i] + " ");
		System.out.println(fraseOrdinata);
		// Cerca parola
		System.out.println("Parola da cercare:");
		String parola = input.next();
//		int posizione = ricercaBinariaIterativa(parole, parola);
		int posizione = ricercaBinariaRicorsiva(parole, parola, 0, parole.length -1);
		if(posizione >= 0)
			System.out.println("La parola " + parola + " compare in posizione " + (posizione+1));
		else
			System.out.println("La parola " + parola + " non compare nella frase");
			
	}

}