'use strict';

Object.defineProperty(exports, '__esModule', { value: true });

var queue = require('@algorithm.ts/queue');

function compress(data) {
    const N = data.length;
    const total = Math.ceil(N / 8);
    const result = new Uint8Array(total + 1);
    result[0] = N & 7 ? N & 7 : 8;
    let t = 0;
    for (let i = 1; i < total; ++i, t += 8) {
        const value = (data[t] << 7) |
            (data[t + 1] << 6) |
            (data[t + 2] << 5) |
            (data[t + 3] << 4) |
            (data[t + 4] << 3) |
            (data[t + 5] << 2) |
            (data[t + 6] << 1) |
            data[t + 7];
        result[i] = value;
    }
    let value = 0;
    for (; t < data.length; ++t)
        value = (value << 1) | data[t];
    result[total] = value;
    return result;
}
function decompress(data) {
    const size = data.length;
    const result = [];
    for (let i = 1, _end = size - 1; i < _end; ++i) {
        const v = data[i];
        for (let x = 0x80; x > 0; x >>= 1)
            result.push(v & x ? 1 : 0);
    }
    {
        const validBits = data[0];
        if (validBits > 0) {
            const v = data[size - 1];
            for (let x = 1 << (validBits - 1); x > 0; x >>= 1)
                result.push(v & x ? 1 : 0);
        }
    }
    return result;
}

function fromText(text) {
    const costMap = {};
    for (const c of text) {
        const cnt = costMap[c] ?? 0;
        costMap[c] = cnt + 1;
    }
    const entries = Object.entries(costMap);
    if (entries.length <= 0)
        return {};
    const minHeap = new queue.PriorityQueue({ compare: (x, y) => x.cost - y.cost });
    minHeap.init();
    minHeap.enqueues(entries.map(([value, cost]) => ({ cost, node: { value } })));
    while (minHeap.size > 1) {
        const o1 = minHeap.dequeue();
        const o2 = minHeap.dequeue();
        const o = { left: o1.node, right: o2.node };
        minHeap.enqueue({
            cost: o1.cost + o2.cost,
            node: o,
        });
    }
    return minHeap.front().node;
}
function fromEncodingTable(table) {
    const entries = Object.entries(table);
    if (entries.length === 0)
        return {};
    const root = {};
    for (const [value, path] of entries) {
        let o = root;
        for (const x of path) {
            if (x === 0) {
                if (o.left === undefined)
                    o.left = {};
                o = o.left;
            }
            else {
                if (o.right === undefined)
                    o.right = {};
                o = o.right;
            }
        }
        o.value = value;
    }
    return root;
}
function toEncodingTable(tree) {
    const prefix = [];
    const encodingTable = {};
    collect(tree, 0);
    return encodingTable;
    function collect(node, cur) {
        if (node.value)
            encodingTable[node.value] = prefix.slice(0, cur);
        else {
            if (node.left) {
                prefix[cur] = 0;
                collect(node.left, cur + 1);
            }
            if (node.right) {
                prefix[cur] = 1;
                collect(node.right, cur + 1);
            }
        }
    }
}

function encode(plaintext) {
    const tree = fromText(plaintext);
    const encodedData = [];
    const encodingTable = toEncodingTable(tree);
    for (const c of plaintext) {
        const data = encodingTable[c];
        encodedData.push(...data);
    }
    return { encodedData, encodingTable, tree };
}
function decode(encodedData, tree) {
    const L = encodedData.length;
    if (L <= 0)
        return '';
    let i = 0;
    let o;
    let plainText = '';
    while (i < L) {
        for (o = tree; o && o.value === undefined; ++i) {
            o = encodedData[i] === 0 ? o.left : o.right;
        }
        if (o?.value === undefined)
            break;
        plainText += o.value;
    }
    if (i !== L || o?.value === undefined) {
        throw new TypeError('Bad encoded data or huffman tree.');
    }
    return plainText;
}

var index = {
    encode,
    decode,
    compress,
    decompress,
    fromText,
    fromEncodingTable,
    toEncodingTable,
};

exports.compress = compress;
exports.decode = decode;
exports.decompress = decompress;
exports.default = index;
exports.encode = encode;
exports.fromEncodingTable = fromEncodingTable;
exports.fromText = fromText;
exports.toEncodingTable = toEncodingTable;