package lista_ordinata;
/*  lista  di oggetti Comparable ordinata in modo non decrescente */

public class ListaOrdinata {
   private NodoLista inizio;
   
   private static class NodoLista {
      Comparable dato;
      NodoLista pros;
   }

   
   /* costruisce una lista vuota */
   public ListaOrdinata() {
      inizio = null;
   }


   /* restituisce la posizione di un oggetto nella lista
      o 0, nel caso l'oggetto non sia presente */
   public int trova(Comparable x) {
      NodoLista p = inizio;
      int posizione = 1;
      while (p != null && p.dato.compareTo(x) < 0) {
         p = p.pros;
         posizione++;
      }
      if (p == null || p.dato.compareTo(x) > 0) //se non c'e'
         return 0;
      else
         return posizione;
   }

   
   /* inserisce un nuovo elemento nella lista */
   public void inserisci(Comparable x) {
      //ricerca della posizione per l'inserimento
      NodoLista p = inizio, q = null;
      while (p != null && p.dato.compareTo(x) < 0) {
         q = p;
         p = p.pros;
      }
      
      //creazione del nuovo nodo
      NodoLista r = new NodoLista();
      r.dato = x;
      
      //inserimento del nodo nella lista tra i nodi riferiti da q e da p
      r.pros = p;
      if (q == null)       //inserimento all'inizio
         inizio = r;
      else           //inserimento dopo il nodo riferito da q
         q.pros = r;
   }

   
   /* cancella un elemento dalla lista */
   public void cancella(Comparable x) {
   
      //ricerca della posizione per l'inserimento
      NodoLista p = inizio, q = null;
      while (p != null && p.dato.compareTo(x) < 0) {
         q = p;
         p = p.pros;
      }
      
      //eliminazione del nodo
      if (p != null && p.dato.compareTo(x) == 0)
         if (q == null)    //cancellazione all'inizio
            inizio = inizio.pros;
         else              //cancellazione dopo il nodo riferito da q
            q.pros = p.pros;
   }

   
   /* restituisce una stringa corrispondente al contenuto della lista */
   public String toString() {
      return this.toString(" ");
   }

   
   /* restituisce una stringa corrispondente al contenuto della lista;
      utilizzando l'argomento per separare i vari elementi */
   public String toString(String separatore) {
      if (inizio == null)
         return "";
      else {
         String s = inizio.dato.toString();
         for (NodoLista nodo = inizio.pros; nodo != null; nodo = nodo.pros)
            s = s + separatore + nodo.dato.toString();
         return s;
      }  
   }

   
   /* restituisce true se la lista e' vuota */
   public boolean vuota() {
      return inizio == null;
   }
}