/*-------------------------------------------------------------------*/
/* mcluster.c        Mohammad Rezaei                                 */
/*                                                                   */
/* grid-based clustering of markers                                  */
/*                                                                   */
/* Version: 0.00                                                     */
/* Last updated : 16.6.2014                                          */
/*-------------------------------------------------------------------*/
#define ProgName        "mcluster"

#define pi 3.14159265358979323846

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <unistd.h>
#include <math.h>

typedef struct { 
  int    queryType;
  char   photo_info_filename[300];
  int    minX;
  int    maxX;
  int    minY;
  int    maxY;
  float  minLat;
  float  maxLat;
  float  minLon;
  float  maxLon;
  float  delta;
  int    cellH;
  int    cellW;
  int    nCells;
  int    minDist;
  int    nColumn;
  int    nRow;
  int    zoomLevel;
  int    reverseX;
  int    maxW;
  int    minX1; // corrected minX when there is vertical end line 
  int    maxX1; // corrected maxX
  int    W1;
  int    W2;
  int    dataSizeCode; // 0:1000, 1:10000, 2:100000, 3:1000000 objects
  int    N; // data size
  int    selected;
} PARAMS;

typedef struct { 
  int   nc; // number of clusters
  int   nCells;
  int   *n; // number of objects in clusters
  // representative in cartezian space
  int   *x;
  int   *y;
  // bounding box
  float *latMin;
  float *latMax;
  float *lonMin;
  float *lonMax;
  // photo filename of representative photo of cluster
  char  **filename;
  double   time; // time of clustering in sec
} GRIDCLUSTER;

typedef struct { 
  float   *lat; 
  float   *lon; 
  // photo filename
  char  **filename;
  char  **name; // name, title or description of an object
} DATA;

PARAMS parseInputArgs(int argc, char** argv)
{
  int c;
  PARAMS params;
  
  opterr = 0;
  
  while ((c = getopt (argc, argv, "t:w:h:d:a:b:p:q:z:r:n:e:f:u:v:s:")) != -1) {
    switch (c) {
	  case 't':
        params.queryType = atoi(optarg);
        break;
      case 'w':
        params.cellW = atoi(optarg);
        break;
      case 'h':
        params.cellH = atoi(optarg);
        break;
      case 'd':
        params.minDist = atoi(optarg);
        break;
      case 'a':
        params.minX = atoi(optarg);
        break;
      case 'b':
        params.maxX = atoi(optarg);
        break;
      case 'p':
        params.minY = atoi(optarg);
        break;
      case 'q':
        params.maxY = atoi(optarg);
        break; 
      case 'z':
        params.zoomLevel = atoi(optarg);
        break;
      case 'r':
        params.reverseX = atoi(optarg);
        break;
      case 'n':
        params.dataSizeCode = atoi(optarg);
        break; 
      case 'e': 
        params.minLat = atof(optarg);
        break; 
      case 'f':
        params.maxLat = atof(optarg);
        break; 
      case 'u':
        params.minLon = atof(optarg);
        break; 
      case 'v':
        params.maxLon = atof(optarg);
        break; 
      case 's':
        params.selected = atoi(optarg);
        break; 
      default:
        break;
    }
  }
  
  params.N = 0;
  // read data file of photos information
  switch ( params.dataSizeCode ) {
    case 0:
	  params.N = 1000;
      strcpy(params.photo_info_filename, "../markerClustering_test/t_photo_info_0.txt"); // 1000 objects
	  break;
	case 1:
	  params.N = 10000;
      strcpy(params.photo_info_filename, "../markerClustering_test/t_photo_info_1.txt"); // 10000 objects
	  break;
	case 2:
	  params.N = 100000;
      strcpy(params.photo_info_filename, "../markerClustering_test/t_photo_info_2.txt"); // 100000 objects
	  break;
	case 3:
	  params.N = 1000000;
      strcpy(params.photo_info_filename, "../markerClustering_test/t_photo_info_3.txt"); // 1000000 objects
	  break;
	default:
	  break;
  }
  
  params.delta = 0.001; // offset for lat and lon
  
  return params;
}

void getPointFromLatLng(float lat, float lon, int zoomLevel, int *x, int *y)
{
  int point[2];
  double offset, radius;
  double xx, yy;
  
  offset = 268435456;
  radius = 85445659.44705395;
  xx = round(offset + radius * lon * pi / 180);
  yy = round(offset - radius * log((1 + sin(lat * pi / 180)) / (1 - sin(lat * pi / 180))) / 2);
  xx = xx / pow(2,21);
  yy = yy / pow(2,21);
  
  xx = xx * pow(2, zoomLevel);
  yy = yy * pow(2, zoomLevel);
  xx = floor(xx);
  yy = floor(yy);
  
  *x = (int)xx;
  *y = (int)yy;
}

void convertDataToPixel(PARAMS params, float *lat, float *lon, int *x, int *y)
{
  int i;
  int xx, yy;
  
  for ( i = 0 ; i < params.N ; i++ ) {
    getPointFromLatLng(lat[i], lon[i], params.zoomLevel, &xx, &yy);
    
    if ( params.reverseX ) { // modify x when map view containd vertical border line
      if ( xx >= params.minX )
        xx -= params.minX;
      else if ( xx < params.maxX )
        xx += params.W1;
    }
    
    x[i] = xx;
    y[i] = yy;
  }
}

// finds the cell containing the point (x,y) in the grid, and returns cell number
int getCellNum(PARAMS params, int x, int y)
{
  int row, column, clusterNum;

  if ( x > params.maxX1 || x < params.minX1 || y > params.maxY || y < params.minY ) {
    // error
    return -1;
  }
  
  row = floor((y-params.minY)/params.cellH);
  column = floor((x-params.minX1)/params.cellW);
  
  row = row<0 ? 0:row;
  row = row>=params.nRow ? params.nRow - 1:row;
  column = column<0 ? 0:column;
  column = column>=params.nColumn ? params.nColumn - 1:column;
  
  clusterNum = row*params.nColumn + column;
  
  return clusterNum;
}

PARAMS boundCorrectionParameters(PARAMS params)
{
  params.maxW = 256*pow(2, params.zoomLevel);
  params.minX1 = params.minX;
  params.maxX1 = params.maxX;
  if ( params.reverseX ) { // when map ends and a new one appears after a vertical line
    params.minX1 = 0;
    params.W1 = params.maxW - params.minX;
    params.W2 = params.maxX;
    params.maxX1 = params.W1+params.W2;
  }
  
  return params;
}

void memAllocClustering(GRIDCLUSTER **C, int nCells)
{
  int i;
  
  (*C) = malloc(sizeof(GRIDCLUSTER));
  (*C)->n = malloc(sizeof(int)*nCells);
  (*C)->x = malloc(sizeof(int)*nCells);
  (*C)->y = malloc(sizeof(int)*nCells);
  (*C)->latMin = malloc(sizeof(float)*nCells);
  (*C)->latMax = malloc(sizeof(float)*nCells);
  (*C)->lonMin = malloc(sizeof(float)*nCells);
  (*C)->lonMax = malloc(sizeof(float)*nCells);
  
  (*C)->filename = malloc(nCells * sizeof(char*));
  for( i = 0 ; i < nCells ; i++ )
    (*C)->filename[i] = malloc((60 + 1) * sizeof(char));
}

void initCluster(GRIDCLUSTER *C, int i, float lat, float lon, char *filename)
{
  C->x[i] = 0; // center in pixel
  C->y[i] = 0; // center in pixel
  C->latMin[i] = lat;
  C->latMax[i] = lat;
  C->lonMin[i] = lon;
  C->lonMax[i] = lon;
  C->n[i] = 0; // number of objects in cluster
  strcpy(C->filename[i], filename);
}

void addObjectToCluster(GRIDCLUSTER *C, int i, int x, int y, float lat, float lon)
{
  C->n[i] += 1;
  C->x[i] += x;
  C->y[i] += y;

  // bounding box
  if ( lat < C->latMin[i] )
    C->latMin[i] = lat;
  if ( lat > C->latMax[i] )
    C->latMax[i] = lat;
  if ( lon < C->lonMin[i] )
    C->lonMin[i] = lon;
  if ( lon > C->lonMax[i] )
    C->lonMax[i] = lon;
}

// grid-based clustering in cartezian space
int gridBasedClustering(DATA *data, PARAMS params, GRIDCLUSTER **C)
{
  int *x, *y, *clusters_order;
  int nClusters, k, i;
  struct timeval tv;
  double timeClustering;
  
  gettimeofday(&tv, NULL);
  timeClustering = (double)tv.tv_sec + ((double)tv.tv_usec /1e6);
  
  x = malloc(sizeof(int)*params.N);
  y = malloc(sizeof(int)*params.N);

  params = boundCorrectionParameters(params);
  // conver data from (lat, lon) to cartezian space (x, y)
  convertDataToPixel(params, data->lat, data->lon, x, y);
  
  params.nRow = ceil((double)(params.maxY - params.minY)/params.cellH);
  params.nColumn = ceil((double)(params.maxX1 - params.minX1)/params.cellW);
  params.nCells = params.nRow*params.nColumn;
  
  clusters_order = malloc(sizeof(int)*params.nCells);
  memAllocClustering(C, params.nCells);
  (*C)->nCells = params.nCells;
  
  for ( i = 0 ; i < params.nCells ; i++ )
    clusters_order[i] = -1; // all empty first
    
  nClusters = 0;
  for ( i = 0 ; i < params.N ; i++ ) {
    k = getCellNum(params, x[i], y[i]);
    
    if ( clusters_order[k] == -1 ) {// found a new cluster
      clusters_order[k] = nClusters;
	  initCluster(*C, nClusters, data->lat[i], data->lon[i], data->filename[i]);
      nClusters++;
    }

	addObjectToCluster(*C, clusters_order[k], x[i], y[i], data->lat[i], data->lon[i]);
  }
  
  (*C)->nc = nClusters;
  
  // centers of clusters
  for ( i = 0 ; i < nClusters ; i++ ) {
    (*C)->x[i] /= (*C)->n[i];
    (*C)->y[i] /= (*C)->n[i];
  }
  
  free(x);
  free(y);
  free(clusters_order);
  
  gettimeofday(&tv, NULL);
  timeClustering = (double)tv.tv_sec + ((double)tv.tv_usec /1e6) - timeClustering;
  (*C)->time = timeClustering;
  
  return nClusters;
}

int readData(PARAMS params, DATA **data)
{
  int i;
  float lat, lon;
  char filename[300];
  char name[300];
  FILE *fp;
  
  (*data) = malloc(sizeof(DATA));
  
  (*data)->lat = malloc(sizeof(float)*params.N);
  (*data)->lon = malloc(sizeof(float)*params.N);
  
  (*data)->filename = malloc(params.N * sizeof(char*));
  for( i = 0 ; i < params.N ; i++ )
    (*data)->filename[i] = malloc((60 + 1) * sizeof(char));
	
  (*data)->name = malloc(params.N * sizeof(char*));
  for( i = 0 ; i < params.N ; i++ )
    (*data)->name[i] = malloc((60 + 1) * sizeof(char));

  fp = fopen(params.photo_info_filename, "r");
  
  for ( i = 0 ; i < params.N ; i++ ) {
    fscanf(fp, "%f\n", &lat);
    fscanf(fp, "%f\n", &lon);
    fscanf(fp, "%[^\n]s", &name);
    fscanf(fp, "%s\n", &filename);
    
    (*data)->lat[i] = lat;
    (*data)->lon[i] = lon;
    strcpy((*data)->filename[i], filename);
    strcpy((*data)->name[i], name);
  }  
  fclose(fp);
  
  return 0;
}

PARAMS findDataBounds(PARAMS params, DATA *data)
{
  int  i;
  FILE *fp;
  
  params.minLat = 90;
  params.maxLat = -90;
  params.minLon = 180;
  params.maxLon = -180;
  
  for ( i = 0 ; i < params.N ; i++ ) {
    if ( data->lat[i] < (params.minLat+params.delta) )
      params.minLat = data->lat[i];
    if ( data->lat[i] > (params.maxLat-params.delta) )
      params.maxLat = data->lat[i];
      
    if ( data->lon[i] < (params.minLon+params.delta) )
      params.minLon = data->lon[i];
    if ( data->lon[i] > (params.maxLon-params.delta) )
      params.maxLon = data->lon[i];
  }
  
  fp = fopen("../../temp1/dataBounds_info.txt", "w");
  fprintf(fp, "%f %f %f %f", params.maxLat, params.maxLon, params.minLat, params.minLon);
  fclose(fp);
  
  return params;
}

PARAMS spatialFiltering(PARAMS params, DATA *data)
{
  int i, j;
  j = 0;
  if ( !params.reverseX ) {
    for ( i = 0 ; i < params.N ; i++ )
      if ( data->lat[i]<=(params.maxLat+params.delta) && data->lat[i]>=(params.minLat-params.delta) && data->lon[i]<=(params.maxLon+params.delta) && data->lon[i]>=(params.minLon-params.delta) ) {
        data->lat[j] = data->lat[i];
	    data->lon[j] = data->lon[i];
	    data->filename[j] = data->filename[i];
        data->name[j] = data->name[i];
        j++;
      }
  } else {
      for ( i = 0 ; i < params.N ; i++ )
        if ( data->lat[i]<=(params.maxLat+params.delta) && data->lat[i]>=(params.minLat-params.delta) && ((data->lon[i]<=(params.maxLon+params.delta) && data->lon[i]>-180) || (data->lon[i]>=(params.minLon-params.delta) && data->lon[i]<180)) ) {
          data->lat[j] = data->lat[i];
          data->lon[j] = data->lon[i];
          data->filename[j] = data->filename[i];
          data->name[j] = data->name[i];
          j++;
        }
   }
 
  params.N = j;
  
  return params;
}

void writeSelectedObjectInfoToFile(PARAMS params, DATA *data)
{
  FILE *fp;
  fp = fopen("../../temp1/selectedPhoto_info.txt", "w");
  fprintf(fp, "%f&&%f&&%s&&%s", data->lat[params.selected], data->lon[params.selected], data->name[params.selected], data->filename[params.selected]);
  fclose(fp);
}

void writeClustersToFile(GRIDCLUSTER *C)
{
  int i;
  FILE *fp;
  
 // printf("c = %d \n",C->nc);

  fp = fopen("../../temp1/clusters_info.txt", "w");
    
  for ( i = 0 ; i < C->nc ; i++ )
    fprintf(fp, "%d %d %d %f %f %f %f %s\n", C->n[i], C->x[i], C->y[i], C->latMin[i], C->latMax[i], C->lonMin[i], C->lonMax[i], C->filename[i]);
  
  fprintf(fp, "%f", C->time); // time elapsed for clustering, write on the last line of text file
  
  fclose(fp);
}

void deleteData(DATA *data)
{
  free(data->lat);
  free(data->lon);
  free(data->filename);
  free(data->name); 
  free(data);
}

void deleteClustering(GRIDCLUSTER *C)
{
  free(C->n);
  free(C->x);
  free(C->y);
  free(C->latMin);
  free(C->latMax);
  free(C->lonMin);
  free(C->lonMax);
  free(C->filename);
  free(C);
}

int main(int argc, char* argv[])
{
  PARAMS params;
  GRIDCLUSTER *C = NULL;
  DATA        *data = NULL;

  params = parseInputArgs(argc, argv);
  readData(params, &data);
  
  // filter data for spatial query
  switch ( params.queryType ) {
    case 1: // finding data bounds
      params = findDataBounds(params, data); 
      break;
    case 2: // non-spatial filtering, grid-based clustering
      gridBasedClustering(data, params, &C);
      writeClustersToFile(C);
      break;
    case 3: // spatial filtering, grid-based clustering
      params = spatialFiltering(params, data);
      gridBasedClustering(data, params, &C);
      writeClustersToFile(C);
      break;
    case 4: // object info
      params = spatialFiltering(params, data); // objects in the target cell
      writeSelectedObjectInfoToFile(params, data);
      break;
    default:
      break;
  }
  
  if ( data )
    deleteData(data);
  if ( C )
    deleteClustering(C);
 
  return 0;
}  /* main() */