RosettaCodeData/Task/Execute-a-Markov-algorithm/C/execute-a-markov-algorithm-1.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <ctype.h>

typedef struct { char * s; size_t alloc_len; } string;

typedef struct {
	char *pat, *repl;
	int terminate;
} rule_t;

typedef struct {
	int n;
	rule_t *rules;
	char *buf;
} ruleset_t;

void ruleset_del(ruleset_t *r)
{
	if (r->rules) free(r->rules);
	if (r->buf) free(r->buf);
	free(r);
}

string * str_new(const char *s)
{
	int l = strlen(s);
	string *str = malloc(sizeof(string));
	str->s = malloc(l + 1);
	strcpy(str->s, s);
	str->alloc_len = l + 1;
	return str;
}

void str_append(string *str, const char *s, int len)
{
	int l = strlen(str->s);
	if (len == -1) len = strlen(s);

	if (str->alloc_len < l + len + 1) {
		str->alloc_len = l + len + 1;
		str->s = realloc(str->s, str->alloc_len);
	}
	memcpy(str->s + l, s, len);
	str->s[l + len] = '\0';
}

/* swap content of dest and src, and truncate src string */
void str_transfer(string *dest, string *src)
{
	size_t tlen = dest->alloc_len;
	dest->alloc_len = src->alloc_len;
	src->alloc_len = tlen;

	char *ts = dest->s;
	dest->s = src->s;
	src->s = ts;
	src->s[0] = '\0';
}

void str_del(string *s)
{
	if (s->s) free(s->s);
	free(s);
}

void str_markov(string *str, ruleset_t *r)
{
	int i, j, sl, pl;
	int changed = 0, done = 0;
	string *tmp = str_new("");

	while (!done) {
		changed = 0;
		for (i = 0; !done && !changed && i < r->n; i++) {
			pl = strlen(r->rules[i].pat);
			sl = strlen(str->s);
			for (j = 0; j < sl; j++) {
				if (strncmp(str->s + j, r->rules[i].pat, pl))
					continue;
				str_append(tmp, str->s, j);
				str_append(tmp, r->rules[i].repl, -1);
				str_append(tmp, str->s + j + pl, -1);

				str_transfer(str, tmp);
				changed = 1;

				if (r->rules[i].terminate)
					done = 1;
				break;
			}
		}
		if (!changed) break;
	}
	str_del(tmp);
	return;
}

ruleset_t* read_rules(const char *name)
{
	struct stat s;
	char *buf;
	size_t i, j, k, tmp;
	rule_t *rules = 0;
	int n = 0; /* number of rules */

	int fd = open(name, O_RDONLY);
	if (fd == -1) return 0;

	fstat(fd, &s);
	buf = malloc(s.st_size + 2);
	read(fd, buf, s.st_size);
	buf[s.st_size] = '\n';
	buf[s.st_size + 1] = '\0';
	close(fd);

	for (i = j = 0; buf[i] != '\0'; i++) {
		if (buf[i] != '\n') continue;

		/* skip comments */
		if (buf[j] == '#' || i == j) {
			j = i + 1;
			continue;
		}

		/* find the '->' */
		for (k = j + 1; k < i - 3; k++)
			if (isspace(buf[k]) && !strncmp(buf + k + 1, "->", 2))
				break;

		if (k >= i - 3) {
			printf("parse error: no -> in %.*s\n", i - j, buf + j);
			break;
		}

		/* left side: backtrack through whitespaces */
		for (tmp = k; tmp > j && isspace(buf[--tmp]); );
		if (tmp < j) {
			printf("left side blank? %.*s\n", i - j, buf + j);
			break;
		}
		buf[++tmp] = '\0';

		/* right side */
		for (k += 3; k < i && isspace(buf[++k]););
		buf[i] = '\0';

		rules = realloc(rules, sizeof(rule_t) * (1 + n));
		rules[n].pat = buf + j;

		if (buf[k] == '.') {
			rules[n].terminate = 1;
			rules[n].repl = buf + k + 1;
		} else {
			rules[n].terminate = 0;
			rules[n].repl = buf + k;
		}
		n++;

		j = i + 1;
	}

	ruleset_t *r = malloc(sizeof(ruleset_t));
	r->buf = buf;
	r->rules = rules;
	r->n = n;
	return r;
}

int test_rules(const char *s, const char *file)
{
	ruleset_t * r = read_rules(file);
	if (!r) return 0;
	printf("Rules from '%s' ok\n", file);

	string *ss = str_new(s);
	printf("text:     %s\n", ss->s);

	str_markov(ss, r);
	printf("markoved: %s\n", ss->s);

	str_del(ss);
	ruleset_del(r);

	return printf("\n");
}

int main()
{
	/* rule 1-5 are files containing rules from page top */
	test_rules("I bought a B of As from T S.", "rule1");
	test_rules("I bought a B of As from T S.", "rule2");
	test_rules("I bought a B of As W my Bgage from T S.", "rule3");
	test_rules("_1111*11111_", "rule4");
	test_rules("000000A000000", "rule5");

	return 0;
}