/**
  * StudentSortedContainer
  * contenitore di oggetti di classe Studente.java
  * @author Adriano Luchetta
  * @version 8-Nov-2003
  * @version 20-Nov-2004
  * @version 20-Nov-2005 java 5.0
  */
import java.util.Scanner;
import java.util.NoSuchElementException;

public class StudentSortedContainer implements Container
{
   static final int INITIAL_SIZE = 1;

   private Studente[] students;
   private int studentsSize;
   
   /**
      inizializza un archivio vuoto
   */
   public StudentSortedContainer()
   {
      makeEmpty();
   }

   /**
      verifica se il contenitore e' vuoto.<br>
      Andamento asintotico O(1)
      @return true se l'array e' vuoto, false altrimenti
   */
   public boolean isEmpty()
   {
      return studentsSize == 0;
   }
   
   /**
      rende vuoto il contenitore.<br>
      Andamento asintotico O(1)
   */
   public void makeEmpty()
   {
      students = new Studente[INITIAL_SIZE];
      studentsSize = 0;
   }
   
   /**
   ritorna il numero di elementi presenti nel contenitore
      @return il numero di elementi
   */
   public int size()
   {
      return studentsSize;
   }

   /**
      Aggiunge un elemento al contenitore, ridimensionandolo se richiesto.
      Attenzione, prima dell'inserimento il contenitore e' ordinato!
      Andamento asintotico O(n).
      @param nome nome dello studente da aggiungere
      @param matr numero di matricola dello studente da aggiungere
   */
   public void add(String nome, int matr)
   {
      //ridimensionamento se necessario
      if (studentsSize >= students.length)
         students = resize(students, 2 * students.length);

      //nuovo studente
      Studente newStudente = new Studente(nome, matr);

      // ricerca indice i per inserimento ordinato e spostamento a destra
      // ciclo interno dell'algoritmo di ordinamento per inserimento!
      int i;
      for (i = studentsSize; i > 0 && newStudente.compareTo(students[i - 1]) > 0; i--)
         students[i] = students[i-1];
   	   
      //inserimento studente
      students[i] = newStudente;
      studentsSize++;
   }
   
   /**
      Aggiunge un elemento al contenitore.
      Andamento asintotico O(n).
      @param studentString stringa in formato matricolaxnome, dove x e' un carattere delimitatore
      @param delimiters caratteri delimitatori
      @throws java.util.NoSuchElementException se la stringa non ha il formato corretto
   */
   public void add(String studentString, String delimiters)
   {
      Scanner tok = new Scanner(studentString);
      tok.useDelimiter("[" + delimiters + "]+");
      String nome = tok.next();
      int matr = tok.nextInt();
      tok.close();
      add(nome, matr);
   }
   
   /**
      restituisce il nome dello studente il cui numero di matricola coincide
      con il parametro esplicito. Andamento asintotico O(log n)
      @param matr il numero di matricola
      @return il nome dello studente
      @throws java.util.NoSuchElementException se il numero di matricola
      non e' presente
   */
   public String findName(int matr)
   {
      // ridimensionamento array
      Studente[] a = resize(students, studentsSize);
      
      // ricerca
      int index = binarySearch(a, 0, a.length - 1, matr);
      if (index < 0)
         throw new NoSuchElementException();
         
      return a[index].nome();
   }
   
   /**
      ritorna il valore massimo del contenitore (massimo nel senso       <br>
      dell'ordinamento naturale della classe Studente, cancellandolo dal <br>
      contenitore. Andamento asintotico O(1).                            <br>
      @return il valore massimo
      @throws java.util.NoSuchElementException se l'array e' vuoto
   */
   public Studente removeMax()
   {
      if (isEmpty())
         throw new NoSuchElementException("archivio vuoto");

      Studente tmpStudente = students[studentsSize - 1];
      students[studentsSize - 1] = null;     // garbage collector
      studentsSize--;

      return tmpStudente;
   }
   
   /* ridimensionamento dinamico */
   private Studente[] resize(Studente[] oldAr, int newLength)
   {
      Studente[] newAr = new Studente[newLength];
      int minLength = Math.min(oldAr.length, newLength);

      for (int i = 0; i < minLength; i++)
        newAr[i] = oldAr[i];

      return newAr;
   }
   
   /* ricerca binaria */
   private int binarySearch(Studente[] v, int from, int to, int target)
   {
      if (from > to)
         return -1;
         
      Studente targetStudent = new Studente("", target);

      int mid = (from + to) / 2;
      if (targetStudent.compareTo(v[mid]) == 0)
         return mid;
      if (targetStudent.compareTo(v[mid])  < 0)
         return binarySearch(v, from, mid - 1, target);
      return binarySearch(v, mid + 1, to, target);
   }
   
   /**
      rende la classe eseguibile.
   */
   public static void main(String[] args)
   {
      final char COMMENT_CHARACTER = '*';
      final String DELIMITER_CHARACTER = ":";

      Scanner in = new Scanner(System.in);
      StudentSortedContainer studentList = new StudentSortedContainer();
      int lineCounter = 0;
      
      while (in.hasNextLine())
      {
         String line = in.nextLine();
         lineCounter++;
         try
         {
            if (line.charAt(0) != COMMENT_CHARACTER)
               studentList.add(line, DELIMITER_CHARACTER);
         }
         catch (NoSuchElementException e)
         {
            System.out.println("Errore alla riga n. " + lineCounter + " >>> " + line);
         }
      }
      in.close();

      System.out.println("\n*** ELENCO ORDINATO DEGLI STUDENTI ***");
      while (!studentList.isEmpty())
         System.out.println(studentList.removeMax());
   }
}