Method buildTree

packages/alphatab/src/zip/DeflaterHuffman.ts:70–215

()

    }

    public buildTree() {
        const numSymbols = this.freqs.length;

        /* heap is a priority queue, sorted by frequency, least frequent
         * nodes first.  The heap is a binary tree, with the property, that
         * the parent node is smaller than both child nodes.  This assures
         * that the smallest node is the first parent.
         *
         * The binary tree is encoded in an array:  0 is root node and
         * the nodes 2*n+1, 2*n+2 are the child nodes of node n.
         */
        const heap = new Int32Array(numSymbols);
        let heapLen = 0;
        let maxCode = 0;
        for (let n = 0; n < numSymbols; n++) {
            const freq = this.freqs[n];
            if (freq !== 0) {
                // Insert n into heap
                let pos = heapLen++;
                while (true) {
                    if (pos > 0) {
                        const ppos = Math.floor((pos - 1) / 2);
                        if (this.freqs[heap[ppos]] > freq) {
                            heap[pos] = heap[ppos];
                            pos = ppos;
                        } else {
                            break;
                        }
                    } else {
                        break;
                    }
                }
                heap[pos] = n;

                maxCode = n;
            }
        }

        /* We could encode a single literal with 0 bits but then we
         * don't see the literals.  Therefore we force at least two
         * literals to avoid this case.  We don't care about order in
         * this case, both literals get a 1 bit code.
         */
        while (heapLen < 2) {
            const node = maxCode < 2 ? ++maxCode : 0;
            heap[heapLen++] = node;
        }

        this.numCodes = Math.max(maxCode + 1, this.minNumCodes);

        const numLeafs = heapLen;
        const childs = new Int32Array(4 * heapLen - 2);
        const values = new Int32Array(2 * heapLen - 1);
        let numNodes = numLeafs;
        for (let i = 0; i < heapLen; i++) {
            const node = heap[i];
            childs[2 * i] = node;
            childs[2 * i + 1] = -1;