import java.io.*;
import java.util.Scanner;
import java.util.NoSuchElementException; //Attenzione: questa eccezione va
                                         // importata per essere usata


public class RubricaTester
{   public static void main(String[] args)
    {   //controllo parametri del metodo main
        if (args.length != 2 || args[0].equals(args[1]))
        { System.out.println("Uso: $java RubricaTester filename1 filename2");
          System.out.println("Non usare stesso nome file in lettura/scrittura");
          System.exit(1);
        }
        String filename1 = args[0];
        String filename2 = args[1];

        //apertura di file1 in lettura
        Scanner file1 = null;
        try{  file1 = new Scanner(new FileReader(filename1));  }
        catch(FileNotFoundException e)
        {   System.out.println("Problema in apertura File1! Termino");
            System.exit(1); }

        //Creazione e  scrittura di rubrica1
        Rubrica rubrica1 = new Rubrica();
        while (file1.hasNextLine())
        {   String line = file1.nextLine();
            Scanner linescan = new Scanner(line);
            try{
            String name = linescan.next(); //nome : campo "key" del dizionario
            String word;
            while (!( word = linescan.next()).equals(":"))//considero anche
                name += " " + word; //nomi eventualmente composti da piu` parole
            long phone = Long.parseLong(linescan.next()); //dopo i ":" ci deve
                                            //essere un numero in formato long
            rubrica1.insert(name, phone);
            }//NoSuchElementException puo` essere lanciata da next se non
            catch(NoSuchElementException e) //vengono trovati token
            {   System.out.println("Formato inserimento sbagliato");  }
            //NumberFormatException puo` essere lanciata da parseLong se la
            catch(NumberFormatException e) //stringa dopo i ":" non e` un intero
            {   System.out.println("Formato inserimento sbagliato");  }
        }
        System.out.println(rubrica1); //controllo il contenuto di rubrica1
        file1.close();

        //Creazione di rubrica2, ricerca e rimozione dati da rubrica1
        //inserimento in rubrica2 di dati rimossi da rubrica1
        Scanner in = new Scanner(System.in); //apertura standard input
        Rubrica rubrica2 = new Rubrica();
        boolean done = false;
        while(!done)
        {   System.out.println("Nome in rubrica1 da spostare in rubrica2?");
            System.out.println("(\"Q\" per terminare)");
            String name = in.nextLine();
            if (name.equalsIgnoreCase("Q"))
                done = true;
            else
            {   try{rubrica2.insert(name, rubrica1.find(name));//prima copio e
                    rubrica1.remove(name);} //poi cancello. Non viceversa!
                catch(DictionaryItemNotFoundException e)
                { System.out.println("Nome non presente in rubrica1" ); }
                System.out.println("Rubrica1:\n" + rubrica1); //controllo i
                System.out.println("Rubrica2:\n" + rubrica2); //contenuti
            }
        }

        //apertura di file2 in scrittura, salvataggio di rubrica2 in file2
        PrintWriter file2 = null;
        try{  file2 = new PrintWriter(filename2);  }
        catch(FileNotFoundException e)
        {   System.out.println("Problema in apertura File2! Termino");
            System.exit(1); }
        file2.print(rubrica2);
        file2.close();  //Se non chiudo rischio che file2 non venga scritto!!!
        System.out.println("Arrivederci");
    }
}


class Rubrica implements Dictionary
{   public Rubrica()
    {   v = new Pair[INITSIZE];
        makeEmpty();
    }

    public boolean isEmpty()
    {   return vSize == 0;  }

    public void makeEmpty()
    {   vSize = 0;  }

    //Bisogna realizzare il comportamento richiesto nell'interfaccia Dictionary:
    //in particolare sovrascrivere coppie gia` presenti e lanciare eccezioni
    //La realizzazione qui proposta ha prestazioni O(n), perche` abbiamo usato
    //un algoritmo di ordinamento per inserimento
    public void insert(Comparable key, Object value)
    {   //precondizioni: controllo anche che value sia un numero long
        if (key == null || !(value instanceof Long) )
            throw new IllegalArgumentException();
        try{   remove(key); } //se la coppia c'e` gia` la rimuovo
        catch(DictionaryItemNotFoundException e){   }//altrimenti tutto ok!

        //uso array ridimensionabile!
        if(vSize == v.length) resize();

        //riordinamento per inserimento. Attenzione ai cast: v[i-1].getName()
        //e` di tipo String, e puo` essere comparato solo a String
        int i = vSize; // questo ciclo ha tempi di esecuzione O(n)
        while (i > 0 && (v[i-1].getName()).compareTo((String)key) > 0)
        {   v[i] = v[i-1];
            i--;
        }
        //creo un nuovo Pair (attenzione ai cast) e aggiungo al punto giusto
        v[i] = new Pair((String)key, (Long)value);
        vSize++; // aggiorno la dimensione
    }

    //metodo ausiliario: lo rendo private, non deve essere usato da altri
    private void resize() //niente parametri espliciti e valori restituiti: ho
    {                     // deciso che raddoppio sempre la dimensione.
        Pair[] newv = new Pair[2*v.length];
        System.arraycopy(v, 0, newv, 0, v.length);
        v = newv; //funziona: v non e` una var. locale ma un campo di esemplare
    }

    public void remove(Comparable key)
    {   //uso binSearch per cercare la chiave nell'array non ordinato
        //se la chiave non c'e` lancio DictionaryItemNotFoundException come da
        //specifiche (viene lanciata da binSearch)
        int i = binSearch(0, vSize-1, key);
        for (int j = i; j < vSize-1; j++)
            v[j] = v[j+1];
        vSize--;
    }

    public Object find(Comparable key)
    {   //uso binSearch per cercare la chiave nell'array non ordinato
        //se la chiave non c'e` lancio DictionaryItemNotFoundException come da
        //specifiche (viene lanciata da binSearch)
        return v[binSearch(0, vSize-1, key)].getPhone();
    }

    //metodo ausiliario: restituisce l'indice in cui ha trovato l'elemento
    private int binSearch(int from, int to, Comparable key)
    {   if (from > to) throw new DictionaryItemNotFoundException();
        int mid = (from + to) / 2; // circa in mezzo
        Comparable middlekey = v[mid].getName();
        if (middlekey.compareTo(key) == 0)
        //In questo caso funzionerebbe anche if (middle.getKey().equals(key))
        //perche` le chiavi sono di tipo String, e il metodo equals e` stato
        //sovrascritto in String in modo da essere coerente con compareTo
            return mid; // elemento trovato
        else if (middlekey.compareTo(key) < 0)  //cerca a destra
            return binSearch(mid + 1, to, key);
        else // cerca a sinistra
            return binSearch(from, mid - 1, key);
    }

    public String toString()
    {   String s = "";
        for (int i = 0; i < vSize; i++)
            s = s + v[i] + "\n"; //sfrutto il metodo toString di Pair!
        return s;
    }

    //campi di esemplare e variabili statiche di Rubrica
    private Pair[] v;
    private int vSize;
    private static int INITSIZE = 1;


    //classe privata Pair: non modificare!!
    private class Pair
    {   public Pair(String aName, long aPhone)
        {   name= aName;
            phone = aPhone;
        }
        public String getName()
        {   return name; }
        public long getPhone()
        {   return phone; }
        /*
            Restituisce una stringa contenente
            - la nome, "name"
            - un carattere di separazione ( : )
            - il numero telefonico, "phone"
        */
        public String toString()
        {   return name + " : " + phone; }
        //campi di esemplare
        private String name;
        private long phone;
    }
}


interface Dictionary
{
    /*
        verifica se il dizionario contiene almeno una coppia chiave/valore
    */
    boolean isEmpty();

    /*
        svuota il dizionario
    */
    void makeEmpty();

    /*
     Inserisce un elemento nel dizionario. L'inserimento va sempre a buon fine.
     Se la chiave non esiste la coppia key/value viene aggiunta al dizionario;
     se la chiave esiste gia' il valore ad essa associato viene sovrascritto
     con il nuovo valore; se key e` null viene lanciata IllegalArgumentException
    */
    void insert(Comparable key, Object value);

    /*
     Rimuove dal dizionario l'elemento specificato dalla chiave key
     Se la chiave non esiste viene lanciata DictionaryItemNotFoundException
    */
    void remove(Comparable key);

    /*
     Cerca nel dizionario l'elemento specificato dalla chiave key
     La ricerca per chiave restituisce soltanto il valore ad essa associato
     Se la chiave non esiste viene lanciata DictionaryItemNotFoundException
    */
    Object find(Comparable key);
}

class DictionaryItemNotFoundException extends RuntimeException {}