package cs2410;

import java.util.*;
import java.io.*;

public class MergeSort {

  // readString() method used from Dr. Daniel Liang's MyInput class
  public static String readString() throws java.io.IOException {
    BufferedReader br = new BufferedReader( new InputStreamReader( System.in ), 1 );

    String string = " ";

    try {
      string = br.readLine();
    }
    catch (IOException ex) {
      System.out.println(ex);
    }

    return string;
  }

  public static void mergeRuns( BufferedReader readA,
                                BufferedReader readB,
                                PrintWriter printToFile,
                                int runLength ) throws java.io.IOException {

    try {
      readA.readLine();
      readB.readLine();
    }
    catch( IOException ex ) {
      System.out.println(ex);
    }

    if ( readA.readLine() == null || readB.readLine() == null ) {
      endOfFile = true;
      return;
    }

    int countA, countB;
    countA = countB = 1;

    int numberFromA = Integer.parseInt( readA.readLine() );
    int numberFromB = Integer.parseInt( readB.readLine() );

    while( countA <= runLength && countB <= runLength ) {
      if( numberFromA < numberFromB ) {
        printToFile.println( numberFromA );

        if( countA < runLength ) {
          readA.readLine();
        }
        countA++;

      } else {
        printToFile.println( numberFromB );

        if( countB < runLength ) {
          readB.readLine();
        }
        countB++;
      }
    }

    if( countA > runLength ) {
      while( countB <= runLength ) {
        printToFile.println( numberFromB );

        if( countB < runLength ) {
          readB.readLine();
        }
        countB++;
      }

    } else {
      while( countA <= runLength ) {
        printToFile.println( numberFromA );

        if( countA < runLength ) {
          readA.readLine();
        }
        countA++;
      }
    }
  }

  static boolean endOfFile;

  public static void main( String[] args ) throws java.io.IOException {
    int toPow, buffSize;

    System.out.println( "Enter Integer (-1 to Exit): " );
    toPow = Integer.parseInt( readString() );

    while( toPow != -1 ) {
      System.out.println( "Enter Buffer Size (-1 to Exit): " );
      buffSize = Integer.parseInt( readString() );

      while( buffSize != -1) {
        System.out.println("DEBUG: Populating numbers.txt");
        FileWriter fwNumbers       = new FileWriter("numbers.txt");
        BufferedWriter bwNumbers   = new BufferedWriter(fwNumbers, buffSize);
        PrintWriter printToNumbers = new PrintWriter(bwNumbers);

        for (int i = 0; i < (Math.pow( 2, toPow )); i++) {
          printToNumbers.println( (int) (Math.random() * 1000) );
        }
        System.out.println("DEBUG: numbers.txt populated\n");

        printToNumbers.close();

        System.out.println("DEBUG: Reading numbers.txt for splitting\n");
        FileReader frNumbers           = new FileReader("numbers.txt");
        BufferedReader readFromNumbers = new BufferedReader(frNumbers);

        System.out.println("DEBUG: Populating tmp_a.txt");
        FileWriter fwA       = new FileWriter("tmp_a.txt");
        BufferedWriter bwA   = new BufferedWriter(fwA, buffSize);
        PrintWriter printToA = new PrintWriter(bwA);

        String token;
        StringTokenizer stringFromLine;
        int numberRead;

        for (int i = 0; i < (Math.pow( 2, (toPow - 1) )); i++) {
          stringFromLine = new StringTokenizer(readFromNumbers.readLine());
          token          = stringFromLine.nextToken();
          numberRead     = Integer.parseInt(token);

          printToA.println( numberRead );
        }
        System.out.println("DEBUG: tmp_a.txt populated\n");
        printToA.close();

        System.out.println("DEBUG: Populating tmp_b.txt");
        FileWriter fwB       = new FileWriter("tmp_b.txt");
        BufferedWriter bwB   = new BufferedWriter(fwB, buffSize);
        PrintWriter printToB = new PrintWriter(bwB);

        for (int i = 0; i < (Math.pow(2, (toPow - 1))); i++) {
          stringFromLine = new StringTokenizer( readFromNumbers.readLine() );
          token          = stringFromLine.nextToken();
          numberRead     = Integer.parseInt( token );

          printToB.println(numberRead);
        }
        System.out.println("DEBUG: tmp_b.txt populated\n");
        printToB.close();

        readFromNumbers.close();

        int runLength = 1;
        int y = 0;
        int z;

        while (runLength <= Math.pow(2, (toPow - 2))) {
          if (y % 2 == 0) {
            System.out.println("DEBUG: reading tmp_a.txt for sorting");
            FileReader frA = new FileReader("tmp_a.txt");
            BufferedReader readFromA = new BufferedReader(frA);

            System.out.println("DEBUG: reading tmp_b.txt for sorting\n");
            FileReader frB = new FileReader("tmp_b.txt");
            BufferedReader readFromB = new BufferedReader(frB);

            endOfFile = false;
            z = 0;

            System.out.println("DEBUG: Populating tmp_c.txt");
            FileWriter fwC = new FileWriter("tmp_c.txt");
            BufferedWriter bwC = new BufferedWriter(fwC, buffSize);
            PrintWriter printToC = new PrintWriter(bwC);

            System.out.println("DEBUG: Populating tmp_d.txt\n");
            FileWriter fwD = new FileWriter("tmp_d.txt");
            BufferedWriter bwD = new BufferedWriter(fwD, buffSize);
            PrintWriter printToD = new PrintWriter(bwD);

            while ( !endOfFile ) {
              if (z % 2 == 0) {
                mergeRuns(readFromA, readFromB, printToC, runLength);
              } else {
                mergeRuns(readFromA, readFromB, printToD, runLength);
              }
              z++;
            }
            printToC.close();
            printToD.close();

          } else {
            System.out.println("DEBUG: reading tmp_c.txt for sorting");
            FileReader frC = new FileReader("tmp_c.txt");
            BufferedReader readFromC = new BufferedReader(frC);

            System.out.println("DEBUG: reading tmp_d.txt for sorting\n");
            FileReader frD = new FileReader("tmp_d.txt");
            BufferedReader readFromD = new BufferedReader(frD);

            endOfFile = false;
            z = 0;

            System.out.println("DEBUG: Populating tmp_a.txt");
            FileWriter fwriterA = new FileWriter("tmp_a.txt");
            BufferedWriter bwriterA = new BufferedWriter(fwriterA, buffSize);
            PrintWriter writeToA = new PrintWriter(bwriterA);

            System.out.println("DEBUG: Populating tmp_b.txt\n");
            FileWriter fwriterB = new FileWriter("tmp_b.txt");
            BufferedWriter bwriterB = new BufferedWriter(fwriterB, buffSize);
            PrintWriter writeToB = new PrintWriter(bwriterB);

            while (!endOfFile) {
              if (z % 2 == 0) {
                mergeRuns(readFromC, readFromD, writeToA, runLength);
              } else {
                mergeRuns(readFromC, readFromD, writeToB, runLength);
              }
              z++;
            }
            writeToA.close();
            writeToB.close();
          }
          runLength = 2 * runLength;
          y++;
        }

        System.out.println("DEBUG: Populating output.txt");
        FileWriter fwOutput = new FileWriter("output.txt");
        BufferedWriter bwOutput = new BufferedWriter(fwOutput, buffSize);
        PrintWriter printToOutput = new PrintWriter(bwOutput);

        if (y % 2 == 0) {
          System.out.println("DEBUG: reading tmp_a.txt for sorting");
          FileReader frA = new FileReader("tmp_a.txt");
          BufferedReader readFromA = new BufferedReader(frA);

          System.out.println("DEBUG: reading tmp_b.txt for sorting\n");
          FileReader frB = new FileReader("tmp_b.txt");
          BufferedReader readFromB = new BufferedReader(frB);

          mergeRuns(readFromA, readFromB, printToOutput, runLength);

          readFromA.close();
          readFromB.close();
          printToOutput.close();
        }
        else {
          System.out.println("DEBUG: reading tmp_c.txt for sorting");
          FileReader frC = new FileReader("tmp_c.txt");
          BufferedReader readFromC = new BufferedReader(frC);

          System.out.println("DEBUG: reading tmp_d.txt for sorting\n");
          FileReader frD = new FileReader("tmp_d.txt");
          BufferedReader readFromD = new BufferedReader(frD);

          mergeRuns(readFromC, readFromD, printToOutput, runLength);

          readFromC.close();
          readFromD.close();
          printToOutput.close();
        }
      }

      System.out.println( "Enter Integer (-1 to Exit): " );
      toPow = Integer.parseInt( readString() );
    }
  }
}