import java.io.*;
import java.util.*;

/**
 * @author Scott Douglas ( scott@scottdouglas.net )
 */
public class HuffmanEncoder {

	public static void main(String[] args) {
		if ( args.length != 1 ) {
			System.err.println( "Usage: HuffmanEncoder filename" );
			System.exit( 0 );
		} 
		
		List characters = new ArrayList();
		int currentChar;
		
		System.out.println( "Beginning Encoding" );
		
		try {
			BufferedReader input = new BufferedReader( new FileReader( args[ 0 ] ) );
		
			System.out.println( "=Generating Frequency Table" );
						
			currentChar = input.read();
			
			// Initialize Array List ( oly 256 valid ASCII characters )
			for ( int i = 0; i < 256; i++ ) {
				characters.add( new HuffmanCharacter( ( char ) i ) );	
			}
			
			// Read in a char at a time while there still are chars
			while( currentChar != -1 ) {
				if ( currentChar < 0 || currentChar > 255 ) {
					System.err.println( "HuffmanEncoder: File contains non-ASCII characters.  Can not compress." );
					System.exit( 0 );
				}
				HuffmanCharacter theCharacter = ( HuffmanCharacter ) characters.get( currentChar );
				theCharacter.incrementFrequency();
				currentChar = input.read();
			}
			
			input.close();
		} catch( FileNotFoundException e ) {
			System.err.println( "HuffmanEncoder: " + args[ 0 ] + " could not be found" );
			System.exit( 0 );
		} catch( IOException e ) {
			System.err.println( "HuffmanEncoder: IO Error" );
			System.exit( 0 );
		}
		
		System.out.println( "=Creating Tree of Character Frequencies" );
		System.out.println( "==Creating Nodes" );
		
		List unusedChars = new LinkedList();
		List unusedNodes = new LinkedList();
		List allNonNullNodes = new LinkedList();
		
		// Trim zero frequency characters
		for ( int i = 0; i < characters.size(); i++ ) {
			HuffmanCharacter aCharacter = ( HuffmanCharacter ) characters.get( i );
			if ( aCharacter.getFrequency() > 0 ) {
				unusedChars.add( aCharacter );
			}
		}	
		
		for ( int i = 0; i < unusedChars.size(); i++ ) {
			HuffmanTreeNode aNode = new HuffmanTreeNode( (HuffmanCharacter) unusedChars.get( i ) );
			unusedNodes.add( aNode );
			allNonNullNodes.add( aNode );
		}
		
		System.out.println( "===Nodes: " + unusedNodes );
		System.out.println( "==Connecting Nodes" );
		System.out.println( "===Total Unique Characters in file: " + unusedNodes.size() );
		
		if ( unusedNodes.size() == 0 ) {
			System.err.println( "===No Nodes to connect" );
			System.err.println( "===Error Encoding...Exiting" );
			System.exit( 0 );
		}
	
		Collections.sort( unusedNodes );

		while ( unusedNodes.size() > 1 ) {
			HuffmanTreeNode newNode = new HuffmanTreeNode();
			newNode.setLeftNode( ( HuffmanTreeNode ) unusedNodes.remove( 0 ) );
			newNode.setRightNode( ( HuffmanTreeNode ) unusedNodes.remove( 0 ) );
			unusedNodes.add( newNode );
			Collections.sort( unusedNodes );
			
			System.out.println( "===Connecting " + newNode.getLeftNode() + " to " + newNode.getRightNode() );
		}
	
		HuffmanTreeNode root = ( HuffmanTreeNode ) unusedNodes.remove( 0 );
		
		System.out.println( "===Total Characters In file: " + root.getCharacterFrequency() );
		System.out.println( "=Assigning bit representations to nodes" );

		HuffmanBitList bitList = root.getBits();
		//bitList.appendBit( false );
		root.assignBits();
		
		System.out.println( "=Substituting bits for characters and saving" );
		
		HuffmanBitList compressed = new HuffmanBitList();
		long bitCount = 0;
		
		try {
			BitOutputStream outputBits = new BitOutputStream( new FileOutputStream( "output.comp") );
			BufferedReader input = new BufferedReader( new FileReader( args[ 0 ] ) );
			currentChar = input.read();
			
			// Read in a char at a time while there still are chars
			while( currentChar != -1 ) {
				// Get the characters bit representation and write to file
				HuffmanCharacter theCharacter = new HuffmanCharacter( (char) ( currentChar ) );
				compressed = getBitRepresentation( theCharacter, allNonNullNodes );
				for ( int i = 0; i < compressed.size(); i++  ) {
					if ( compressed.getBitAt( i ).booleanValue() == true ) {
						outputBits.writeBit( 1 );
					} else {
						outputBits.writeBit( 0 );
					}
					bitCount++;
				}				
				
				currentChar = input.read();
			}
			
			outputBits.flushToFile();
			outputBits.close();
			input.close();
		} catch( FileNotFoundException e ) {
			System.err.println( "HuffmanEncoder: " + args[ 0 ] + " could not be found" );
			System.exit( 0 );
		} catch( IOException e ) {
			System.err.println( "HuffmanEncoder: IO Error" );
			System.exit( 0 );
		}	

		FrequencyTable.saveTableFromNodes( allNonNullNodes, "output.freq", bitCount );
		
		System.out.println( "Done Encoding" );
	}
	
	private static HuffmanBitList getBitRepresentation( HuffmanCharacter character, List allNonNullNodes ) {
		HuffmanBitList bitRepresentation = new HuffmanBitList();
		for ( int i = 0; i < allNonNullNodes.size(); i++ ) {
			HuffmanTreeNode aNode = ( HuffmanTreeNode ) allNonNullNodes.get( i );
			
			if ( character.equals( aNode.getCharacter() ) ) {
				bitRepresentation = aNode.getBits();
			}
		}
		
		return bitRepresentation;
	}

	/*
	private static HuffmanCharacter getHuffmanCharacter( HuffmanCharacter characterToFind, Set aSet ) {
		HuffmanCharacter foundCharacter = null;
		
		for( Iterator i = aSet.iterator(); foundCharacter == null && i.hasNext(); ) {
			HuffmanCharacter aCharacter = ( HuffmanCharacter ) i.next();
			if ( aCharacter.equals( characterToFind ) ) {
					foundCharacter = aCharacter;
			}
		}
		
		return foundCharacter;
	}
	*/
	/*
	private static HuffmanTreeNode findSmallestNode( Set unusedNodes, Map frequencies ) {
		HuffmanTreeNode smallestNode = null;
		
		// Loop over the unused nodes
		for ( Iterator i = unusedNodes.iterator(); i.hasNext(); ) {
			// Get the next node
			HuffmanTreeNode aNode = ( HuffmanTreeNode ) i.next();
			
			// Check if the smallest node hasn't been set yet, if not, set it; otherwise test
			if ( smallestNode == null ) {
				smallestNode = aNode;
			} else {
				int smallestFrequency = ( ( Integer ) frequencies.get( smallestNode.getNodeValue() ) ).intValue();
				int aFrequency = ( ( Integer ) frequencies.get( aNode.getNodeValue() ) ).intValue();
				
				if ( aFrequency < smallestFrequency ) {
					smallestNode = aNode;
				}
			}
		}

		return smallestNode;
	}
	*/
}