/*
 * kmeans.C
 *
 * For Example 1 in Chapter 9
 *
 */

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

main()
{
  int i, j, k;
  
  double dmin, dx;
  double x[9][3], mean[3][3], sum[3][3];
  int cluster[9], count[9], color;
  int flips;

 
// initialize the seven patterns

  x[0][0] = -1.2; x[0][1] = 0.6; x[0][2] = 0.8;
  x[1][0] = 1.5; x[1][1] = 0.5; x[1][2] = 1.8;
  x[2][0] = 0.5; x[2][1] = -1.0; x[2][2] = 0.8;
  x[3][0] = -0.5; x[3][1] = 1.2; x[3][2] = 0.7;
  x[4][0] = 1.0; x[4][1] = 1.5; x[4][2] = -0.8;
  x[5][0] = -1.2; x[5][1] = 0.2; x[5][2] = 0.5;
  x[6][0] = 0.2; x[6][1] = 1.0; x[6][2] = 0.2;
  x[7][0] = -0.2; x[7][1] = -1.0; x[7][2] = 1.8;
  x[8][0] = 0.5; x[8][1] = -1.5; x[8][2] = 1.5;


// initialize three means

  mean[0][0] = -2.0; mean[0][1] = 0.0; mean[0][2] = 1.5;
  mean[1][0] = 1.0; mean[1][1] = 1.0; mean[1][2] = 1.0;
  mean[2][0] = -1.0; mean[2][1] = -1.0; mean[2][2] = 0.0;

// note the clusters won by each pattern

  for (i = 0; i<9; i++) cluster[i] = 0;

// until there is no change of clusters belonging to each pattern, continue

  flips = 9;
  while (flips>0) {

    flips = 0;

    for (j = 0; j < 3; j++) {
      count[j] = 0; 
      for (i = 0; i < 3; i++) 
	sum[j][i] = 0.0;
    }
    
    for (i = 0; i < 9; i++) {
      
      dmin = 100000000.0; color = cluster[i];
      for (j = 0; j < 3; j++) {
	dx = 0.0;
	for (k = 0; k < 3; k++) 
	  dx +=  (x[i][k] - mean[j][k])*(x[i][k] - mean[j][k]);
	fprintf(stdout, "%5.2f ", dx);
	if (dx < dmin) {
	  color = j;
	  dmin = dx;
	}
      }
      fprintf(stdout, "  * %d *\n", color);

      if (cluster[i] != color) {
	flips++;
        cluster[i] = color;
      }
      
      count[cluster[i]]++;

      for (j = 0; j < 3; j++) 
	sum[cluster[i]][j] += x[i][j];
    }
 
    for (i = 0; i < 3; i++) {
      fprintf(stderr,"(");
      for (j = 0; j < 3; j++) {
	mean[i][j] = sum[i][j]/count[i];
	fprintf(stderr, "%5.2f ", mean[i][j]);
      }
      fprintf(stderr,")  ");
    }

    fprintf(stderr, "\n **%d** \n", flips);
  }

}