text: #include "lab1_sequential.h"
  #include <bits/stdc++.h>
  #include <malloc.h>
  #include <cmath>
  #include <stdlib.h>
  #include <stdio.h>
  
  using namespace std;
  void kmeans_sequential(int N, int K, int* data_points, int** data_point_cluster, int** centroids, int* num_iterations);
  
  vector<int> vect;
  
  struct Point{
      double x; //x coordinate
      double y; //y coordinate
      double z; //z coordinate
      int cluster; //cluster to which the point belongs
  };
  
  //helper function prototypes
  void mean_recompute(int K, int N, Point points[],Point centr[]);
  Point addtwo(Point a, Point b);
  double euclid(Point a, Point b);
  Point mean(Point arr[], int N);
  void assignclusters(Point points[], Point centr[], int K, int N);
  void putback(Point centr[],int K);
  
  //driver function
  void kmeans_sequential(int N, int K, int* data_points, int** data_point_cluster, float** centroids, int* num_iterations){
      Point points[N];
  
      //---------------------------
      int j=0;
      for (int i=0;  i<(3*N); i+=3){
          points[j].x  = data_points[i];
          points[j].y  = data_points[i+1];
          points[j].z  = data_points[i+2];
          j++;
      }
  
      //---------------------------
  
      //random centroid initialization. centroids are random points
      //center is the array of centroids containing their locations and cluster number as their index in this array
      srand(10);
      Point centr[K];
      for (int i = 0; i< K; i++){
          int random = rand()%N;//some random value
          centr[i] = points[random];
      }
  
      //---------------------------
  
      //array to keep a track of distances of a point from all centroids, to take the minimum out of them
      double distances[K];
      //computing distance of a point and assigning all
      for (int i=0; i<N; i++){
          for(int j=0; j<K ; j++){
              distances[j] = euclid(points[i], centr[j]);
          }
          int index = 0;
          for(int i = 1; i < K; i++){
              if(distances[i] < distances[index])
                  index = i;
          }
          points[i].cluster = index;
      }
  
      //---------------------------
  
      mean_recompute(K, N, points,centr);
      putback(centr, K);
  
      //---------------------------
  
      int iterations = 1;
      int count;
      do {
          mean_recompute(K, N, points,centr);
          putback(centr, K);
          //storing old values for convergence check
          int old[N];
          for (int i=0; i<N; i++){
              old[i] = points[i].cluster;
          }
          assignclusters(points, centr, K, N);
          iterations++;
          count = 0;
          for (int i=0; i<N; i++){
              if (old[i] == points[i].cluster)
                  count++;
          }
      } while(count!=N);
  
      //---------------------------
  
      *data_point_cluster= (int*) calloc(4*N, sizeof(int));
      *centroids = (float*) calloc(vect.size(), sizeof(float));
  
      int q = 0;
      for (int i = 0; i< 4*N; i+=4){
          data_point_cluster[0][i] = points[q].x;
          data_point_cluster[0][i+1] = points[q].y;
          data_point_cluster[0][i+2] = points[q].z;
          data_point_cluster[0][i+3] = points[q].cluster;
          q++;
      }
      for (int i = 0; i<vect.size(); i++){
          centroids[0][i] = vect[i];
      }
  
      * num_iterations = vect.size()/K -1 ;
  }
  
  //funtion to recompute the new centroids for each cluster
  //N is the total number of data points and K is the total number of clusters
  void mean_recompute(int K, int N, Point points[], Point centr[]){
      int count[K];
      Point sum[K];
      for(int i=0; i< N ; i++){
          count[points[i].cluster]++;
          sum[points[i].cluster] = addtwo(points[i],sum[points[i].cluster] );
      }
      for(int i=0; i< K ; i++){
          centr[i].x = sum[i].x/count[i];
          centr[i].y = sum[i].y/count[i];
          centr[i].z = sum[i].z/count[i];
      }
  }
  
  //assuming they are the same cluster
  Point addtwo(Point a, Point b){
      Point ans;
      ans.x = a.x + b.x;
      ans.y = a.y + b.y;
      ans.z = a.z + b.z;
      ans.cluster = a.cluster;
      return ans;
  }
  
  void assignclusters(Point points[], Point centr[],int K, int N){
      double distances[K];
      //computing distance of a point and assigning all the data points, a centroid/cluster value
      for (int i=0; i<N; i++)
      {
          for(int j=0; j<K ; j++){
              distances[j] = euclid(points[i], centr[j]);
          }
          int index = 0;
          for(int i = 1; i < K; i++)
          {
              if(distances[i] < distances[index])
                  index = i;
          }
          //assigning the minimum distance cluster, which is an index
          points[i].cluster = index;
      }
  }
  
  //function to calculate euclidea distance between two points
  double euclid(Point a, Point b){
      double x = a.x- b.x;
      double y = a.y- b.y;
      double z = a.z- b.z;
      double dist = sqrt(pow(x, 2) + pow(y, 2) + pow(z, 2));
      return dist;
  }
  
  void putback(Point centr[],int K){
      for (int i =0; i<K; i++) {
          vect.push_back(centr[i].x);
          vect.push_back(centr[i].y);
          vect.push_back(centr[i].z);
      }
  }
  