// Here we implement the "forward" Burrows-Wheeler Transform (BWT), an
// application of suffix sorting.
//
// Left TODO:
//   1. faster forward transform (do not form new strings)
//   2. the reverse transform
// In fact both transforms can be linear time.  The forward
// transform is a special case of suffix sorting, and the reverse
// transform requires some clever ideas but is no harder.

// Intended command-line usage:
//    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("second arg should be single 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);
        }
    }

    // A slow and literal implementation of the BW transform.
    // We assume the mark has not already been added to the input.
    static String transform(String input, char mark)
    {
        assert input.indexOf(mark)<0;
        int len = input.length();
        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);
        StringBuilder ret = new StringBuilder();
        for (int i = 0; i <= len; ++i)
            ret.append(shifts[i].charAt(len));
        return ret.toString();
    }

    // The reverse transformation, return the original input text.
    static String transformBack(String bwtrans, char mark) {
        int at = bwtrans.indexOf(mark);
        assert at >= 0;
        throw new UnsupportedOperationException
            ("transformBack is not implemented");
    }
}