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

#define WIDTH 30
#define HEIGHT 10 

#define K 3
#define round(x) ((x)>=0?(long)((x)+0.5):(long)((x)-0.5))
#define min(X, Y)  ((X) < (Y) ? (X) : (Y))

int startx = 0;
int starty = 0;

struct list_elm {
  int x;
  int y;
  int len;
  struct list_elm* next;
};

struct pt {
  int x;
  int y;
};

struct list_elm* add_new_point(struct list_elm* head, MEVENT* event);
void drop_into_array(struct list_elm* head, int points_x[], int points_y[]);
void kmeans(struct pt centers[],struct list_elm* head);
void kmeans_with_pts(struct pt centers[], int k, int len, int points_x[], int points_y[]);
struct pt* find_centroid(int len, int points_x[], int points_y[]);
void display_points(int len, int points_x[], int points_y[]);
void print_menu(WINDOW *menu_win, int highlight);
void random_point_assign(struct pt center[], int k, int len, int points_x[], int points_y[]);
void group_points(struct pt centers[], int groupings[], 
		  int k, int len, int points_x[], int point_y[]);
double rate_cluster(struct pt centers[],int groupings[],
		    int k,int len,int points_x[],int points_y[]);
void make_new_centers(struct pt centers[], int groupings[],int k, 
		      int len, int points_x[], int points_y[]);
double dist(int x1, int y1, int x2, int y2);
int min_pt(struct pt centers[], int x, int y, int k); // find index of closet center
double cdf(double x, double m, double s);

int main(){
  WINDOW *menu_win;
  int highlight = 1;
  int choice = 0;
  int c;
  MEVENT event;
  // struct list_elm* curr;
  struct list_elm* head = NULL; 

  initscr();
  clear();
  noecho();
  cbreak();	/* Line buffering disabled. pass on everything */
  startx = (80 - WIDTH) / 2;
  starty = (24 - HEIGHT) / 2;
		
  menu_win = newwin(HEIGHT, WIDTH, starty, startx);
  keypad(menu_win, TRUE);
  mvprintw(0, 0, "Use the mouse to make points. Hit space to cluster points");
  refresh();
  curs_set(0);
  //print_menu(menu_win, highlight);
  wrefresh(menu_win);
  mousemask(ALL_MOUSE_EVENTS, NULL);
  while(1) {
    c = wgetch(menu_win);
    switch(c) {	
    case KEY_MOUSE:
      getmouse(&event);
      mvprintw(24,0,"Mouse at %d %d",event.x,event.y);
      mvprintw(event.y,event.x,"x");
			
      head = add_new_point(head,&event);

      refresh();
      break;
    case 32:
      clear();
      mvprintw(0, 0, "Use the mouse to make points. Hit space to cluster points");
      mvprintw(24,0,"Space pressed\n");

      refresh();
      if (head != NULL) {
	struct pt centers[K];
	kmeans(centers,head);
	head = NULL;
      }
      refresh();
				
      break;
    default:
      break;
    }
    //print_menu(menu_win, highlight);
    wrefresh(menu_win);
    if(c == 10)	/* User did a choice come out of the infinite loop */
      break;
  }	
  clrtoeol();
  refresh();
  endwin();
  return 0;
}

void kmeans(struct pt centers[],struct list_elm* head) {
  int len = head->len;
  int points_x[len];
  int points_y[len];

  drop_into_array(head,points_x,points_y);
  head = NULL;
  kmeans_with_pts(centers, K, len, points_x, points_y);
  display_points(len,points_x,points_y);

  start_color();
  use_default_colors();
  // assume_default_colors(-1,-1);
  init_pair(1, COLOR_RED, COLOR_WHITE);
  attron(COLOR_PAIR(1));
  
  int i=0;
  for (i=0; i<min(K,len);i++) {
    struct pt center = centers[i];
    mvprintw(center.y,center.x,"o");
  }

  attroff(COLOR_PAIR(1));
}

void kmeans_with_pts(struct pt centers[], int k, int len, int points_x[], int points_y[]) {
  int i=0;
  int groupings[len]; //array indexed with which cluster a point is in

  random_point_assign(centers,k,len,points_x,points_y);
  group_points(centers, groupings, k, len, points_x, points_y);
  
  while(i<30) {
    make_new_centers(centers,groupings,k,len,points_x,points_y);
    group_points(centers, groupings, k, len, points_x, points_y);
    i++;
  }
}

void random_point_assign(struct pt center[], int k, int len, int points_x[], int points_y[]) {
  int i=0; int rp;
  for (i=0; i<min(k,len); i++) {
    rp = rand()%(len-i);
    center[i].x = points_x[rp];
    center[i].y = points_y[rp];
    points_x[rp] = points_x[len-i-1];
    points_y[rp] = points_y[len-i-1];
    points_x[len-i-1] = center[i].x;
    points_y[len-i-1] = center[i].y;
  }
}

void make_new_centers(struct pt centers[], int groupings[],int k, 
		      int len, int points_x[], int points_y[]) {
  int i=0;
  int gr_len[k];
  for(i=0;i<min(k,len);i++) {
    centers[i].x = 0;
    centers[i].y = 0;
    gr_len[i] = 0;
  }
  for(i=0;i<len;i++) {
    centers[groupings[i]].x += points_x[i];
    centers[groupings[i]].y += points_y[i];
    gr_len[groupings[i]]++;
  }
  for(i=0;i<min(k,len);i++) {
    centers[i].x = round(centers[i].x / gr_len[i]);
    centers[i].y = round(centers[i].y / gr_len[i]);
  }
}

double cdf(double x, double m, double s) {
  return 0.5*(1+erf((x-m)/(s*sqrt(2.0))));
}

double anderson_darling(double x[], int n) {
  return 0.0;
}

double rate_cluster(struct pt centers[],int groupings[],
		    int k,int len,int points_x[],int points_y[]) {
  double sum = 0;
  int i=0; struct pt* c;
  for (i=0;i<len;i++) {
    c = &(centers[groupings[i]]);
    sum += dist(c->x,c->y,points_x[i],points_y[i]);
  }
  return sum;
}

void group_points(struct pt centers[], int groupings[], 
		  int k, int len, int points_x[], int points_y[]) {
  int i=0;
  for(i=0; i<len; i++) {
    groupings[i] = min_pt(centers,points_x[i],points_y[i],min(k,len));
  }
}

int min_pt(struct pt centers[], int x, int y, int k) {
  int best = 0;
  int i=0;
  for (i=1; i<k; i++) {
    if (dist(x,y,centers[i].x,centers[i].y) <
	dist(x,y,centers[best].x,centers[best].y))
      best = i;
  }
  return best;
}

double dist(int x1, int y1, int x2, int y2) {
  return sqrt((x2 - x1)*(x2-x1) + (y2 - y1)*(y2 - y1));
}

struct list_elm* add_new_point(struct list_elm* head, MEVENT* event) {
  struct list_elm* curr = malloc(sizeof(struct list_elm));
  if (head == NULL) {
    curr->len = 1;
  } else {
    curr->len = head->len + 1;
  }
  curr->x = event->x;
  curr->y = event->y;
  curr->next = head;
  return curr;
}

void drop_into_array(struct list_elm* head, int points_x[], int points_y[]) {
  struct list_elm* curr;
  while (head != NULL) {
    points_x[head->len - 1] = head->x;
    points_y[head->len - 1] = head->y;
    curr = head->next;
    free(head); head = curr;
  }
}

struct pt* find_centroid(int len, int points_x[], int points_y[]) {
  struct pt* center = malloc(sizeof(struct pt));
  int i=0;
  center->x=0;
  center->y=0;
  for(i=0;i<len;i++) {
    mvprintw(points_y[i],points_x[i],"x"); // reprint points
    center->x += points_x[i];
    center->y += points_y[i];
  } 
  center->x = round(center->x / len);
  center->y = round(center->y / len);
  return center;
}

void display_points(int len, int points_x[], int points_y[]) {
  int i=0;
  for(i=0;i<len;i++) {
    mvprintw(points_y[i],points_x[i],"x"); // reprint points
  }
}

void print_menu(WINDOW *menu_win, int highlight)
{
  int x, y, i;	

  x = 2;
  y = 2;
  box(menu_win, 0, 0);
  wrefresh(menu_win);
}