/**
 * La classe <code>ArrayOrdinato</code> implementa il tipo di dato Dizionario
 * mantenendo le coppie (elemento, chiave) in un array S in modo
 * tale che coppie consecutive abbiano chiavi non decrescenti,
 * cio&egrave; che l'array sia ordinato in base alle chiavi.
 */

public class ArrayOrdinato implements Dizionario {
	
	// array di coppie (elem,chiave)
	private Coppia[] S= new Coppia[0];
	
	/**
     * Classe definita localmente alla classe <code>ArrayOrdinato</code>
     * per il mantenimento delle coppie (elemento, chiave)
     *
     */

    private class Coppia {
        public Object elem;
        public Comparable chiave;
        public Coppia(Object e, Comparable k) {
            this.elem = e;
            this.chiave = k;
        }
        public String toString(){
        	return chiave.toString()+ ":"+elem.toString();
        }
    }


    /**
	 * Rimuove dal dizionario l'elemento con chiave <code>k</code> (<font color=red>Tempo O(n)</font>).
	 * In caso di duplicati, l'elemento cancellato
	 * &egrave; scelto arbitrariamente tra quelli con chiave <code>k</code>.
	 * La ricerca dell'elemento da cancellare avviene
	 * mediante una scansione binaria dell'array.
	 * 
	 * @param k chiave dell'elemento da cancellare
	 * @throws EccezioneChiaveNonValida se la chiave ricercata non &egrave; presente nel dizionario
	 */

	public void delete(Comparable k) {
		// TODO Auto-generated method stub
		

	}

	/**
	 * Aggiunge al dizionario la coppia <code>(e,k)</code> (<font color=red>Tempo O(n)</font>).
	 * L'inserimento viene realizzato incrementando
	 * di uno la taglia dell'array e collocando la nuova
	 * coppia in modo tale da rispettare la relazione
	 * di ordinamento.
	 * 
	 * @param e elemento da mantenere nel dizionario
	 * @param k chiave associata all'elemento
	 */

	public void insert(Object e, Comparable k) {
		
		
	  int i, j;
	  //creare un vettore temp di dimensione S.length+1
        Coppia[] temp = new Coppia[S.length + 1];
        //copiare in temp S
        for (i = 0; i < S.length; i++) 
        	temp[i] = S[i];
        //assegnare ad S temp 
        S = temp;
        //ricercale la posizione in cui inserire l'elemento e
        for (i = 0; i < S.length - 1; i++)
            if (k.compareTo(S[i].chiave) <= 0)  
            	break; // i corrisponde alla posizione in cui deve essere inserito e
        for (j = S.length - 1; j > i; j--)
            S[j] = S[j - 1]; //shiftare a destra
        S[i] = new Coppia(e, k);


	}


	/**
	 * Restituisce l'elemento <code>e</code> con chiave <code>k</code> (<font color=red>Tempo O(log(n)</font>).
	 * In caso di duplicati, l'elemento restituito
	 * &egrave; scelto arbitrariamente tra quelli con chiave <code>k</code>.
	 * La ricerca dell'elemento con chiave <code>k</code> 
	 * avviene utilizzando l'algoritmo di ricerca binaria.
	 * 
	 * @param k chiave dell'elemento da ricercare
	 * @return elemento di chiave <code>k</code>, <code>null</code> se assente
	 */
	public Object search(Comparable k) {
		// TODO Auto-generated method stub
		int i=0;
		int j=S.length;
		while (i<j) 
		{
			int m=(i+j)/2;
			if (k.compareTo(S[m].chiave)==0)
				return S[m].elem;
			else
				if(k.compareTo(S[m].chiave) < 0) // ricerca in partizione a sinistra di m
					j=m;
				else // ricerca in partizione a destra di m
					i=m+1;
			
		}		
				
		
		return null;
	}
	
	private static void inizializza(Dizionario d) {
		
		d.insert("Pippo","080123456");
		d.insert("Giņ", "080654321");
		d.insert("Lisa", "081123456");
		d.insert("Gennarino", "081654321");
		d.insert("Emy", "347112233");
			
			
		
	}



	public static void main(String[] args) {
		ArrayOrdinato rubrica = new ArrayOrdinato();
		inizializza(rubrica);
		System.out.println(rubrica.search("081654321"));
		
	}
		




}