Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Pavel Valenta
- * xvalen33
- * 2.12.2022
- * IZP Project 2 - Data Structures
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include <assert.h>
- #include <math.h> // sqrtf
- #include <limits.h> // INT_MAX
- #include <string.h>
- #include <errno.h>
- /*****************************************************************
- * 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 objt_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'
- *
- */
- void init_cluster(struct cluster_t *c, int cap)
- {
- assert(c != NULL);
- assert(cap >= 0);
- if (cap == 0)
- c->obj = NULL;
- else
- {
- size_t size = sizeof(struct obj_t) * cap;
- c->obj = malloc(size);
- assert(c->obj != NULL);
- }
- c->capacity = cap;
- c->size = 0;
- }
- void clear_cluster(struct cluster_t *c)
- {
- assert(c != NULL);
- if (c->obj != NULL)
- free(c->obj);
- c->obj = NULL;
- c->capacity = 0;
- c->size = 0;
- }
- /// Chunk of cluster objects. Value recommended for reallocation.
- const int CLUSTER_CHUNK = 10;
- struct cluster_t *resize_cluster(struct cluster_t *c, int new_cap)
- {
- 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 = arr;
- c->capacity = new_cap;
- return c;
- }
- void append_cluster(struct cluster_t *c, struct obj_t obj)
- {
- assert(c != NULL);
- //expand cluster, if there is not enough space
- if (c->size+1 > c->capacity)
- {
- resize_cluster(c, c->capacity > 0 ? c->capacity * 2 : 1);
- }
- c->obj[c->size] = obj;
- c->size += 1;
- }
- void sort_cluster(struct cluster_t *c);
- 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++)
- {
- append_cluster(c1, c2->obj[i]);
- }
- sort_cluster(c1);
- }
- int remove_cluster(struct cluster_t *carr, int narr, int idx)
- {
- assert(idx < narr);
- assert(narr > 0);
- //first remove cluster on index idx
- clear_cluster(&(carr[idx]));
- //than move other items in array
- for (int i = idx; i < narr-1; i++)
- {
- carr[i] = carr[i+1];
- }
- //return array_size - 1
- return narr-1;
- }
- float obj_distance(struct obj_t *o1, struct obj_t *o2)
- {
- assert(o1 != NULL);
- assert(o2 != NULL);
- return sqrtf((o1->x - o2->x)*(o1->x - o2->x) + (o1->y - o2->y)*(o1->y - o2->y));
- }
- 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);
- //first set minimum value to compare with
- float min = 10000;
- //two for cycles, for two clusters
- for (int i = 0; i < c1->size; i++) {
- for (int j = 0; j < c2->size; j++)
- {
- //calculate distance and save it to tmp
- float tmp = (obj_distance(&(c1->obj[i]), &(c2->obj[j])));
- //compare with min value, if tmp is smaller, replace it
- if (tmp < min)
- min = tmp;
- }
- }
- //return final minimum
- return min;
- }
- void find_neighbours(struct cluster_t *carr, int narr, int *c1, int *c2)
- {
- assert(narr > 0);
- assert(carr != NULL);
- //if there is only one value, no need to calculate
- if (narr == 1)
- {
- *c1 = 0;
- *c2 = 0;
- }
- //if there are two items, no need to calculate
- else if (narr == 2)
- {
- *c1 = 0;
- *c2 = 1;
- }
- else
- {
- float min = 9999;
- //same as previous function
- for (int i = 0; i < narr; i++)
- {
- for (int j = i+1; j < narr; j++)
- {
- float tmp = (cluster_distance(&(carr[i]), &(carr[j])));
- if (tmp < min)
- {
- //when found, set indexes
- min = tmp;
- *c1 = i;
- *c2 = j;
- }
- }
- }
- }
- }
- static int obj_sort_compar(const void *a, const void *b)
- {
- const struct obj_t *o1 = a;
- const struct obj_t *o2 = b;
- if (o1->id < o2->id) return -1;
- if (o1->id > o2->id) return 1;
- return 0;
- }
- void sort_cluster(struct cluster_t *c)
- {
- qsort(c->obj, c->size, sizeof(struct obj_t), &obj_sort_compar);
- }
- void print_cluster(struct cluster_t *c)
- {
- 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');
- }
- int load_clusters(char *filename, struct cluster_t **arr)
- {
- assert(arr != NULL);
- FILE * file;
- //First, open the file and check if it is OK
- if ((file = fopen(filename, "r")) == NULL)
- {
- fprintf(stderr, "File could not be opened\n");
- //if opening failed, we need to close it and clean memory
- *arr = NULL;
- fclose(file);
- return -1;
- }
- // First line - count=<number>
- //two buffers with purpose to store particular lines
- char buff1[7];
- char buff2[101];
- int var;
- //Number of clusters which will be needed to load
- int counter = 0;
- //number of controlled line of code
- int line_variable = 1;
- //fgets function used to read each line with specific amount of bytes
- if (fgets(buff1, 7, file) == NULL)
- {
- fprintf(stderr, "Error during file reading\n");
- *arr = NULL;
- return -1;
- }
- if (strcmp(buff1, "count=\0") != 0)
- {
- fprintf(stderr, "First line has to contain: count=<number>\n");
- *arr = NULL;
- return -1;
- }
- if (fgets(buff2, 101, file) == NULL)
- {
- fprintf(stderr, "Error during file reading - missing value\n");
- *arr = NULL;
- return -1;
- }
- var = sscanf(buff2, "%d", &counter);
- if (var < 1 || var == EOF )
- {
- fprintf(stderr, "Error during file reading - wrong value\n");
- *arr = NULL;
- return -1;
- }
- if (counter <= 0)
- {
- fprintf(stderr, "NUmber of object must be greater than zero\n");
- *arr = NULL;
- return -1;
- }
- //contiunue with reading lines
- for (int i = 0; i < counter; i++)
- {
- line_variable++;
- char buff3[304];
- int helper_var;
- int new_id;
- int axe_x;
- int axe_y;
- if (fgets(buff3, 304, file) == NULL)
- {
- fprintf(stderr, "Error reading file\n");
- *arr = NULL;
- return -1;
- }
- helper_var = sscanf(buff3, "%d %d %d", &new_id, &axe_x, &axe_y);
- if (helper_var < 3 ||helper_var == EOF )
- {
- fprintf(stderr, "Error reading line\n");
- *arr = NULL;
- return -1;
- }
- if (axe_x < 0 || axe_x > 1000 || axe_y < 0 || axe_y > 1000)
- {
- fprintf(stderr, "Coordinates values out of range\n");
- *arr = NULL;
- return -1;
- }
- }
- //continue reading file
- rewind(file);
- struct cluster_t *clusters = malloc(sizeof(struct cluster_t)*counter);
- while (1)
- {
- int help = fgetc(file);
- if (help == '\n')
- break;
- }
- // reading another objects
- for (int i = 0; i < counter; i++)
- {
- char buffer[108];
- int new_id;
- int axe_x;
- int axe_y;
- fgets(buffer, 108, file);
- sscanf(buffer, "%d %d %d", &new_id, &axe_x, &axe_y);
- struct obj_t new_obj;
- new_obj.id = new_id;
- new_obj.x = axe_x;
- new_obj.y = axe_y;
- struct cluster_t c;
- init_cluster(&c, 1);
- append_cluster(&c, new_obj);
- clusters[i] = c;
- }
- fclose(file);
- *arr = &clusters[0];
- return counter;
- }
- 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[])
- {
- //cluster aray
- struct cluster_t *clusters;
- //number of clusters
- int cluster_count;
- //number of wanted clusters
- int cluster_req; //
- //processing and checking arguments
- if (argc < 2)
- {
- fprintf(stderr, "Missing arguments\n");
- return 1;
- }
- if (argc > 2)
- {
- long int test_var;
- //strtol function is safer than atoi - due to overflow risks
- test_var = strtol(argv[2], NULL, 10);
- if (errno == ERANGE || test_var > INT_MAX || test_var <= 0 )
- {
- fprintf(stderr, "Invalid cluster_count or out of range\n");
- return 1;
- }
- cluster_req = (int)test_var;
- }
- else
- {
- cluster_req = 1;
- }
- //using load_cluster function to read and load from file
- cluster_count = load_clusters(argv[1], &clusters);
- // if cluster_count is lower than zero, something failed
- if (cluster_count < 0)
- return 1;
- if (cluster_count < cluster_req)
- {
- fprintf(stderr, "Not enough read objects\n");
- return 1;
- }
- //repeat until this condition won´t match
- while(cluster_count != cluster_req)
- {
- int first;
- int second;
- find_neighbours(clusters, cluster_count, &first, &second);
- merge_clusters(&(clusters[first]), &(clusters[second]));
- cluster_count = remove_cluster(clusters, cluster_count, second);
- }
- //print clusters
- print_clusters(clusters, cluster_count);
- //and free memory
- free(clusters);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement