huffman-table ( lengths single? -- table )

Vocabulary

compression.deflate.private

Inputs

lengths	an object
single?	an object

Outputs

table

an object

Definition

USING: arrays assocs compression.deflate kernel math sequences ;

IN: compression.deflate.private

:: huffman-table ( lengths single? -- table )
    16 0 <array> :> counts lengths
    [| n | n counts nth 1 + n counts set-nth ] each
    1 :> left! 15 [| i |
        left 2 * i 1 + counts nth - left! left 0 <
        [ "oversubscribed Huffman tree" invalid-deflate ] when
    ] each-integer left 0 > [
        single? 1 counts nth 1 = and lengths [ 0 > ] count 1 =
        and [ "incomplete Huffman tree" invalid-deflate ] unless
    ] when 16 0 <array> :> next 0 :> code! 15 [| i |
        code i zero? [ 0 ] [ i counts nth ] if + 2 *
        code! code i 1 + next set-nth
    ] each-integer H{ } clone :> table lengths [| n symbol |
        n 0 > [
            n next nth :> c symbol 1 n shift c + table set-at
            c 1 + n next set-nth
        ] when
    ] each-index table ;