#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

// run with no arguments for help

// usage: madmax strlen displaywidth \tau(a) \tau(b) etc.
// e.g. "madmax 10000 40 ab a" to produce a string of length at
// least 10000 and search for periods in it, printing only those
// of width less than or equal to 40.

// an attempt at a fast apply function
char *apply(char *u, int alsize, char *tau[]) {
	size_t maxlen = 0;
	for(int i = 0; i < alsize; i++) {
		if (strlen(tau[i]) > maxlen) maxlen = strlen(tau[i]);
	}
	char *result = malloc(maxlen * strlen(u) +1);

	char *dst = result;
	char *src;
	while(*u) {
		src = tau[*u - 'a'];
		while(*src) {*(dst++) = *(src++);}
		u++;
	}
	*dst = 0;

	return result;
}

// generates sturmian sequence - given the right input
char *gensturm(unsigned long len, double alpha) {
	char *result = malloc(len + 1);
	*(result + len) = 0;
	for(unsigned long n = 0; n < len; n++) {
		*(result + n) = 'a' + (ceil(n*alpha+alpha) - ceil(n*alpha));
	}
    return result;
}

// finds and prints powers of periods
double strmp(char *instr, int displaywidth) {
	unsigned long limit = strlen(instr); // length of input string
	unsigned long offset;  // offset searching for not-equal pair
	unsigned long lastneq; // offset of previous not-equal pair
	unsigned long len, width; // length and width of period found
	unsigned long maxwidth = 0; unsigned long maxlen = 1; // length and width of max period found
	char *substr; // dunnmy for extracting substring to print

	for(len = 1;; len++) {
		offset = 0;
		while(offset+len+1 <= limit && *(instr+offset) == *(instr+offset+len)) {offset++;}
		if(offset+len+1 > limit) {return (double)maxwidth/maxlen;}
		lastneq = offset; offset++;

		while(1) {
			while(offset+len+1 <= limit && *(instr+offset) == *(instr+offset+len)) {offset++;}
			if(offset+len+1 > limit) {break;}
			width = offset+len-1-lastneq;
			if(width/len > maxwidth/maxlen || (width/len == maxwidth/maxlen && (width%len)*maxlen > (maxwidth%maxlen)*len)) {
				maxwidth = width; maxlen = len;
				printf("new lb: %f from ",width/(double)len);
					if (width <= displaywidth) {
						substr = malloc(width+1); // extracting substrings is a hassle in C
						strncpy(substr,(instr+lastneq+1),width); *(substr+width) = 0;
						printf("(%s,%d)\n",substr,len);
						free(substr);
					} else {
						printf("[anonymous, length %d]\n",len);
					}
			}
			lastneq = offset; offset++;
		}
	}
}

// this is where it all begins... and ends
int main(int argc, char *argv[]) {
	if(argc < 3) {
		printf("Mad Max 1.2.0 by thamsborg@itu.dk\n - your fast & friendly MP approximator\n");
		printf("\n");
		printf("Sturmian seq: madmax L alpha, e.g., madmax 500000 0.618033988749894\n");
		printf("Substutution: madmax L tau(a) tau(b), e.g., madmax 100000 ab a\n");
		printf("L denotes length of string to search\n");
	}
	if(argc == 3) {strmp(gensturm(strtoul(argv[1],0,0), strtod(argv[2],0)),50);}
	if(argc > 3) {
		// produce long string
		char *lu = malloc(2); *lu = 'a'; *(lu+1) = 0;
		char *oldlu = lu;
		while(strlen(lu) < strtol(argv[1],0,0)) {lu = apply(lu, argc-2, argv+2); free(oldlu);	oldlu = lu;}

		// go for it!
		strmp(lu, 50);
	}

	return 0;
}