// THIS CODE IS MY OWN WORK, IT WAS WRITTEN WITHOUT CONSULTING
// A TUTOR OR CODE WRITTEN BY OTHER STUDENTS - YOUR NAME

// TODO (see Notes.txt for more detail):
//  Standard Credit: implement transformBack() below.
//  Extra Credit: replace Arrays.sort() so "make pipi" is faster.
//     You may take code from Manber.java.

// Usage (also try running via the Makefile):
//    java BWT INFILE Z OUTFILE
//
// First the program reads all text from INFILE.
// If the text does not contain the "marker" character (Z), then
// apply the BWT, and write the resulting text to OUTFILE.
// If the text does contain Z, then apply the reverse BWT,
// and write the resulting text to OUTFILE.
// In either case, we refuse to overwrite an existing OUTFILE.

import java.io.FileReader;
import java.io.FileWriter;
import java.io.File;
import java.util.Arrays;

public class BWT
{
    static void die(String msg)
    {
        System.err.printf("error: %s\n", msg);
        System.exit(1);
    }

    public static void main(String[] args)
    {
        if (args.length != 3)
            die("expected three arguments");
        String inFileName = args[0];
        String markStr = args[1];
        String outFileName = args[2];
        if (markStr.length()!=1)
            die("mark arg should be one char");
        char mark = markStr.charAt(0);

        // Read the input string.
        String input = null;
        try {
            System.out.printf("Reading file %s\n", inFileName);
            StringBuilder sb = new StringBuilder();
            FileReader rd = new FileReader(inFileName);
            char[] buf = new char[256];
            while (true) {
                int got = rd.read(buf);
                if (got < 0) break;
                sb.append(buf, 0, got);
            }
            rd.close();
            input = sb.toString();
        } catch(Exception e) {
            die("while reading: " + e);
        }

        String result;
        // Check whether the input contains the marker char.
        if (input.indexOf(mark) < 0) {
            System.out.printf("Transforming %d chars\n", input.length());
            result = transform(input, mark);
        } else {
            System.out.printf("UnTransforming %d chars\n", input.length());
            result = transformBack(input, mark);
        }

        // Now write the result to outFileName.
        try {
            File outFile = new File(outFileName);
            if (outFile.exists())
                die("will not overwrite existing file " + outFileName);
            System.out.printf("Writing result to %s\n", outFileName);
            FileWriter wr = new FileWriter(outFile);
            wr.write(result);
            wr.close();
        } catch(Exception e) {
            die("while writing: " + e);
        }
        System.out.println();   // done
    }

    // The forward BWT.  Note we represent all the cyclic shifts using
    // only linear space.  The main issue here is the speed of sorting.
    static String transform(String input, char mark)
    {
        // The mark should not appear in the input.
        assert input.indexOf(mark)<0;
        int len = input.length();
        // Compute "square array" of all cyclic shifts of input+mark.
        String[] shifts = new String[len+1];
        String pad = input + mark + input;
        for (int i = 0; i <= len; ++i)
            shifts[i] = pad.substring(i, i+len+1);
        Arrays.sort(shifts);
        // Return "final column" of the sorted array.
        StringBuilder ret = new StringBuilder();
        for (String s: shifts)
            ret.append(s.charAt(len));
        return ret.toString();
    }

    // The reverse (or inverse) BWT, returning the original text.
    // This should take O(N+C) time and space, where N is the string
    // length and C is the maximum char code (you may assume C<256).
    static String transformBack(String bw, char mark) {
        int at = bw.indexOf(mark), size = bw.length();
        // The mark should appear once, but not twice.
        assert at >= 0;
        assert bw.indexOf(mark, at+1) < 0;
        // TODO: finish this! See Notes.txt for method sketch.
        throw new UnsupportedOperationException
            ("transformBack is not implemented");
        // Remember to use a StringBuilder, not a String, to build up
        // the answer.
    }
}