Lzw - lzw

/*
 * LZW.java
 *
 * Created on 01 Dec 2005
 *
 * Implementation of LZW compression/decompression algorithm
 */
import java.io.* ;
/**
 *
 * @author  Moshe Fresko
 * @course	Algorithmic Programming 1
 * @exercise	3
 */
public class LZW implements Compression
{
	boolean stopped = false ;
	Dict dict ;
		// The bits that should be written for each code
	int numOfBits ;
		// The previous string that we should remember
		// in order to insert into the dictionary
	final ByteArray emptyBA = new ByteArray() ;
	ByteArray w=emptyBA ;
		// Constructor gets the number of bits to be written for each code
	public LZW()
	{
		numOfBits = 12 ;
			// Create a new Limited Dictionary
			// For maximum of 2^bits entries
		dict = new LimitedDict(1<<numOfBits) ;
			// Add all ascii characters to the dictionary
		for (int i=0;i<256;++i)
			dict.add(new ByteArray((byte)i)) ;
	}
		// Encodes the next character.
		// If there is a code generated returns it.
		// If not returns -1.
	int encodeOneChar(int n) {
		byte c = (byte) n ;
		ByteArray nw = w.conc(c) ;
		int code = dict.numFromStr(nw) ;
			// if it exists then we continue to search for a longer string
		if (code!=-1) {
			w = nw ;
			return -1 ;
		} else {
			dict.add(nw) ;
			nw = w ;
			w = new ByteArray(c) ;
			return dict.numFromStr(nw) ;
		}
	}
		// If there is something left in w, returns its code
	int encodeLast() {
		ByteArray nw = w ;
		w = emptyBA ;
		return dict.numFromStr(nw) ;
	}
		// Write the code in bits into output stream
	void writeCode(OutputStream os, int code) throws IOException
	{
		for (int i=0;i<numOfBits;++i) {
			os.write(code&1) ;
			code /= 2 ;
		}
	}
	int readCode(InputStream is) throws IOException
	{
		int num = 0 ;
		for (int i=0;i<numOfBits;++i) {
			int next = is.read() ;
			if (next<0)
				return -1 ;
			num += next<<i ;
		}
		return num ;
	}
	public void compress(InputStream is, OutputStream os) throws IOException {
		os = new BitOutputStream(os) ;
		int next ;	// next input character
		int code ;	// next code generated
		while ((next=is.read())>=0) {
			if (stopped)
				break ;
			code = encodeOneChar(next) ;
			if (code>=0)
				writeCode(os,code) ;
		}
		code = encodeLast() ;
		if (code>=0)
			writeCode(os,code) ;
    os.flush() ;
	}
	ByteArray decodeOne(int code) {
			// Either "ABA" or null, w="AB"
		ByteArray str = dict.strFromNum(code) ;
		if (str==null) {
			str = w.conc(w.getAt(0)) ;
			dict.add(str) ;
		} else
			if (! w.isEmpty())
				dict.add(w.conc(str.getAt(0))) ;
            w = str ;
		return w ;
	}
	public void decompress(InputStream is, OutputStream os) throws IOException {
		is = new BitInputStream(is) ;
		ByteArray str ;	// Next entry
		int code ;		// Next code to be read
		while ((code=readCode(is))>=0) {
			if (stopped)
				break ;
			str = decodeOne(code) ;
			os.write(str.getBytes()) ;
		}
	}
	public void stop()
		{ stopped = true ; }
}