function zip_build_tree()

in themes/docsy/static/js/deflate.js [1122:1205]

• 47 lines of code
• 9 McCabe index (conditional complexity)

    function zip_build_tree(desc) { // the tree descriptor
        var tree = desc.dyn_tree;
        var stree = desc.static_tree;
        var elems = desc.elems;
        var n, m;		// iterate over heap elements
        var max_code = -1;	// largest code with non zero frequency
        var node = elems;	// next internal node of the tree

        /* Construct the initial heap, with least frequent element in
            * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
            * heap[0] is not used.
            */
        zip_heap_len = 0;
        zip_heap_max = zip_HEAP_SIZE;

        for (n = 0; n < elems; n++) {
            if (tree[n].fc != 0) {
                zip_heap[++zip_heap_len] = max_code = n;
                zip_depth[n] = 0;
            } else
                tree[n].dl = 0;
        }

        /* The pkzip format requires that at least one distance code exists,
            * and that at least one bit should be sent even if there is only one
            * possible code. So to avoid special checks later on we force at least
            * two codes of non zero frequency.
            */
        while (zip_heap_len < 2) {
            var xnew = zip_heap[++zip_heap_len] = (max_code < 2 ? ++max_code : 0);
            tree[xnew].fc = 1;
            zip_depth[xnew] = 0;
            zip_opt_len--;
            if (stree != null)
                zip_static_len -= stree[xnew].dl;
            // new is 0 or 1 so it does not have extra bits
        }
        desc.max_code = max_code;

        /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
            * establish sub-heaps of increasing lengths:
            */
        for (n = zip_heap_len >> 1; n >= 1; n--)
            zip_pqdownheap(tree, n);

        /* Construct the Huffman tree by repeatedly combining the least two
            * frequent nodes.
            */
        do {
            n = zip_heap[zip_SMALLEST];
            zip_heap[zip_SMALLEST] = zip_heap[zip_heap_len--];
            zip_pqdownheap(tree, zip_SMALLEST);

            m = zip_heap[zip_SMALLEST];  // m = node of next least frequency

            // keep the nodes sorted by frequency
            zip_heap[--zip_heap_max] = n;
            zip_heap[--zip_heap_max] = m;

            // Create a new node father of n and m
            tree[node].fc = tree[n].fc + tree[m].fc;
            //	depth[node] = (char)(MAX(depth[n], depth[m]) + 1);
            if (zip_depth[n] > zip_depth[m] + 1)
                zip_depth[node] = zip_depth[n];
            else
                zip_depth[node] = zip_depth[m] + 1;
            tree[n].dl = tree[m].dl = node;

            // and insert the new node in the heap
            zip_heap[zip_SMALLEST] = node++;
            zip_pqdownheap(tree, zip_SMALLEST);

        } while (zip_heap_len >= 2);

        zip_heap[--zip_heap_max] = zip_heap[zip_SMALLEST];

        /* At this point, the fields freq and dad are set. We can now
            * generate the bit lengths.
            */
        zip_gen_bitlen(desc);

        // The field len is now set, we can generate the bit codes
        zip_gen_codes(tree, max_code);
    }