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

#include "../powMod/powMod.h"

typedef struct _Polynom {
	int count;
	int data[0];
} *Polynom;

Polynom createPolynom(int count) {
	Polynom list = (Polynom)malloc(sizeof(Polynom) + sizeof(int)*(count));
	list->count = count;
	return list;
}

void displayPolynom(Polynom list) {
	int i;
	printf("Polynom:");
	for (i = 0; i < list->count; i++) {
		printf(" %i", list->data[i]);
	}
	printf("\n");
}

int applyMod(Polynom in, int x, int mod) {
	// accumulator
	int acc = 0;
	int i;
	printf("Applying %i mod %i to ", x, mod);
	displayPolynom(in);
	for (i = 0; in != NULL && i < in->count; i++) {
		acc += in->data[i] * uiPowMod(x, i, mod);
		acc %= mod;
	}
	return acc;
}

Polynom FFT(Polynom in, int omega, int mod) {
	int i;
	if (in == NULL)
		return NULL;
	Polynom out = createPolynom(in->count);
	printf("FFT for omega = %i mod %i\n", omega, mod);
	for (i = 0; i < in->count; i++) {
		out->data[i] = applyMod(in, uiPowMod(omega, i, mod), mod);
	}
	return out;
}

void usage(char *programName) {
	printf("[%s] [mod] [omega] [list]\n", programName);
}

int main(int argc, char **argv) {
	Polynom input, output;
	int i, omega, mod;
	if (argc <= 3) {
		usage(argv[0]);
		exit(-1);
	}
	input = createPolynom(argc - 3);
	for (i = 0; i < argc - 3; i++) {
		input->data[i] = atoi(argv[i+3]);
	}
	omega = atoi(argv[2]);
	mod = atoi(argv[1]);
	displayPolynom(input);
	output = FFT(input, omega, mod);
	displayPolynom(output);
	return 0;
}