local fn LevenshteinDistance( s1 as CFStringRef, s2 as CFStringRef ) as NSInteger
  NSInteger result

  // If strings are equal, Levenshtein distance is 0
  if ( fn StringIsEqual( s1, s2 ) ) then result = 0 : exit fn

  // If either string is empty, then distance is the length of the other string.
  if ( len(s1) == 0) then result = len(s2) : exit fn
  if ( len(s2) == 0) then result = len(s1) : exit fn

  // The remaining recursive process uses first characters and remainder of each string.
  CFStringRef s1First = fn StringSubstringToIndex( s1, 1 )
  CFStringRef s2First = fn StringSubstringToIndex( s2, 1 )
  CFStringRef s1Rest  = mid( s1, 1, len(s1) -1 )
  CFStringRef s2Rest  = mid( s2, 1, len(s2) -1 )

  // If leading characters are the same, then distance is that between the rest of the strings.
  if fn StringIsEqual( s1First, s2First ) then result = fn LevenshteinDistance( s1Rest, s2Rest ) : exit fn

  // Find the distances between sub strings.
  NSInteger distA = fn LevenshteinDistance( s1Rest,     s2 )
  NSInteger distB = fn LevenshteinDistance( s1,     s2Rest )
  NSInteger distC = fn LevenshteinDistance( s1Rest, s2Rest )

  // Return the minimum distance between substrings.
  NSInteger minDist = distA
  if ( distB < minDist ) then minDist = distB
  if ( distC < minDist ) then minDist = distC
  result = minDist + 1 // Include change for the first character.
end fn = result


NSInteger  i
CFStringRef testStr( 6, 2 )

testStr( 0, 0 ) = @"kitten"      : testStr( 0, 1 ) = @"sitting"
testStr( 1, 0 ) = @"rosettacode" : testStr( 1, 1 ) = @"raisethysword"
testStr( 2, 0 ) = @"Saturday"    : testStr( 2, 1 ) = @"Sunday"
testStr( 3, 0 ) = @"FutureBasic" : testStr( 3, 1 ) = @"FutureBasic"
testStr( 4, 0 ) = @"rave"        : testStr( 4, 1 ) = @"ravel"
testStr( 5, 0 ) = @"black"       : testStr( 5, 1 ) = @"slack"
testStr( 6, 0 ) = @"rave"        : testStr( 6, 1 ) = @"grave"

for i = 0 to 6
  print @"1st string = "; testStr( i, 0 )
  print @"2nd string = "; testStr( i, 1 )
  print @"Levenshtein distance = "; fn LevenshteinDistance( testStr( i, 0 ), testStr( i, 1 ) )
  print
next

HandleEvents