package com.lin.HuffmanCode_0314;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class HuffmanCode {

    public static void main(String[] args) {
        
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
        System.out.println(contentBytes.length); // 40
        
        List<Node> nodes = getNodes(contentBytes);
        System.out.println(nodes);
        
        // 创建哈夫曼树
        System.out.println("哈夫曼树");
        Node createHuffmanTree = createHuffmanTree(nodes);
        
        preOrder(createHuffmanTree);
        
    }
    
    /**
     * 
     * @Description:生成赫夫曼树对应的赫夫曼编码<br>
     *                 思路：将赫夫曼编码存放在Map< 
     * @author LinZM  
     * @date 2021-3-14 21:09:30 
     * @version V1.8
     */
    
    // 前序遍历
    private static void preOrder(Node root){
        if(root != null) {
            root.preOrder();
        } else {
            System.out.println("空树！");
        }
    }
    /**
     * 
     * @Description: 
     * @author LinZM  
     * @date 2021-3-14 20:45:23 
     * @version V1.8
     * @param bytes接收字节数组
     * @param 
     */
    private static List<Node> getNodes(byte[] bytes){
        // 1 创建一个ArrayList
        ArrayList<Node> nodes= new ArrayList<Node>();
        
        // 遍历bytes，统计每一个byte出现的次数->map[key, value]
        Map<Byte, Integer> counts = new HashMap();
        for(byte b: bytes) {
            Integer count = counts.get(b);    // 
            if(count == null) {    // Map中还没有这个字符数据, 第一次
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }
        // 把每个键值对转成一个Node对象， 并加入到nodes集合
        for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }
    
    // 通过List创建赫夫曼树
    private static Node createHuffmanTree(List<Node> nodes) {
        while(nodes.size() > 1) {
            Collections.sort(nodes);
            
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            
            parent.left = leftNode;
            parent.right = rightNode;
            
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            
            nodes.add(parent); 
        }
    return nodes.get(0);
    }
    
    
}

class Node implements Comparable<Node>{
    Byte data;// 存放数据本身
    int weight; // 权值，字符出现的次数
    Node left;
    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        // TODO Auto-generated method stub
        return this.weight - o.weight;
    }
    
    @Override
    public String toString() {
        return "Node [data = " + data + " weight= " + weight + "]";
    }
    
    // 前序遍历
    public void preOrder() {
        System.out.println(this);
        if(this.left != null) {
            this.left.preOrder();
        }
        if(this.right != null) {
            this.right.preOrder();
        }
    }
}