import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Test {


          private static FileInputStream inFile;
          private static InputStreamReader inReader;
          private static  BufferedReader reader;

          private static Scanner inputReader = new Scanner (System.in);

         private static List<Student> classroom = new ArrayList<Student>(); // ArrayList to store the classroom.






              public static void main (String args[]) throws IOException
              {


                if(type()){
                    initFile();
                    getData();
                    System.out.print(classroom);  //output of the complete class.
                    mergeSort(classroom);
                    System.out.print(classroom); //output after sorting.
                    inFile.close();
                    }else{
                        initFile();
                        getData();
                        System.out.print(classroom);  //output of the complete class.
                        int left = 0;
                    int right = classroom.size() -1;
                    quickSort(classroom, left, right);
               System.out.print(classroom); //output after sorting.
                inFile.close(); }


              }

             // preparing the file for input

              public static void initFile() throws IOException


              {
                inFile = new FileInputStream ("c:\\!!VHSAPCSData\\truefalse.txt");
                inReader = new InputStreamReader(inFile);
                reader = new BufferedReader(inReader);

              }


              //  Separate the id from the answers and store the answers in an array.

              public static void getData() throws IOException
              {
                String line = reader.readLine();  //Seed

                String[] answerkey = new String[10];  //Store the answer key from the first line of the txt file.

                for(int i=0; i<answerkey.length; i++){ // take that line and place each answer in an array.

                    answerkey[i]=line.substring(i,i+1);
                }

                line = reader.readLine();    // read the following line of the txt file.


                while(line != null)   // Read and create a student for each line.
                {
                  String[] answers = new String[10];
                  StringTokenizer strTkn = new StringTokenizer(line);
                  String id = strTkn.nextToken();
                  String answerline = strTkn.nextToken();


                  for(int i=0; i<answers.length; i++){

                      answers[i]=answerline.substring(i, i+1);

                  }

                  Student stu = new Student(id,answers);

                  stu.grade(answerkey, answers);

                  classroom.add(stu);




                  line = reader.readLine();   //updating what is being read

                }

              }


              public static void swap(List<Student> example, int x, int y) {
                    Student temp = example.remove(x);
                    example.add(x, classroom.remove(y - 1));
                    example.add(y, temp);
             }

          // In this method you should sort the classroom in ascending order depending on the score obtained on the quiz.
              public static void mergeSort(List<Student> a){
                  divide(0, a.size()-1);
                }

                public static void divide(int startIndex,int endIndex){

                    //Divide till you breakdown your list to single element
                    if(startIndex<endIndex && (endIndex-startIndex)>=1){
                        int mid = (endIndex + startIndex)/2;
                        divide(startIndex, mid);
                        divide(mid+1, endIndex);

                        //merging Sorted array produce above into one sorted array
                        merger(startIndex,mid,endIndex);
                    }
                }

                public static void merger(int startIndex,int midIndex,int endIndex){

                    //Below is the mergedarray that will be sorted array Array[i-midIndex] , Array[(midIndex+1)-endIndex]
                    List<Student> mergedSortedArray = new ArrayList<Student>();

                    int leftIndex = startIndex;
                    int rightIndex = midIndex+1;

                    while(leftIndex<=midIndex && rightIndex<=endIndex){
                        if(classroom.get(leftIndex).getGrade()<=classroom.get(rightIndex).getGrade()){
                            mergedSortedArray.add(classroom.get(leftIndex));
                            leftIndex++;
                        }else{
                            mergedSortedArray.add(classroom.get(rightIndex));
                            rightIndex++;
                        }
                    }

                    //Either of below while loop will execute
                    while(leftIndex<=midIndex){
                        mergedSortedArray.add(classroom.get(leftIndex));
                        leftIndex++;
                    }

                    while(rightIndex<=endIndex){
                        mergedSortedArray.add(classroom.get(rightIndex));
                        rightIndex++;
                    }

                    int i = 0;
                    int j = startIndex;
                    //Setting sorted array to original one
                    while(i<mergedSortedArray.size()){
                        classroom.set(j, mergedSortedArray.get(i++));
                        j++;
                    }
                }




              public static void quickSort(List<Student> example, int left, int right){
                  if (left >= right) return;

                  int i = left;
                  int j = right;
                  int pivotValue = classroom.get((i+j)/2).getGrade();

                  while (i < j) {
                   while (example.get(i).getGrade() < pivotValue) i++;
                   while (pivotValue < example.get(j).getGrade()) j--;
                   if(i <= j) {
                    Student temp = example.remove(i);
                    example.add(i, classroom.remove(j - 1));
                    example.add(j, temp);
                             j--;
                             i++;
                   }
                  }
                  quickSort (example, left, j);
                  quickSort (example, i, right);
               }


                  public static boolean type(){
                  System.out.print("If you wish to use merge sort, type 'yes' if you would rather quick sort, enter anything: ");
                 String reply = inputReader.next();
                  if(isYes(reply)){
                      return true;
                  }else{
                      return false;
                  }
              }
              //Method that returns true if the user inputs yes
                  public static boolean isYes(String response){
                            if(response.equals("yes")){
                                return true;
                            }else{
                                    return false;
                            }
}}