#include <assert.h>
#include <stdlib.h>

#include "levenshtein.h"

// Serial single-threaded Levenshtein =============================================================
static inline size_t distance_serial_ascii(const char* s1, size_t len1, const char* s2, size_t len2, size_t* prev, size_t* curr)
{
	// Descent in the matrix
	for ( size_t row = 0; row < len1; ++row )
	{
		// Calculate distances for current line
		curr[0] = row + 1;
		for ( size_t col = 0; col < len2; ++col )
			curr[col + 1] = min3(
				prev[col + 1] + 1,
				curr[col] + 1,
				prev[col] + (size_t)(s1[row] != s2[col]) );

		// Swap both lines
		size_t* temp = prev;
		prev = curr;
		curr = temp;
	}

	return prev[len2];
}

static inline size_t distance_serial_unicode(const wchar_t* s1, size_t len1, const wchar_t* s2, size_t len2, size_t* prev, size_t* curr)
{
	// Descent in the matrix
	for ( size_t row = 0; row < len1; ++row )
	{
		// Calculate distances for current line
		curr[0] = row + 1;
		for ( size_t col = 0; col < len2; ++col )
			curr[col + 1] = min3(
				prev[col + 1] + 1,
				curr[col] + 1,
				prev[col] + (size_t)(s1[row] != s2[col]) );

		// Swap both lines
		size_t* temp = prev;
		prev = curr;
		curr = temp;
	}

	return prev[len2];
}

size_t levenshtein_distance_serial(const void* s1, size_t len1, const void* s2, size_t len2, bool unicode)
{
	assert(s1);
	assert(s2);

	// Create a vector of distances for the previous line
	size_t distances = len2 + 1;
	size_t* prev = malloc( distances * sizeof(size_t) );
	if ( prev == NULL) return (size_t) -1;

	// Create a vector of distances for the current line
	size_t* curr = malloc( distances * sizeof(size_t) );
	if ( curr == NULL) return (void)free(prev), (size_t) -1;

	// Init the first row
	for ( size_t col = 0; col < distances; ++col )
		prev[col] = col;

	// Calculate the distance
	size_t result = unicode
		? distance_serial_unicode((const wchar_t*)s1, len1, (const wchar_t*)s2, len2, prev, curr)
		: distance_serial_ascii((const char*)s1, len1, (const char*)s2, len2, prev, curr);

	// Free the arrays
	free(prev);
	free(curr);

	// Done
	return result;
}