import java.util.Arrays;

public class MergeSort {
    private static final int I = 2;
    /**
     * Sortiere die Datensätze von Band t[0] auf eines der Bänder t[i]
     * 
     * @return Nummer <code>i</code> des Bandes, auf dem sich das Ergebnis
     *         befindet.
     */
    public static int mergesort(Stream[] t) {
        createInitialRuns(t[0], t[2], t[3]); // von 0 nach 2,3
        int in1 = 2, in2 = 3, out1 = 0, out2 = 1;
        int runLength = I;
        
        printTapes(t, 2,3, runLength);
        while(true) {
            rewindEverything(t, in1, in2, out1, out2);
            if (t[in2].eof()) { // t[in1] ist immer länger!
                // Alles hat auf ein Band, in1, gepasst: wir sind fertig
                return in1;
            }
            
            mergeAllRuns(t, in1, in2, out1, out2, runLength);
            
            int tmp1 = in1; in1 = out1; out1 = tmp1;
            int tmp2 = in2; in2 = out2; out2 = tmp2;
            runLength = runLength * 2;

            printTapes(t, in1, in2, runLength); // oben haben wir auf in1/in2 geschrieben
        }
    }


    private static void mergeAllRuns(Stream[] t, int in1, int in2, int out1,
            int out2, int runLength) {
        int out = out1;
        // t[in1] ist das längere von beiden Bändern!
        while(! t[in2].eof()) {
            mergeTwoRuns(t[in1], t[in2], t[out], runLength);
            if (out == out1) {
                out = out2;
            } else {
                out = out1;
            }
        }
        copyRest(t[in1], t[out]); // kopiere Rest des längeren Bands
    }

    private static void rewindEverything(Stream[] t, int ein1, int ein2, int aus1, int aus2) {
        t[ein1].reset();
        t[ein2].reset();
        t[aus1].rewrite();
        t[aus2].rewrite();
    }

    /**
      */
    private static void mergeTwoRuns(Stream in1, Stream in2, Stream out, int runLength) {
        // in1 ist länger als in2
        // weder in1 noch in2 sind EOF
        if (in1.eof()) {
            System.out.println(in1.toString());
            System.out.println(in2.toString());
        }
        int value1 = in1.read();
        int value2 = in2.read();
        int remainingReads1 = runLength-1;
        int remainingReads2 = runLength-1;
        while(true) {
            if (value1 <= value2) {
                out.write(value1);
                if (canStillRead(remainingReads1, in1)) {
                    value1 = in1.read();
                    remainingReads1--;
                } else {
                    // Band 1 ist leer und komplett geschrieben
                    out.write(value2);
                    copyAtMost(in2, out, remainingReads2);
                    return;
                }
            } else {
                out.write(value2);
                if (canStillRead(remainingReads2, in2)) {
                    value2 = in2.read();
                    remainingReads2--;
                } else {
                    // Band 2 ist leer und komplett geschrieben
                    out.write(value1);
                    copyAtMost(in1, out, remainingReads1);
                    return;
                }
            }
        }
    }
    private static boolean canStillRead(int nochZuLesen, Stream ein) {
        return !ein.eof() && nochZuLesen > 0; 
    }

    private static void copyAtMost(Stream ein, Stream aus, int maxAnzahl) {
        for(int i=0; i < maxAnzahl; i++) {
            if (ein.eof()) return;
            aus.write(ein.read());
        }
    }

    private static void copyRest(Stream ein, Stream aus) {
        while(! ein.eof()) {
            aus.write(ein.read());
        }
    }

    /**
     * <code>I</code> Datensätze einlesen, sortieren und wechselnd auf aus1/aus2 verteilen
     */
    private static void createInitialRuns(Stream in, Stream out1, Stream out2) {
        in.reset();
        out1.rewrite();
        out2.rewrite();

        int[] mainMemory = new int[I];
        Stream aus = out1;
        while(true) {
            int size = readIntoMemory(in, mainMemory);
            Arrays.sort(mainMemory, 0, size);
            for(int i=0; i < size; i++) {
                aus.write(mainMemory[i]);
            }
            // Alterniere: Verwende anderen Stream zur Ausgabe
            if (aus == out1) {
                aus = out2;
            } else {
                aus = out1;
            }
        }
    }

    private static int readIntoMemory(Stream in, int[] mainMemory) {
        int counter;
        for(counter = 0; counter < I; counter++) {
            if (in.eof()) break;
            mainMemory[counter] = in.read();
        }
        return counter;
    }

    //---------------------- Helpers
    
    private static void printTapes(Stream[] t, int out1, int out2, int runLength) {
        System.out.println("Runlänge: "+runLength);
        for(int i=0; i<t.length; i++) {
            boolean wasWrittenTo = (i == out1 || i == out2);
            if (wasWrittenTo) {
                System.out.println("> "+i+": "+t[i].toString(runLength));
            } else {
                System.out.println("  "+i+": "+t[i].toString(runLength / 2));
            }
        }
        System.out.println();
    }

    //---------------------- Main

    public static void main(String[] args) {
        // Beispiele:
        // 40, 39, 38, 37, 36, 11, 10, 9, 8, 7, 6, 3, 2
        // 7, 6, 5, 4, 3, 2, 1
        // 12,5,2,15,13,6,14,1,4,9,10,3,11,7,8
        Stream[] tapes = { new Stream(40, 39, 38, 37, 36, 11, 10, 9, 8, 7, 6, 3, 2),
                new Stream(), new Stream(), new Stream() };
        mergesort(tapes);
    }
}