' Arithmetic coding: symbol probability intervals, encode/decode
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL i  AS LONG
    LOCAL j  AS LONG
    LOCAL numSymbols  AS LONG
    LOCAL inputStr AS STRING
    LOCAL totalCount AS LONG
    LOCAL sym(256) AS LONG
    LOCAL count(256) AS LONG
    LOCAL low(256) AS DOUBLE
    LOCAL high(256) AS DOUBLE
    LOCAL codeLow  AS DOUBLE
    LOCAL codeHigh  AS DOUBLE
    LOCAL codeRange  AS DOUBLE
    LOCAL encoded  AS DOUBLE
    LOCAL decoded  AS DOUBLE
    LOCAL decodeResult AS STRING
    LOCAL ch AS STRING
    LOCAL chIdx  AS LONG
    LOCAL symIdx  AS LONG
    LOCAL foundSym AS LONG
    LOCAL cumLow  AS DOUBLE
    LOCAL cumHigh  AS DOUBLE
    LOCAL cumCount  AS DOUBLE
    PRINT "=== Arithmetic Coding ==="
    PRINT

    inputStr = "AABCABAD"
    totalCount = LEN(inputStr)
    PRINT "Input: " & inputStr
    PRINT

    FOR i = 1 TO totalCount
        ch = MID$(inputStr, i, 1)
        chIdx = ASC(ch)
        IF count(chIdx) = 0 THEN
            sym(numSymbols) = chIdx
            numSymbols = numSymbols + 1
        END IF
        count(chIdx) = count(chIdx) + 1
    NEXT i

    PRINT "--- Symbol Probabilities ---"
    FOR i = 0 TO numSymbols - 1
        PRINT "  '" & CHR$(sym(i)) & "': " & FORMAT$(count(sym(i))) & "/" & FORMAT$(totalCount)
    NEXT i
    PRINT

    cumCount = 0
    FOR i = 0 TO numSymbols - 1
        low(sym(i)) = cumCount / totalCount
        cumCount = cumCount + count(sym(i))
        high(sym(i)) = cumCount / totalCount
        PRINT "  '" & CHR$(sym(i)) & "' range: [" & FORMAT$(low(sym(i))) & ", " & FORMAT$(high(sym(i))) & ")"
    NEXT i
    PRINT

    codeLow = 0.0
    codeHigh = 1.0

    FOR i = 1 TO totalCount
        ch = MID$(inputStr, i, 1)
        chIdx = ASC(ch)
        codeRange = codeHigh - codeLow
        codeHigh = codeLow + codeRange * high(chIdx)
        codeLow = codeLow + codeRange * low(chIdx)
    NEXT i

    encoded = (codeLow + codeHigh) / 2.0
    PRINT "--- Encoding ---"
    PRINT "  Final interval: [" & FORMAT$(codeLow) & ", " & FORMAT$(codeHigh) & ")"
    PRINT "  Encoded value: " & FORMAT$(encoded)
    PRINT

    PRINT "--- Decoding ---"
    decoded = encoded
    decodeResult = ""

    FOR i = 1 TO totalCount
        foundSym = 0
        FOR j = 0 TO numSymbols - 1
            symIdx = sym(j)
            IF decoded >= low(symIdx) AND decoded < high(symIdx) THEN
                foundSym = 1
                decodeResult = decodeResult + CHR$(symIdx)
                codeRange = high(symIdx) - low(symIdx)
                IF codeRange > 0 THEN
                    decoded = (decoded - low(symIdx)) / codeRange
                END IF
            END IF
        NEXT j
    NEXT i

    PRINT "  Decoded: " & decodeResult
    IF decodeResult = inputStr THEN
        PRINT "  MATCH: Lossless compression confirmed"
    ELSE
        PRINT "  MISMATCH: Error in coding"
    END IF
    PRINT

    PRINT "--- Compression ---"
    PRINT "  Original: " & FORMAT$(totalCount * 8) & " bits"
    PRINT "  Arithmetic: ~" & FORMAT$(totalCount * 2.5) & " bits (estimated)"
    PRINT

    PRINT "--- Properties ---"
    PRINT "  Arithmetic coding vs Huffman:"
    PRINT "  - Can encode fractional bits per symbol"
    PRINT "  - Approaches Shannon entropy limit"
    PRINT "  - Slower than Huffman"
    PRINT "  - Better compression for skewed distributions"

    PRINT
    PRINT "Arithmetic coder complete."

    FUNCTION = 0
END FUNCTION
