package algs55; // section 5.5
import stdlib.*;
import algs52.TST;
/* ***********************************************************************
 *  Compilation:  javac LZW.java
 *  Execution:    java LZW - < input.txt   (compress)
 *  Execution:    java LZW + < input.txt   (expand)
 *  Dependencies: BinaryIn.java BinaryOut.java
 *
 *  Compress or expand binary input from standard input using LZW.
 *
 *  WARNING: STARTING WITH ORACLE JAVA 6, UPDATE 7 the SUBSTRING
 *  METHOD TAKES TIME AND SPACE LINEAR IN THE SIZE OF THE EXTRACTED
 *  SUBSTRING (INSTEAD OF CONSTANT SPACE AND TIME AS IN EARLIER
 *  IMPLEMENTATIONS).
 *
 *  See <a href = "http://java-performance.info/changes-to-string-java-1-7-0_06/">this article</a>
 *  for more details.
 *
 **************************************************************************/

public class LZW {
	private static BinaryIn binaryIn;
	private static BinaryOut binaryOut;

	private static final int R = 256;        // number of input chars
	private static final int L = 4096;       // number of codewords = 2^W
	private static final int W = 12;         // codeword width

	public static void compress() {
		String input = binaryIn.readString();
		TST<Integer> st = new TST<>();
		for (int i = 0; i < R; i++)
			st.put("" + (char) i, i);
		int code = R+1;  // R is codeword for EOF

		while (input.length() > 0) {
			String s = st.longestPrefixOf(input);  // Find max prefix match s.
			binaryOut.write(st.get(s), W);         // Print s's encoding.
			int t = s.length();
			if (t < input.length() && code < L)    // Add s to symbol table.
				st.put(input.substring(0, t + 1), code++);
			input = input.substring(t);            // Scan past s in input.
		}
		binaryOut.write(R, W);
		binaryOut.close();
	}


	public static void expand() {
		String[] st = new String[L];
		int i; // next available codeword value

		// initialize symbol table with all 1-character strings
		for (i = 0; i < R; i++)
			st[i] = "" + (char) i;
		st[i++] = "";                        // (unused) lookahead for EOF

		int codeword = binaryIn.readInt(W);
		String val = st[codeword];

		while (true) {
			binaryOut.write(val);
			codeword = binaryIn.readInt(W);
			if (codeword == R) break;
			String s = st[codeword];
			if (i == codeword) s = val + val.charAt(0);   // special case hack
			if (i < L) st[i++] = val + s.charAt(0);
			val = s;
		}
		binaryOut.close();
	}



	public static void main(String[] args) {
		String txtFile = "data/genomeTiny.txt";
		String binFile = "/tmp/genomeTiny.bin";
		//args = new String[] { "+" }; binaryIn = new BinaryIn(binFile); binaryOut = new BinaryOut();
		args = new String[] { "-" }; binaryIn = new BinaryIn(txtFile); binaryOut = new BinaryOut(binFile);
		if      (args[0].equals("-")) compress();
		else if (args[0].equals("+")) expand();
		else throw new Error("Illegal command line argument");
	}

}