/***
 *
 * 
 * 
 *  
 *
 *
 */
class Node {
    data;//存放数据(字符本身),比如 'a' => 97, ' '=>32
    weight;//权值，表示字符串出现的次数
    left;//
    constructor(data, weight) {
        this.data = data;
        this.weight = weight;
    }  
    //前序遍历
    preOrder(arr) {
        arr.push(this);
        if (this.left) {
            this.left.preOrder(arr);
        }
        if (this.right) {
            this.right.preOrder(arr);
        }
    }
}

const _MKHUFFMANFUNCTION = {
    stringToByte:function(str) {
        let bytes = new Array();
        let len, c;
        len = str.length;
        for (let i = 0; i < len; i++) {
            c = str.codePointAt(i);
            if (c >= 0x010000 && c <= 0x10FFFF) {
                bytes.push(((c >> 18) & 0x07) | 0xF0);
                bytes.push(((c >> 12) & 0x3F) | 0x80);
                bytes.push(((c >> 6) & 0x3F) | 0x80);
                bytes.push((c & 0x3F) | 0x80);
            } else if (c >= 0x000800 && c <= 0x00FFFF) {
                bytes.push(((c >> 12) & 0x0F) | 0xE0);
                bytes.push(((c >> 6) & 0x3F) | 0x80);
                bytes.push((c & 0x3F) | 0x80);
            } else if (c >= 0x000080 && c <= 0x0007FF) {
                bytes.push(((c >> 6) & 0x1F) | 0xC0);
                bytes.push((c & 0x3F) | 0x80);
            } else {
                bytes.push(c & 0xFF);
            }
        }
        return bytes;
    },
    add00:function(len, str){
        const len_str = str.length;
        if(len === len_str){
        return str;
        }else{
        const n = len - len_str;
        let s = ''
        for(let i = 0; i < n; i++) s += 0;
        const t = s+str;
        return t;
        }
    },  
    getNodes:function(bytes) {
        let list = [];
        let counts = {};
        for (let b of bytes) {
            let count = counts[b];//map还没有这个字符数据
            if (count == null) {
                counts[b] = 1;
            } else {
                counts[b]++;
            }
        }
        for (const [key, value] of Object.entries(counts)) {
            list.push(new Node(key, value));
        }
        return list;
    },
    //通过list创建赫夫曼树
    createHuffmanTree:function(nodes) {
        const compareFun = function (a, b) {
            return a.weight - b.weight
        };
        while (nodes.length > 1) {
            //排序,从小到大
            nodes.sort(compareFun);
            //取出第一颗最小的二叉树
            let leftNode = nodes.shift(), rightNode = nodes.shift();
            //创建一个新的二叉树，它的根节点，没有data，只有权值
            let parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            //将新的二叉树，加入到nodes
            nodes.unshift(parent);
        }
        //nodes最后的节点，就是根节点
        return nodes.shift();
    },  
    //生成赫夫曼树对应的赫夫曼编码表
    getCodes2:function(root) {
        let huffmanCodes = {};
        let string = [];
        function getCodes(node, code, string) {
            let string2 = [...string];
            //将code加入到string中
            string2.push(code);
            if (node != null) { //如果node == null不处理
                //判断当前node是叶子节点还是非叶子节点
                if (node.data == null) {//非叶子节点
                    getCodes(node.left, '0', string2);
                    //向右递归
                    getCodes(node.right, '1', string2)
                } else {//说明是一个叶子节点
                    //就表示找到了某个叶子节点的最后
                    huffmanCodes[node.data] = string2.join('');
                }
            }
        }
        getCodes(root, "", string);
        return huffmanCodes;
    },    
    huffmanTreetoBs64:function(table){
        let num = Object.getOwnPropertyNames(table).length;
        let tree = '';
        let tail = '';
        for(k in table){
            tree += String.fromCodePoint(parseInt(k));
            tree += String.fromCodePoint(parseInt(table[k].length));
            tail += table[k];             
        }
        const len_tail = tail.length;
        const lenRem = len_tail%8 ? 8 - len_tail%8 : len_tail%8;
        for(let i = 0; i < lenRem; i++) tail += 0;
        let zStr = '';
        for(let i = 0; i < len_tail+lenRem; i += 8) zStr += String.fromCodePoint(parseInt(tail.slice(i, i+8), 2));
        return '####num&&&&'+num+'####tree&&&&'+_Base64.encode(tree)+'####tail&&&&'+_Base64.encode(zStr);
    },  
    /***
     * @param {赫夫曼编码表} huffmanCodes 
     * @param {赫夫曼编码得到的二进制数组}heffmanStr 
     */
    deHuffman:function(table, heffmanStr) {
        let tree = {};
        for(let k in table) tree[table[k]] = k   
        let list = [];
        let s = ''
        for (let i = 0; i < heffmanStr.length; i++) {
            s += heffmanStr[i];
            for(let k in tree){
                if(s === k) {
                    list.push(tree[k]);
                    s = '';
                    break
                }
            }
        }
        return list
    },
    deZipBs64:function(string){
        const zip = _Base64.decode(string)
        let unit8 = [];
        for(let i = 0; i < zip.length; i++) unit8[i] = (zip[i].codePointAt(0) & 0xff).toString(2);
        let s = '';
        for(let i = 0; i < unit8.length; i++){
            if(unit8[i].length === 8){
                s += unit8[i];
            }else{
                let len_add = 8 - unit8[i].length
                let add0 = '';
                for(let j = 0; j < len_add; j++) add0 += 0;
                s += add0 + unit8[i];
            }
        }
        return s;
    },
    deTableBs64:function(len, tree, tail){
        const tree_bs64 = _Base64.decode(tree);
        const table = _MKHUFFMANFUNCTION.deZipBs64(tail);   
        const len_tree = parseInt(len)
        let set = {};
        let k = 0;
        for(let i = 0; i < len_tree*2; i++){
            const key =  tree_bs64[i].codePointAt(0);
            const value = parseInt(tree_bs64[++i].codePointAt(0))
            set[key] = table.slice(k, value+k);
            k += value;
        }  
        return set;
    }
}

function huffman_encode_decode(type, string){
    if(type === 1){
        const byte = _MKHUFFMANFUNCTION.stringToByte(string);
        const nodes = _MKHUFFMANFUNCTION.getNodes(byte);
        const root = _MKHUFFMANFUNCTION.createHuffmanTree(nodes);
        const table = _MKHUFFMANFUNCTION.getCodes2(root);
        const tree = _MKHUFFMANFUNCTION.huffmanTreetoBs64(table);
        let zip = '';
        for(let i = 0; i < byte.length; i++) zip += table[byte[i]];
        const lenzip = zip.length;
        const lenRem = lenzip%8 ? 8 - lenzip%8 : lenzip%8;
        for(let i = 0; i < lenRem; i++) zip += 0;
        let zStr = '';
        for(let i = 0; i < lenzip+lenRem; i += 8) zStr += String.fromCodePoint(parseInt(zip.slice(i, i+8), 2));
        let body = _Base64.encode(zStr)
        return '####ydata&&&&'+tree+"####len&&&&"+(lenRem+lenzip)+"####body&&&&"+body+"####cinraw&&&&\n\r"
    }else{
        const len_tree = string.split('####num&&&&')[1].split('####tree&&&&')[0];
        const tree = string.split('####tree&&&&')[1].split('####tail&&&&')[0];
        const tail = string.split('####tail&&&&')[1].split('####len&&&&')[0];
        const body = string.split('####body&&&&')[1].split('####cinraw&&&&')[0];
        const len_body = string.split('####len&&&&')[1].split('####body&&&&')[0];  
        const zip = _MKHUFFMANFUNCTION.deZipBs64(body);
        const table = _MKHUFFMANFUNCTION.deTableBs64(len_tree, tree, tail);
        const list = _MKHUFFMANFUNCTION.deHuffman(table, zip);
        const res = UTF8.decode(list)    
        return res;
    }
}