/**
  * classe ExtendedCLL
  * Lista di Elementi Comparabili
  * prova di programmazione del 14-12-2007
  * la lista e' realizzata tramite lista concatenata
  * @author A. Luchetta
  * @version: 12-12-2007
  */
  
import java.util.NoSuchElementException;

public class ExtendedCLL extends CLL
{
   public Object get(int k)
   {
      if (k < 0 || k >= size())
         throw new NoSuchElementException();

      CListIterator iter = getIterator();
      
      int i = 0;
      while (i < k)
      {
         iter.next();
         i++;
      }

      return iter.next();
   }
   
   public Object[] toSortedArray()
   {
      Comparable[] c = new Comparable[size()];
      
      CListIterator iter = getIterator();
      
      int i = 0;
      while (iter.hasNext())
         c[i++] = (Comparable)iter.next();
      
      sort(c);
         
      return c;
   }
   
   private static void sort(Comparable[] v)
   {
      if (v.length < 2)
         return;
         
      int mid = v.length / 2;
      
      Comparable[] left = new Comparable[mid]; 
      Comparable[] right = new Comparable[v.length - mid];
      
      System.arraycopy(v, 0, left, 0, mid);
      System.arraycopy(v, mid, right, 0, v.length - mid);
      
      sort(left);
      sort(right);
      
      merge(v, left, right);   
   }
   
   private static void merge(Comparable[] a, Comparable[] b, Comparable[] c)
   {
      int ia = 0, ib = 0, ic = 0;
      
      while (ib < b.length && ic < c.length)
         if (b[ib].compareTo(c[ic]) < 0)
            a[ia++] = b[ib++];
         else
            a[ia++] = c[ic++];
            
      while (ib < b.length)
         a[ia++] = b[ib++];
         
      while (ic < c.length)
         a[ia++] = c[ic++];                         
   }
}