#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <math.h>
#include <stdbool.h>

struct vecteur_s {
  double *v;
  int taille;
  int num_classe;
};
typedef struct vecteur_s vecteur;


struct noeud_s {
  vecteur *c;
  struct noeud_s *suivant;
};
typedef struct noeud_s noeud;

void printvect(vecteur *v) {
  printf("taille: %d\n", v->taille);
  printf("num_classe: %d\n", v->num_classe);
  for (int i = 0; i < v->taille; i++)
    printf("%f ", v->v[i]);
  printf("\n");
}

void printnoeud(noeud *n) {
  if (n == NULL) return;
  printvect(n->c);
  printf("\n");
  printnoeud(n->suivant);
}


void ajoutVecteur(vecteur *vec, noeud **tete) {
  noeud *n = malloc(sizeof(noeud));
  assert(n != NULL);
  n -> c = vec;
  n -> suivant = *tete;
  *tete =  n;
};

double delta(vecteur *di, vecteur *c) {
  double r = 0;
  for (int i = 0; i < di->taille; i++)
    r += fabs(di->v[i] - c->v[i]);
  return r;
};

double distmax(double dists[], int j, double theta) {
  for (int i = 0; i < j; i++)
    if (dists[i] <= theta) return false;
  return true;
};

int distmin(double dists[], int j) {
  int r = 0;
  for (int i = 0; i < j; i++)
    if (dists[i] < dists[r])
      r = i;
  return r;
}

void recalculCentre(vecteur *documents[],int nb_documents, noeud* centres, int l);

vecteur *copy(vecteur* v) {
  vecteur *r = malloc(sizeof(vecteur));
  r->taille = v->taille;
  r->v = malloc(r->taille * sizeof(double));
  for (int i = 0; i < r->taille; i++)
    r->v[i] = v->v[i];
  return r;
}

void printdist(double *d, int n) {
  for (int i = 0; i < n; i++)
    printf("%f ", d[i]);
  printf("\n");
};

noeud *algorithme1(vecteur *documents[], int nb_documents, double theta)
{
  noeud *classes = malloc(sizeof(noeud));
  classes -> c = copy(documents[0]);
  classes -> c -> num_classe = 1;
  classes -> suivant = NULL;
  int j = 1;
  for (int i = 2; i <= nb_documents; i++)
    {
      double *dists = malloc(j*sizeof(double));
      noeud *c = classes;
      for (int k = 1; k <= j; k++)
	{
	  dists[j-k] = delta(documents[i-1], c->c);
	  c = c -> suivant;
	}
      if (distmax(dists, j, theta))
	{
	  j = j+1;
	  ajoutVecteur(copy(documents[i-1]), &classes);
	  classes -> c -> num_classe = j;
	}
      else
	{
	  int l = distmin(dists, j);
	  documents[i-1]->num_classe = l;
	  recalculCentre(documents, nb_documents, centres, l);
	}
	free(dists);
    }
  return classes;
};



vecteur *initDocs() {
  vecteur *r = malloc(5*sizeof(vecteur));
  for (int i = 0; i < 5; i++)
    {
      r[i].taille = 3;
      r[i].v = malloc(3*sizeof(double));
    }
  r[0].v[0] = 1;   r[0].v[1] = 3;   r[0].v[2] = 3; 
  r[1].v[0] = 2;   r[1].v[1] = 1;   r[1].v[2] = 0; 
  r[2].v[0] = 0;   r[2].v[1] = 1;   r[2].v[2] = 0; 
  r[3].v[0] = 1;   r[3].v[1] = 3;   r[3].v[2] = 1; 
  r[4].v[0] = 1;   r[4].v[1] = 0;   r[4].v[2] = 1; 
  return r;
};


int main(int argc, char **argv) {
  vecteur *documents = initDocs();
  noeud *classes = algorithme1(documents, 5, 5);
  printnoeud(classes);
};