#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL str1 AS STRING
    LOCAL str2 AS STRING
    LOCAL len_a AS LONG
    LOCAL len_b AS LONG
    LOCAL dm(400) AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL cost AS LONG
    LOCAL temp_val AS LONG
    LOCAL min_dist AS LONG
    LOCAL temp_str AS STRING

    ' Damerau-Levenshtein distance: adds transposition of adjacent characters
    ' d[i,j] = min(
    '   d[i-1,j] + 1,           deletion
    '   d[i,j-1] + 1,           insertion
    '   d[i-1,j-1] + cost,      substitution
    '   d[i-2,j-2] + cost_t     transposition
    ' )

    PRINT "Damerau-Levenshtein Distance"
    PRINT "============================"
    PRINT ""

    ' Test 1: ca -> abc (transposition: ab -> ba)
    str1 = "ca"
    str2 = "abc"

    PRINT "Testing transposition detection:"
    PRINT "  'ab' -> 'ba' should detect 1 transposition"

    ' Test 2: knight -> night
    str1 = "knight"
    str2 = "night"
    len_a = LEN(str1)
    len_b = LEN(str2)

    i = 0
    WHILE i <= len_a
        dm(i * (len_b + 1) + 0) = i
        i = i + 1
    WEND
    j = 0
    WHILE j <= len_b
        dm(0 * (len_b + 1) + j) = j
        j = j + 1
    WEND

    i = 1
    WHILE i <= len_a
        j = 1
        WHILE j <= len_b
            cost = 0
            IF MID$(str1, i, 1) <> MID$(str2, j, 1) THEN
                cost = 1
            END IF

            min_dist = dm((i - 1) * (len_b + 1) + j) + 1
            temp_val = dm(i * (len_b + 1) + (j - 1)) + 1
            IF temp_val < min_dist THEN min_dist = temp_val
            temp_val = dm((i - 1) * (len_b + 1) + (j - 1)) + cost
            IF temp_val < min_dist THEN min_dist = temp_val

            ' Transposition check
            IF i > 1 AND j > 1 THEN
                IF MID$(str1, i - 1, 1) = MID$(str2, j, 1) AND MID$(str1, i, 1) = MID$(str2, j - 1, 1) THEN
                    temp_val = dm((i - 2) * (len_b + 1) + (j - 2)) + cost
                    IF temp_val < min_dist THEN min_dist = temp_val
                END IF
            END IF

            dm(i * (len_b + 1) + j) = min_dist
            j = j + 1
        WEND
        i = i + 1
    WEND

    temp_str = STR$(dm(len_a * (len_b + 1) + len_b))
    PRINT "'knight' -> 'night' = " + temp_str + " edits"

    ' Test 3: abc -> acb (transposition test)
    str1 = "abc"
    str2 = "acb"
    len_a = 3
    len_b = 3

    i = 0
    WHILE i <= len_a
        dm(i * (len_b + 1) + 0) = i
        i = i + 1
    WEND
    j = 0
    WHILE j <= len_b
        dm(0 * (len_b + 1) + j) = j
        j = j + 1
    WEND

    i = 1
    WHILE i <= len_a
        j = 1
        WHILE j <= len_b
            cost = 0
            IF MID$(str1, i, 1) <> MID$(str2, j, 1) THEN cost = 1

            min_dist = dm((i - 1) * (len_b + 1) + j) + 1
            temp_val = dm(i * (len_b + 1) + (j - 1)) + 1
            IF temp_val < min_dist THEN min_dist = temp_val
            temp_val = dm((i - 1) * (len_b + 1) + (j - 1)) + cost
            IF temp_val < min_dist THEN min_dist = temp_val

            IF i > 1 AND j > 1 THEN
                IF MID$(str1, i - 1, 1) = MID$(str2, j, 1) AND MID$(str1, i, 1) = MID$(str2, j - 1, 1) THEN
                    temp_val = dm((i - 2) * (len_b + 1) + (j - 2)) + cost
                    IF temp_val < min_dist THEN min_dist = temp_val
                END IF
            END IF

            dm(i * (len_b + 1) + j) = min_dist
            j = j + 1
        WEND
        i = i + 1
    WEND

    temp_str = STR$(dm(3 * 4 + 3))
    PRINT "'abc' -> 'acb' = " + temp_str + " edits (transposition)"

    ' Test 4: transposition detection
    str1 = "ABCD"
    str2 = "ACBD"
    len_a = 4
    len_b = 4

    i = 0
    WHILE i <= len_a
        dm(i * (len_b + 1) + 0) = i
        i = i + 1
    WEND
    j = 0
    WHILE j <= len_b
        dm(0 * (len_b + 1) + j) = j
        j = j + 1
    WEND

    i = 1
    WHILE i <= len_a
        j = 1
        WHILE j <= len_b
            cost = 0
            IF MID$(str1, i, 1) <> MID$(str2, j, 1) THEN cost = 1

            min_dist = dm((i - 1) * (len_b + 1) + j) + 1
            temp_val = dm(i * (len_b + 1) + (j - 1)) + 1
            IF temp_val < min_dist THEN min_dist = temp_val
            temp_val = dm((i - 1) * (len_b + 1) + (j - 1)) + cost
            IF temp_val < min_dist THEN min_dist = temp_val

            IF i > 1 AND j > 1 THEN
                IF MID$(str1, i - 1, 1) = MID$(str2, j, 1) AND MID$(str1, i, 1) = MID$(str2, j - 1, 1) THEN
                    temp_val = dm((i - 2) * (len_b + 1) + (j - 2)) + cost
                    IF temp_val < min_dist THEN min_dist = temp_val
                END IF
            END IF

            dm(i * (len_b + 1) + j) = min_dist
            j = j + 1
        WEND
        i = i + 1
    WEND

    temp_str = STR$(dm(4 * 5 + 4))
    PRINT "'ABCD' -> 'ACBD' = " + temp_str + " edits (1 transposition expected)"

    PRINT ""
    PRINT "Damerau-Levenshtein distance complete."

    FUNCTION = 0
END FUNCTION
