class Node {
    constructor(val) {
        this.value = val;
        this.child = [];
    }
    addLeft(node) {this.child[0] = node}
    addRight(node) {this.child[1] = node}
}

function count(str) {
    // strの中のそれぞれの文字の出現回数をカウントする
    const counter = new Map();
    for (const s of str) counter.set(s, counter.has(s) ? counter.get(s) + 1 : 0);
    return [...counter.entries()];
}
function createHuffmanTree(pairs) {
    // pairs:= [['a', 2], ['b', 2], ...]
    pairs = pairs.map(item => [new Node(item[0]), item[1]]);
    while (pairs.length > 1) {
        let min1 = 0, min2 = 1; // min1は最小要素のインデックス、min2は二番目へのインデックス
        if (pairs[min1][1] > pairs[min2][1]) [min1, min2] = [min2, min1];
        for (let i = 2, _i = pairs.length; i < _i; i++) {
            if (pairs[i][1] < pairs[min1][1]) {
                [min1, min2] = [i, min1];
            } else if (pairs[i][1] < pairs[min2][1]) {
                min2 = i;
            }
        }
        const parent = new Node(null);
        parent.addLeft(pairs[min1][0]);
        parent.addRight(pairs[min2][0]);
        if (min1 > min2) [min1, min2] = [min2, min1]; // 下でpairsからmin1、min2の要素を取り除くときにspliceを使うため、必要なら入れ替え
        pairs.push([parent, pairs[min1][1] + pairs[min2][1]]);
        pairs.splice(min2, 1); pairs.splice(min1, 1);
    }
    return pairs[0][0];
}
function HuffmanCoding(tree, dic = {}, s = '') {
    if (tree.value !== null) dic[tree.value] = s;
    if (tree.child[0]) dic = HuffmanCoding(tree.child[0], dic, s + '0');
    if (tree.child[1]) dic = HuffmanCoding(tree.child[1], dic, s + '1');
    return dic;
}
const test = 'Lorem ipsum dolor sit amet, consectetur adipiscing elit';
const huffmanCode = HuffmanCoding(createHuffmanTree(count(test)));
console.log(huffmanCode);
console.log([...test].map(s => huffmanCode[s]).join(''));
console.log(([...test].map(s => huffmanCode[s]).join('').length / 8) + 'byte');