izp2

/**
 * 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;
}