package huffman;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.util.LinkedList;

/**
 * 利用哈夫曼编码实现文件压缩的类
 * 
 * @author dongyunqi
 * @date 2018年7月30日上午9:53:45
 * @description
 */
public class Conpress {
	// 0~255个位置，存储所有字符出现的次数，注意仅限于英文字母
	public int[] times = new int[256];
	// 存储每个字符（ASCII码）的哈夫曼编码
	public String[] huffmCodes = new String[256];
	public LinkedList<HuffmanNode1> list = new LinkedList<HuffmanNode1>();

	public Conpress() {
		// 循环赋值，避免空指针
		for (int i = 0; i < huffmCodes.length; i++) {
			huffmCodes[i] = "";
		}
	}

	/**
	 * 统计文件中每个字符出现的次数
	 * 
	 * @param path
	 *            要统计文件的路径
	 * @throws Exception
	 */
	public void countTimes(String path) throws Exception {
		FileInputStream fis = new FileInputStream(path);
		int value = fis.read();
		while (value != -1) {
			times[value]++;
			value = fis.read();
		}
		// 关闭流
		fis.close();
	}

	/**
	 * 根据统计字符次数信息构建哈夫曼树（次数作为权值使用）
	 * 
	 * @return
	 */
	public HuffmanNode1 createTree() {
		// 将次数作为权值构造森林
		for (int i = 0; i < times.length; i++) {
			// 0说明该数组对应对应的字符没有出现过，所以需要跳过
			if (times[i] != 0) {
				HuffmanNode1 node = new HuffmanNode1(i, times[i]);
				// 将构造好的节点加入到容器中的正确位置，保证权值越大越靠前,这样最终的得到一个
				// 权值由大到小依次排列的列表集合
				list.add(getIndex(node), node);
			}
		}
		// 将森林（容器中的各个节点）构造成哈夫曼树
		while (list.size() > 1) {
			// 获取容器中第一个元素（权值最小的节点）
			HuffmanNode1 firstNode = list.removeFirst();
			// 获取中新的第一个元素，原来的第一个元素已经被移除了（权值次小的节点）
			HuffmanNode1 secondNode = list.removeFirst();
			// 将权值最小的两个节点构造成父节点
			HuffmanNode1 fatherNode = new HuffmanNode1(-1,
						firstNode.getWeight() + secondNode.getWeight());
			// 权值较小的作为新根节点左子节点，建立父子关系
			fatherNode.setLeftNode(firstNode);
			// 权值较大的作为新根节点的右子节点，建立父子关系
			fatherNode.setRightNode(secondNode);
			// 父节点加入到容器中的正确位置
			list.add(getIndex(fatherNode), fatherNode);
		}
		return list.getFirst();
	}

	// 利用前序遍历获取编码表
	public void getHuffmCode(HuffmanNode1 root, String code) {
		// 往左走，哈夫曼编码加0
		if (root.getLeftNode() != null) {
			getHuffmCode(root.getLeftNode(), code + "0");
		}
		// 往右走，哈夫曼编码加1
		if (root.getRightNode() != null) {
			getHuffmCode(root.getRightNode(), code + "1");
		}
		// 如果是叶子节点，返回该叶子节点的哈夫曼编码
		if (root.getLeftNode() == null && root.getRightNode() == null) {
			// System.out.println(root.getIndex()+"的编码为："+code);
			huffmCodes[root.getData()] = code;
		}
	}

	public void compress(String path, String destpath) throws Exception {
		// 构建文件输出流
		FileOutputStream fos = new FileOutputStream(destpath);
		FileInputStream fis = new FileInputStream(path);
		/** ===============把码表写入文件================ */
		// 记录顺序记录每个哈夫曼编码长度信息开始 //
		String code = "";
		for (int i = 0; i < 256; i++) {
			fos.write(huffmCodes[i].length());
			code += huffmCodes[i];
			fos.flush();
		}
		// 记录顺序记录每个哈夫曼编码长度信息结束 //
		// System.out.println("code=" + code);
		// 记录哈夫曼编码信息开始，八个字符为一组生成一个整数 //
		String str1 = "";
		while (code.length() >= 8) {
			str1 = code.substring(0, 8);
			int c = changeStringToInt(str1);
			// System.out.println(c);
			fos.write(c);
			fos.flush();
			code = code.substring(8);
		}
		// 处理最后一个不为8的数
		int last = 8 - code.length();
		for (int i = 0; i < last; i++) {
			code += "0";
		}
		str1 = code.substring(0, 8);
		int c = changeStringToInt(str1);
		fos.write(c);
		fos.flush();
		// 记录哈夫曼编码信息结束，八个字符为一组生成一个整数 //
		// 正式写入压缩数据开始 //
		// 读取文件，将每个字符对应生成的哈夫曼码拼接为一个完整的字符串
		// 然后对字符串8字符一组进行处理，生成一个整数，写入到压缩二进制文件中
		// 读文件，并将对应的哈夫曼编码串接成字符串
		int value = fis.read();
		String str = "";
		while (value != -1) {
			// 拼接当前字符的哈夫曼码
			str += huffmCodes[value];
			// System.out.println((char)value+":"+str);
			value = fis.read();
		}
		// System.out.println(str);
		fis.close();
		String s = "";
		// 将字符8位分割，对弈一个字节
		while (str.length() >= 8) {
			s = str.substring(0, 8);
			int b = changeStringToInt(s);
			// System.out.println(c);
			fos.write(b);
			fos.flush();
			str = str.substring(8);
		}
		// 最后不够8位添0
		int last1 = 8 - str.length();
		for (int i = 0; i < last1; i++) {
			str += "0";
		}
		s = str.substring(0, 8);
		// System.out.println(s);
		int d = changeStringToInt(s);
		fos.write(d);
		// 压缩后不够补0的个数暂
		fos.write(last1);
		fos.flush();
		fos.close();
		// 正式写入压缩数据结束 //
	}

	// 将字符串转换成整数
	public int changeStringToInt(String s) {
		int v1 = (s.charAt(0) - 48) * 128;
		int v2 = (s.charAt(1) - 48) * 64;
		int v3 = (s.charAt(2) - 48) * 32;
		int v4 = (s.charAt(3) - 48) * 16;
		int v5 = (s.charAt(4) - 48) * 8;
		int v6 = (s.charAt(5) - 48) * 4;
		int v7 = (s.charAt(6) - 48) * 2;
		int v8 = (s.charAt(7) - 48) * 1;
		return v1 + v2 + v3 + v4 + v5 + v6 + v7 + v8;
	}

	// 插入元素位置的索引，保证权值越大越靠前
	public int getIndex(HuffmanNode1 node) {
		for (int i = 0; i < list.size(); i++) {
			if (node.getWeight() <= list.get(i).getWeight()) {
				return i;
			}
		}
		return list.size();
	}
}