/*****************************************************************************************************************
									Sequential Leader Algorithm

	Author: Pramod Lakshmi Narasimha
			Image Processing and Neural Networks Lab,
			Electrical Engineering Department,
			University of Texas at Arlington.

****************************************************************************************************************/

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

extern double T = 0.0, E = 0.0;

struct pattern
{
	double *x;
	int Membership;
	struct pattern *next;
};

struct Clust
{
	struct pattern *Clust_Pattern, *Clust_Start_Pattern, *Clust_Prev_Pattern;
	double *mean;
	int Num_vec, ClassId;
	struct Clust *next;
}*Start_Clust, *Pres_Clust, *Prev_Clust;

void SL_Clustering(char *Infile, int N)
{
	FILE *fpIn;
	int Nv, K, minIndex, k, i;
	double *x, dist, min_dist, *mean;

	double Distance(double *, double *, int);
	double Error(int);

	x = (double *) calloc(N, sizeof(double));
	mean = (double *) calloc(N, sizeof(double));


// Calculation of Threshold.

	fpIn = fopen(Infile, "r");

	if(fpIn == NULL)
	{
		perror(Infile);
		exit(1);
	}

	Nv = 0;

	while(!feof(fpIn))
	{
		Nv++;

		for(i = 0; i < N; i++)
		{
			fscanf(fpIn, "%lf", &x[i]);
			mean[i] += x[i];
		}
	}

	Nv--;

	for(i = 0; i < N; i++)
	{
		mean[i] /= Nv;
	}

	rewind(fpIn);

	while(!feof(fpIn))
	{
		for(i = 0; i < N; i++)
			fscanf(fpIn, "%lf", &x[i]);

		T += sqrt(Distance(x, mean, N)) / Nv;
	}

	fclose(fpIn);

	printf("Threshold = %lf\n", T);

	Pres_Clust = (struct Clust *) malloc(sizeof(struct Clust));
	Pres_Clust->Clust_Pattern = (struct pattern *) malloc(sizeof(struct pattern));

	Start_Clust = Pres_Clust;

	Start_Clust->Clust_Start_Pattern = Pres_Clust->Clust_Pattern;
	Pres_Clust->Clust_Pattern->next = NULL;

	Pres_Clust->Clust_Pattern->x = (double *) calloc(N, sizeof(double));
	Pres_Clust->mean = (double *) calloc(N, sizeof(double));
	Pres_Clust->next = NULL;
	Pres_Clust->Num_vec = 1;
	Pres_Clust->Clust_Pattern->Membership = 1;
	Pres_Clust->ClassId = 1;

	K = 0;

	fpIn = fopen(Infile, "r");

	if(fpIn == NULL)
	{
		perror(Infile);
		exit(0);
	}

	for(i = 0; i < N; i++)
	{
		fscanf(fpIn, "%lf", &Pres_Clust->Clust_Pattern->x[i]);
		Pres_Clust->mean[i] = Pres_Clust->Clust_Pattern->x[i];
	}

	while(!feof(fpIn))
	{
		for(i = 0; i < N; i++)
			fscanf(fpIn, "%lf", &x[i]);

		min_dist = Distance(x, Start_Clust->mean, N);
		minIndex = 1;

		for(Pres_Clust = Start_Clust, k = 1; Pres_Clust->next != NULL; Pres_Clust = Pres_Clust->next, k++)
		{
			dist = Distance(x, Pres_Clust->mean, N);

			if(dist < min_dist)
			{
				min_dist = dist;
				minIndex = k;
			}
		}

		dist = Distance(x, Pres_Clust->mean, N);

		if(dist < min_dist)
		{
			min_dist = dist;
			minIndex = k;
		}

		if(min_dist <= T)
		{
			for(Pres_Clust = Start_Clust, k = 1; minIndex > k; Pres_Clust = Pres_Clust->next, k++);
			Pres_Clust->Num_vec ++;
			Pres_Clust->ClassId = k;
			for(Pres_Clust->Clust_Pattern = Pres_Clust->Clust_Start_Pattern; Pres_Clust->Clust_Pattern->next != NULL; Pres_Clust->Clust_Pattern = Pres_Clust->Clust_Pattern->next);
			Pres_Clust->Clust_Prev_Pattern = Pres_Clust->Clust_Pattern;
			Pres_Clust->Clust_Pattern = (struct pattern *) malloc(sizeof(struct pattern));
			Pres_Clust->Clust_Prev_Pattern->next = Pres_Clust->Clust_Pattern;
			Pres_Clust->Clust_Pattern->x = (double *) calloc(N, sizeof(double));
			Pres_Clust->Clust_Pattern->next = NULL;

			for(i = 0; i < N; i++)
				Pres_Clust->Clust_Pattern->x[i] = x[i];

			Pres_Clust->Clust_Pattern->Membership = k;
		}
		else
		{
			for(Pres_Clust = Start_Clust, k = 1; Pres_Clust->next != NULL; Pres_Clust = Pres_Clust->next, k++);

			Prev_Clust = Pres_Clust;
			Pres_Clust = (struct Clust *) malloc(sizeof(struct Clust));
			Prev_Clust->next = Pres_Clust;
			Pres_Clust->Clust_Pattern = (struct pattern *) malloc(sizeof(struct pattern));

			Pres_Clust->Clust_Start_Pattern = Pres_Clust->Clust_Pattern;
			Pres_Clust->Clust_Pattern->next = NULL;

			Pres_Clust->Clust_Pattern->x = (double *) calloc(N, sizeof(double));
			Pres_Clust->mean = (double *) calloc(N, sizeof(double));
			Pres_Clust->next = NULL;
			Pres_Clust->Num_vec = 1;
			Pres_Clust->ClassId = k + 1;
			Pres_Clust->Clust_Pattern->Membership = k + 1;

			for(i = 0; i < N; i++)
			{
				Pres_Clust->Clust_Pattern->x[i] = x[i];
				Pres_Clust->mean[i] = x[i];
			}
		}
	}

	fclose(fpIn);

	E = Error(N);

	printf("Error for SL = %lf\n", E);
}

// Distance() This Function returns Euclidean Distance between the two vectors(x and mean).

double Distance(double *x, double *mean, int N)
{
	int i;
	double dist = 0.0;

	for(i = 0; i < N; i++)
		dist += (x[i] - mean[i]) * (x[i] - mean[i]);

	return dist;
}

// Error() This Function returns Error value after the clustering.

double Error(int N)
{
	double E = 0.0;

	for(Pres_Clust = Start_Clust; Pres_Clust->next != NULL; Pres_Clust = Pres_Clust->next)
	{
		if(Pres_Clust->Num_vec != 0)
		{
			for(Pres_Clust->Clust_Pattern = Pres_Clust->Clust_Start_Pattern; Pres_Clust->Clust_Pattern->next != NULL; Pres_Clust->Clust_Pattern = Pres_Clust->Clust_Pattern->next)
			{
				E += Distance(Pres_Clust->Clust_Pattern->x, Pres_Clust->mean, N) / Pres_Clust->Num_vec;
			}

			E += Distance(Pres_Clust->Clust_Pattern->x, Pres_Clust->mean, N) / Pres_Clust->Num_vec;
		}
	}

	if(Pres_Clust->Num_vec != 0)
	{
		for(Pres_Clust->Clust_Pattern = Pres_Clust->Clust_Start_Pattern; Pres_Clust->Clust_Pattern->next != NULL; Pres_Clust->Clust_Pattern = Pres_Clust->Clust_Pattern->next)
		{
			E += Distance(Pres_Clust->Clust_Pattern->x, Pres_Clust->mean, N) / Pres_Clust->Num_vec;
		}

		E += Distance(Pres_Clust->Clust_Pattern->x, Pres_Clust->mean, N) / Pres_Clust->Num_vec;
	}

	return sqrt(E);
}
