/**************************
   Debug config
**************************/

//#define DEBUGPATTERN 1
//#define DEBUGTEMPLATE 1
//#define DEBUGMATCH 1
//#define DEBUGREPLACE 1

/**************************
   Debug define helpers
**************************/

#if DEBUGPATTERN || DEBUGTEMPLATE || DEBUGMATCH || DEBUGREPLACE
#define DEBUG 1
#endif

#define noprint(fmt, args...) do { } while(0)
#define dprintf(fmt, args...) fprintf(stderr, "%s:%i (%s): " fmt "\n", __FILE__, __LINE__, __FUNCTION__, ##args)

#define writeErrorMsg(msg) write(2, msg, sizeof(msg));

#ifdef DEBUGPATTERN
#define debugPattern(fmt, args...) dprintf(fmt, ##args)
#else
#define debugPattern noprint
#endif

#ifdef DEBUGTEMPLATE
#define debugTemplate(fmt, args...) dprintf(fmt, ##args)
#else
#define debugTemplate noprint
#endif

#ifdef DEBUGMATCH
#define debugMatch(fmt, args...) dprintf(fmt, ##args)
#else
#define debugMatch noprint
#endif

#ifdef DEBUGREPLACE
#define debugReplace(fmt, args...) dprintf(fmt, ##args)
#else
#define debugReplace noprint
#endif

/**************************
      Includes
**************************/

#include "string.h"
#include "timer.h"

#include <stdio.h>


/**************************
   Enums, Structs, Globals
**************************/

enum Bases {
	BASE_I = 1, BASE_C, BASE_F, BASE_P, BASE_X,
	CMD_NEXT
};
const char *bases = " ICFPX";
enum PatternCmd {
	P_SKIP = CMD_NEXT, P_SEARCH, P_OPEN, P_CLOSE
};
enum TemplateCmd {
	T_REF = CMD_NEXT, T_LEN
};

typedef struct pattern {
	char cmd;
	unsigned int skip;
	sstring_t search;
} pattern_t;

typedef struct template {
	char cmd;
	unsigned int ref, level;
} template_t;

typedef struct environment {
	string_pos_t begin;
	int outerenv;
} env_t;

#define TABLE_PAGE ((size_t)(1 << 8))
static inline size_t TABLE_ROUND_UP(size_t size) { return (size+TABLE_PAGE-1) & ~(TABLE_PAGE-1); }

pattern_t *pattern_table;
size_t pattern_count, pattern_size;

template_t *template_table;
size_t template_count, template_size;

string_t *dnaString, *replString;
string_pos_t dnaPos;

env_t *envPos;
string_t *envStr;
size_t env_count, env_size, envStr_count;
int cur_env = -1;

inline static void printDna(string_pos_t pos, int len) {
	char c;
	while (len-- && string_pos_take(&pos, &c))
		write(2, &bases[(int)c], 1);
}

#ifdef DEBUG
inline static void printDnaStr(string_t *str, int len) {
	string_pos_t pos = {};
	string_begin(str, &pos);
	char c;
	while (len-- && string_pos_take(&pos, &c))
		fprintf(stderr, "%c", bases[(int)c]);
}

inline static void printDnaSimple(sstring_t *str) {
	char *data = sstring_data(str);
	for (size_t i = 0, l = sstring_len(str); i < l; i++, data++)
		fprintf(stderr, "%c", bases[(int)*data]);
}
#endif

/**************************
      Parse helpers
**************************/

int WriteRna() {
	char rna[7], c;
	int i;
	for (i = 0; i < 7; i++) {
		if (!string_pos_take(&dnaPos, &c)) break;
		rna[i] = bases[(int)c];
	}
	write(1, rna, i);
//	if (i != 7) fprintf(stderr, "Rna breaked\n");
	return i == 7;
}

int Nat(unsigned int *number) {
	unsigned int n = 0, n1 = 1;
	char c;
	while (string_pos_take(&dnaPos, &c)) {
		switch (c) {
			case BASE_P: *number = n; return 1;
			case BASE_C: n |= n1;
		}
		n1 <<= 1;
	}
	*number = 0;
//	fprintf(stderr, "Nat breaked\n");
	return 0;
}

int Const(sstring_t *str) {
	char c;
	while (string_pos_take(&dnaPos, &c)) {
		switch (c) {
			case BASE_X: sstring_append_char(str, BASE_X); break;
			case BASE_C: sstring_append_char(str, BASE_I); break;
			case BASE_F: sstring_append_char(str, BASE_C); break;
			case BASE_P: sstring_append_char(str, BASE_F); break;
			case BASE_I:
				if (string_pos_eos(&dnaPos) || (string_pos_get(&dnaPos) != BASE_C)) {
					string_pos_prev(&dnaPos, dnaString);
					return 1;
				}
				string_pos_next(&dnaPos);
				sstring_append_char(str, BASE_P); break;
		}
	}
//	fprintf(stderr, "Const breaked\n");
	return 0;
}

/**************************
      Pattern management
**************************/

static inline void clearPatterns() {
	for (size_t i = 0; i < pattern_count; i++)
		if (pattern_table[i].cmd == P_SEARCH)
			sstring_zero(&pattern_table[i].search);
	pattern_count = 0;
}

static inline void freePatterns() {
	for (size_t i = 0; i < pattern_size; i++)
		sstring_clear(&pattern_table[i].search);
	pattern_count = pattern_size = 0;
	free(pattern_table); pattern_table = 0;
}

static inline pattern_t* appendPattern() {
	if (pattern_count == pattern_size) {
		size_t i = pattern_size;
		pattern_size = TABLE_ROUND_UP(pattern_size+1);
		pattern_table = realloc(pattern_table, pattern_size * sizeof(pattern_t));
		for ( ; i < pattern_size; i++)
			sstring_init(&pattern_table[i].search);
	}
	return &pattern_table[pattern_count++];
}

static inline void appendPCmdBase(char base) {
	appendPattern()->cmd = base;
	debugPattern("Base '%c'", bases[(int)base]);
}

static inline int appendPCmdSkip() {
	pattern_t *p = appendPattern();
	p->cmd = P_SKIP;
	if (!Nat(&p->skip)) return 0;
	debugPattern("Skip %i", p->skip);
	return 1;
}

static inline int appendPCmdSearch() {
	pattern_t *p = appendPattern();
	p->cmd = P_SEARCH;
//	debugPattern("Search");
	if (!Const(&p->search)) return 0;
#ifdef DEBUGPATTERN
	fprintf(stderr, "Search '"); printDnaSimple(&p->search); fprintf(stderr, "'\n");
#endif
	return 1;
}

static inline void appendPCmdOpen() {
	appendPattern()->cmd = P_OPEN;
	debugPattern("Open");
}

static inline void appendPCmdClose() {
	appendPattern()->cmd = P_CLOSE;
	debugPattern("Close");
}

int readPattern() {
	unsigned int lvl = 0;
	char c;
	while (string_pos_take(&dnaPos, &c)) {
		switch (c) {
			case BASE_X: appendPCmdBase(BASE_X); break;
			case BASE_C: appendPCmdBase(BASE_I); break;
			case BASE_F: appendPCmdBase(BASE_C); break;
			case BASE_P: appendPCmdBase(BASE_F); break;
			case BASE_I:
				if (!string_pos_take(&dnaPos, &c)) {
					debugPattern("Pattern break (unexpected end after 'I')");
					return 0;
				}
				switch (c) {
					case BASE_X: printDna(dnaPos, -1); write(2, "\n", 1); return 0;
					case BASE_C: appendPCmdBase(BASE_P); break;
					case BASE_P: if (!appendPCmdSkip()) return 0; break;
					case BASE_F:
						if (!string_pos_take(&dnaPos, &c)) {
							debugPattern("Pattern break (unexpected end after 'IF')");
							return 0;
						}
						if (!appendPCmdSearch()) return 0;
						break;
					case BASE_I:
						if (!string_pos_take(&dnaPos, &c)) {
							debugPattern("Pattern break (unexpected end after 'II')");
							return 0;
						}
						switch (c) {
							case BASE_C:
							case BASE_F:
								if (!lvl) return 1;
								lvl--; appendPCmdClose();
								break;
							case BASE_P: lvl++; appendPCmdOpen(); break;
							case BASE_I: if (!WriteRna()) return 0;
						}
				}
				
		}
	}
	return 0;
}

/**************************
      Template management
**************************/

static inline void clearTemplates() {
	template_count = 0;
}

static inline void freeTemplates() {
	template_count = template_size = 0;
	free(template_table); template_table = 0;
}

static inline template_t* appendTemplate() {
	if (template_count == template_size) {
		template_size = TABLE_ROUND_UP(template_size+1);
		template_table = realloc(template_table, template_size * sizeof(template_t));
	}
	return &template_table[template_count++];
}

static inline void appendTCmdBase(char base) {
	appendTemplate()->cmd = base;
	debugTemplate("Base '%c'", bases[(int)base]);
}

static inline int appendTCmdRef() {
	template_t *t = appendTemplate();
	t->cmd = T_REF;
	if (!Nat(&t->level)) return 0;
	if (!Nat(&t->ref)) return 0;
	debugTemplate("Ref %i, Level %i", t->ref, t->level);
	return 1;
}

static inline int appendTCmdLen() {
	template_t *t = appendTemplate();
	t->cmd = T_LEN;
	if (!Nat(&t->ref)) return 0;
	debugTemplate("Len %i", t->ref);
	return 1;
}

int readTemplate() {
	char c;
	while (string_pos_take(&dnaPos, &c)) {
		switch (c) {
			case BASE_X: appendTCmdBase(BASE_X); break;
			case BASE_C: appendTCmdBase(BASE_I); break;
			case BASE_F: appendTCmdBase(BASE_C); break;
			case BASE_P: appendTCmdBase(BASE_F); break;
			case BASE_I:
				if (!string_pos_take(&dnaPos, &c)) return 0;
				switch (c) {
					case BASE_C: appendTCmdBase(BASE_P); break;
					case BASE_P:
					case BASE_F:
						if (!appendTCmdRef()) return 0;
						break;
					case BASE_I:
						if (!string_pos_take(&dnaPos, &c)) return 0;
						switch (c) {
							case BASE_C:
							case BASE_F:
								return 1;
							case BASE_P: if (!appendTCmdLen()) return 0; break;
							case BASE_I: if (!WriteRna()) return 0;
						}
				}
				
		}
	}
	return 0;
}

/**************************
   Environment management
**************************/

static inline void clearEnvironment() {
	for (size_t i = 0; i < envStr_count; i++) {
		string_clear(&envStr[i]);
	}
	env_count = 0; cur_env = -1;
	envStr_count = 0;
}

static inline void freeEnvironment() {
	for (size_t i = 0; i < envStr_count; i++)
		string_clear(&envStr[i]);
	env_count = env_size = 0; cur_env = -1;
	envStr_count = 0;
	free(envPos); envPos = 0;
	free(envStr); envStr = 0;
}

static inline void startEnvironment() {
	if (env_count == env_size) {
		size_t i = env_size;
		env_size = TABLE_ROUND_UP(env_size+1);
		envPos = realloc(envPos, env_size * sizeof(env_t));
		envStr = realloc(envStr, env_size * sizeof(string_t));
		for (; i < env_size; i++)
			string_init(&envStr[i]);
	}
	envPos[env_count].begin = dnaPos;
	envPos[env_count].outerenv = cur_env;
	cur_env = env_count++;
}

static inline void endEnvironment() {
	string_append_range(&envStr[envStr_count++], &envPos[cur_env].begin, &dnaPos);
	debugMatch("envStr[%i].len = %i", envStr_count-1, string_len(&envStr[envStr_count-1]));
	cur_env = envPos[cur_env].outerenv;
}

/**************************
      Replace helpers
**************************/

static inline void expand(string_t *str, unsigned int level, char c) {
	if (level + c > 4 && c != BASE_X) {
		level = level - 5 + c;
		expand(str, level, BASE_I);
		expand(str, level, BASE_C);
	} else {
		string_append_char(str, (c + level - 1) % 4 + 1);
	}
}

static inline void protect(string_t *str, unsigned int level, string_t *dna) {
	char c;
	string_pos_t i = {  };
	string_begin(dna, &i);
	while (string_pos_take(&i, &c))
		expand(str, level, c);
}

static inline void asnat(string_t *str, int n) {
	for (; n; n >>= 1)
		string_append_char(str, (n & 0x1) ? BASE_C : BASE_I);
	string_append_char(str, BASE_P);
}

static inline void applyRef(string_t *str, unsigned int ref, unsigned int level) {
	if (ref < envStr_count) {
		if (level)
			protect(str, level, &envStr[ref]);
		else
			string_append_string(str, &envStr[ref]);
	}
}

static inline void applyLen(string_t *str, unsigned int ref) {
	asnat(str, (ref < envStr_count) ? string_len(&envStr[ref]) : 0);
}

/**************************
      Match + Replace
**************************/

int Match() {
	string_pos_t markDna = dnaPos;
	pattern_t *pat = pattern_table;
	char c;
	for (size_t i = 0; i < pattern_count; i++, pat++) {
		switch (pat->cmd) {
			case BASE_I:
			case BASE_C:
			case BASE_F:
			case BASE_P:
			case BASE_X:
				if (!string_pos_take(&dnaPos, &c) || c != pat->cmd) {
					debugMatch("Match: Didn't find base '%c'", bases[(int) pat->cmd]);
					goto notfound;
				}
				break;
			case P_SKIP:
				if (string_pos_remain(&dnaPos) < pat->skip) {
					debugMatch("Match: Couldn't skip %i acids", pat->skip);
					goto notfound;
				}
				string_pos_inc(&dnaPos, pat->skip);
				break;
			case P_SEARCH:
				if (!string_find_sstring(&dnaPos, &pat->search)) goto notfound;
				break;
			case P_OPEN:
				startEnvironment();
				break;
			case P_CLOSE:
				endEnvironment();
				break;
		}
	}
	return 1;
notfound:
	dnaPos = markDna;
	return 0;
}

void Replace() {
	template_t *tmpl = template_table;
	for (size_t i = 0; i < template_count; i++, tmpl++) {
		switch (tmpl->cmd) {
			case BASE_I:
			case BASE_C:
			case BASE_F:
			case BASE_P:
			case BASE_X:
				debugReplace("append '%c'", bases[(int)tmpl->cmd]);
				string_append_char(replString, tmpl->cmd);
				break;
			case T_REF:
				debugReplace("append Ref");
				applyRef(replString, tmpl->ref, tmpl->level);
				break;
			case T_LEN:
				debugReplace("append Len");
				applyLen(replString, tmpl->ref);
				break;
		}
	}
	if (string_len(replString)) {
		debugReplace("Repl len: %i, dna remain len: %i", string_len(replString), string_pos_remain(&dnaPos));
#ifdef DEBUGREPLACE
		fprintf(stderr, "Replace: '"); printDnaStr(replString, 50); fprintf(stderr, "'\n");
#endif
		string_simplify(replString);
		string_append_from(replString, &dnaPos);
		debugReplace("new dna len: %i", string_len(replString));
		string_t *tmp = dnaString; dnaString = replString; replString = tmp;
		string_begin(dnaString, &dnaPos);
		string_clear(replString);
	} else {
		debugReplace("Replace empty\n");
	}
}

/**************************
      Main part
**************************/

string_t* readdna() {
	static const char convert[256] = {
		['I'] = BASE_I, ['C'] = BASE_C, ['F'] = BASE_F, ['P'] = BASE_P, ['X'] = BASE_X
	};
	const size_t blocksize = 1 << 18; // 256k
	int readed;
	char *data;
	string_t *buf = string_new();
	do {
		data = string_buf_reserve(buf, blocksize);
		readed = read(0, data, blocksize);
		if (readed < 0) {
			writeErrorMsg("Read error\n");
			exit(-1);
		}
		int used = 0;
		for (int i = 0; i < readed; i++) {
			char c = convert[(int) data[i]];
			if (c) data[used++] = c;
		}
		string_buf_used(buf, used);
	} while (readed);
	return buf;
}

// String will be free'd
void dna2rna(string_t *str) {
	duration_t timer;
	timerBegin(&timer);
	dnaString = str;
	replString = string_new();
	string_begin(dnaString, &dnaPos);
	int iterations = 0;
	while (string_pos_remain(&dnaPos)) {
//		fprintf(stderr, "Dna: '"); printDna(dnaPos, 20); fprintf(stderr, "...'\n");
		if (!(iterations % 100000)) {
			fprintf(stderr, "Iteration: %i\n", iterations);
//			fprintf(stderr, "Parts: %i\n", dnaString->part_count);
		}

		if (!(iterations % 10000) && (dnaString->part_count > 96)) {
			string_flatten(dnaString);
			size_t pos = dnaPos.abspos;
			string_begin(dnaString, &dnaPos);
			if (pos) string_pos_inc(&dnaPos, pos);
		}
		if (!readPattern()) {
			debugPattern("Pattern breaked");
			break;
		}
		if (!readTemplate()) {
			debugTemplate("Template breaked");
			break;
		}
		if (Match())
			Replace();
		clearPatterns();
		clearTemplates();
		clearEnvironment();
		iterations++;
	}
//	fprintf(stderr, "Needed Iterations: %i\n", iterations);
	freePatterns();
	freeTemplates();
	freeEnvironment();
	string_free(dnaString); dnaString = 0;
	string_free(replString); replString = 0;
	timerEnd(&timer);
	float ips = (float) iterations / timerAsFloat(&timer);
	fprintf(stderr, "%f iterations per second (%f s)\n", ips, timerAsFloat(&timer));
}

int main() {
	writeErrorMsg("Dna -> Rna...\n");
	dna2rna(readdna());
	return 0;
}