import java.util.NoSuchElementException;//This is needed to throw exceptions.
  
 //This class generates the tList in A3Test using the methods contained within.
public class StudentList implements StudentListInterface {
 public Student[] student;//The array of Student objects.
 private int length;//the true length of the list (Not the Array)
 public int num_comparisons;//This is used to count the sorting method comparisons
 public SortGUI graphics; //This is used to implement Graphics
 public int arlength;//This is used to double the array size
   
 public StudentList(){//Constructor
  arlength = 1;//Initial Length of Array - change the value to 0 or higher
  student = new Student[arlength];
  length = 0;//An empty list is of size 0
  num_comparisons = 0;
 }
  
public void bubbleSort(int showGui) {//if ShowGui is 0 - no GUI will be shown.
      
 //    GUI INITIALIZATION
  if (showGui == 1) {//If you want the Gui to be shown
    graphics = new SortGUI(false);
   }
   else if (showGui == 2) {//If you want to show a Random Gui
    graphics = new SortGUI(true);
   }
      // END GUI INITIALIZATION
   
  num_comparisons=0;//Resets Comparison Count
  int index = 0;//This is outerloop index
  int index2 = 0;//This is the innerloop index
  Student temp = null;//This is used during updates - Changed from holder to temp  
  
  while (index < length) {//This is the outer while loop. It goes through the list length times regardless if it is sorted.
   index2 =0;//Resets index 2
   while (index2 < length-1){//This is the inner while loop. It has an IF statement that checks whether items must be swapped.
    num_comparisons++;
    if (student[index2].compareTo(student[index2+1]) >= 0) {//Comparison part. It checks if Student index2 is bigger or less than Student index2+1
     if (showGui== 1 || showGui==2) {
      graphics.update(this);//Updates the Graphics
     }
     temp = student[index2];//This part updates the studentlist if Student index2 is bigger than Student student2+1
     student[index2] = student[index2+1];
     student[index2+1] = temp;
    }//If Student index2 is less than Student index2+1 - then do nothing - they are already sorted.
    index2++;
   }//Ends Inner Loop
   index++;
  }//Ends Outer Loop
  
 if (showGui== 1 || showGui==2) {
    graphics.clear();//Clears the window after sorting is done.
     }
}//End of BubbleSort method
 
public void insertionSort(int showGui){//if ShowGui is 0 - no GUI will be shown.
   
 //GUI INITIALIZATION
  if (showGui == 1) {//If you want the Gui to be shown
    graphics = new SortGUI(false);
   }
   else if (showGui == 2) {//If you want to show a Random Gui
    graphics = new SortGUI(true);
   }
     // END GUI INITIALIZATION
   
  num_comparisons = 0;//Resets the comparison count
  int tempindex  = 0;//This is the counter of the Sorted Part
  int fullindex = 1;//This is the Index of the Unsorted part
  int insertlength = 0;//This is the length required to make room in the Sorted Part whenever an item is placed that is out of order.
  Student temp = null;//This is the temp file needed to swap items in the array
  int templength = 1;//This is the length of the Sorted Part .
   
  while (templength < length) {//This loop is run until the length of the List is the same as the Sorted Part
   while (templength > tempindex) {//This loop runs until the Student object to be placed in the Sorted Part is sorted correctly.
    num_comparisons++;
     
    if (student[tempindex].compareTo(student[fullindex]) < 0) {//If Object is in the wrong place, then increase tempindex.
     tempindex++;
    }
     
    else {//Places the item from the Unsorted Part into the Sorted part correctly.
     temp = student[fullindex];//This sets the temp to the object being swapped
     insertlength = templength;
        
     while (insertlength > tempindex) {//This loop will make room for the new Object to be sorted.
      student[insertlength] = student[insertlength-1];
      insertlength--;
     }//Ends Make-Room loop
        
     if (showGui== 1 || showGui==2) {
      graphics.update(this); //Updates the Graphics
     }
       
     student[tempindex] = temp;//Sets the student object in the correct location.
     break;
    }
   }//Ends Inner Loop
   templength++;//Increments
   tempindex=0; //Resets Tempindex
   fullindex++;
  }//Ends Outer Loop
   
  if (showGui== 1 || showGui==2) {
   graphics.clear(); //Clears the window after sorting is done.
  }
}//Ends Insertion Sort
  
 
 
public void mergeSort(int showGui) {//if ShowGui is 0 - no GUI will be shown.
   
 //GUI INITIALIZATION
  if (showGui == 1) {//If you want the Gui to be shown
    graphics = new SortGUI(false);
   }
   else if (showGui == 2) {//If you want to show a Random Gui
    graphics = new SortGUI(true);
   }
     // END GUI INITIALIZATION
   
  num_comparisons = 0;//Resets the Comparison Count
  breaker(length, 0,showGui);//Initializes the "Breaking" of the array into Abstract parts.
   
 if (showGui== 1 || showGui==2) {
  graphics.clear(); //Clears the window after sorting is done.
 }
 }
 
//This part breaks the array into Abstract Parts.
public void breaker(int length, int index, int showGui) {
 //Initialization of variables
    int middle = length/2;//Selects the middle
 int leftindex = index; //Leftmost index
 int rightindex = index + middle;//Rightmost index
 int leftlength = middle;//Length of the Left Abstract Array
 int rightlength = length - middle;//Length of the Right Abstract Array
  
  if (leftlength!=1) //Breaks if Left Abstract Array is unsorted.
  {
   breaker(leftlength, leftindex, showGui);//Calls the Breaker method with the  Left Abstract Array
  }
  if (rightlength!=1) //Breaks if Right Abstract Array is unsorted.
  {
   breaker(rightlength,rightindex,showGui);//Calls the Breaker method with the Right Abstract Array
  }
  //The following command merges the two Abstract Arrays
  merge(leftindex, rightindex, leftlength, rightlength,showGui);
}
 
//This part merges Abstract Parts of the MergeSort
public void merge(int leftindex, int rightindex, int leftlength, int rightlength,int showGui) {
      Student[] temparray = new Student[leftlength + rightlength];//Initialization of the Temp Array
      int copyindex = leftindex;//This index is used to copy values back into Student from the Temp Array
      int rightcounter=0;//The index of the Abstract right part - this is not the same as rightindex!
      int leftcounter =0;//The index of the Abstract left part - this is not the same as leftindex!
   int tempindex = 0;//This is the tempindex of the TempArray
   int tempcounter = 0;//This is the counter that tells when the objects are sorted in the Temp Array
    
   while (temparray.length > tempindex) {//This part chooses the smallest value and place into the Temp Array
     
    if (leftcounter >= leftlength) {//This part checks if the Left Abstract Array  is already copied
     temparray[tempindex] =student[rightindex];//Copes the element from the Right Abstract Array into the Temp Array
     rightindex++;//increments the right index
     tempindex++;//incremends the index of the temp array
     tempcounter++;}//increments the counter of the temporary array
     
    else if (rightcounter >= rightlength) {//This part checks if the Right Abstract Array is already copied
     temparray[tempindex] = student[leftindex];//Copes the element from the Left Abstract Array into the Temp Array
     leftindex++;//increments the left index
     tempindex++;//incremends the index of the temp array
     tempcounter++;}//increments the counter of the temporary array
     
    else {//Compares the elements from both lists
     num_comparisons++;
      
     if (student[leftindex].compareTo(student[rightindex]) > 0) {//If student in Left Abstract Array is bigger than student in Right Abstract Array
      temparray[tempindex] = student[rightindex];//copies the student from the Right Abstract Array into the Temp Array
      rightindex++;//increments the right index
      rightcounter++;//increments the counter of the right index
      tempindex++;//increments the index of the temp array
      tempcounter++;}//increments the counter of the temp array
      
     else  {//If student in Right Abstract Array is bigger than student in Left Abstract Array
      temparray[tempindex] = student[leftindex];//copies the student from the Left Abstract Array into the Temp Array
      leftindex++;//increments the left index
      leftcounter++;//increments the counter of the left index
      tempindex++;//increments the index of the temp array
      tempcounter++;}//increments the counter of the temp array
     }
    }//End Copy into Temp part
 
 for (int i = 0; temparray.length > i; i++) {//Copies everything back into the Student Array from the Temp Array
  student[copyindex]=temparray[i];
  if (showGui== 1 || showGui==2) {
   graphics.update(this);//Updates the Graphics
   }
  copyindex++;
 }//End For Loop
} //End Merge Sort
    
   
  //Add Method
  public void add(Student s){
   //Begin Array doubling if it is already full.  
   if (length == student.length) {
    Student[] doubler = new Student[length*2];
    for (int i = 0; i<length; i++ ){
     doubler[i]=student[i];
    }
       arlength*=2;
       student = doubler;}
   // End Array doubling if it is already full.
    
   student[length]=s;
   length++;
 }
   
  //Add in position Add method
  public void add(Student s, int n) {
   //Begin Array doubling if it is already full.  
    if (length == student.length) {
     Student[] doubler = new Student[length*2];
     for (int i = 0; i<length; i++ ){
      doubler[i]=student[i];
     }
        arlength*=2;
        student = doubler;}
    // End Array doubling if it is already full.
  
   int tempindex = n;
   int curlength = length;
   while (curlength > n-1) {
     student[curlength] = student[curlength-1];//Moves the entire array to make room for the added slot.
     curlength--;
    }
   student[tempindex] = s;
   length++;
 }
   
  //Get method
  public Student get(int n){
   if (n<0 || n>arlength) {
    throw new NoSuchElementException("GET ERROR: Elements must be between 0 and " + arlength + " and your input was " + n);
   }
   return student[n];
  }
   
  //Remove method
  public Student remove(int n) {
   if (n<0 || n>arlength) {
    throw new NoSuchElementException("REMOVE ERROR: Elements must be between 0 and " + arlength + " and your input was " + n);
   }
   else if (length == 0){
    throw new IndexOutOfBoundsException("REMOVE ERROR: The array is empty!");
   }
   Student output = student[n];
  
   while (length > n && n<student.length-1) {//Moves the entire array to fill up the removed slot.
    student[n] = student[n+1];
    n++;
   }
   student[length-1]=null;
   length--;
   return output;//Returns the student removed
  }//End Remove Method
   
  //Clears the List of all contents
  public  void clear(){
   int index = 0;
   while (length>index) { //goodbye dear list We'll miss you!
      this.remove(length-1);
   }
  }//End Clear Method
   
  //How big is this list anyway? Returns the size of the List
  public int size(){
   return length;
  }//End Size Method
   
  //Displays the Students in the list.
  public void display(){
   int n = 0;
   while (length > n) {
    student[n].display();
    n++;
   }
  }//End Display Method
   
}//End StudentList Class