;;;; levenshtein-byte.scm -*- Scheme -*-
;;;; Kon Lovett, Mar '20
;;;; Kon Lovett, Apr '12
;;;; Kon Lovett, Sep '05

(module levenshtein-byte

(;export
  levenshtein-distance/byte)

(import scheme)
(import (chicken base))
(import (chicken type))
(import (chicken foreign))
(import (chicken blob))
(import type-errors)


(define-type byte-sequence (or string blob))

(: levenshtein-distance/byte (byte-sequence byte-sequence -> fixnum))
;
(define (levenshtein-distance/byte s t)
	(unless (or (string? s) (blob? s))
		(error-argument-type 'levenshtein-distance/byte s "string or blob" "source") )
	(unless (or (string? t) (blob? t))
		(error-argument-type 'levenshtein-distance/byte t "string or blob" "target") )
  ((foreign-lambda* unsigned-int ((scheme-object os) (scheme-object ot)) #<<EOF

/*
 Computes Levenshtein distance between 8-bit per character strings Source (s) and Target (t).
 Uses O(m) storage and O(nm) time.
*/

# define SWAP(t, a, b) \
	do {\
		t _swap = (a);\
		(a) = (b);\
		(b) = _swap;\
	} while (0)

# define MIN(a, b)      (((a) < (b)) ? (a) : (b))
# define MIN3(a, b, c)  MIN(MIN((a), (b)), (c))

# define VEC_ALLOC(typ, ne) ((typ *) malloc(sizeof(typ) * (ne)))
# define VEC_FREE(v)        free(v)

  /* Cost of edit operations; can be overridden at compile time */
# ifndef INS_COST
#   define INS_COST   1
# endif
# ifndef DEL_COST
#   define DEL_COST   1
# endif
# ifndef SUBST_COST
#   define SUBST_COST 1
# endif

	/* Get bytes */
	uint8_t *s = (C_truep(C_stringp(os)) ? (uint8_t *) C_c_string(os) : (uint8_t *) C_c_bytevector(os));
	uint8_t *t = (C_truep(C_stringp(ot)) ? (uint8_t *) C_c_string(ot) : (uint8_t *) C_c_bytevector(ot));

  /* N = # of columns, M = # of rows */
  uint32_t n = C_header_size(os);
  uint32_t m = C_header_size(ot);

  /* Handle empty string arguments */
  if (n == 0) {
    C_return(m);
  }
  if (m == 0) {
    C_return(n);
  }

  /* Use shorter for work vector allocation */
  if (n < m) {
    SWAP(uint32_t, n, m);
    SWAP(uint8_t *, s, t);
  }

  /* Cost vector storage */
  uint32_t *w = VEC_ALLOC(uint32_t, m + 1);

  uint32_t i, j;

  /* Initialize cost to position */
  for (j = 0; j <= m; ++j) {
    w[j] = j;
  }

  uint32_t next;
  for (i = 0; i < n; ++i) {

    const uint32_t s_i = s[i];

    uint32_t cur = i + 1;
    for (j = 0; j < m; ++j) {

      const uint32_t ic = w[j+1] + INS_COST;
      const uint32_t dc = cur + DEL_COST;
      const uint32_t sc = w[j] + (t[j] == s_i ? 0 : SUBST_COST);

      next = MIN3(ic, dc, sc);
      w[j] = cur;
      cur = next;
    }

    w[m] = next;
  }

  VEC_FREE(w);

  C_return(next);

# undef SWAP

# undef MIN
# undef MIN3

# undef VEC_ALLOC
# undef VEC_FREE

# undef INS_COST
# undef DEL_COST
# undef SUBST_COST
EOF
) s t) )

) ;module levenshtein-byte