/**
 * 构建赫夫曼树
 */
public static Node createHuffman(int[] arr) {
    List<Node> list = new ArrayList<>(arr.length);
    for (int value : arr) {
        list.add(new Node(value));
    }

    while (list.size() > 1) {
        Collections.sort(list);
        //先排序，从小到大
        Node leftNode = list.get(0);
        Node rigthNode = list.get(1);
        Node parent = new Node(leftNode.no + rigthNode.no);
        parent.left = leftNode;
        parent.rigth = rigthNode;

        list.remove(leftNode);
        list.remove(rigthNode);
        list.add(parent);
    }
    return list.get(0);
}

static class Node implements Comparable<Node>{
    int no;
    Node left;
    Node rigth;

    public Node(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "Node[" +
                "no=" + no +
                ']';
    }

    @Override
    public int compareTo(Node node) {
        return this.no - node.no;
    }
}

/**
 * 整合 : 将原始的数据转换为赫夫曼数组
 */
private static byte[] encodeToHuffmanBytes(byte[] contentBytes) {
    //第一步:构建node结点集合，将每个字符(byte)出现的次数统计并封装到list集合中
    List<Node> nodes = getNodes(contentBytes);
    //第二步:构建赫夫曼树
    Node root = creatHuffmanTree(nodes);
    //第三步:获取赫夫曼树中每个结点对应的字符(byte)，出现对应的路径。其中key为字符(byte)，value为路径(0,1组装)
    Map<Byte, String> nodePath = getNodePath(root);
    //第四步:根据字符路径集合，获取赫夫曼编码的字符串
    String huffmanCode = createHuffmanCode(contentBytes, nodePath);
    System.out.println(huffmanCode);
    //第五步:将赫夫曼编码字符串，转换为压缩后的赫夫曼数组
    return convertToHuffmanBytes(huffmanCode);
}

/**
 * 将赫夫曼编码数据转换为压缩之后的数组
 *
 * @param code 赫夫曼编码的字符串
 * @return 赫夫曼压缩数组
 */
private static byte[] convertToHuffmanBytes(String code) {
    //获取转换后数组长度
    int length = (code.length() + 7) / 8;
    byte[] bytes = new byte[length+1];
    for (int i = 0, index = 0; i < code.length(); i += 8, index++) {
        if (code.length() > i + 8) {
            //将2进制转成10进制  并强转为byte
            bytes[index] = (byte) Integer.parseInt(code.substring(i, i + 8), 2);
        } else {
            //最后一个byte存储  倒数第二个字节的位数(防止出现0110->6->110)  出现位数少1的情况 最后无法匹配而报错
            String substring = code.substring(i);
            bytes[index] = (byte) Integer.parseInt(substring, 2);
            bytes[index + 1] = (byte) substring.length();
        }
    }
    return bytes;
}

/**
 * 获取赫夫曼编码的字符串
 */
private static String createHuffmanCode(byte[] contentBytes, Map<Byte, String> nodePath) {
    StringBuilder stringBuilder = new StringBuilder();
    for (byte key : contentBytes) {
        stringBuilder.append(nodePath.get(key));
    }
    return stringBuilder.toString();
}

/**
 * 根据根节点获取对应的编码集合
 */
private static Map<Byte, String> getNodePath(Node node) {
    return getNodePath(node, "", new StringBuilder());
}

static Map<Byte, String> huffmanCodeMap = new HashMap<>();

/**
 * 获取对应的节点和对应的编码
 *
 * @param node          需要获取的节点
 * @param code          当前节点相对上一个节点的编码
 * @param stringBuilder 父节点的路径
 * @return map集合:key为字符byte,value为路径
 */
private static Map<Byte, String> getNodePath(Node node, String code, StringBuilder stringBuilder) {
    StringBuilder sb = new StringBuilder(stringBuilder);
    sb.append(code);
    if (node != null) {
        //非叶子结点
        if (node.data == null) {
            //左子树
            getNodePath(node.left, "0", sb);
            //右子数
            getNodePath(node.right, "1", sb);
        } else {
            //叶子结点
            huffmanCodeMap.put(node.data, sb.toString());
        }
    }
    return huffmanCodeMap;
}

/**
 * 获取节点集合
 */
private static List<Node> getNodes(byte[] contentBytes) {
    //先统计bytes中每个字节的次数
    Map<Byte, Integer> map = new HashMap<>();
    for (byte key : contentBytes) {
        map.put(key, map.get(key) == null ? 1 : map.get(key) + 1);
    }

    List<Node> list = new ArrayList<>();
    for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
        list.add(new Node(entry.getKey(), entry.getValue()));
    }
    return list;
}

/**
 * 生成赫夫曼树
 */
private static Node creatHuffmanTree(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.count + rightNode.count);
        parent.left = leftNode;
        parent.right = rightNode;

        nodes.remove(leftNode);
        nodes.remove(rightNode);
        nodes.add(parent);
    }

    return nodes.get(0);
}

public static void preOrder(Node root) {
    if (root == null) {
        System.out.println("当前二叉树为空，不能遍历!");
        return;
    }
    root.preOrder();
}


/**
 * 结点
 */
static class Node implements Comparable<Node> {
    //字节 i l i ...
    Byte data;
    //出现的次数
    Integer count;
    //左子树
    Node left;
    //右子数
    Node right;

    //前序遍历
    public void preOrder() {
//            System.out.println((this.data == null?null:(char)Integer.parseInt(this.data.toString()))+"\t"+this.count);
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    public Node(Byte data, Integer count) {
        this.data = data;
        this.count = count;
    }

    @Override
    public String toString() {
        return "Node[" +
                "data=" + data +
                ", count=" + count +
                ']';
    }

    @Override
    public int compareTo(Node o) {
        return this.count - o.count;
    }
}

/**
 * 转换成原始的字符串
 */
private static byte[] decodeToSourceStr(byte[] bytes, Map<Byte, String> huffmanMap) {
    //先将数组转换为对应的赫夫曼编码的10010..组成的字符串
    String huffmancode = decodeBytesToHuffmancode(bytes);
    System.out.println(huffmancode);
    //将赫夫曼编码转换为对应的字符串
    return decodeHuffmancodeToSourceStr(huffmancode, huffmanMap);
}

/**
 * 将赫夫曼编码进行解码为原始字节数组
 *
 * @param huffmancode 赫夫曼编码
 * @param huffmanMap  记录原始字节与编码的map集合
 * @return 原始字符串
 */
private static byte[] decodeHuffmancodeToSourceStr(String huffmancode, Map<Byte, String> huffmanMap) {
    //将map反转。原来是32->010,98->001... 转换为001->98,010->32...
    Map<String, Byte> map = new HashMap<>();
    for (Map.Entry<Byte, String> entry : huffmanMap.entrySet()) {
        map.put(entry.getValue(), entry.getKey());
    }
    //原始字节集合
    List<Byte> byteList = new ArrayList<>();
    for (int i = 0; i < huffmancode.length(); ) {
        StringBuilder stringBuilder = new StringBuilder();
        //将huffman编码组成的字符村1000100011...，进行遍历。
        //当指针指向一定的值存储在反转红藕的map集合中时，停止
        while (map.get(stringBuilder.toString()) == null) {
            if (i >= huffmancode.length()) {
                break;
            }
            stringBuilder.append(huffmancode.charAt(i));
            i++;
        }
        //获取每个字符，并组装成对应的字符串
        Byte aByte = map.get(stringBuilder.toString());
        byteList.add(aByte);
    }
    byte[] bytes = new byte[byteList.size()];
    for (int i = 0; i < byteList.size(); i++) {
        bytes[i] = byteList.get(i);
    }
    return bytes;
}

/**
 * 将压缩后的数组转换为赫夫曼编码
 *
 * @param bytes 压缩后的字节数组
 * @return 赫夫曼编码
 */
private static String decodeBytesToHuffmancode(byte[] bytes) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < bytes.length; i++) {
        byte b = bytes[i];
        //将当前byte转换为二进制字符串
        String binaryString = Integer.toBinaryString(b);
        //判断当前二进制是否长度大于8，如果大于8则截取
        if (binaryString.length() > 8) {
            sb.append(binaryString.substring(binaryString.length() - 8));
        } else {
            //判断是否为倒数第二个字节，如果为倒数第二个字节  则其二进制的长度应该为倒数第一个数的长度。
            if (i == bytes.length - 2) {
                byte last = bytes[i + 1];
                int length = binaryString.length();
                StringBuilder builder = new StringBuilder();
                //将少于倒数第一个数值长度 的二进制  前面用0 补齐
                for (int j = 0; j < last - length; j++) {
                    builder.append(0);
                }
                builder.append(binaryString);
                sb.append(builder);
                break;
            } else {
                //如果不是则补齐前面的0
                int length = binaryString.length();
                StringBuilder builder = new StringBuilder();
                for (int j = 0; j < 8 - length; j++) {
                    builder.append(0);
                }
                builder.append(binaryString);
                sb.append(builder);
            }
        }

    }
    return sb.toString();
}

/**
 * 压缩文件
 *
 * @param srcFile  原始文件路径
 * @param destFile 压缩后文件路径
 */
private static void zipFile(String srcFile, String destFile) {
    InputStream is = null;
    OutputStream os = null;
    //对象输出流
    ObjectOutputStream oos = null;
    try {
        is = new FileInputStream(srcFile);
        //创建原始字节数组
        byte[] bytes = new byte[is.available()];
        //读取文件
        is.read(bytes);
        //压缩
        byte[] zip = zip(bytes);

        os = new FileOutputStream(destFile);
        //关联
        oos = new ObjectOutputStream(os);
        //将压缩之后的数组 和 赫夫曼编码对应关系 写出
        oos.writeObject(zip);
        oos.writeObject(huffmanCodeMap);
    } catch (Exception e) {
        e.printStackTrace();
    } finally {
        try {
            oos.close();
            os.close();
            is.close();
        } catch (IOException e) {
            e.printStackTrace();
        }

    }
}

/**
 * 解压文件
 *
 * @param srcFile   压缩之后的文件
 * @param destFile  解压后的文件
 */
private static void unzipFile(String srcFile, String destFile) {
    InputStream is = null;
    ObjectInputStream ois = null;
    OutputStream os = null;
    try {
        is = new FileInputStream(srcFile);
        ois = new ObjectInputStream(is);
        //读取压缩之后的 文件 和 对应的赫夫曼编码
        byte[] zipBytes = (byte[]) ois.readObject();
        Map<Byte, String> huffmanMap = (Map<Byte, String>) ois.readObject();

        //解压
        byte[] srcBytes = unzip(zipBytes, huffmanMap);

        //输出
        os = new FileOutputStream(destFile);
        os.write(srcBytes);
    } catch (Exception e) {
        e.printStackTrace();
    }finally {
        try {
            os.close();
            ois.close();
            is.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

/**
 * 添加结点
 */
public void add(Node node) {
    if (node == null) {
        return;
    }
    //如果当前节点值大于添加的值
    if (this.value > node.value) {
        //如果左节点不为空就向左递，否则就赋值给左节点
        if (this.left != null) {
            this.left.add(node);
        } else {
            this.left = node;
        }
    } else {
        if (this.right != null) {
            this.right.add(node);
        } else {
            this.right = node;
        }
    }
}

public void del(int value) {
    Node target = root.search(value);
    if (target == null) {
        return;
    }

    Node parent = root.searchParent(value);
    //1)叶子结点
    if (target.left == null && target.right == null) {
        //当前父节点为空，目标结点是叶子结点(目标结点是根节点)
        if (parent == null) {
            root = null;
            return;
        }
        if (parent.left == target) {
            parent.left = null;
        }
        if (parent.right == target) {
            parent.right = null;
        }

    }
    //2)存在两个叶子结点
    else if (target.left != null && target.right != null) {
        //找到右子树的最左结点，并删除它
        Node endNode = findLeft(target.right);
        del(endNode.value);
        //如果parent为null 则删除结点为根节点
        if (parent == null) {
            root = endNode;
        } else {
            if (parent.left == target) {
                parent.left = endNode;
            }
            if (parent.right == target) {
                parent.right = endNode;
            }
        }
        endNode.left = target.left;
        endNode.right = target.right;
    }
    //3)存在一个叶子结点
    else {
        if (target.left != null) {
            //当前删除为根节点,设置目标结点的左节点为根节点
            if (parent == null) {
                root = target.left;
                return;
            }
            if (parent.left == target) {
                parent.left = target.left;
            } else {
                parent.right = target.left;
            }
        }
        if (target.right != null) {
            if (parent == null) {
                root = target.right;
                return;
            }
            if (parent.left == target) {
                parent.left = target.right;
            } else {
                parent.right = target.right;
            }
        }
    }
}

/**
 * 查询目标结点的父节点
 */
public Node searchParent(int val) {
    if (this.value > val && this.left != null) {
        //左节点为需要寻找的结点
        if (this.left.value == val) {
            return this;
        }
        return this.left.searchParent(val);
    }
    if (this.value < val && this.right != null) {
        if (this.right.value == val) {
            return this;
        }
        return this.right.searchParent(val);
    }
    return null;
}

/**
 * 查找当前结点
 */
public Node search(int val) {
    if (this.value == val) {
        return this;
    }
    //如果查找的值小于当前值 并且 左子节点不为空 递归查找
    if (this.value > val && this.left != null) {
        return this.left.search(val);
    }
    if (this.value < val && this.right != null) {
        return this.right.search(val);
    }
    return null;
}