' LZW compression: dictionary build, encode, decode (GIF-style)
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL i  AS LONG
    LOCAL j  AS LONG
    LOCAL numCodes  AS LONG
    LOCAL dictSize  AS LONG
    LOCAL maxDict  AS LONG
    LOCAL inputStr  AS STRING
    LOCAL w  AS STRING
    LOCAL k  AS STRING
    LOCAL entry  AS STRING
    LOCAL outputCodes(200) AS LONG
    LOCAL numOutputCodes  AS LONG
    LOCAL codeIdx  AS LONG
    LOCAL decodeStr  AS STRING
    LOCAL resultStr  AS STRING
    LOCAL dictStr(4096) AS STRING
    LOCAL dictLen(4096) AS LONG
    LOCAL code  AS LONG
    LOCAL prevCode  AS LONG
    LOCAL nextCode  AS LONG
    LOCAL ch AS STRING
    LOCAL found AS LONG

    PRINT "=== LZW Compression ==="
    PRINT

    inputStr = "TOBEORNOTTOBEORTOBEORNOT"
    PRINT "Input: " & inputStr
    PRINT "Length: " & FORMAT$(LEN(inputStr)) & " characters"
    PRINT

    maxDict = 256
    FOR i = 0 TO 255
        dictStr(i) = CHR$(i)
        dictLen(i) = 1
    NEXT i
    dictSize = 256

    numOutputCodes = 0
    w = ""

    FOR i = 1 TO LEN(inputStr)
        ch = MID$(inputStr, i, 1)
        k = ch
        entry = w + k

        found = 0
        FOR j = 0 TO dictSize - 1
            IF dictStr(j) = entry THEN
                found = 1
            END IF
        NEXT j

        IF found = 1 THEN
            w = entry
        ELSE
            FOR j = 0 TO dictSize - 1
                IF dictStr(j) = w THEN
                    outputCodes(numOutputCodes) = j
                    numOutputCodes = numOutputCodes + 1
                END IF
            NEXT j
            IF dictSize < 4096 THEN
                dictStr(dictSize) = entry
                dictLen(dictSize) = LEN(entry)
                dictSize = dictSize + 1
            END IF
            w = k
        END IF
    NEXT i

    IF LEN(w) > 0 THEN
        FOR j = 0 TO dictSize - 1
            IF dictStr(j) = w THEN
                outputCodes(numOutputCodes) = j
                numOutputCodes = numOutputCodes + 1
            END IF
        NEXT j
    END IF

    PRINT "--- Encoded Output ---"
    PRINT "  " & STR$(numOutputCodes) & " codes"
    FOR i = 0 TO numOutputCodes - 1
        PRINT "  Code " & FORMAT$(i) & ": " & FORMAT$(outputCodes(i))
    NEXT i
    PRINT

    PRINT "--- Dictionary after encoding ---"
    PRINT "  Size: " & FORMAT$(dictSize) & " entries (256 initial + " & FORMAT$(dictSize - 256) & " new)"
    FOR i = 256 TO dictSize - 1
        IF i < 266 THEN
            PRINT "  Entry " & FORMAT$(i) & ": '" & TRIM$(dictStr(i)) & "' (len " & FORMAT$(dictLen(i)) & ")"
        END IF
    NEXT i
    IF dictSize > 266 THEN
        PRINT "  ... and " & FORMAT$(dictSize - 266) & " more entries"
    END IF
    PRINT

    PRINT "--- Compression Ratio ---"
    PRINT "  Original: " & FORMAT$(LEN(inputStr) * 8) & " bits"
    PRINT "  Compressed: " & FORMAT$(numOutputCodes * 12) & " bits (12-bit codes)"
    PRINT "  Ratio: " & FORMAT$((LEN(inputStr) * 8) / (numOutputCodes * 12)) & ":1"

    PRINT
    PRINT "LZW codec complete."

    FUNCTION = 0
END FUNCTION
