//Jed Stark
//IT 214
import java.io.*;
//http://en.allexperts.com/q/Java-1046/counting-characters-file.htm
/**
* CountLetters - read unicode characters
* from an input file, count the
* occurrences of each character, then
* print the counts only for letters. To
* handle just ASCII, change MAX_CHAR to 255.
*/
 
class Node
{
	//Our instance variables
	private char value;
	private int count;
	private Node left;
	private Node right;
	private Node link;
 
 
	//The constructor method
	public Node() {
		this.left = null;
		this.right = null;
		this.link = null;
	}
 
	public Node(char value, int count)
	{
		this.value = value;
		this.count = count;
		this.right= null;
		this.left = null;
		this.link = null;
	}
	// The set methods
	public void setLink(Node p)
	{
		link = p;
	}	
	public void setLeft(Node p)
	{
		left = p;
	}
	public void setRight(Node p)
	{
		right = p;
	}
	public void setValue(char p)
	{
		value = p;
	}
	public void setCount(int r)
	{
		count = r;
	}
 
	//The get methods
 
	public int getCount()
	{
		return count;
	}
	public char getValue()
	{
		return value;
	}
	public Node getLeft()
	{
		return left;
	}
	public Node getRight()
	{
		return right;
	}
	public Node getLink()
	{
		return link;
	}
	public String printer()
	{
		return "Character is "+value+" and there were "+count+".";
	}	
 
}
class OrderedLinkedList
{
	private Node head;
	public OrderedLinkedList()
	{
		this.head = null;
	}
 
	public Node buildRoot() {
		Node root = new Node();
		root.setLeft(head);
		root.setRight(head.getLink());
		root.setLink(head);
		return root;
	}
 
	public Node buildTree(Node current, int X, Node leftspot, Node rightspot, Node root) {
		while (current != null) {
			if (X == 1) {
				leftspot = head;
				rightspot = head.getLink();
				X++;
			}
			current.setLeft(leftspot);
			leftspot = moveLeftSpot(leftspot);
			current.setRight(rightspot);
			rightspot = moveRightSpot(rightspot);
			buildTree(current.getLink(), X, leftspot, rightspot, root);
		}
		return root;
	}
 
 
	public Node moveLeftSpot(Node leftspot) {
		if (leftspot == null) 
			leftspot = null;
		else {
			leftspot = leftspot.getLink();
			leftspot = leftspot.getLink();
		}
		return leftspot;
	}
 
	public Node moveRightSpot(Node rightspot) {
		if (rightspot == null)
			rightspot = null;
		else {
			rightspot = rightspot.getLink();
			rightspot = rightspot.getLink();
		}
		return rightspot;
	}
 
	public void insert(Node p)
	{
		Node front = head;
		Node back = null;
		while ((front != null) && (p.getCount() <= front.getCount()))
		{
			back = front;
			front = front.getLink();
		}
		if (head == null)
		{
			head = p;
		}
		else if (p.getCount() > head.getCount())
		{
			p.setLink(head);
			head = p;
		}
		else
		{
			p.setLink(front);
			back.setLink(p);
		}
	}
	//The traverse method for moving through the list
	public void traverse()
	{
		Node p = head;
		while(p != null)
		{
			System.out.println(p.printer());
			p = p.getLink();
		}
	}
		//The delete method. Gives confirmation when someone is deleted, or returns an error if they are not.
	public void delete(char target)
	{
		Node front = head;
		Node back = null;
		while ((front != null) && ((target !=front.getValue())))
		{
			back = front;
			front = front.getLink();
		}
		if (front == null)
			System.out.println("Target not in list");
		else if (target == head.getValue())
		{	
			head = head.getLink();
			System.out.println("ID "+target+" has been deleted.");
		}
 
		else
		{
			back.setLink(front.getLink());
			front.setLink(null);
			System.out.println("ID "+target+" has been deleted.");
		}
	}
 
}
public class HuffmanTest {
	public static final int MAX_CHAR = 65535;
	public static void printTree(Node node, int depthI, String spaceS){
		if (node == null) return;
			printTree(node.getRight(), depthI+1, spaceS + "      ");
			printTreeResult(node, spaceS);
			printTree(node.getLeft(), depthI+1, spaceS + "      ");
	}
 
 
	public static void printTreeResult(Node node, String spaceS){
		System.out.println(spaceS + node.getValue());
	}	
	public static void main(String[] args) {
		OrderedLinkedList myList = new OrderedLinkedList();
		Node newNode;
		Node root;
		Node finalTree;
		Node leftspot = null;
		Node rightspot = null;
		char newChar;
		int charCount;
		int c;
		long total;
		File inputFile = new File("myIn.txt");
		File outputFile = new File("myOut.txt");
		int counts[];
		counts = new int[MAX_CHAR+1];
		total = 0;
		try {
			FileReader in = new FileReader(inputFile);			
			for(total = 0;(c = in.read()) != -1; total++) {
				if (c <= MAX_CHAR) counts[c] += 1;
			}
			in.close();
		}
		catch (IOException e) {
			System.err.println("I/O Error: " + e);
		System.exit(1);
		}
		// print the counts for all letters
		try {
			FileWriter out = new FileWriter(outputFile);
			for(c = 0; c <= MAX_CHAR; c++) {
				if (counts[c] > 0) {
					newChar = (char)c;
					charCount = counts[c];
					newNode = new Node(newChar, charCount);
					myList.insert(newNode);
					System.out.println(" " + (char)c + " " +
						counts[c]);
					out.write(" " + (char)c + " " + counts[c]+"\r\n");
				}
			}
			out.close();
		}
		catch (IOException e) {
			System.err.println("I/O Error: " + e);
		System.exit(1);
		}
		root = myList.buildRoot();
		myList.buildTree(root, 1, leftspot, rightspot, root);
		printTree(root, 0, " ");
		System.out.println("Total chars read: " + total);
		myList.traverse();
	}    
}