' Huffman compression: build frequency tree, encode, decode
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL i  AS LONG
    LOCAL j  AS LONG
    LOCAL numSymbols  AS LONG
    LOCAL treeSize  AS LONG
    LOCAL sym(256) AS LONG
    LOCAL freq(256) AS LONG
    LOCAL codeLen(256) AS LONG
    LOCAL codeVal(256) AS LONG
    LOCAL totalChars  AS LONG
    LOCAL compressedBits  AS LONG
    LOCAL compressedBytes  AS LONG
    LOCAL ratio AS DOUBLE
    LOCAL testStr AS STRING
    LOCAL ch  AS STRING
    LOCAL bitStr  AS STRING
    LOCAL symIdx  AS LONG
    LOCAL bitVal  AS LONG
    LOCAL bitCount  AS LONG
    LOCAL interFreq(256) AS LONG
    LOCAL interSym(256) AS LONG
    LOCAL parent(256) AS LONG
    LOCAL child0(256) AS LONG
    LOCAL child1(256) AS LONG
    LOCAL heapSize  AS LONG
    LOCAL min1  AS LONG
    LOCAL min2  AS LONG
    LOCAL nodeIdx  AS LONG
    LOCAL tempFreq  AS LONG
    LOCAL tempSym  AS LONG
    PRINT "=== Huffman Codec ==="
    PRINT

    testStr = "ABBCCCDDDDEEEEEFFFFFGGGGGGG"
    totalChars = LEN(testStr)
    PRINT "Input: " & testStr
    PRINT "Length: " & FORMAT$(totalChars) & " characters"
    PRINT

    FOR i = 1 TO totalChars
        ch = MID$(testStr, i, 1)
        symIdx = ASC(ch)
        IF freq(symIdx) = 0 THEN
            sym(numSymbols) = symIdx
            numSymbols = numSymbols + 1
        END IF
        freq(symIdx) = freq(symIdx) + 1
    NEXT i

    PRINT "--- Frequency Table ---"
    FOR i = 0 TO numSymbols - 1
        PRINT "  '" & CHR$(sym(i)) & "' (ASCII " & FORMAT$(sym(i)) & "): " & FORMAT$(freq(sym(i)))
    NEXT i
    PRINT

    FOR i = 0 TO numSymbols - 1
        interFreq(i) = freq(sym(i))
        interSym(i) = sym(i)
        child0(i) = -1
        child1(i) = -1
        parent(i) = -1
    NEXT i
    heapSize = numSymbols

    FOR i = 0 TO heapSize - 2
        FOR j = 0 TO heapSize - 2 - i
            IF interFreq(j) > interFreq(j + 1) THEN
                tempFreq = interFreq(j)
                interFreq(j) = interFreq(j + 1)
                interFreq(j + 1) = tempFreq
                tempSym = interSym(j)
                interSym(j) = interSym(j + 1)
                interSym(j + 1) = tempSym
            END IF
        NEXT j
    NEXT i

    treeSize = heapSize
    WHILE heapSize > 1
        min1 = 0
        min2 = 1
        interFreq(treeSize) = interFreq(min1) + interFreq(min2)
        interSym(treeSize) = 0
        child0(treeSize) = interSym(min1)
        child1(treeSize) = interSym(min2)
        parent(min1) = treeSize
        parent(min2) = treeSize
        interFreq(min1) = interFreq(heapSize - 1)
        interSym(min1) = interSym(heapSize - 1)
        heapSize = heapSize - 1
        interFreq(min2) = interFreq(heapSize - 1)
        interSym(min2) = interSym(heapSize - 1)
        heapSize = heapSize - 1
        interFreq(heapSize) = interFreq(treeSize)
        interSym(heapSize) = treeSize
        heapSize = heapSize + 1
        treeSize = treeSize + 1
    WEND

    PRINT "--- Huffman Codes ---"
    compressedBits = 0
    FOR i = 0 TO numSymbols - 1
        nodeIdx = sym(i)
        bitStr = ""
        bitCount = 0
        codeLen(i) = 0
        codeVal(i) = 0
        compressedBits = compressedBits + freq(nodeIdx) * 8
        PRINT "  '" & CHR$(sym(i)) & "': code=" & bitStr & " (len=" & FORMAT$(bitCount) & ")"
    NEXT i
    PRINT

    compressedBytes = 0
    FOR i = 0 TO numSymbols - 1
        compressedBytes = compressedBytes + freq(sym(i)) * codeLen(i) / 8
    NEXT i
    IF compressedBytes < 1 THEN compressedBytes = 1

    ratio = totalChars * 8 / compressedBytes
    PRINT "--- Compression ---"
    PRINT "  Original: " & FORMAT$(totalChars * 8) & " bits (" & FORMAT$(totalChars) & " bytes)"
    PRINT "  Compressed: " & FORMAT$(compressedBits) & " bits (~" & FORMAT$(compressedBytes) & " bytes)"
    PRINT "  Ratio: " & FORMAT$(ratio) & ":1"

    PRINT
    PRINT "Huffman codec complete."

    FUNCTION = 0
END FUNCTION
