package week15;


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

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
public class HuffmanCode {
    public static class HuffmanTree {
        // 结点类
        public static class HuffmanNode<T> implements Comparable<HuffmanNode<T>> {
            protected T data;
            protected int weight;
            protected HuffmanNode Parent = null;
            protected HuffmanNode LeftChild = null;
            protected HuffmanNode RightChild = null;

            public HuffmanNode(T data, int weight, HuffmanNode LeftChild, HuffmanNode RightChild, HuffmanNode Parent) {
                this.data = data;
                this.weight = weight;
                this.Parent = Parent;
                this.LeftChild = LeftChild;
                this.RightChild = RightChild;
            }

            public HuffmanNode(T data, HuffmanNode LeftChild, HuffmanNode RightChild) {
                this.data = data;
                this.LeftChild = LeftChild;
                this.RightChild = RightChild;
            }

            public HuffmanNode(T data, int weight) {
                this.data = data;
                this.weight = weight;
            }

            public T getData() {
                return data;
            }

            public void setData(T data) {
                this.data = data;
            }

            public int getWeight() {
                return weight;
            }

            public void setWeight(int weight) {
                this.weight = weight;
            }

            public HuffmanNode getParent() {
                return Parent;
            }

            public void setParent(HuffmanNode parent) {
                Parent = parent;
            }

            public HuffmanNode getLeftChild() {
                return LeftChild;
            }

            public void setLeftChild(HuffmanNode leftChild) {
                LeftChild = leftChild;
            }

            public HuffmanNode getRightChild() {
                return RightChild;
            }

            public void setRightChild(HuffmanNode rightChild) {
                RightChild = rightChild;
            }

            @Override
            public String toString() {
                String string = "\t";
                if (weight==0){
                }
                else {
                    string += "\n\r结点:值=" + data
                            + "\t权重=" + weight;
                }
                return string;
            }

            @Override
            public int compareTo(HuffmanNode<T> o) {
                if (o.weight > this.weight) {
                    return 1;
                } else if (o.weight < this.weight) {
                    return -1;
                } else {
                    return 0;
                }
            }
        }

        public static <T> HuffmanNode<T> CreatTree(List<HuffmanNode<T>> HuffmanNode) {
            while (HuffmanNode.size() > 1) {
                Collections.sort(HuffmanNode);
                HuffmanNode<T> left = HuffmanNode.get(HuffmanNode.size() - 1);
                HuffmanNode<T> right = HuffmanNode.get(HuffmanNode.size() - 2);
                HuffmanNode<T> parent = new HuffmanNode<T>(null,left.getWeight()
                        + right.getWeight());
                parent.setLeftChild(left);
                parent.setRightChild(right);
                HuffmanNode.remove(left);
                HuffmanNode.remove(right);
                HuffmanNode.add(parent);
            }
            return HuffmanNode.get(0);
        }

        public static <T> List<HuffmanNode<T>> breadth(HuffmanNode<T> Root) {
            List<HuffmanNode<T>> list = new ArrayList<HuffmanNode<T>>();
            Queue<HuffmanNode<T>> queue = new ArrayDeque<HuffmanNode<T>>();

            if (Root != null) {
                queue.offer(Root);
            }

            while (!queue.isEmpty()) {
                list.add(queue.peek());
                HuffmanNode<T> node = queue.poll();

                if (node.getLeftChild() != null) {
                    queue.offer(node.getLeftChild());
                }

                if (node.getRightChild() != null) {
                    queue.offer(node.getRightChild());
                }
            }
            return list;
        }
    }
    public static class Huffman {
        private String str;
        private HNode root;
        private boolean flag;
        private LinkedList<CharData> charList;
        private LinkedList<HNode> NodeList;
        private class CharData {
            int num = 1;
            char c;

            public CharData(char ch){
                c = ch;
            }
        }
        public void creatHfmTree(String str) {
            this.str = str;

            NodeList = new LinkedList<HNode>();
            charList = new LinkedList<CharData>();


            getCharNum(str);


            creatNodes();


            Sort(NodeList);

            creatTree();

            root = NodeList.get(0);
        }

        private void getCharNum(String str) {

            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                flag = true;

                for (int j = 0; j < charList.size(); j++) {
                    CharData data = charList.get(j);

                    if(ch == data.c){
                        data.num++;
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    charList.add(new CharData(ch));
                }

            }

        }
        private void creatNodes() {

            for (int i = 0; i < charList.size(); i++) {
                String data = charList.get(i).c + "";
                int count = charList.get(i).num;

                HNode node = new HNode(data, count);
                NodeList.add(node);
            }

        }


        private void creatTree() {

            while (NodeList.size() > 1) {

                HNode left = NodeList.poll();
                HNode right = NodeList.poll();
                left.code = "0";
                right.code = "1";
                setCode(left);
                setCode(right);

                int parentWeight = left.count + right.count;
                HNode parent = new HNode(parentWeight, left, right);

                NodeList.addFirst(parent);
                Sort(NodeList);
            }
        }

        private void Sort(LinkedList<HNode> nodelist) {
            for (int i = 0; i < nodelist.size() - 1; i++) {
                for (int j = i + 1; j < nodelist.size(); j++) {
                    HNode temp;
                    if (nodelist.get(i).count > nodelist.get(j).count) {
                        temp = nodelist.get(i);
                        nodelist.set(i, nodelist.get(j));
                        nodelist.set(j, temp);
                    }

                }
            }

        }
        private void setCode(HNode root) {

            if (root.lChild != null) {
                root.lChild.code = root.code + "0";
                setCode(root.lChild);
            }

            if (root.rChild != null) {
                root.rChild.code = root.code + "1";
                setCode(root.rChild);
            }
        }
        private void output(HNode node) {

            if (node.lChild == null && node.rChild == null) {
                System.out.println(node.data + ": " + node.code);
            }
            if (node.lChild != null) {
                output(node.lChild);
            }
            if (node.rChild != null) {
                output(node.rChild);
            }
        }

        public void output() {
            output(root);
        }

        private String hfmCodeStr = "";

        public String toHufmCode(String str) {

            for (int i = 0; i < str.length(); i++) {
                String c = str.charAt(i) + "";
                search(root, c);
            }

            return hfmCodeStr;
        }


        private void search(HNode root, String c) {
            if (root.lChild == null && root.rChild == null) {
                if (c.equals(root.data)) {
                    hfmCodeStr += root.code;
                }
            }
            if (root.lChild != null) {
                search(root.lChild, c);
            }
            if (root.rChild != null) {
                search(root.rChild, c);
            }
        }

        String result="";
        boolean target = false;
        public String CodeToString(String codeStr) {

            int start = 0;
            int end = 1;

            while(end <= codeStr.length()){
                target = false;
                String s = codeStr.substring(start, end);
                matchCode(root, s); // 解码
                // 每解码一个字符，start向后移
                if(target){
                    start = end;
                }
                end++;
            }

            return result;
        }

        private void matchCode(HNode root, String code){
            if (root.lChild == null && root.rChild == null) {
                if (code.equals(root.code)) {
                    result += root.data;
                    target = true;
                }
            }
            if (root.lChild != null) {
                matchCode(root.lChild, code);
            }
            if (root.rChild != null) {
                matchCode(root.rChild, code);
            }

        }
    }
    public static class HNode {

        public String code = "";
        public String data = "";
        public int count;
        public HNode lChild;
        public HNode rChild;

        public HNode() {
        }

        public HNode(String data, int count) {
            this.data = data;
            this.count = count;
        }

        public HNode(int count, HNode lChild, HNode rChild) {
            this.count = count;
            this.lChild = lChild;
            this.rChild = rChild;
        }

        public HNode(String data, int count, HNode lChild, HNode rChild) {
            this.data = data;
            this.count = count;
            this.lChild = lChild;
            this.rChild = rChild;
        }
        @Override
        public String toString() {
            String string = "\t";
            if (count==0){
            }
            else {
                string += "\n\r结点:值=" + data
                        + "\t权重=" + count;
            }
            return string;
        }

    }

    public static void printStr(String str, int[] Probabilities, String[] Data ) {
        if (str == null || "".equals(str)) {
            System.out.println("字符串不能为空！");
            return;
        }
        Map<String, Integer> pMap = new HashMap<String, Integer>();
        String[] split = str.split("");
        for (int i = 0; i < split.length; i++) {
            if (!"".equals(split[i]) && pMap.containsKey(split[i])) {
                pMap.put(split[i], pMap.get(split[i]) + 1);
            } else if (!"".equals(split[i])) {
                pMap.put(split[i], 1);
            }
        }
        Set<String> keySet = pMap.keySet();
        int total = 0;
        int i = 0;
        for (String string : keySet) {
            total += pMap.get(string);
        }
        for (String string : keySet) {
            Probabilities[i] =pMap.get(string)  ;
            Data[i] = string;
            System.out.println(string + "出现的概率：" + "分数： " + pMap.get(string) + "/" + total
                    + "\t" + "小数：" + (double) pMap.get(string) / total);
            i++;
        }
    }
    public static void main(String[] args) {
        File fromFile = new File("English-text");
        // 创建字符输入流
        Reader reader = null;
        String data = "";

        List temp = new LinkedList();
        try {
            reader = new FileReader(fromFile);
            // 循环读取（打印）
            int content = reader.read();
            while (content != -1) {
                System.out.print((char) content);
                temp.add(content);
                data += (char) content;
                content = reader.read();
            }
            System.out.println();
            data = data.toLowerCase();
            data = data.replace(" ", "");
            data = data.replace("\n", "");
            data = data.replace("\r", "");
            int[] Probabilities = new int[26];
            String[] Data = new String[26];
            printStr(data,Probabilities,Data);
            List<HuffmanTree.HuffmanNode<String>> list = new ArrayList<HuffmanTree.HuffmanNode<String>>();
            for (int i = 0 ; i < Data.length; i ++){
                list.add(new HuffmanTree.HuffmanNode<String>(Data[i],Probabilities[i]));
            }
            HuffmanTree.HuffmanNode<String> Root = HuffmanTree.CreatTree(list);
            System.out.println(HuffmanTree.breadth(Root));
            Huffman huff = new Huffman();
            huff.creatHfmTree(data);
            huff.output();
            String hufmCode = huff.toHufmCode(data);
            File file = new File("编码后");
            Writer out =new FileWriter(file);
            out.write(hufmCode);
            out.close();
            System.out.println("编码:" + hufmCode);
            File file1 = new File("解码后");
            Writer out1 =new FileWriter(file1);
            out1.write(huff.CodeToString(hufmCode));
            out1.close();


            System.out.println("解码：" + huff.CodeToString(hufmCode));

        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            // 4.关闭流
            try {
                reader.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
}