#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/errno.h>

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

int csvRead(char *fname, char ***olsp);

static inline unsigned int distance(int o1len, char *o1seq, int o2len, char *o2seq) {
	unsigned int x, y, lastdiag, olddiag;
	unsigned int column[o1len + 1];

	for (y = 1; y <= o1len; y++)
		column[y] = y;

	for (x = 1; x <= o2len; x++) {
		column[0] = x;
		for (y = 1, lastdiag = x-1; y <= o1len; y++) {
			olddiag = column[y];
			column[y] = MIN3(column[y] + 1, column[y-1] + 1, lastdiag + (o1seq[y-1] == o2seq[x-1] ? 0 : 1));
			lastdiag = olddiag;
		}
	}

	return(column[o1len]);
}

int main(int argc, char **argv) {
	int dsnum, olnum;
	char **dss, **ols;
	double start, end;
	struct timespec ts;

	if (argc != 3) {
		fprintf(stderr, "expecting dictionary-file sequencing-file\n");
		return -1;
	}

	dsnum = csvRead(argv[1], &dss);
	olnum = csvRead(argv[2], &ols);

	fprintf(stderr, "ds %d ol %d\n", dsnum, olnum);

	for(int i = 0; i < olnum; i++) {
		int olen = strlen(ols[i]);
		unsigned int dist = 10000;
		clock_gettime(CLOCK_MONOTONIC, &ts);
		start = ts.tv_sec * 1000.0 + ts.tv_nsec / 10000000.0; 
		for(int j = 0; j < dsnum; j++) {
			unsigned int d = distance(olen, ols[i], strlen(dss[j]), dss[j]);
			if (d < dist) {
				dist = d;
			}
		}
		clock_gettime(CLOCK_MONOTONIC, &ts);
		end = ts.tv_sec * 1000.0 + ts.tv_nsec / 10000000.0; 

		printf("%d: %d %f ms\n", i, dist, end - start);
	}

	return 0;
}

int csvRead(char *fname, char ***olsp) {
	FILE *fp;
	char buf[1024];
	char *p, *ol, *cu;
	char **ols, *o;
	int olsz, olsnum;
	double cubu;

	fp = fopen(fname, "r");
	if (!fp) {
		return -errno;
	}

	olsz = 0;
	olsnum = 0;
	ols = NULL;
	while ((p = fgets(buf, sizeof(buf), fp)) != NULL) {
		int plen;

		plen = strlen(p);
		if (p[plen - 1] == '\n') {
			p[plen - 1] = '\0';
			plen--;
		}

		ol = p;
		cu = NULL;
		if ((cu = (char *) memchr(p, ' ', plen)) != NULL) {
			*cu = '\0';
			cu++;
			if ((p = strchr(cu, ' ')) != NULL) {
				*p = '\0';
			}
		} else if ((cu = (char *) memchr(p, ',', plen)) != NULL) {
			*cu = '\0';
			cu++;
			if ((p = strchr(cu, ',')) != NULL) {
				*p = '\0';
			}
		}

		cubu = 1.0;
		if (cu != NULL) {
			cubu = strtod(cu, &p);
			if (*p != '\0') {
				cubu = 1.0;
			}
		}

		o = malloc(strlen(ol) + 1);
		memcpy(o, ol, strlen(ol) + 1);
		if (olsz <= olsnum) {
			olsz += 1000;
			ols = (char **) realloc(ols, sizeof(char *) * olsz);
		}

		ols[olsnum] = o;
		olsnum++;
	}

	if (ferror(fp)) {
		return -errno;
	}

	*olsp = ols;
	return olsnum;
}