proj3.c

/**
 * Kostra programu pro 3. projekt IZP 2018/19
 *
 * Jednoducha shlukova analyza: 2D nejblizsi soused.
 * Single linkage
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h> // sqrtf
#include <limits.h> // INT_MAX

/*****************************************************************
 * Ladici makra. Vypnout jejich efekt lze definici makra
 * NDEBUG, napr.:
 *   a) pri prekladu argumentem prekladaci -DNDEBUG
 *   b) v souboru (na radek pred #include <assert.h>
 *      #define NDEBUG
 */
#ifdef NDEBUG
#define debug(s)
#define dfmt(s, ...)
#define dint(i)
#define dfloat(f)
#else

// vypise ladici retezec
#define debug(s) printf("- %s\n", s)

// vypise formatovany ladici vystup - pouziti podobne jako printf
#define dfmt(s, ...) printf(" - "__FILE__":%u: "s"\n",__LINE__,__VA_ARGS__)

// vypise ladici informaci o promenne - pouziti dint(identifikator_promenne)
#define dint(i) printf(" - " __FILE__ ":%u: " #i " = %d\n", __LINE__, i)

// vypise ladici informaci o promenne typu float - pouziti
// dfloat(identifikator_promenne)
#define dfloat(f) printf(" - " __FILE__ ":%u: " #f " = %g\n", __LINE__, f)

#endif

/*****************************************************************
 * Deklarace potrebnych datovych typu:
 *
 * TYTO DEKLARACE NEMENTE
 *
 *   struct obj_t - struktura objektu: identifikator a souradnice
 *   struct cluster_t - shluk objektu:
 *      pocet objektu ve shluku,
 *      kapacita shluku (pocet objektu, pro ktere je rezervovano
 *          misto v poli),
 *      ukazatel na pole shluku.
 */

struct obj_t {
    int id;
    float x;
    float y;
};

struct cluster_t {
    int size;
    int capacity;
    struct obj_t *obj;
};

/*****************************************************************
 * Deklarace potrebnych funkci.
 *
 * PROTOTYPY FUNKCI NEMENTE
 *
 * IMPLEMENTUJTE POUZE FUNKCE NA MISTECH OZNACENYCH 'TODO'
 *
 */

/*
 Inicializace shluku 'c'. Alokuje pamet pro cap objektu (kapacitu).
 Ukazatel NULL u pole objektu znamena kapacitu 0.
*/
void init_cluster(struct cluster_t *c, int cap)
{
    assert(c != NULL);
    assert(cap >= 0);

    c->capacity = cap;
    if(cap == 0){
      c->obj = NULL;
      exit(0);
    }
  c->obj = malloc(cap * sizeof(struct obj_t));
}

/*
 Odstraneni vsech objektu shluku a inicializace na prazdny shluk.
 */
void clear_cluster(struct cluster_t *c)
{
    free(c->obj);
    c->size = 0;
    c->capacity = 0;
}

/// Chunk of cluster objects. Value recommended for reallocation.
const int CLUSTER_CHUNK = 10;

/*
 Zmena kapacity shluku 'c' na kapacitu 'new_cap'.
 */
struct cluster_t *resize_cluster(struct cluster_t *c, int new_cap)
{
    // TUTO FUNKCI NEMENTE
    assert(c);
    assert(c->capacity >= 0);
    assert(new_cap >= 0);

    if (c->capacity >= new_cap)
        return c;

    size_t size = sizeof(struct obj_t) * new_cap;

    void *arr = realloc(c->obj, size);
    if (arr == NULL)
        return NULL;

    c->obj = (struct obj_t*)arr;
    c->capacity = new_cap;
    return c;
}

/*
 Prida objekt 'obj' na konec shluku 'c'. Rozsiri shluk, pokud se do nej objekt
 nevejde.
 */
void append_cluster(struct cluster_t *c, struct obj_t obj)
{
    if (c->size == c->capacity){
      resize_cluster(c, c->capacity + CLUSTER_CHUNK);
      if (resize_cluster(c, c->capacity + CLUSTER_CHUNK) == NULL)fprintf(stderr,"ERROR\n");
    }
    c->obj[c->size] = obj;
    c->size += 1;
}

/*
 Seradi objekty ve shluku 'c' vzestupne podle jejich identifikacniho cisla.
 */
void sort_cluster(struct cluster_t *c);

/*
 Do shluku 'c1' prida objekty 'c2'. Shluk 'c1' bude v pripade nutnosti rozsiren.
 Objekty ve shluku 'c1' budou serazeny vzestupne podle identifikacniho cisla.
 Shluk 'c2' bude nezmenen.
 */
void merge_clusters(struct cluster_t *c1, struct cluster_t *c2)
{
    assert(c1 != NULL);
    assert(c2 != NULL);

    for(int i = 0; i<c2->size; i++){
      if (c1->size == c1->capacity){
        resize_cluster(c1, c1->capacity + CLUSTER_CHUNK);
      }
      append_cluster(c1, c2->obj[i]);
    }
  sort_cluster(c1);
}

/**********************************************************************/
/* Prace s polem shluku */

/*
 Odstrani shluk z pole shluku 'carr'. Pole shluku obsahuje 'narr' polozek
 (shluku). Shluk pro odstraneni se nachazi na indexu 'idx'. Funkce vraci novy
 pocet shluku v poli.
*/
int remove_cluster(struct cluster_t *carr, int narr, int idx)
{
    assert(idx < narr);
    assert(narr > 0);

    free(carr[idx].obj);
    for (; idx < narr - 1; idx++){
      carr[idx] = carr[idx+1];
    }
    return narr - 1;
}

/*
 Pocita Euklidovskou vzdalenost mezi dvema objekty.
 */
float obj_distance(struct obj_t *o1, struct obj_t *o2)
{
    assert(o1 != NULL);
    assert(o2 != NULL);

    double d = sqrt((o1->x - o2->x)*(o1->x - o2->x) + (o1->y - o2->y)*(o1->y - o2->y));
    return d;
}

/*
 Pocita vzdalenost dvou shluku.
*/
float cluster_distance(struct cluster_t *c1, struct cluster_t *c2)
{
    assert(c1 != NULL);
    assert(c1->size > 0);
    assert(c2 != NULL);
    assert(c2->size > 0);

    float MinDist = obj_distance(&c1->obj[0], &c2->obj[0]);
    for(int i = 0; i < c1->size; i++){
      for(int j = 0; j < c2->size; j++){
        if (obj_distance(&c1->obj[i], &c2->obj[j]) < MinDist) MinDist = obj_distance(&c1->obj[i], &c2->obj[j]);
      }
    }
  return MinDist;
}

/*
 Funkce najde dva nejblizsi shluky. V poli shluku 'carr' o velikosti 'narr'
 hleda dva nejblizsi shluky. Nalezene shluky identifikuje jejich indexy v poli
 'carr'. Funkce nalezene shluky (indexy do pole 'carr') uklada do pameti na
 adresu 'c1' resp. 'c2'.
*/
void find_neighbours(struct cluster_t *carr, int narr, int *c1, int *c2)
{
  assert(narr > 0);

  float temp = 0;
  float dist = INFINITY;
  for(int i = 0;i<narr;i++)
  {
   for (int j = 0;j<narr;j++)
   {
    if (i != j)
    {
     temp = cluster_distance(&carr[i], &carr[j]);
     if (temp<dist)
     {
      dist = temp;
      *c1 = i;
      *c2 = j;
     }
    }
   }
  }
}

// pomocna funkce pro razeni shluku
static int obj_sort_compar(const void *a, const void *b)
{
    // TUTO FUNKCI NEMENTE
    const struct obj_t *o1 = (const struct obj_t *)a;
    const struct obj_t *o2 = (const struct obj_t *)b;
    if (o1->id < o2->id) return -1;
    if (o1->id > o2->id) return 1;
    return 0;
}

/*
 Razeni objektu ve shluku vzestupne podle jejich identifikatoru.
*/
void sort_cluster(struct cluster_t *c)
{
    // TUTO FUNKCI NEMENTE
    qsort(c->obj, c->size, sizeof(struct obj_t), &obj_sort_compar);
}

/*
 Tisk shluku 'c' na stdout.
*/
void print_cluster(struct cluster_t *c)
{
    // TUTO FUNKCI NEMENTE
    for (int i = 0; i < c->size; i++)
    {
        if (i) putchar(' ');
        printf("%d[%g,%g]", c->obj[i].id, c->obj[i].x, c->obj[i].y);
    }
    putchar('\n');
}

/*
 Ze souboru 'filename' nacte objekty. Pro kazdy objekt vytvori shluk a ulozi
 jej do pole shluku. Alokuje prostor pro pole vsech shluku a ukazatel na prvni
 polozku pole (ukalazatel na prvni shluk v alokovanem poli) ulozi do pameti,
 kam se odkazuje parametr 'arr'. Funkce vraci pocet nactenych objektu (shluku).
 V pripade nejake chyby uklada do pameti, kam se odkazuje 'arr', hodnotu NULL.
*/
int load_clusters(char *filename, struct cluster_t **arr)
{
  assert(arr != NULL);

  int load;
  int o_count;                     // pocet nactenych pocatecnich objektu
  int l_count = 0;                 // kontrola jedinecnosti ID
  char c;

  FILE *file = fopen(filename, "r");

  if (file == NULL){
   fprintf(stderr,"ERROR: Soubor %s se nepodarilo nacist\n", filename);
   exit(1);
  }

  fscanf(file,"count=%d",&o_count);

  if(o_count==0){
   fprintf(stderr,"ERROR: Nastala chyba pri otevirani souboru %s\n", filename);
   if(fclose(file)==EOF)fprintf(stderr,"ERROR: soubor se nepodarilo zavrit\n");
  exit(1);
  }

  *arr = (struct cluster_t *)(malloc(sizeof(struct cluster_t)*o_count));

  if(*arr == NULL){
   fprintf(stderr,"ERROR: Nezdarilo se alokovat pamet pro pole vsech shluku\n");
   if(fclose(file)==EOF)fprintf(stderr,"ERROR: soubor se nepodarilo zavrit\n");
   exit(1);
  }

  for (int i=0;i<o_count;i++){
   init_cluster(&(*arr)[i],1);
   (*arr)[i].size = 1;

   if((*arr)[i].obj == NULL){
    fprintf(stderr,"Chyba pri nacitani objektu\n");
    if(fclose(file)==EOF) fprintf(stderr,"ERROR: soubor se nepodarilo zavrit\n");
    for (i=0;i<l_count;i++) clear_cluster(&(*arr)[i]);
    free(*arr);
    exit(1);
   }

   load = fscanf(file, "%d %f %f",(&(*arr)[i].obj->id),(&(*arr)[i].obj->x),(&(*arr)[i].obj->y));

   if (load != 3){
    fprintf(stderr,"ERROR: Chybne zadane parametry objektu\n");
    if(fclose(file)==EOF)fprintf(stderr,"ERROR: soubor se nepodarilo zavrit\n");
    for (i=0;i<l_count;i++)clear_cluster(&(*arr)[i]);
    free(*arr);
    exit(1);
   }

   c=fgetc(file);

   if (c != '\n'){
    fprintf(stderr,"ERROR: Chybne zadane parametry objektu");
    if(fclose(file)==EOF)fprintf(stderr,"ERROR: soubor se nepodarilo zavrit\n");
    for (i=0;i<l_count;i++)clear_cluster(&(*arr)[i]);
    free(*arr);
    exit(1);
   }

   for (int j = 0;j<l_count;j++){

    if (((*arr)[i].obj->id == (*arr)[j].obj->id) && (j != i)){ // originalita ID
     fprintf(stderr,"ERROR: V souboru jsou dva objekty se shodnym ID\n");
     if(fclose(file)==EOF)fprintf(stderr,"ERROR: soubor se nepodarilo zavrit\n");
     for (i=0;i<l_count-1;i++)clear_cluster(&(*arr)[i]);
     free(*arr);
     exit(1);
    }

   }
  l_count++;
  }
  if(fclose(file) == EOF){
   fprintf(stderr,"ERROR: Nepodarilo se zavrit soubor\n");
   for (int i=0;i<l_count;i++)clear_cluster(&(*arr)[i]);
   free(*arr);
   exit(1);
  }
  return l_count;
}

/*
 Tisk pole shluku. Parametr 'carr' je ukazatel na prvni polozku (shluk).
 Tiskne se prvnich 'narr' shluku.
*/
void print_clusters(struct cluster_t *carr, int narr)
{
    printf("Clusters:\n");
    for (int i = 0; i < narr; i++){
        printf("cluster %d: ", i);
        print_cluster(&carr[i]);
    }
}

int main(int argc, char *argv[])
{
  struct cluster_t *clusters;

  int c_count;

  if (argc == 2){
   c_count = load_clusters(argv[1],&clusters);
   for (int i=c_count;i!=0;i--) merge_clusters(&clusters[i-1],&clusters[i]);
   print_clusters(clusters,1);
   for (int i=0;i<c_count;i++) clear_cluster(&clusters[i]);
   free(clusters);
  }

  if (argc == 3){
   int c1;
   int c2;
   c_count = load_clusters(argv[1],&clusters);
   double o_count = strtod(argv[2],NULL);
   while (c_count != o_count){
    find_neighbours(clusters,c_count,&c1,&c2);
    merge_clusters(&clusters[c1],&clusters[c2]);
    c_count = remove_cluster(clusters,c_count,c2);
   }
   print_clusters(clusters,c_count);
   for (int i=0; i<o_count; i++) clear_cluster(&(clusters[i]));
   free(clusters);
  }
  return 0;
}