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