#include <stdio.h>
#include <string.h>
#include <memory.h>

#include "triangle.h"
#include "queue.h"

static groupelement_t *find_adj(groupelement_t *cur, int gen, int other, int order)
{
	groupelement_t *next = cur->adj[other];
	for(int i = 0; i < order - 1; i++) {
		if(!next)
			break;
		next = next->adj[gen];
		if(!next)
			break;
		next = next->adj[other];
	}
	return next;
}

int generate_triangle_group(groupelement_t *group, int size, int k1, int k2, int k3)
{
	queue_t q;
	int id, n;
	groupelement_t *cur, *inv;

	int k[3] = {k1, k2, k3};

	memset(group, 0, size*sizeof(groupelement_t));
	group[0].letter = -1;
	n = 1;
	queue_init(&q);
	queue_put(&q, 0);

	while((id = queue_get(&q)) != -1) {
		cur = &group[id];

		for(int gen = 0; gen < 3; gen++) {
			if(!cur->adj[gen])
				cur->adj[gen] = find_adj(cur, gen, (gen+2)%3, k[(gen+1)%3]);

			if(!cur->adj[gen])
				cur->adj[gen] = find_adj(cur, gen, (gen+1)%3, k[(gen+2)%3]);

			if(!cur->adj[gen] && n < size) {
				cur->adj[gen] = &group[n];
				cur->adj[gen]->id = n;
				cur->adj[gen]->parent = cur;
				cur->adj[gen]->letter = gen;
				cur->adj[gen]->length = cur->length + 1;
				queue_put(&q, n);
				n++;
			}

			if(cur->adj[gen])
				cur->adj[gen]->adj[gen] = cur;
		}
	}

	for(int i = 0; i < size; i++) {
		cur = &group[i];
		inv = &group[0];
		while(cur->parent && inv) {
			inv = inv->adj[cur->letter];
			cur = cur->parent;
		}
		group[i].inverse = inv;
	}

	return n;
}