#include <float.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NOT_USED  0 // node which is currently not used
#define LEAF_NODE 1 // node which contains a leaf node 
#define A_MERGER  2 // node which contains a merged pair of previous root clusters 
#define MAX_LABEL_LEN 16

#define AVERAGE_LINKAGE  'a' // select average distance
#define CENTROID_LINKAGE 't' // select distance between cluster centroids 
#define COMPLETE_LINKAGE 'c' // select maximum distance 
#define SINGLE_LINKAGE   's' // select minimum distance 

#define alloc_mem(N, T) (T *) calloc(N, sizeof(T))
#define alloc_fail(M) fprintf(stderr,                                   \
                              "Failed to allocate memory for %s.\n", M)
#define read_fail(M) fprintf(stderr, "Failed to read %s from file.\n", M)
#define invalid_node(I) fprintf(stderr,                                 \
                                "Invalid cluster node at index %d.\n", I)

typedef struct cluster_s cluster_t;
typedef struct cluster_node_s ClusterNodeT;
typedef struct neighbour_s neighbour_t;
typedef struct item_s item_t;

float (*distance_fptr)(float **, const int *, const int *, int, int);

typedef struct coord_s {
        float x, y;
} coord_t;

struct cluster_s {
        int num_items; /* number of items that was clustered */
        int num_clusters; /* current number of root clusters */
        int num_nodes; /* number of leaf and merged clusters */
        ClusterNodeT *nodes; /* leaf and merged clusters */
        float **distances; /* distance between leaves */
};

struct cluster_node_s {
        int type; /* type of the cluster node */
        int is_root; /* true if cluster hasn't merged with another */
        int height; /* height of node from the bottom */
        coord_t centroid; /* centroid of this cluster */
        char *label; /* label of a leaf node */
        int *merged; /* indexes of root clusters merged */
        int num_items; /* number of leaf nodes inside new cluster */
        int *items; /* array of leaf nodes indices inside merged clusters */
        neighbour_t *neighbours; /* sorted linked list of distances to roots */
};

struct neighbour_s {
        int target; /* the index of cluster node representing neighbour */
        float distance; /* distance between the nodes */
        neighbour_t *next, *prev; /* linked list entries */
};

struct item_s {
        coord_t coord; /* coordinate of the input data point */
        char label[MAX_LABEL_LEN]; /* label of the input data point */
};

float euclidean_distance(const coord_t *a, const coord_t *b)
{
        return sqrt(pow(a->x - b->x, 2) + pow(a->y - b->y, 2));
}

void fill_euclidean_distances(float **matrix, int num_items,
                              const item_t items[])
{
        for (int i = 0; i < num_items; ++i)
                for (int j = 0; j < num_items; ++j) {
                        matrix[i][j] =
                                euclidean_distance(&(items[i].coord),
                                                   &(items[j].coord));
                        matrix[j][i] = matrix[i][j];
                }
}

float **generate_distance_matrix(int num_items, const item_t items[])
{
        float **matrix = alloc_mem(num_items, float *);
        if (matrix) {
                for (int i = 0; i < num_items; ++i) {
                        matrix[i] = alloc_mem(num_items, float);
                        if (!matrix[i]) {
                                alloc_fail("distance matrix row");
                                num_items = i;
                                for (i = 0; i < num_items; ++i)
                                        free(matrix[i]);
                                free(matrix);
                                matrix = NULL;
                                break;
                        }
                }
                if (matrix)
                        fill_euclidean_distances(matrix, num_items, items);
        } else
                alloc_fail("distance matrix");
        return matrix;
}

float single_linkage(float **distances, const int a[],
                     const int b[], int m, int n)
{
        float min = FLT_MAX, d;
        for (int i = 0; i < m; ++i)
                for (int j = 0; j < n; ++j) {
                        d = distances[a[i]][b[j]];
                        if (d < min)
                                min = d;
                }
        return min;
}

float complete_linkage(float **distances, const int a[],
                       const int b[], int m, int n)
{
        float d, max = 0.0 /* assuming distances are positive */;
        for (int i = 0; i < m; ++i)
                for (int j = 0; j < n; ++j) {
                        d = distances[a[i]][b[j]];
                        if (d > max)
                                max = d;
                }
        return max;
}

float average_linkage(float **distances, const int a[],
                      const int b[], int m, int n)
{
        float total = 0.0;
        for (int i = 0; i < m; ++i)
                for (int j = 0; j < n; ++j)
                        total += distances[a[i]][b[j]];
        return total / (m * n);
}

float centroid_linkage(float **distances, const int a[],
                       const int b[], int m, int n)
{
        return 0; /* empty function */
}

float get_distance(cluster_t *cluster, int index, int target)
{
        /* if both are leaves, just use the distances matrix */
        if (index < cluster->num_items && target < cluster->num_items)
                return cluster->distances[index][target];
        else {
                ClusterNodeT *a = &(cluster->nodes[index]);
                ClusterNodeT *b = &(cluster->nodes[target]);
                if (distance_fptr == centroid_linkage)
                        return euclidean_distance(&(a->centroid),
                                                  &(b->centroid));
                else return distance_fptr(cluster->distances,
                                          a->items, b->items,
                                          a->num_items, b->num_items);
        }
}

void free_neighbours(neighbour_t *node)
{
        neighbour_t *t;
        while (node) {
                t = node->next;
                free(node);
                node = t;
        }
}

void free_cluster_nodes(cluster_t *cluster)
{
        for (int i = 0; i < cluster->num_nodes; ++i) {
                ClusterNodeT *node = &(cluster->nodes[i]);
                if (node->label)
                        free(node->label);
                if (node->merged)
                        free(node->merged);
                if (node->items)
                        free(node->items);
                if (node->neighbours)
                        free_neighbours(node->neighbours);
        }
        free(cluster->nodes);
}

void FreeCluster(cluster_t * cluster)
{
        if (cluster) {
                if (cluster->nodes)
                        free_cluster_nodes(cluster);
                if (cluster->distances) {
                        for (int i = 0; i < cluster->num_items; ++i)
                                free(cluster->distances[i]);
                        free(cluster->distances);
                }
                free(cluster);
        }
}

void insert_before(neighbour_t *current, neighbour_t *neighbours,
                   ClusterNodeT *node)
{
        neighbours->next = current;
        if (current->prev) {
                current->prev->next = neighbours;
                neighbours->prev = current->prev;
        } else
                node->neighbours = neighbours;
        current->prev = neighbours;
}

void InsertAfter(neighbour_t *current, neighbour_t *neighbours)
{
        neighbours->prev = current;
        current->next = neighbours;
}

void insert_sorted(ClusterNodeT *node, neighbour_t *neighbours)
{
        neighbour_t *temp = node->neighbours;
        while (temp->next) {
                if (temp->distance >= neighbours->distance) {
                        insert_before(temp, neighbours, node);
                        return;
                }
                temp = temp->next;
        }
        if (neighbours->distance < temp->distance)
                insert_before(temp, neighbours, node);
        else
                InsertAfter(temp, neighbours);
}


neighbour_t *add_neighbour(cluster_t *cluster, int index, int target)
{
        neighbour_t *neighbour = alloc_mem(1, neighbour_t);
        if (neighbour) {
                neighbour->target = target;
                neighbour->distance = get_distance(cluster, index, target);
                ClusterNodeT *node = &(cluster->nodes[index]);
                if (node->neighbours)
                        insert_sorted(node, neighbour);
                else
                        node->neighbours = neighbour;
        } else
                alloc_fail("neighbour node");
        return neighbour;
}

cluster_t *update_neighbours(cluster_t *cluster, int index)
{
        ClusterNodeT *node = &(cluster->nodes[index]);
        if (node->type == NOT_USED) {
                invalid_node(index);
                cluster = NULL;
        } else {
                int root_clusters_seen = 1, target = index;
                while (root_clusters_seen < cluster->num_clusters) {
                        ClusterNodeT *temp = &(cluster->nodes[--target]);
                        if (temp->type == NOT_USED) {
                                invalid_node(index);
                                cluster = NULL;
                                break;
                        }
                        if (temp->is_root) {
                                ++root_clusters_seen;
                                add_neighbour(cluster, index, target);
                        }
                }
        }
        return cluster;
}

#define init_leaf(cluster, node, item, len)             \
        do {                                            \
                strncpy(node->label, item->label, len); \
                node->centroid = item->coord;           \
                node->type = LEAF_NODE;                 \
                node->is_root = 1;                      \
                node->height = 0;                       \
                node->num_items = 1;                    \
                node->items[0] = cluster->num_nodes++;  \
        } while (0)                                     \

ClusterNodeT *add_leaf(cluster_t *cluster, const item_t *item)
{
        ClusterNodeT *leaf = &(cluster->nodes[cluster->num_nodes]);
        int len = strlen(item->label) + 1;
        leaf->label = alloc_mem(len, char);
        if (leaf->label) {
                leaf->items = alloc_mem(1, int);
                if (leaf->items) {
                        init_leaf(cluster, leaf, item, len);
                        cluster->num_clusters++;
                } else {
                        alloc_fail("node items");
                        free(leaf->label);
                        leaf = NULL;
                }
        } else {
                alloc_fail("node label");
                leaf = NULL;
        }
        return leaf;
}

#undef init_leaf

cluster_t *add_leaves(cluster_t *cluster, item_t *items)
{
        for (int i = 0; i < cluster->num_items; ++i) {
                if (add_leaf(cluster, &items[i]))
                        update_neighbours(cluster, i);
                else {
                        cluster = NULL;
                        break;
                }
        }
        return cluster;
}

void print_cluster_items(cluster_t *cluster, int index)
{
        ClusterNodeT *node = &(cluster->nodes[index]);
        fprintf(stdout, "Items: ");
        if (node->num_items > 0) {
                fprintf(stdout, "%s", cluster->nodes[node->items[0]].label);
                for (int i = 1; i < node->num_items; ++i)
                        fprintf(stdout, ", %s",
                                cluster->nodes[node->items[i]].label);
        }
        fprintf(stdout, "\n");
}

void print_cluster_node(cluster_t *cluster, int index)
{
        ClusterNodeT *node = &(cluster->nodes[index]);
        fprintf(stdout, "Node %d - height: %d, centroid: (%5.3f, %5.3f)\n",
                index, node->height, node->centroid.x, node->centroid.y);
        if (node->label)
                fprintf(stdout, "\tLeaf: %s\n\t", node->label);
        else
                fprintf(stdout, "\tMerged: %d, %d\n\t",
                        node->merged[0], node->merged[1]);
        print_cluster_items(cluster, index);
        fprintf(stdout, "\tNeighbours: ");
        neighbour_t *t = node->neighbours;
        while (t) {
                fprintf(stdout, "\n\t\t%2d: %5.3f", t->target, t->distance);
                t = t->next;
        }
        fprintf(stdout, "\n");
}

void merge_items(cluster_t *cluster, ClusterNodeT *node,
                 ClusterNodeT **to_merge)
{
        node->type = A_MERGER;
        node->is_root = 1;
        node->height = -1;

        /* copy leaf indexes from merged clusters */
        int k = 0, idx;
        coord_t centroid = { .x = 0.0, .y = 0.0 };
        for (int i = 0; i < 2; ++i) {
                ClusterNodeT *t = to_merge[i];
                t->is_root = 0; /* no longer root: merged */
                if (node->height == -1 ||
                    node->height < t->height)
                        node->height = t->height;
                for (int j = 0; j < t->num_items; ++j) {
                        idx = t->items[j];
                        node->items[k++] = idx;
                }
                centroid.x += t->num_items * t->centroid.x;
                centroid.y += t->num_items * t->centroid.y;
        }
        /* calculate centroid */
        node->centroid.x = centroid.x / k;
        node->centroid.y = centroid.y / k;
        node->height++;
}

#define MergeToOne(cluster, to_merge, node, node_idx)         \
        do {                                                    \
                node->num_items = to_merge[0]->num_items +      \
                        to_merge[1]->num_items;                 \
                node->items = alloc_mem(node->num_items, int);  \
                if (node->items) {                              \
                        merge_items(cluster, node, to_merge);   \
                        cluster->num_nodes++;                   \
                        cluster->num_clusters--;                \
                        update_neighbours(cluster, node_idx);   \
                } else {                                        \
                        alloc_fail("array of merged items");    \
                        free(node->merged);                     \
                        node = NULL;                            \
                }                                               \
        } while(0)                                              \

ClusterNodeT *merge(cluster_t *cluster, int first, int second)
{
        int new_idx = cluster->num_nodes;
        ClusterNodeT *node = &(cluster->nodes[new_idx]);
        node->merged = alloc_mem(2, int);
        if (node->merged) {
                ClusterNodeT *to_merge[2] = {
                        &(cluster->nodes[first]),
                        &(cluster->nodes[second])
                };
                node->merged[0] = first;
                node->merged[1] = second;
                MergeToOne(cluster, to_merge, node, new_idx);
        } else {
                alloc_fail("array of merged nodes");
                node = NULL;
        }
        return node;
}

#undef MergeToOne

void FindBestDistanceNeighbour(ClusterNodeT *nodes,
                                  int node_idx,
                                  neighbour_t *neighbour,
                                  float *best_distance,
                                  int *first, int *second)
{
        while (neighbour) {
                if (nodes[neighbour->target].is_root) {
                        if (*first == -1 ||
                            neighbour->distance < *best_distance) {
                                *first = node_idx;
                                *second = neighbour->target;
                                *best_distance = neighbour->distance;
                        }
                        break;
                }
                neighbour = neighbour->next;
        }
}


int FinalClustersToMerge(cluster_t *cluster, int *first, int *second)
{
        float best_distance = 0.0;
        int root_clusters_seen = 0;
        int j = cluster->num_nodes; /* traverse hierarchy top-down */
        *first = -1;
        while (root_clusters_seen < cluster->num_clusters) {
                ClusterNodeT *node = &(cluster->nodes[--j]);
                if (node->type == NOT_USED || !node->is_root)
                        continue;
                ++root_clusters_seen;
                FindBestDistanceNeighbour(cluster->nodes, j,
                                             node->neighbours,
                                             &best_distance,
                                             first, second);
        }
        return *first;
}

cluster_t *merge_clusters(cluster_t *cluster)
{
        int first, second;
        while (cluster->num_clusters > 1) {
                if (FinalClustersToMerge(cluster, &first, &second) != -1)
                        merge(cluster, first, second);
        }
        return cluster;
}

#define init_cluster(cluster, num_items, items)                         \
        do {                                                            \
                cluster->distances =                                    \
                        generate_distance_matrix(num_items, items);     \
                if (!cluster->distances)                                \
                        goto cleanup;                                   \
                cluster->num_items = num_items;                         \
                cluster->num_nodes = 0;                                 \
                cluster->num_clusters = 0;                              \
                if (add_leaves(cluster, items))                         \
                        merge_clusters(cluster);                        \
                else                                                    \
                        goto cleanup;                                   \
        } while (0)                                                     \

cluster_t *agglomerate(int num_items, item_t *items)
{
        cluster_t *cluster = alloc_mem(1, cluster_t);
        if (cluster) {
                cluster->nodes = alloc_mem(2 * num_items - 1, ClusterNodeT);
                if (cluster->nodes)
                        init_cluster(cluster, num_items, items);
                else {
                        alloc_fail("cluster nodes");
                        goto cleanup;
                }
        } else
                alloc_fail("cluster");
        goto done;

cleanup:
        FreeCluster(cluster);
        cluster = NULL;

done:
        return cluster;
}

#undef init_cluster

int PrintRootChildern(cluster_t *cluster, int i, int NodesToDiscard)
{
        ClusterNodeT *node = &(cluster->nodes[i]);
        int RoootsFound = 0;
        if (node->type == A_MERGER) {
                for (int j = 0; j < 2; ++j) {
                        int t = node->merged[j];
                        if (t < NodesToDiscard) {
                                print_cluster_items(cluster, t);
                                ++RoootsFound;
                        }
                }
        }
        return RoootsFound;
}

void GetKthCluster(cluster_t *cluster, int k)
{
        if (k < 1)
                return;
        if (k > cluster->num_items)
                k = cluster->num_items;

        int i = cluster->num_nodes - 1;
        int RoootsFound = 0;
        int NodesToDiscard = cluster->num_nodes - k + 1;
        while (k) {
                if (i < NodesToDiscard) {
                        print_cluster_items(cluster, i);
                        RoootsFound = 1;
                } else
                        RoootsFound = PrintRootChildern(cluster, i,
                                                          NodesToDiscard);
                k -= RoootsFound;
                --i;
        }
}

void print_cluster(cluster_t *cluster)
{
        for (int i = 0; i < cluster->num_nodes; ++i)
                print_cluster_node(cluster, i);
}

int read_items(int count, item_t *items, FILE *f)
{
        for (int i = 0; i < count; ++i) {
                item_t *t = &(items[i]);
                if (fscanf(f, "%[^|]| %10f %10f\n",
                           t->label, &(t->coord.x),
                           &(t->coord.y)))
                        continue;
                read_fail("item line");
                return i;
        }
        return count;
}

int ReadItemsFromFile(item_t **items, FILE *f)
{
        int count, r;
        r = fscanf(f, "%5d\n", &count);
        if (r == 0) {
                read_fail("number of lines");
                return 0;
        }
        if (count) {
                *items = alloc_mem(count, item_t);
                if (*items) {
                        if (read_items(count, *items, f) != count)
                                free(items);
                } else
                        alloc_fail("items array");
        }
        return count;
}

void SetLinkage(char LinkageType)
{
        switch (LinkageType) {
        case AVERAGE_LINKAGE:
                distance_fptr = average_linkage;
                break;
        case COMPLETE_LINKAGE:
                distance_fptr = complete_linkage;
                break;
        case CENTROID_LINKAGE:
                distance_fptr = centroid_linkage;
                break;
        case SINGLE_LINKAGE:
        default: distance_fptr = single_linkage;
        }
}

int ProcessInput(item_t **items, const char *fname)
{
        int count = 0;
        FILE *f = fopen(fname, "r");
        if (f) {
                count = ReadItemsFromFile(items, f);
                fclose(f);
        } else
                fprintf(stderr, "Failed to open input file %s.\n", fname);
        return count;
}

int main(int argc, char **argv)
{
        if (argc != 4) {
                fprintf(stderr, "Usage: %s <input file> <num clusters> "
                        "<linkage type>\n", argv[0]);
                exit(1);
        } else {
                item_t *items = NULL;
                int num_items = ProcessInput(&items, argv[1]);
                SetLinkage(argv[3][0]);
                if (num_items) {
                        cluster_t *cluster = agglomerate(num_items, items);
                        free(items);

                        if (cluster) {
                                fprintf(stdout, "CLUSTER HIERARCHY\n"
                                        "--------------------\n");
                                print_cluster(cluster);

                                int k = atoi(argv[2]);
                                fprintf(stdout, "\n\n%d CLUSTERS\n"
                                        "--------------------\n", k);
                                GetKthCluster(cluster, k);
                                FreeCluster(cluster);
                        }
                }
        }
        return 0;
}

	.file	"tmpxft_00349f07_00000000-6_code.cudafe1.cpp"
	.text
#APP

#NO_APP
	.globl	_Z14single_linkagePPfPKiS2_ii
	.type	_Z14single_linkagePPfPKiS2_ii, @function
_Z14single_linkagePPfPKiS2_ii:
.LFB2030:
	.cfi_startproc
	endbr64
	movss	.LC0(%rip), %xmm0
	movq	%rsi, %r9
	xorl	%eax, %eax
.L2:
	cmpl	%eax, %ecx
	jle	.L8
	xorl	%esi, %esi
.L5:
	cmpl	%esi, %r8d
	jle	.L9
	movslq	(%r9,%rax,4), %r10
	movslq	(%rdx,%rsi,4), %r11
	incq	%rsi
	movq	(%rdi,%r10,8), %r10
	movss	(%r10,%r11,4), %xmm1
	minss	%xmm0, %xmm1
	movaps	%xmm1, %xmm0
	jmp	.L5
.L9:
	incq	%rax
	jmp	.L2
.L8:
	ret
	.cfi_endproc
.LFE2030:
	.size	_Z14single_linkagePPfPKiS2_ii, .-_Z14single_linkagePPfPKiS2_ii
	.globl	_Z16complete_linkagePPfPKiS2_ii
	.type	_Z16complete_linkagePPfPKiS2_ii, @function
_Z16complete_linkagePPfPKiS2_ii:
.LFB2031:
	.cfi_startproc
	endbr64
	movq	%rsi, %r9
	xorl	%eax, %eax
	xorps	%xmm0, %xmm0
.L11:
	cmpl	%eax, %ecx
	jle	.L16
	xorl	%esi, %esi
.L14:
	cmpl	%esi, %r8d
	jle	.L17
	movslq	(%r9,%rax,4), %r10
	movslq	(%rdx,%rsi,4), %r11
	incq	%rsi
	movq	(%rdi,%r10,8), %r10
	movss	(%r10,%r11,4), %xmm1
	maxss	%xmm0, %xmm1
	movaps	%xmm1, %xmm0
	jmp	.L14
.L17:
	incq	%rax
	jmp	.L11
.L16:
	ret
	.cfi_endproc
.LFE2031:
	.size	_Z16complete_linkagePPfPKiS2_ii, .-_Z16complete_linkagePPfPKiS2_ii
	.globl	_Z15average_linkagePPfPKiS2_ii
	.type	_Z15average_linkagePPfPKiS2_ii, @function
_Z15average_linkagePPfPKiS2_ii:
.LFB2032:
	.cfi_startproc
	endbr64
	movq	%rsi, %r9
	xorl	%eax, %eax
	xorps	%xmm0, %xmm0
.L19:
	cmpl	%eax, %ecx
	jle	.L23
	xorl	%esi, %esi
.L21:
	cmpl	%esi, %r8d
	jle	.L24
	movslq	(%r9,%rax,4), %r10
	movslq	(%rdx,%rsi,4), %r11
	incq	%rsi
	movq	(%rdi,%r10,8), %r10
	addss	(%r10,%r11,4), %xmm0
	jmp	.L21
.L24:
	incq	%rax
	jmp	.L19
.L23:
	imull	%r8d, %ecx
	cvtsi2ssl	%ecx, %xmm1
	divss	%xmm1, %xmm0
	ret
	.cfi_endproc
.LFE2032:
	.size	_Z15average_linkagePPfPKiS2_ii, .-_Z15average_linkagePPfPKiS2_ii
	.globl	_Z16centroid_linkagePPfPKiS2_ii
	.type	_Z16centroid_linkagePPfPKiS2_ii, @function
_Z16centroid_linkagePPfPKiS2_ii:
.LFB2033:
	.cfi_startproc
	endbr64
	xorps	%xmm0, %xmm0
	ret
	.cfi_endproc
.LFE2033:
	.size	_Z16centroid_linkagePPfPKiS2_ii, .-_Z16centroid_linkagePPfPKiS2_ii
	.type	_ZL26__cudaUnregisterBinaryUtilv, @function
_ZL26__cudaUnregisterBinaryUtilv:
.LFB2063:
	.cfi_startproc
	endbr64
	movq	_ZL20__cudaFatCubinHandle(%rip), %rdi
	jmp	__cudaUnregisterFatBinary@PLT
	.cfi_endproc
.LFE2063:
	.size	_ZL26__cudaUnregisterBinaryUtilv, .-_ZL26__cudaUnregisterBinaryUtilv
	.globl	_Z18euclidean_distancePK7coord_sS1_
	.type	_Z18euclidean_distancePK7coord_sS1_, @function
_Z18euclidean_distancePK7coord_sS1_:
.LFB2027:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	movss	(%rdi), %xmm0
	movss	4(%rdi), %xmm1
	subss	(%rsi), %xmm0
	subss	4(%rsi), %xmm1
	cvtss2sd	%xmm0, %xmm0
	mulsd	%xmm0, %xmm0
	cvtss2sd	%xmm1, %xmm1
	mulsd	%xmm1, %xmm1
	addsd	%xmm1, %xmm0
	call	sqrt@PLT
	popq	%rdx
	.cfi_def_cfa_offset 8
	cvtsd2ss	%xmm0, %xmm0
	ret
	.cfi_endproc
.LFE2027:
	.size	_Z18euclidean_distancePK7coord_sS1_, .-_Z18euclidean_distancePK7coord_sS1_
	.globl	_Z24fill_euclidean_distancesPPfiPK6item_s
	.type	_Z24fill_euclidean_distancesPPfiPK6item_s, @function
_Z24fill_euclidean_distancesPPfiPK6item_s:
.LFB2028:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	movslq	%esi, %rax
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	movq	%rdx, %r14
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	movq	%rdi, %r13
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	movq	%rax, %r12
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	xorl	%ebx, %ebx
	subq	$40, %rsp
	.cfi_def_cfa_offset 96
.L30:
	cmpl	%ebx, %r12d
	jle	.L35
	imulq	$24, %rbx, %r15
	xorl	%ebp, %ebp
	leaq	(%r15,%r14), %rdx
	leaq	0(,%rbx,4), %r15
	movq	%rdx, 8(%rsp)
.L31:
	imulq	$24, %rbp, %rsi
	movq	0(%r13,%rbx,8), %rcx
	movq	8(%rsp), %rdi
	movq	%rax, 24(%rsp)
	leaq	(%rcx,%rbp,4), %rcx
	addq	%r14, %rsi
	movq	%rcx, 16(%rsp)
	call	_Z18euclidean_distancePK7coord_sS1_
	movq	16(%rsp), %rcx
	movq	24(%rsp), %rax
	movss	%xmm0, (%rcx)
	movq	0(%r13,%rbp,8), %rcx
	incq	%rbp
	movss	%xmm0, (%rcx,%r15)
	cmpq	%rax, %rbp
	jne	.L31
	incq	%rbx
	jmp	.L30
.L35:
	addq	$40, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2028:
	.size	_Z24fill_euclidean_distancesPPfiPK6item_s, .-_Z24fill_euclidean_distancesPPfiPK6item_s
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC2:
	.string	"distance matrix row"
.LC3:
	.string	"Failed to allocate memory for %s.\n"
.LC4:
	.string	"distance matrix"
	.text
	.globl	_Z24generate_distance_matrixiPK6item_s
	.type	_Z24generate_distance_matrixiPK6item_s, @function
_Z24generate_distance_matrixiPK6item_s:
.LFB2029:
	.cfi_startproc
	endbr64
	pushq	%r14
	.cfi_def_cfa_offset 16
	.cfi_offset 14, -16
	movslq	%edi, %r14
	pushq	%r13
	.cfi_def_cfa_offset 24
	.cfi_offset 13, -24
	movq	%r14, %rdi
	movq	%rsi, %r13
	movl	$8, %esi
	pushq	%r12
	.cfi_def_cfa_offset 32
	.cfi_offset 12, -32
	pushq	%rbp
	.cfi_def_cfa_offset 40
	.cfi_offset 6, -40
	pushq	%rbx
	.cfi_def_cfa_offset 48
	.cfi_offset 3, -48
	call	calloc@PLT
	testq	%rax, %rax
	je	.L50
	movq	%r14, %rbp
	movq	%rax, %rbx
	xorl	%r12d, %r12d
.L37:
	cmpl	%r12d, %ebp
	jle	.L51
	movl	$4, %esi
	movq	%r14, %rdi
	call	calloc@PLT
	leaq	1(%r12), %rdx
	movq	%rax, (%rbx,%r12,8)
	testq	%rax, %rax
	jne	.L45
	movq	stderr(%rip), %rdi
	leaq	.LC2(%rip), %rcx
	movl	$2, %esi
	movq	%rbx, %rbp
	leaq	.LC3(%rip), %rdx
	leaq	(%rbx,%r12,8), %r12
	call	__fprintf_chk@PLT
.L39:
	cmpq	%r12, %rbp
	je	.L52
	movq	0(%rbp), %rdi
	addq	$8, %rbp
	call	free@PLT
	jmp	.L39
.L52:
	movq	%rbx, %rdi
	call	free@PLT
.L43:
	xorl	%ebx, %ebx
	jmp	.L36
.L45:
	movq	%rdx, %r12
	jmp	.L37
.L51:
	movq	%r13, %rdx
	movl	%ebp, %esi
	movq	%rbx, %rdi
	call	_Z24fill_euclidean_distancesPPfiPK6item_s
	jmp	.L36
.L50:
	movq	stderr(%rip), %rdi
	leaq	.LC4(%rip), %rcx
	leaq	.LC3(%rip), %rdx
	xorl	%eax, %eax
	movl	$2, %esi
	call	__fprintf_chk@PLT
	jmp	.L43
.L36:
	movq	%rbx, %rax
	popq	%rbx
	.cfi_def_cfa_offset 40
	popq	%rbp
	.cfi_def_cfa_offset 32
	popq	%r12
	.cfi_def_cfa_offset 24
	popq	%r13
	.cfi_def_cfa_offset 16
	popq	%r14
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2029:
	.size	_Z24generate_distance_matrixiPK6item_s, .-_Z24generate_distance_matrixiPK6item_s
	.globl	_Z12get_distanceP9cluster_sii
	.type	_Z12get_distanceP9cluster_sii, @function
_Z12get_distanceP9cluster_sii:
.LFB2034:
	.cfi_startproc
	endbr64
	movq	%rdi, %rax
	cmpl	%edx, %esi
	movslq	%esi, %rdi
	movslq	%edx, %rcx
	cmovl	%edx, %esi
	cmpl	%esi, (%rax)
	jg	.L58
	movq	16(%rax), %rsi
	movq	distance_fptr(%rip), %r9
	salq	$6, %rdi
	leaq	_Z16centroid_linkagePPfPKiS2_ii(%rip), %rdx
	salq	$6, %rcx
	addq	%rsi, %rdi
	addq	%rcx, %rsi
	cmpq	%rdx, %r9
	jne	.L56
	addq	$12, %rsi
	addq	$12, %rdi
	jmp	_Z18euclidean_distancePK7coord_sS1_
.L56:
	movq	48(%rdi), %r10
	movl	40(%rdi), %ecx
	movq	48(%rsi), %rdx
	movl	40(%rsi), %r8d
	movq	24(%rax), %rdi
	movq	%r10, %rsi
	jmp	*%r9
.L58:
	movq	24(%rax), %rax
	movq	(%rax,%rdi,8), %rax
	movss	(%rax,%rcx,4), %xmm0
	ret
	.cfi_endproc
.LFE2034:
	.size	_Z12get_distanceP9cluster_sii, .-_Z12get_distanceP9cluster_sii
	.globl	_Z15free_neighboursP11neighbour_s
	.type	_Z15free_neighboursP11neighbour_s, @function
_Z15free_neighboursP11neighbour_s:
.LFB2035:
	.cfi_startproc
	endbr64
	testq	%rdi, %rdi
	jne	.L64
	ret
.L64:
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
.L61:
	movq	8(%rdi), %rbx
	call	free@PLT
	movq	%rbx, %rdi
	testq	%rbx, %rbx
	jne	.L61
	popq	%rbx
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2035:
	.size	_Z15free_neighboursP11neighbour_s, .-_Z15free_neighboursP11neighbour_s
	.globl	_Z18free_cluster_nodesP9cluster_s
	.type	_Z18free_cluster_nodesP9cluster_s, @function
_Z18free_cluster_nodesP9cluster_s:
.LFB2036:
	.cfi_startproc
	endbr64
	pushq	%r12
	.cfi_def_cfa_offset 16
	.cfi_offset 12, -16
	movq	%rdi, %r12
	pushq	%rbp
	.cfi_def_cfa_offset 24
	.cfi_offset 6, -24
	xorl	%ebp, %ebp
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -32
.L66:
	movq	16(%r12), %rdi
	cmpl	%ebp, 8(%r12)
	jle	.L85
	movq	%rbp, %rax
	salq	$6, %rax
	leaq	(%rdi,%rax), %rbx
	movq	24(%rbx), %rdi
	testq	%rdi, %rdi
	je	.L67
	call	free@PLT
.L67:
	movq	32(%rbx), %rdi
	testq	%rdi, %rdi
	je	.L68
	call	free@PLT
.L68:
	movq	48(%rbx), %rdi
	testq	%rdi, %rdi
	je	.L69
	call	free@PLT
.L69:
	movq	56(%rbx), %rdi
	testq	%rdi, %rdi
	je	.L70
	call	_Z15free_neighboursP11neighbour_s
.L70:
	incq	%rbp
	jmp	.L66
.L85:
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%rbp
	.cfi_def_cfa_offset 16
	popq	%r12
	.cfi_def_cfa_offset 8
	jmp	free@PLT
	.cfi_endproc
.LFE2036:
	.size	_Z18free_cluster_nodesP9cluster_s, .-_Z18free_cluster_nodesP9cluster_s
	.globl	_Z11FreeClusterP9cluster_s
	.type	_Z11FreeClusterP9cluster_s, @function
_Z11FreeClusterP9cluster_s:
.LFB2037:
	.cfi_startproc
	endbr64
	testq	%rdi, %rdi
	je	.L86
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	pushq	%rbx
	.cfi_def_cfa_offset 24
	.cfi_offset 3, -24
	movq	%rdi, %rbx
	pushq	%rdx
	.cfi_def_cfa_offset 32
	cmpq	$0, 16(%rdi)
	je	.L88
	call	_Z18free_cluster_nodesP9cluster_s
.L88:
	xorl	%ebp, %ebp
	cmpq	$0, 24(%rbx)
	je	.L90
.L89:
	movq	24(%rbx), %rdi
	cmpl	%ebp, (%rbx)
	jle	.L97
	movq	(%rdi,%rbp,8), %rdi
	incq	%rbp
	call	free@PLT
	jmp	.L89
.L97:
	call	free@PLT
.L90:
	popq	%rax
	.cfi_def_cfa_offset 24
	movq	%rbx, %rdi
	popq	%rbx
	.cfi_restore 3
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_restore 6
	.cfi_def_cfa_offset 8
	jmp	free@PLT
.L86:
	ret
	.cfi_endproc
.LFE2037:
	.size	_Z11FreeClusterP9cluster_s, .-_Z11FreeClusterP9cluster_s
	.globl	_Z13insert_beforeP11neighbour_sS0_P14cluster_node_s
	.type	_Z13insert_beforeP11neighbour_sS0_P14cluster_node_s, @function
_Z13insert_beforeP11neighbour_sS0_P14cluster_node_s:
.LFB2038:
	.cfi_startproc
	endbr64
	movq	16(%rdi), %rax
	movq	%rdi, 8(%rsi)
	testq	%rax, %rax
	je	.L99
	movq	%rsi, 8(%rax)
	movq	%rax, 16(%rsi)
	jmp	.L100
.L99:
	movq	%rsi, 56(%rdx)
.L100:
	movq	%rsi, 16(%rdi)
	ret
	.cfi_endproc
.LFE2038:
	.size	_Z13insert_beforeP11neighbour_sS0_P14cluster_node_s, .-_Z13insert_beforeP11neighbour_sS0_P14cluster_node_s
	.globl	_Z11InsertAfterP11neighbour_sS0_
	.type	_Z11InsertAfterP11neighbour_sS0_, @function
_Z11InsertAfterP11neighbour_sS0_:
.LFB2039:
	.cfi_startproc
	endbr64
	movq	%rdi, 16(%rsi)
	movq	%rsi, 8(%rdi)
	ret
	.cfi_endproc
.LFE2039:
	.size	_Z11InsertAfterP11neighbour_sS0_, .-_Z11InsertAfterP11neighbour_sS0_
	.globl	_Z13insert_sortedP14cluster_node_sP11neighbour_s
	.type	_Z13insert_sortedP14cluster_node_sP11neighbour_s, @function
_Z13insert_sortedP14cluster_node_sP11neighbour_s:
.LFB2040:
	.cfi_startproc
	endbr64
	movq	56(%rdi), %rax
	movss	4(%rsi), %xmm0
	movq	%rdi, %rdx
.L103:
	movq	%rax, %rdi
	movq	8(%rax), %rax
	movss	4(%rdi), %xmm1
	testq	%rax, %rax
	je	.L112
	comiss	%xmm0, %xmm1
	jb	.L103
	jmp	.L111
.L112:
	comiss	%xmm0, %xmm1
	jbe	.L110
.L111:
	jmp	_Z13insert_beforeP11neighbour_sS0_P14cluster_node_s
.L110:
	movq	%rdi, 16(%rsi)
	movq	%rsi, 8(%rdi)
	ret
	.cfi_endproc
.LFE2040:
	.size	_Z13insert_sortedP14cluster_node_sP11neighbour_s, .-_Z13insert_sortedP14cluster_node_sP11neighbour_s
	.section	.rodata.str1.1
.LC5:
	.string	"neighbour node"
	.text
	.globl	_Z13add_neighbourP9cluster_sii
	.type	_Z13add_neighbourP9cluster_sii, @function
_Z13add_neighbourP9cluster_sii:
.LFB2041:
	.cfi_startproc
	endbr64
	pushq	%r12
	.cfi_def_cfa_offset 16
	.cfi_offset 12, -16
	movq	%rdi, %r12
	movl	$1, %edi
	pushq	%rbp
	.cfi_def_cfa_offset 24
	.cfi_offset 6, -24
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -32
	movl	%esi, %ebx
	movl	$24, %esi
	subq	$16, %rsp
	.cfi_def_cfa_offset 48
	movl	%edx, 12(%rsp)
	call	calloc@PLT
	movq	%rax, %rbp
	testq	%rax, %rax
	je	.L114
	movl	12(%rsp), %edx
	movq	%r12, %rdi
	movl	%ebx, %esi
	movl	%edx, (%rax)
	call	_Z12get_distanceP9cluster_sii
	movslq	%ebx, %rdi
	salq	$6, %rdi
	addq	16(%r12), %rdi
	movss	%xmm0, 4(%rbp)
	cmpq	$0, 56(%rdi)
	je	.L115
	movq	%rbp, %rsi
	call	_Z13insert_sortedP14cluster_node_sP11neighbour_s
	jmp	.L113
.L115:
	movq	%rbp, 56(%rdi)
	jmp	.L113
.L114:
	movq	stderr(%rip), %rdi
	leaq	.LC5(%rip), %rcx
	leaq	.LC3(%rip), %rdx
	xorl	%eax, %eax
	movl	$2, %esi
	call	__fprintf_chk@PLT
.L113:
	addq	$16, %rsp
	.cfi_def_cfa_offset 32
	movq	%rbp, %rax
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%rbp
	.cfi_def_cfa_offset 16
	popq	%r12
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2041:
	.size	_Z13add_neighbourP9cluster_sii, .-_Z13add_neighbourP9cluster_sii
	.section	.rodata.str1.1
.LC6:
	.string	"Invalid cluster node at index %d.\n"
	.text
	.globl	_Z17update_neighboursP9cluster_si
	.type	_Z17update_neighboursP9cluster_si, @function
_Z17update_neighboursP9cluster_si:
.LFB2042:
	.cfi_startproc
	endbr64
	pushq	%r13
	.cfi_def_cfa_offset 16
	.cfi_offset 13, -16
	pushq	%r12
	.cfi_def_cfa_offset 24
	.cfi_offset 12, -24
	pushq	%rbp
	.cfi_def_cfa_offset 32
	.cfi_offset 6, -32
	movslq	%esi, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 40
	.cfi_offset 3, -40
	movq	%rbp, %rax
	movq	%rbp, %rcx
	salq	$6, %rax
	subq	$24, %rsp
	.cfi_def_cfa_offset 64
	addq	16(%rdi), %rax
	cmpl	$0, (%rax)
	je	.L127
	decq	%rbp
	movq	%rdi, %rbx
	movl	%ecx, %r13d
	movl	$1, %r12d
	salq	$6, %rbp
	jmp	.L120
.L122:
	cmpl	$0, 4(%rax)
	je	.L124
	movl	%ecx, %esi
	movl	%r13d, %edx
	movq	%rbx, %rdi
	movl	%ecx, 12(%rsp)
	call	_Z13add_neighbourP9cluster_sii
	movl	12(%rsp), %ecx
	incl	%r12d
.L124:
	subq	$64, %rbp
.L120:
	cmpl	%r12d, 4(%rbx)
	jle	.L123
	movq	16(%rbx), %rax
	decl	%r13d
	addq	%rbp, %rax
	cmpl	$0, (%rax)
	jne	.L122
.L127:
	movq	stderr(%rip), %rdi
	movl	$2, %esi
	xorl	%eax, %eax
	xorl	%ebx, %ebx
	leaq	.LC6(%rip), %rdx
	call	__fprintf_chk@PLT
.L123:
	addq	$24, %rsp
	.cfi_def_cfa_offset 40
	movq	%rbx, %rax
	popq	%rbx
	.cfi_def_cfa_offset 32
	popq	%rbp
	.cfi_def_cfa_offset 24
	popq	%r12
	.cfi_def_cfa_offset 16
	popq	%r13
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2042:
	.size	_Z17update_neighboursP9cluster_si, .-_Z17update_neighboursP9cluster_si
	.section	.rodata.str1.1
.LC7:
	.string	"node items"
.LC8:
	.string	"node label"
	.text
	.globl	_Z8add_leafP9cluster_sPK6item_s
	.type	_Z8add_leafP9cluster_sPK6item_s, @function
_Z8add_leafP9cluster_sPK6item_s:
.LFB2043:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	leaq	8(%rsi), %rax
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	movq	%rsi, %r13
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	movq	%rdi, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	subq	$24, %rsp
	.cfi_def_cfa_offset 80
	movslq	8(%rdi), %rbx
	movq	%rax, 8(%rsp)
	movq	%rbx, %r14
	salq	$6, %rbx
	addq	16(%rdi), %rbx
	movq	%rax, %rdi
	call	strlen@PLT
	movl	$1, %esi
	leal	1(%rax), %r12d
	movslq	%r12d, %r12
	movq	%r12, %rdi
	call	calloc@PLT
	movq	%rax, 24(%rbx)
	testq	%rax, %rax
	je	.L129
	movl	$4, %esi
	movl	$1, %edi
	movq	%rax, %r15
	call	calloc@PLT
	movq	%rax, 48(%rbx)
	testq	%rax, %rax
	je	.L130
	movq	8(%rsp), %rsi
	movq	%r12, %rcx
	movq	%r12, %rdx
	movq	%r15, %rdi
	call	__strncpy_chk@PLT
	movq	0(%r13), %rax
	movl	$1, 40(%rbx)
	movq	%rax, 12(%rbx)
	movabsq	$4294967297, %rax
	movq	%rax, (%rbx)
	xorl	%eax, %eax
	movl	%eax, 8(%rbx)
	leal	1(%r14), %eax
	movl	%eax, 8(%rbp)
	movq	48(%rbx), %rax
	movl	%r14d, (%rax)
	incl	4(%rbp)
	jmp	.L128
.L130:
	movq	stderr(%rip), %rdi
	leaq	.LC7(%rip), %rcx
	leaq	.LC3(%rip), %rdx
	xorl	%eax, %eax
	movl	$2, %esi
	call	__fprintf_chk@PLT
	movq	24(%rbx), %rdi
	call	free@PLT
	jmp	.L132
.L129:
	movq	stderr(%rip), %rdi
	leaq	.LC8(%rip), %rcx
	leaq	.LC3(%rip), %rdx
	xorl	%eax, %eax
	movl	$2, %esi
	call	__fprintf_chk@PLT
.L132:
	xorl	%ebx, %ebx
.L128:
	addq	$24, %rsp
	.cfi_def_cfa_offset 56
	movq	%rbx, %rax
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2043:
	.size	_Z8add_leafP9cluster_sPK6item_s, .-_Z8add_leafP9cluster_sPK6item_s
	.globl	_Z10add_leavesP9cluster_sP6item_s
	.type	_Z10add_leavesP9cluster_sP6item_s, @function
_Z10add_leavesP9cluster_sP6item_s:
.LFB2044:
	.cfi_startproc
	endbr64
	pushq	%r12
	.cfi_def_cfa_offset 16
	.cfi_offset 12, -16
	xorl	%r12d, %r12d
	pushq	%rbp
	.cfi_def_cfa_offset 24
	.cfi_offset 6, -24
	movq	%rsi, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -32
	movq	%rdi, %rbx
.L135:
	cmpl	%r12d, (%rbx)
	jle	.L142
	movq	%rbp, %rsi
	movq	%rbx, %rdi
	addq	$24, %rbp
	call	_Z8add_leafP9cluster_sPK6item_s
	testq	%rax, %rax
	je	.L134
	movl	%r12d, %esi
	movq	%rbx, %rdi
	incl	%r12d
	call	_Z17update_neighboursP9cluster_si
	jmp	.L135
.L142:
	movq	%rbx, %rax
.L134:
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%rbp
	.cfi_def_cfa_offset 16
	popq	%r12
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2044:
	.size	_Z10add_leavesP9cluster_sP6item_s, .-_Z10add_leavesP9cluster_sP6item_s
	.section	.rodata.str1.1
.LC9:
	.string	"Items: "
.LC10:
	.string	"\n"
.LC11:
	.string	"%s"
.LC12:
	.string	", %s"
	.text
	.globl	_Z19print_cluster_itemsP9cluster_si
	.type	_Z19print_cluster_itemsP9cluster_si, @function
_Z19print_cluster_itemsP9cluster_si:
.LFB2045:
	.cfi_startproc
	endbr64
	pushq	%r13
	.cfi_def_cfa_offset 16
	.cfi_offset 13, -16
	xorl	%eax, %eax
	leaq	.LC9(%rip), %rdx
	pushq	%r12
	.cfi_def_cfa_offset 24
	.cfi_offset 12, -24
	pushq	%rbp
	.cfi_def_cfa_offset 32
	.cfi_offset 6, -32
	movq	%rdi, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 40
	.cfi_offset 3, -40
	movslq	%esi, %rbx
	movl	$2, %esi
	pushq	%r8
	.cfi_def_cfa_offset 48
	salq	$6, %rbx
	addq	16(%rdi), %rbx
	movq	stdout(%rip), %rdi
	call	__fprintf_chk@PLT
	cmpl	$0, 40(%rbx)
	jg	.L144
.L147:
	movq	stdout(%rip), %rdi
	leaq	.LC10(%rip), %rdx
	popq	%rcx
	.cfi_remember_state
	.cfi_def_cfa_offset 40
	movl	$2, %esi
	popq	%rbx
	.cfi_def_cfa_offset 32
	xorl	%eax, %eax
	popq	%rbp
	.cfi_def_cfa_offset 24
	popq	%r12
	.cfi_def_cfa_offset 16
	popq	%r13
	.cfi_def_cfa_offset 8
	jmp	__fprintf_chk@PLT
.L144:
	.cfi_restore_state
	movq	48(%rbx), %rax
	movq	stdout(%rip), %rdi
	movl	$2, %esi
	xorl	%r13d, %r13d
	leaq	.LC11(%rip), %rdx
	leaq	.LC12(%rip), %r12
	movslq	(%rax), %rax
	salq	$6, %rax
	addq	16(%rbp), %rax
	movq	24(%rax), %rcx
	xorl	%eax, %eax
	call	__fprintf_chk@PLT
.L145:
	movq	stdout(%rip), %rdi
	incq	%r13
	cmpl	%r13d, 40(%rbx)
	jle	.L147
	movq	48(%rbx), %rax
	movq	%r12, %rdx
	movl	$2, %esi
	movslq	(%rax,%r13,4), %rax
	salq	$6, %rax
	addq	16(%rbp), %rax
	movq	24(%rax), %rcx
	xorl	%eax, %eax
	call	__fprintf_chk@PLT
	jmp	.L145
	.cfi_endproc
.LFE2045:
	.size	_Z19print_cluster_itemsP9cluster_si, .-_Z19print_cluster_itemsP9cluster_si
	.section	.rodata.str1.1
.LC13:
	.string	"Node %d - height: %d, centroid: (%5.3f, %5.3f)\n"
.LC14:
	.string	"\tLeaf: %s\n\t"
.LC15:
	.string	"\tMerged: %d, %d\n\t"
.LC16:
	.string	"\tNeighbours: "
.LC17:
	.string	"\n\t\t%2d: %5.3f"
	.text
	.globl	_Z18print_cluster_nodeP9cluster_si
	.type	_Z18print_cluster_nodeP9cluster_si, @function
_Z18print_cluster_nodeP9cluster_si:
.LFB2046:
	.cfi_startproc
	endbr64
	pushq	%r12
	.cfi_def_cfa_offset 16
	.cfi_offset 12, -16
	movq	%rdi, %r12
	leaq	.LC13(%rip), %rdx
	movb	$2, %al
	pushq	%rbp
	.cfi_def_cfa_offset 24
	.cfi_offset 6, -24
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -32
	movslq	%esi, %rbx
	movl	$2, %esi
	movq	%rbx, %rbp
	salq	$6, %rbx
	addq	16(%rdi), %rbx
	movq	stdout(%rip), %rdi
	movl	8(%rbx), %r8d
	movl	%ebp, %ecx
	cvtss2sd	12(%rbx), %xmm0
	cvtss2sd	16(%rbx), %xmm1
	call	__fprintf_chk@PLT
	movq	24(%rbx), %rcx
	movq	stdout(%rip), %rdi
	testq	%rcx, %rcx
	je	.L150
	leaq	.LC14(%rip), %rdx
	movl	$2, %esi
	xorl	%eax, %eax
	call	__fprintf_chk@PLT
	jmp	.L151
.L150:
	movq	32(%rbx), %rax
	leaq	.LC15(%rip), %rdx
	movl	$2, %esi
	movl	4(%rax), %r8d
	movl	(%rax), %ecx
	xorl	%eax, %eax
	call	__fprintf_chk@PLT
.L151:
	movl	%ebp, %esi
	movq	%r12, %rdi
	leaq	.LC17(%rip), %rbp
	call	_Z19print_cluster_itemsP9cluster_si
	movq	stdout(%rip), %rdi
	leaq	.LC16(%rip), %rdx
	xorl	%eax, %eax
	movl	$2, %esi
	call	__fprintf_chk@PLT
	movq	56(%rbx), %rbx
.L152:
	movq	stdout(%rip), %rdi
	testq	%rbx, %rbx
	je	.L155
	movl	(%rbx), %ecx
	movq	%rbp, %rdx
	movl	$2, %esi
	movb	$1, %al
	cvtss2sd	4(%rbx), %xmm0
	call	__fprintf_chk@PLT
	movq	8(%rbx), %rbx
	jmp	.L152
.L155:
	popq	%rbx
	.cfi_def_cfa_offset 24
	leaq	.LC10(%rip), %rdx
	popq	%rbp
	.cfi_def_cfa_offset 16
	movl	$2, %esi
	xorl	%eax, %eax
	popq	%r12
	.cfi_def_cfa_offset 8
	jmp	__fprintf_chk@PLT
	.cfi_endproc
.LFE2046:
	.size	_Z18print_cluster_nodeP9cluster_si, .-_Z18print_cluster_nodeP9cluster_si
	.globl	_Z11merge_itemsP9cluster_sP14cluster_node_sPS2_
	.type	_Z11merge_itemsP9cluster_sP14cluster_node_sPS2_, @function
_Z11merge_itemsP9cluster_sP14cluster_node_sPS2_:
.LFB2047:
	.cfi_startproc
	endbr64
	movl	$2147483649, %ecx
	xorps	%xmm0, %xmm0
	movq	%rsi, %rax
	xorl	%r9d, %r9d
	addq	%rcx, %rcx
	movl	$-1, 8(%rsi)
	movaps	%xmm0, %xmm1
	xorl	%r8d, %r8d
	movq	%rcx, (%rsi)
.L161:
	movq	(%rdx,%r9,8), %rcx
	movl	8(%rax), %edi
	xorl	%esi, %esi
	movl	%esi, 4(%rcx)
	movl	8(%rcx), %esi
	cmpl	$-1, %edi
	je	.L157
	cmpl	%esi, %edi
	jge	.L158
.L157:
	movl	%esi, 8(%rax)
.L158:
	movslq	%r8d, %rdi
	xorl	%esi, %esi
	salq	$2, %rdi
.L159:
	movl	40(%rcx), %r10d
	cmpl	%esi, %r10d
	jle	.L166
	movq	48(%rcx), %r10
	movl	(%r10,%rsi,4), %r11d
	movq	48(%rax), %r10
	incq	%rsi
	movl	%r11d, (%r10,%rdi)
	addq	$4, %rdi
	jmp	.L159
.L166:
	cvtsi2ssl	%r10d, %xmm2
	movss	12(%rcx), %xmm3
	addl	%esi, %r8d
	mulss	%xmm2, %xmm3
	mulss	16(%rcx), %xmm2
	addss	%xmm3, %xmm1
	addss	%xmm2, %xmm0
	testq	%r9, %r9
	jne	.L167
	movl	$1, %r9d
	jmp	.L161
.L167:
	cvtsi2ssl	%r8d, %xmm2
	incl	8(%rax)
	divss	%xmm2, %xmm1
	divss	%xmm2, %xmm0
	movss	%xmm1, 12(%rax)
	movss	%xmm0, 16(%rax)
	ret
	.cfi_endproc
.LFE2047:
	.size	_Z11merge_itemsP9cluster_sP14cluster_node_sPS2_, .-_Z11merge_itemsP9cluster_sP14cluster_node_sPS2_
	.section	.rodata.str1.1
.LC18:
	.string	"array of merged items"
.LC19:
	.string	"array of merged nodes"
	.text
	.globl	_Z5mergeP9cluster_sii
	.type	_Z5mergeP9cluster_sii, @function
_Z5mergeP9cluster_sii:
.LFB2048:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	movl	%edx, %r15d
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	movl	%esi, %r13d
	movl	$4, %esi
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	movq	%rdi, %r12
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	subq	$56, %rsp
	.cfi_def_cfa_offset 112
	movslq	8(%rdi), %rbp
	movq	16(%rdi), %r14
	movl	$2, %edi
	movq	%fs:40, %rax
	movq	%rax, 40(%rsp)
	xorl	%eax, %eax
	movl	%ebp, 12(%rsp)
	salq	$6, %rbp
	call	calloc@PLT
	addq	%r14, %rbp
	movq	%rax, 32(%rbp)
	movq	%rax, %rbx
	testq	%rax, %rax
	je	.L169
	movslq	%r13d, %rax
	movslq	%r15d, %rdx
	movl	%r13d, (%rbx)
	movl	$4, %esi
	salq	$6, %rdx
	salq	$6, %rax
	movl	%r15d, 4(%rbx)
	addq	%r14, %rax
	addq	%rdx, %r14
	movl	40(%r14), %edi
	addl	40(%rax), %edi
	movq	%rax, 24(%rsp)
	movl	%edi, 40(%rbp)
	movslq	%edi, %rdi
	movq	%r14, 32(%rsp)
	call	calloc@PLT
	movq	%rax, 48(%rbp)
	movq	%rax, %rbx
	testq	%rax, %rax
	je	.L170
	leaq	24(%rsp), %rdx
	movq	%rbp, %rsi
	movq	%r12, %rdi
	movq	%rbp, %rbx
	call	_Z11merge_itemsP9cluster_sP14cluster_node_sPS2_
	incl	8(%r12)
	movl	12(%rsp), %esi
	movq	%r12, %rdi
	decl	4(%r12)
	call	_Z17update_neighboursP9cluster_si
	jmp	.L168
.L170:
	movq	stderr(%rip), %rdi
	leaq	.LC18(%rip), %rcx
	leaq	.LC3(%rip), %rdx
	xorl	%eax, %eax
	movl	$2, %esi
	call	__fprintf_chk@PLT
	movq	32(%rbp), %rdi
	call	free@PLT
	jmp	.L168
.L169:
	movq	stderr(%rip), %rdi
	leaq	.LC19(%rip), %rcx
	leaq	.LC3(%rip), %rdx
	xorl	%eax, %eax
	movl	$2, %esi
	call	__fprintf_chk@PLT
.L168:
	movq	40(%rsp), %rax
	subq	%fs:40, %rax
	je	.L173
	call	__stack_chk_fail@PLT
.L173:
	addq	$56, %rsp
	.cfi_def_cfa_offset 56
	movq	%rbx, %rax
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2048:
	.size	_Z5mergeP9cluster_sii, .-_Z5mergeP9cluster_sii
	.globl	_Z25FindBestDistanceNeighbourP14cluster_node_siP11neighbour_sPfPiS4_
	.type	_Z25FindBestDistanceNeighbourP14cluster_node_siP11neighbour_sPfPiS4_, @function
_Z25FindBestDistanceNeighbourP14cluster_node_siP11neighbour_sPfPiS4_:
.LFB2049:
	.cfi_startproc
	endbr64
	movq	%rdi, %rax
.L176:
	testq	%rdx, %rdx
	je	.L175
	movslq	(%rdx), %rdi
	salq	$6, %rdi
	cmpl	$0, 4(%rax,%rdi)
	je	.L177
	cmpl	$-1, (%r8)
	movss	4(%rdx), %xmm0
	je	.L178
	movss	(%rcx), %xmm1
	comiss	%xmm0, %xmm1
	jbe	.L175
.L178:
	movl	%esi, (%r8)
	movl	(%rdx), %eax
	movl	%eax, (%r9)
	movss	%xmm0, (%rcx)
	ret
.L177:
	movq	8(%rdx), %rdx
	jmp	.L176
.L175:
	ret
	.cfi_endproc
.LFE2049:
	.size	_Z25FindBestDistanceNeighbourP14cluster_node_siP11neighbour_sPfPiS4_, .-_Z25FindBestDistanceNeighbourP14cluster_node_siP11neighbour_sPfPiS4_
	.globl	_Z20FinalClustersToMergeP9cluster_sPiS1_
	.type	_Z20FinalClustersToMergeP9cluster_sPiS1_, @function
_Z20FinalClustersToMergeP9cluster_sPiS1_:
.LFB2050:
	.cfi_startproc
	endbr64
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
	movq	%rsi, %r8
	movq	%rdi, %rbx
	movq	%rdx, %r9
	xorl	%r11d, %r11d
	subq	$16, %rsp
	.cfi_def_cfa_offset 32
	movslq	8(%rdi), %r10
	movq	%fs:40, %rax
	movq	%rax, 8(%rsp)
	xorl	%eax, %eax
	movl	$0x00000000, 4(%rsp)
	leaq	4(%rsp), %rcx
	movl	$-1, (%r8)
	movq	%r10, %rsi
	decq	%r10
	salq	$6, %r10
.L183:
	cmpl	%r11d, 4(%rbx)
	jle	.L188
	movq	16(%rbx), %rdi
	decl	%esi
	leaq	(%rdi,%r10), %rax
	cmpl	$0, (%rax)
	je	.L184
	cmpl	$0, 4(%rax)
	je	.L184
	movq	56(%rax), %rdx
	incl	%r11d
	call	_Z25FindBestDistanceNeighbourP14cluster_node_siP11neighbour_sPfPiS4_
.L184:
	subq	$64, %r10
	jmp	.L183
.L188:
	movl	(%r8), %eax
	movq	8(%rsp), %rdx
	subq	%fs:40, %rdx
	je	.L186
	call	__stack_chk_fail@PLT
.L186:
	addq	$16, %rsp
	.cfi_def_cfa_offset 16
	popq	%rbx
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2050:
	.size	_Z20FinalClustersToMergeP9cluster_sPiS1_, .-_Z20FinalClustersToMergeP9cluster_sPiS1_
	.globl	_Z14merge_clustersP9cluster_s
	.type	_Z14merge_clustersP9cluster_s, @function
_Z14merge_clustersP9cluster_s:
.LFB2051:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	pushq	%rbx
	.cfi_def_cfa_offset 24
	.cfi_offset 3, -24
	movq	%rdi, %rbx
	subq	$24, %rsp
	.cfi_def_cfa_offset 48
	movq	%fs:40, %rax
	movq	%rax, 8(%rsp)
	xorl	%eax, %eax
	leaq	4(%rsp), %rbp
.L191:
	cmpl	$1, 4(%rbx)
	jle	.L197
	movq	%rsp, %rsi
	movq	%rbp, %rdx
	movq	%rbx, %rdi
	call	_Z20FinalClustersToMergeP9cluster_sPiS1_
	incl	%eax
	je	.L191
	movl	4(%rsp), %edx
	movl	(%rsp), %esi
	movq	%rbx, %rdi
	call	_Z5mergeP9cluster_sii
	jmp	.L191
.L197:
	movq	8(%rsp), %rax
	subq	%fs:40, %rax
	je	.L193
	call	__stack_chk_fail@PLT
.L193:
	addq	$24, %rsp
	.cfi_def_cfa_offset 24
	movq	%rbx, %rax
	popq	%rbx
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2051:
	.size	_Z14merge_clustersP9cluster_s, .-_Z14merge_clustersP9cluster_s
	.section	.rodata.str1.1
.LC20:
	.string	"cluster nodes"
.LC21:
	.string	"cluster"
	.text
	.globl	_Z11agglomerateiP6item_s
	.type	_Z11agglomerateiP6item_s, @function
_Z11agglomerateiP6item_s:
.LFB2052:
	.cfi_startproc
	endbr64
	pushq	%r12
	.cfi_def_cfa_offset 16
	.cfi_offset 12, -16
	movq	%rsi, %r12
	movl	$32, %esi
	pushq	%rbp
	.cfi_def_cfa_offset 24
	.cfi_offset 6, -24
	movl	%edi, %ebp
	movl	$1, %edi
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -32
	call	calloc@PLT
	testq	%rax, %rax
	je	.L199
	leal	-1(%rbp,%rbp), %edi
	movl	$64, %esi
	movq	%rax, %rbx
	movslq	%edi, %rdi
	call	calloc@PLT
	movq	%rax, 16(%rbx)
	testq	%rax, %rax
	je	.L200
	movq	%r12, %rsi
	movl	%ebp, %edi
	call	_Z24generate_distance_matrixiPK6item_s
	movq	%rax, 24(%rbx)
	testq	%rax, %rax
	je	.L203
	xorl	%eax, %eax
	movl	%ebp, (%rbx)
	movq	%r12, %rsi
	movq	%rbx, %rdi
	movq	%rax, 4(%rbx)
	call	_Z10add_leavesP9cluster_sP6item_s
	testq	%rax, %rax
	je	.L203
	movq	%rbx, %rdi
	call	_Z14merge_clustersP9cluster_s
	jmp	.L198
.L200:
	movq	stderr(%rip), %rdi
	leaq	.LC20(%rip), %rcx
	leaq	.LC3(%rip), %rdx
	xorl	%eax, %eax
	movl	$2, %esi
	call	__fprintf_chk@PLT
	jmp	.L203
.L199:
	movq	stderr(%rip), %rdi
	leaq	.LC21(%rip), %rcx
	leaq	.LC3(%rip), %rdx
	xorl	%eax, %eax
	movl	$2, %esi
	call	__fprintf_chk@PLT
.L204:
	xorl	%ebx, %ebx
	jmp	.L198
.L203:
	movq	%rbx, %rdi
	call	_Z11FreeClusterP9cluster_s
	jmp	.L204
.L202:
.L198:
	movq	%rbx, %rax
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%rbp
	.cfi_def_cfa_offset 16
	popq	%r12
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2052:
	.size	_Z11agglomerateiP6item_s, .-_Z11agglomerateiP6item_s
	.globl	_Z17PrintRootChildernP9cluster_sii
	.type	_Z17PrintRootChildernP9cluster_sii, @function
_Z17PrintRootChildernP9cluster_sii:
.LFB2053:
	.cfi_startproc
	endbr64
	pushq	%r13
	.cfi_def_cfa_offset 16
	.cfi_offset 13, -16
	pushq	%r12
	.cfi_def_cfa_offset 24
	.cfi_offset 12, -24
	xorl	%r12d, %r12d
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -32
	movslq	%esi, %rbx
	salq	$6, %rbx
	subq	$16, %rsp
	.cfi_def_cfa_offset 48
	addq	16(%rdi), %rbx
	cmpl	$2, (%rbx)
	jne	.L212
	movq	32(%rbx), %rax
	movl	%edx, %r13d
	movl	(%rax), %esi
	cmpl	%esi, %edx
	jle	.L214
	movq	%rdi, 8(%rsp)
	movl	$1, %r12d
	call	_Z19print_cluster_itemsP9cluster_si
	movq	8(%rsp), %rdi
.L214:
	movq	32(%rbx), %rax
	movl	4(%rax), %esi
	cmpl	%esi, %r13d
	jle	.L212
	call	_Z19print_cluster_itemsP9cluster_si
	incl	%r12d
.L212:
	addq	$16, %rsp
	.cfi_def_cfa_offset 32
	movl	%r12d, %eax
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%r12
	.cfi_def_cfa_offset 16
	popq	%r13
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2053:
	.size	_Z17PrintRootChildernP9cluster_sii, .-_Z17PrintRootChildernP9cluster_sii
	.globl	_Z13GetKthClusterP9cluster_si
	.type	_Z13GetKthClusterP9cluster_si, @function
_Z13GetKthClusterP9cluster_si:
.LFB2054:
	.cfi_startproc
	endbr64
	testl	%esi, %esi
	jle	.L226
	pushq	%r13
	.cfi_def_cfa_offset 16
	.cfi_offset 13, -16
	pushq	%r12
	.cfi_def_cfa_offset 24
	.cfi_offset 12, -24
	movq	%rdi, %r12
	pushq	%rbp
	.cfi_def_cfa_offset 32
	.cfi_offset 6, -32
	pushq	%rbx
	.cfi_def_cfa_offset 40
	.cfi_offset 3, -40
	pushq	%rdx
	.cfi_def_cfa_offset 48
	movl	(%rdi), %eax
	movl	8(%rdi), %ebp
	cmpl	%eax, %esi
	cmovle	%esi, %eax
	leal	-1(%rbp), %r13d
	subl	%eax, %ebp
	movl	%eax, %ebx
	incl	%ebp
.L220:
	testl	%ebx, %ebx
	je	.L229
	cmpl	%ebp, %r13d
	jge	.L221
	movl	%r13d, %esi
	movq	%r12, %rdi
	call	_Z19print_cluster_itemsP9cluster_si
	movl	$1, %eax
	jmp	.L222
.L221:
	movl	%ebp, %edx
	movl	%r13d, %esi
	movq	%r12, %rdi
	call	_Z17PrintRootChildernP9cluster_sii
.L222:
	subl	%eax, %ebx
	decl	%r13d
	jmp	.L220
.L229:
	popq	%rax
	.cfi_def_cfa_offset 40
	popq	%rbx
	.cfi_def_cfa_offset 32
	popq	%rbp
	.cfi_def_cfa_offset 24
	popq	%r12
	.cfi_def_cfa_offset 16
	popq	%r13
	.cfi_def_cfa_offset 8
	ret
.L226:
	.cfi_restore 3
	.cfi_restore 6
	.cfi_restore 12
	.cfi_restore 13
	ret
	.cfi_endproc
.LFE2054:
	.size	_Z13GetKthClusterP9cluster_si, .-_Z13GetKthClusterP9cluster_si
	.globl	_Z13print_clusterP9cluster_s
	.type	_Z13print_clusterP9cluster_s, @function
_Z13print_clusterP9cluster_s:
.LFB2055:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rdi, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 24
	.cfi_offset 3, -24
	xorl	%ebx, %ebx
	pushq	%rdx
	.cfi_def_cfa_offset 32
.L231:
	cmpl	%ebx, 8(%rbp)
	jle	.L234
	movl	%ebx, %esi
	movq	%rbp, %rdi
	incl	%ebx
	call	_Z18print_cluster_nodeP9cluster_si
	jmp	.L231
.L234:
	popq	%rax
	.cfi_def_cfa_offset 24
	popq	%rbx
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2055:
	.size	_Z13print_clusterP9cluster_s, .-_Z13print_clusterP9cluster_s
	.section	.rodata.str1.1
.LC22:
	.string	"%[^|]| %10f %10f\n"
.LC23:
	.string	"item line"
.LC24:
	.string	"Failed to read %s from file.\n"
	.text
	.globl	_Z10read_itemsiP6item_sP8_IO_FILE
	.type	_Z10read_itemsiP6item_sP8_IO_FILE, @function
_Z10read_itemsiP6item_sP8_IO_FILE:
.LFB2056:
	.cfi_startproc
	endbr64
	pushq	%r14
	.cfi_def_cfa_offset 16
	.cfi_offset 14, -16
	leaq	.LC22(%rip), %r14
	pushq	%r13
	.cfi_def_cfa_offset 24
	.cfi_offset 13, -24
	movq	%rdx, %r13
	pushq	%r12
	.cfi_def_cfa_offset 32
	.cfi_offset 12, -32
	xorl	%r12d, %r12d
	pushq	%rbp
	.cfi_def_cfa_offset 40
	.cfi_offset 6, -40
	movl	%edi, %ebp
	pushq	%rbx
	.cfi_def_cfa_offset 48
	.cfi_offset 3, -48
	leaq	8(%rsi), %rbx
.L236:
	cmpl	%ebp, %r12d
	jge	.L238
	xorl	%eax, %eax
	leaq	-8(%rbx), %rcx
	leaq	-4(%rbx), %r8
	movq	%rbx, %rdx
	movq	%r14, %rsi
	movq	%r13, %rdi
	call	__isoc23_fscanf@PLT
	testl	%eax, %eax
	je	.L237
	addq	$24, %rbx
	incl	%r12d
	jmp	.L236
.L237:
	movq	stderr(%rip), %rdi
	movl	$2, %esi
	xorl	%eax, %eax
	movl	%r12d, %ebp
	leaq	.LC23(%rip), %rcx
	leaq	.LC24(%rip), %rdx
	call	__fprintf_chk@PLT
.L238:
	popq	%rbx
	.cfi_def_cfa_offset 40
	movl	%ebp, %eax
	popq	%rbp
	.cfi_def_cfa_offset 32
	popq	%r12
	.cfi_def_cfa_offset 24
	popq	%r13
	.cfi_def_cfa_offset 16
	popq	%r14
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2056:
	.size	_Z10read_itemsiP6item_sP8_IO_FILE, .-_Z10read_itemsiP6item_sP8_IO_FILE
	.section	.rodata.str1.1
.LC25:
	.string	"%5d\n"
.LC26:
	.string	"number of lines"
.LC27:
	.string	"items array"
	.text
	.globl	_Z17ReadItemsFromFilePP6item_sP8_IO_FILE
	.type	_Z17ReadItemsFromFilePP6item_sP8_IO_FILE, @function
_Z17ReadItemsFromFilePP6item_sP8_IO_FILE:
.LFB2057:
	.cfi_startproc
	endbr64
	pushq	%r12
	.cfi_def_cfa_offset 16
	.cfi_offset 12, -16
	movq	%rsi, %r12
	leaq	.LC25(%rip), %rsi
	pushq	%rbp
	.cfi_def_cfa_offset 24
	.cfi_offset 6, -24
	movq	%rdi, %rbp
	movq	%r12, %rdi
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -32
	subq	$16, %rsp
	.cfi_def_cfa_offset 48
	movq	%fs:40, %rax
	movq	%rax, 8(%rsp)
	xorl	%eax, %eax
	leaq	4(%rsp), %rdx
	call	__isoc23_fscanf@PLT
	testl	%eax, %eax
	jne	.L242
	movq	stderr(%rip), %rdi
	movl	%eax, %ebx
	xorl	%eax, %eax
	leaq	.LC26(%rip), %rcx
	leaq	.LC24(%rip), %rdx
	movl	$2, %esi
	call	__fprintf_chk@PLT
	jmp	.L241
.L242:
	movl	4(%rsp), %ebx
	testl	%ebx, %ebx
	je	.L245
	movl	$24, %esi
	movslq	%ebx, %rdi
	call	calloc@PLT
	movq	%rax, 0(%rbp)
	movq	%rax, %rsi
	testq	%rax, %rax
	je	.L246
	movq	%r12, %rdx
	movl	%ebx, %edi
	call	_Z10read_itemsiP6item_sP8_IO_FILE
	cmpl	%eax, 4(%rsp)
	je	.L245
	movq	%rbp, %rdi
	call	free@PLT
	jmp	.L245
.L246:
	movq	stderr(%rip), %rdi
	leaq	.LC27(%rip), %rcx
	leaq	.LC3(%rip), %rdx
	xorl	%eax, %eax
	movl	$2, %esi
	call	__fprintf_chk@PLT
.L245:
	movl	4(%rsp), %ebx
.L241:
	movq	8(%rsp), %rax
	subq	%fs:40, %rax
	je	.L248
	call	__stack_chk_fail@PLT
.L248:
	addq	$16, %rsp
	.cfi_def_cfa_offset 32
	movl	%ebx, %eax
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%rbp
	.cfi_def_cfa_offset 16
	popq	%r12
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2057:
	.size	_Z17ReadItemsFromFilePP6item_sP8_IO_FILE, .-_Z17ReadItemsFromFilePP6item_sP8_IO_FILE
	.globl	_Z10SetLinkagec
	.type	_Z10SetLinkagec, @function
_Z10SetLinkagec:
.LFB2058:
	.cfi_startproc
	endbr64
	leaq	_Z16complete_linkagePPfPKiS2_ii(%rip), %rax
	cmpb	$99, %dil
	je	.L251
	leaq	_Z16centroid_linkagePPfPKiS2_ii(%rip), %rax
	cmpb	$116, %dil
	je	.L251
	cmpb	$97, %dil
	leaq	_Z15average_linkagePPfPKiS2_ii(%rip), %rax
	leaq	_Z14single_linkagePPfPKiS2_ii(%rip), %rdx
	cmovne	%rdx, %rax
.L251:
	movq	%rax, distance_fptr(%rip)
	ret
	.cfi_endproc
.LFE2058:
	.size	_Z10SetLinkagec, .-_Z10SetLinkagec
	.section	.rodata.str1.1
.LC28:
	.string	"r"
.LC29:
	.string	"Failed to open input file %s.\n"
	.text
	.globl	_Z12ProcessInputPP6item_sPKc
	.type	_Z12ProcessInputPP6item_sPKc, @function
_Z12ProcessInputPP6item_sPKc:
.LFB2059:
	.cfi_startproc
	endbr64
	pushq	%r12
	.cfi_def_cfa_offset 16
	.cfi_offset 12, -16
	movq	%rdi, %r12
	pushq	%rbp
	.cfi_def_cfa_offset 24
	.cfi_offset 6, -24
	movq	%rsi, %rbp
	leaq	.LC28(%rip), %rsi
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -32
	movq	%rbp, %rdi
	call	fopen@PLT
	testq	%rax, %rax
	je	.L256
	movq	%rax, %rbx
	movq	%r12, %rdi
	movq	%rax, %rsi
	call	_Z17ReadItemsFromFilePP6item_sP8_IO_FILE
	movq	%rbx, %rdi
	movl	%eax, %ebp
	call	fclose@PLT
	jmp	.L255
.L256:
	movq	stderr(%rip), %rdi
	movq	%rbp, %rcx
	movl	$2, %esi
	xorl	%eax, %eax
	leaq	.LC29(%rip), %rdx
	xorl	%ebp, %ebp
	call	__fprintf_chk@PLT
.L255:
	movl	%ebp, %eax
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%rbp
	.cfi_def_cfa_offset 16
	popq	%r12
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2059:
	.size	_Z12ProcessInputPP6item_sPKc, .-_Z12ProcessInputPP6item_sPKc
	.section	.rodata.str1.1
.LC30:
	.string	"Usage: %s <input file> <num clusters> <linkage type>\n"
.LC31:
	.string	"CLUSTER HIERARCHY\n--------------------\n"
.LC32:
	.string	"\n\n%d CLUSTERS\n--------------------\n"
	.section	.text.startup,"ax",@progbits
	.globl	main
	.type	main, @function
main:
.LFB2060:
	.cfi_startproc
	endbr64
	pushq	%r12
	.cfi_def_cfa_offset 16
	.cfi_offset 12, -16
	pushq	%rbp
	.cfi_def_cfa_offset 24
	.cfi_offset 6, -24
	movq	%rsi, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -32
	subq	$16, %rsp
	.cfi_def_cfa_offset 48
	movq	%fs:40, %rax
	movq	%rax, 8(%rsp)
	xorl	%eax, %eax
	cmpl	$4, %edi
	je	.L260
	movq	(%rsi), %rcx
	movq	stderr(%rip), %rdi
	leaq	.LC30(%rip), %rdx
	movl	$2, %esi
	call	__fprintf_chk@PLT
	movl	$1, %edi
	call	exit@PLT
.L260:
	xorl	%esi, %esi
	movq	%rsp, %rdi
	movq	%rsi, (%rsp)
	movq	8(%rbp), %rsi
	call	_Z12ProcessInputPP6item_sPKc
	movl	%eax, %ecx
	movq	24(%rbp), %rax
	movsbl	(%rax), %edi
	call	_Z10SetLinkagec
	testl	%ecx, %ecx
	je	.L262
	movq	(%rsp), %r12
	movl	%ecx, %edi
	movq	%r12, %rsi
	call	_Z11agglomerateiP6item_s
	movq	%r12, %rdi
	movq	%rax, %rbx
	call	free@PLT
	testq	%rbx, %rbx
	je	.L262
	movq	stdout(%rip), %rdi
	leaq	.LC31(%rip), %rdx
	movl	$2, %esi
	xorl	%eax, %eax
	call	__fprintf_chk@PLT
	movq	%rbx, %rdi
	call	_Z13print_clusterP9cluster_s
	movq	16(%rbp), %rdi
	call	atoi@PLT
	movq	stdout(%rip), %rdi
	movl	$2, %esi
	leaq	.LC32(%rip), %rdx
	movl	%eax, %ecx
	movl	%eax, %ebp
	xorl	%eax, %eax
	call	__fprintf_chk@PLT
	movq	%rbx, %rdi
	movl	%ebp, %esi
	call	_Z13GetKthClusterP9cluster_si
	movq	%rbx, %rdi
	call	_Z11FreeClusterP9cluster_s
.L262:
	movq	8(%rsp), %rax
	subq	%fs:40, %rax
	je	.L264
	call	__stack_chk_fail@PLT
.L264:
	addq	$16, %rsp
	.cfi_def_cfa_offset 32
	xorl	%eax, %eax
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%rbp
	.cfi_def_cfa_offset 16
	popq	%r12
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2060:
	.size	main, .-main
	.type	_ZL24__sti____cudaRegisterAllv, @function
_ZL24__sti____cudaRegisterAllv:
.LFB2086:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	leaq	_ZL15__fatDeviceText(%rip), %rdi
	call	__cudaRegisterFatBinary@PLT
	movq	%rax, %rdi
	movq	%rax, _ZL20__cudaFatCubinHandle(%rip)
	call	__cudaRegisterFatBinaryEnd@PLT
	leaq	_ZL26__cudaUnregisterBinaryUtilv(%rip), %rdi
	popq	%rdx
	.cfi_def_cfa_offset 8
	jmp	atexit@PLT
	.cfi_endproc
.LFE2086:
	.size	_ZL24__sti____cudaRegisterAllv, .-_ZL24__sti____cudaRegisterAllv
	.section	.init_array,"aw"
	.align 8
	.quad	_ZL24__sti____cudaRegisterAllv
	.section	.nvFatBinSegment,"aw"
	.align 8
	.type	_ZL15__fatDeviceText, @object
	.size	_ZL15__fatDeviceText, 24
_ZL15__fatDeviceText:
	.long	1180844977
	.long	1
	.quad	fatbinData
	.quad	0
	.local	_ZL20__cudaFatCubinHandle
	.comm	_ZL20__cudaFatCubinHandle,8,8
	.globl	distance_fptr
	.bss
	.align 8
	.type	distance_fptr, @object
	.size	distance_fptr, 8
distance_fptr:
	.zero	8
	.section	.rodata.cst4,"aM",@progbits,4
	.align 4
.LC0:
	.long	2139095039
	.ident	"GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:


#include <hip/hip_runtime.h>
#include <float.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NOT_USED  0 // node which is currently not used
#define LEAF_NODE 1 // node which contains a leaf node 
#define A_MERGER  2 // node which contains a merged pair of previous root clusters 
#define MAX_LABEL_LEN 16

#define AVERAGE_LINKAGE  'a' // select average distance
#define CENTROID_LINKAGE 't' // select distance between cluster centroids 
#define COMPLETE_LINKAGE 'c' // select maximum distance 
#define SINGLE_LINKAGE   's' // select minimum distance 

#define alloc_mem(N, T) (T *) calloc(N, sizeof(T))
#define alloc_fail(M) fprintf(stderr,                                   \
                              "Failed to allocate memory for %s.\n", M)
#define read_fail(M) fprintf(stderr, "Failed to read %s from file.\n", M)
#define invalid_node(I) fprintf(stderr,                                 \
                                "Invalid cluster node at index %d.\n", I)

typedef struct cluster_s cluster_t;
typedef struct cluster_node_s ClusterNodeT;
typedef struct neighbour_s neighbour_t;
typedef struct item_s item_t;

float (*distance_fptr)(float **, const int *, const int *, int, int);

typedef struct coord_s {
        float x, y;
} coord_t;

struct cluster_s {
        int num_items; /* number of items that was clustered */
        int num_clusters; /* current number of root clusters */
        int num_nodes; /* number of leaf and merged clusters */
        ClusterNodeT *nodes; /* leaf and merged clusters */
        float **distances; /* distance between leaves */
};

struct cluster_node_s {
        int type; /* type of the cluster node */
        int is_root; /* true if cluster hasn't merged with another */
        int height; /* height of node from the bottom */
        coord_t centroid; /* centroid of this cluster */
        char *label; /* label of a leaf node */
        int *merged; /* indexes of root clusters merged */
        int num_items; /* number of leaf nodes inside new cluster */
        int *items; /* array of leaf nodes indices inside merged clusters */
        neighbour_t *neighbours; /* sorted linked list of distances to roots */
};

struct neighbour_s {
        int target; /* the index of cluster node representing neighbour */
        float distance; /* distance between the nodes */
        neighbour_t *next, *prev; /* linked list entries */
};

struct item_s {
        coord_t coord; /* coordinate of the input data point */
        char label[MAX_LABEL_LEN]; /* label of the input data point */
};

float euclidean_distance(const coord_t *a, const coord_t *b)
{
        return sqrt(pow(a->x - b->x, 2) + pow(a->y - b->y, 2));
}

void fill_euclidean_distances(float **matrix, int num_items,
                              const item_t items[])
{
        for (int i = 0; i < num_items; ++i)
                for (int j = 0; j < num_items; ++j) {
                        matrix[i][j] =
                                euclidean_distance(&(items[i].coord),
                                                   &(items[j].coord));
                        matrix[j][i] = matrix[i][j];
                }
}

float **generate_distance_matrix(int num_items, const item_t items[])
{
        float **matrix = alloc_mem(num_items, float *);
        if (matrix) {
                for (int i = 0; i < num_items; ++i) {
                        matrix[i] = alloc_mem(num_items, float);
                        if (!matrix[i]) {
                                alloc_fail("distance matrix row");
                                num_items = i;
                                for (i = 0; i < num_items; ++i)
                                        free(matrix[i]);
                                free(matrix);
                                matrix = NULL;
                                break;
                        }
                }
                if (matrix)
                        fill_euclidean_distances(matrix, num_items, items);
        } else
                alloc_fail("distance matrix");
        return matrix;
}

float single_linkage(float **distances, const int a[],
                     const int b[], int m, int n)
{
        float min = FLT_MAX, d;
        for (int i = 0; i < m; ++i)
                for (int j = 0; j < n; ++j) {
                        d = distances[a[i]][b[j]];
                        if (d < min)
                                min = d;
                }
        return min;
}

float complete_linkage(float **distances, const int a[],
                       const int b[], int m, int n)
{
        float d, max = 0.0 /* assuming distances are positive */;
        for (int i = 0; i < m; ++i)
                for (int j = 0; j < n; ++j) {
                        d = distances[a[i]][b[j]];
                        if (d > max)
                                max = d;
                }
        return max;
}

float average_linkage(float **distances, const int a[],
                      const int b[], int m, int n)
{
        float total = 0.0;
        for (int i = 0; i < m; ++i)
                for (int j = 0; j < n; ++j)
                        total += distances[a[i]][b[j]];
        return total / (m * n);
}

float centroid_linkage(float **distances, const int a[],
                       const int b[], int m, int n)
{
        return 0; /* empty function */
}

float get_distance(cluster_t *cluster, int index, int target)
{
        /* if both are leaves, just use the distances matrix */
        if (index < cluster->num_items && target < cluster->num_items)
                return cluster->distances[index][target];
        else {
                ClusterNodeT *a = &(cluster->nodes[index]);
                ClusterNodeT *b = &(cluster->nodes[target]);
                if (distance_fptr == centroid_linkage)
                        return euclidean_distance(&(a->centroid),
                                                  &(b->centroid));
                else return distance_fptr(cluster->distances,
                                          a->items, b->items,
                                          a->num_items, b->num_items);
        }
}

void free_neighbours(neighbour_t *node)
{
        neighbour_t *t;
        while (node) {
                t = node->next;
                free(node);
                node = t;
        }
}

void free_cluster_nodes(cluster_t *cluster)
{
        for (int i = 0; i < cluster->num_nodes; ++i) {
                ClusterNodeT *node = &(cluster->nodes[i]);
                if (node->label)
                        free(node->label);
                if (node->merged)
                        free(node->merged);
                if (node->items)
                        free(node->items);
                if (node->neighbours)
                        free_neighbours(node->neighbours);
        }
        free(cluster->nodes);
}

void FreeCluster(cluster_t * cluster)
{
        if (cluster) {
                if (cluster->nodes)
                        free_cluster_nodes(cluster);
                if (cluster->distances) {
                        for (int i = 0; i < cluster->num_items; ++i)
                                free(cluster->distances[i]);
                        free(cluster->distances);
                }
                free(cluster);
        }
}

void insert_before(neighbour_t *current, neighbour_t *neighbours,
                   ClusterNodeT *node)
{
        neighbours->next = current;
        if (current->prev) {
                current->prev->next = neighbours;
                neighbours->prev = current->prev;
        } else
                node->neighbours = neighbours;
        current->prev = neighbours;
}

void InsertAfter(neighbour_t *current, neighbour_t *neighbours)
{
        neighbours->prev = current;
        current->next = neighbours;
}

void insert_sorted(ClusterNodeT *node, neighbour_t *neighbours)
{
        neighbour_t *temp = node->neighbours;
        while (temp->next) {
                if (temp->distance >= neighbours->distance) {
                        insert_before(temp, neighbours, node);
                        return;
                }
                temp = temp->next;
        }
        if (neighbours->distance < temp->distance)
                insert_before(temp, neighbours, node);
        else
                InsertAfter(temp, neighbours);
}


neighbour_t *add_neighbour(cluster_t *cluster, int index, int target)
{
        neighbour_t *neighbour = alloc_mem(1, neighbour_t);
        if (neighbour) {
                neighbour->target = target;
                neighbour->distance = get_distance(cluster, index, target);
                ClusterNodeT *node = &(cluster->nodes[index]);
                if (node->neighbours)
                        insert_sorted(node, neighbour);
                else
                        node->neighbours = neighbour;
        } else
                alloc_fail("neighbour node");
        return neighbour;
}

cluster_t *update_neighbours(cluster_t *cluster, int index)
{
        ClusterNodeT *node = &(cluster->nodes[index]);
        if (node->type == NOT_USED) {
                invalid_node(index);
                cluster = NULL;
        } else {
                int root_clusters_seen = 1, target = index;
                while (root_clusters_seen < cluster->num_clusters) {
                        ClusterNodeT *temp = &(cluster->nodes[--target]);
                        if (temp->type == NOT_USED) {
                                invalid_node(index);
                                cluster = NULL;
                                break;
                        }
                        if (temp->is_root) {
                                ++root_clusters_seen;
                                add_neighbour(cluster, index, target);
                        }
                }
        }
        return cluster;
}

#define init_leaf(cluster, node, item, len)             \
        do {                                            \
                strncpy(node->label, item->label, len); \
                node->centroid = item->coord;           \
                node->type = LEAF_NODE;                 \
                node->is_root = 1;                      \
                node->height = 0;                       \
                node->num_items = 1;                    \
                node->items[0] = cluster->num_nodes++;  \
        } while (0)                                     \

ClusterNodeT *add_leaf(cluster_t *cluster, const item_t *item)
{
        ClusterNodeT *leaf = &(cluster->nodes[cluster->num_nodes]);
        int len = strlen(item->label) + 1;
        leaf->label = alloc_mem(len, char);
        if (leaf->label) {
                leaf->items = alloc_mem(1, int);
                if (leaf->items) {
                        init_leaf(cluster, leaf, item, len);
                        cluster->num_clusters++;
                } else {
                        alloc_fail("node items");
                        free(leaf->label);
                        leaf = NULL;
                }
        } else {
                alloc_fail("node label");
                leaf = NULL;
        }
        return leaf;
}

#undef init_leaf

cluster_t *add_leaves(cluster_t *cluster, item_t *items)
{
        for (int i = 0; i < cluster->num_items; ++i) {
                if (add_leaf(cluster, &items[i]))
                        update_neighbours(cluster, i);
                else {
                        cluster = NULL;
                        break;
                }
        }
        return cluster;
}

void print_cluster_items(cluster_t *cluster, int index)
{
        ClusterNodeT *node = &(cluster->nodes[index]);
        fprintf(stdout, "Items: ");
        if (node->num_items > 0) {
                fprintf(stdout, "%s", cluster->nodes[node->items[0]].label);
                for (int i = 1; i < node->num_items; ++i)
                        fprintf(stdout, ", %s",
                                cluster->nodes[node->items[i]].label);
        }
        fprintf(stdout, "\n");
}

void print_cluster_node(cluster_t *cluster, int index)
{
        ClusterNodeT *node = &(cluster->nodes[index]);
        fprintf(stdout, "Node %d - height: %d, centroid: (%5.3f, %5.3f)\n",
                index, node->height, node->centroid.x, node->centroid.y);
        if (node->label)
                fprintf(stdout, "\tLeaf: %s\n\t", node->label);
        else
                fprintf(stdout, "\tMerged: %d, %d\n\t",
                        node->merged[0], node->merged[1]);
        print_cluster_items(cluster, index);
        fprintf(stdout, "\tNeighbours: ");
        neighbour_t *t = node->neighbours;
        while (t) {
                fprintf(stdout, "\n\t\t%2d: %5.3f", t->target, t->distance);
                t = t->next;
        }
        fprintf(stdout, "\n");
}

void merge_items(cluster_t *cluster, ClusterNodeT *node,
                 ClusterNodeT **to_merge)
{
        node->type = A_MERGER;
        node->is_root = 1;
        node->height = -1;

        /* copy leaf indexes from merged clusters */
        int k = 0, idx;
        coord_t centroid = { .x = 0.0, .y = 0.0 };
        for (int i = 0; i < 2; ++i) {
                ClusterNodeT *t = to_merge[i];
                t->is_root = 0; /* no longer root: merged */
                if (node->height == -1 ||
                    node->height < t->height)
                        node->height = t->height;
                for (int j = 0; j < t->num_items; ++j) {
                        idx = t->items[j];
                        node->items[k++] = idx;
                }
                centroid.x += t->num_items * t->centroid.x;
                centroid.y += t->num_items * t->centroid.y;
        }
        /* calculate centroid */
        node->centroid.x = centroid.x / k;
        node->centroid.y = centroid.y / k;
        node->height++;
}

#define MergeToOne(cluster, to_merge, node, node_idx)         \
        do {                                                    \
                node->num_items = to_merge[0]->num_items +      \
                        to_merge[1]->num_items;                 \
                node->items = alloc_mem(node->num_items, int);  \
                if (node->items) {                              \
                        merge_items(cluster, node, to_merge);   \
                        cluster->num_nodes++;                   \
                        cluster->num_clusters--;                \
                        update_neighbours(cluster, node_idx);   \
                } else {                                        \
                        alloc_fail("array of merged items");    \
                        free(node->merged);                     \
                        node = NULL;                            \
                }                                               \
        } while(0)                                              \

ClusterNodeT *merge(cluster_t *cluster, int first, int second)
{
        int new_idx = cluster->num_nodes;
        ClusterNodeT *node = &(cluster->nodes[new_idx]);
        node->merged = alloc_mem(2, int);
        if (node->merged) {
                ClusterNodeT *to_merge[2] = {
                        &(cluster->nodes[first]),
                        &(cluster->nodes[second])
                };
                node->merged[0] = first;
                node->merged[1] = second;
                MergeToOne(cluster, to_merge, node, new_idx);
        } else {
                alloc_fail("array of merged nodes");
                node = NULL;
        }
        return node;
}

#undef MergeToOne

void FindBestDistanceNeighbour(ClusterNodeT *nodes,
                                  int node_idx,
                                  neighbour_t *neighbour,
                                  float *best_distance,
                                  int *first, int *second)
{
        while (neighbour) {
                if (nodes[neighbour->target].is_root) {
                        if (*first == -1 ||
                            neighbour->distance < *best_distance) {
                                *first = node_idx;
                                *second = neighbour->target;
                                *best_distance = neighbour->distance;
                        }
                        break;
                }
                neighbour = neighbour->next;
        }
}


int FinalClustersToMerge(cluster_t *cluster, int *first, int *second)
{
        float best_distance = 0.0;
        int root_clusters_seen = 0;
        int j = cluster->num_nodes; /* traverse hierarchy top-down */
        *first = -1;
        while (root_clusters_seen < cluster->num_clusters) {
                ClusterNodeT *node = &(cluster->nodes[--j]);
                if (node->type == NOT_USED || !node->is_root)
                        continue;
                ++root_clusters_seen;
                FindBestDistanceNeighbour(cluster->nodes, j,
                                             node->neighbours,
                                             &best_distance,
                                             first, second);
        }
        return *first;
}

cluster_t *merge_clusters(cluster_t *cluster)
{
        int first, second;
        while (cluster->num_clusters > 1) {
                if (FinalClustersToMerge(cluster, &first, &second) != -1)
                        merge(cluster, first, second);
        }
        return cluster;
}

#define init_cluster(cluster, num_items, items)                         \
        do {                                                            \
                cluster->distances =                                    \
                        generate_distance_matrix(num_items, items);     \
                if (!cluster->distances)                                \
                        goto cleanup;                                   \
                cluster->num_items = num_items;                         \
                cluster->num_nodes = 0;                                 \
                cluster->num_clusters = 0;                              \
                if (add_leaves(cluster, items))                         \
                        merge_clusters(cluster);                        \
                else                                                    \
                        goto cleanup;                                   \
        } while (0)                                                     \

cluster_t *agglomerate(int num_items, item_t *items)
{
        cluster_t *cluster = alloc_mem(1, cluster_t);
        if (cluster) {
                cluster->nodes = alloc_mem(2 * num_items - 1, ClusterNodeT);
                if (cluster->nodes)
                        init_cluster(cluster, num_items, items);
                else {
                        alloc_fail("cluster nodes");
                        goto cleanup;
                }
        } else
                alloc_fail("cluster");
        goto done;

cleanup:
        FreeCluster(cluster);
        cluster = NULL;

done:
        return cluster;
}

#undef init_cluster

int PrintRootChildern(cluster_t *cluster, int i, int NodesToDiscard)
{
        ClusterNodeT *node = &(cluster->nodes[i]);
        int RoootsFound = 0;
        if (node->type == A_MERGER) {
                for (int j = 0; j < 2; ++j) {
                        int t = node->merged[j];
                        if (t < NodesToDiscard) {
                                print_cluster_items(cluster, t);
                                ++RoootsFound;
                        }
                }
        }
        return RoootsFound;
}

void GetKthCluster(cluster_t *cluster, int k)
{
        if (k < 1)
                return;
        if (k > cluster->num_items)
                k = cluster->num_items;

        int i = cluster->num_nodes - 1;
        int RoootsFound = 0;
        int NodesToDiscard = cluster->num_nodes - k + 1;
        while (k) {
                if (i < NodesToDiscard) {
                        print_cluster_items(cluster, i);
                        RoootsFound = 1;
                } else
                        RoootsFound = PrintRootChildern(cluster, i,
                                                          NodesToDiscard);
                k -= RoootsFound;
                --i;
        }
}

void print_cluster(cluster_t *cluster)
{
        for (int i = 0; i < cluster->num_nodes; ++i)
                print_cluster_node(cluster, i);
}

int read_items(int count, item_t *items, FILE *f)
{
        for (int i = 0; i < count; ++i) {
                item_t *t = &(items[i]);
                if (fscanf(f, "%[^|]| %10f %10f\n",
                           t->label, &(t->coord.x),
                           &(t->coord.y)))
                        continue;
                read_fail("item line");
                return i;
        }
        return count;
}

int ReadItemsFromFile(item_t **items, FILE *f)
{
        int count, r;
        r = fscanf(f, "%5d\n", &count);
        if (r == 0) {
                read_fail("number of lines");
                return 0;
        }
        if (count) {
                *items = alloc_mem(count, item_t);
                if (*items) {
                        if (read_items(count, *items, f) != count)
                                free(items);
                } else
                        alloc_fail("items array");
        }
        return count;
}

void SetLinkage(char LinkageType)
{
        switch (LinkageType) {
        case AVERAGE_LINKAGE:
                distance_fptr = average_linkage;
                break;
        case COMPLETE_LINKAGE:
                distance_fptr = complete_linkage;
                break;
        case CENTROID_LINKAGE:
                distance_fptr = centroid_linkage;
                break;
        case SINGLE_LINKAGE:
        default: distance_fptr = single_linkage;
        }
}

int ProcessInput(item_t **items, const char *fname)
{
        int count = 0;
        FILE *f = fopen(fname, "r");
        if (f) {
                count = ReadItemsFromFile(items, f);
                fclose(f);
        } else
                fprintf(stderr, "Failed to open input file %s.\n", fname);
        return count;
}

int main(int argc, char **argv)
{
        if (argc != 4) {
                fprintf(stderr, "Usage: %s <input file> <num clusters> "
                        "<linkage type>\n", argv[0]);
                exit(1);
        } else {
                item_t *items = NULL;
                int num_items = ProcessInput(&items, argv[1]);
                SetLinkage(argv[3][0]);
                if (num_items) {
                        cluster_t *cluster = agglomerate(num_items, items);
                        free(items);

                        if (cluster) {
                                fprintf(stdout, "CLUSTER HIERARCHY\n"
                                        "--------------------\n");
                                print_cluster(cluster);

                                int k = atoi(argv[2]);
                                fprintf(stdout, "\n\n%d CLUSTERS\n"
                                        "--------------------\n", k);
                                GetKthCluster(cluster, k);
                                FreeCluster(cluster);
                        }
                }
        }
        return 0;
}

	.text
	.file	"code.hip"
	.globl	_Z18euclidean_distancePK7coord_sS1_ # -- Begin function _Z18euclidean_distancePK7coord_sS1_
	.type	_Z18euclidean_distancePK7coord_sS1_,@function
_Z18euclidean_distancePK7coord_sS1_:    # @_Z18euclidean_distancePK7coord_sS1_
	.cfi_startproc
# %bb.0:
	movss	(%rdi), %xmm0                   # xmm0 = mem[0],zero,zero,zero
	subss	(%rsi), %xmm0
	movss	4(%rdi), %xmm1                  # xmm1 = mem[0],zero,zero,zero
	cvtss2sd	%xmm0, %xmm0
	subss	4(%rsi), %xmm1
	mulsd	%xmm0, %xmm0
	cvtss2sd	%xmm1, %xmm1
	mulsd	%xmm1, %xmm1
	addsd	%xmm0, %xmm1
	xorps	%xmm0, %xmm0
	sqrtsd	%xmm1, %xmm0
	cvtsd2ss	%xmm0, %xmm0
	retq
.Lfunc_end0:
	.size	_Z18euclidean_distancePK7coord_sS1_, .Lfunc_end0-_Z18euclidean_distancePK7coord_sS1_
	.cfi_endproc
                                        # -- End function
	.globl	_Z24fill_euclidean_distancesPPfiPK6item_s # -- Begin function _Z24fill_euclidean_distancesPPfiPK6item_s
	.type	_Z24fill_euclidean_distancesPPfiPK6item_s,@function
_Z24fill_euclidean_distancesPPfiPK6item_s: # @_Z24fill_euclidean_distancesPPfiPK6item_s
	.cfi_startproc
# %bb.0:
	testl	%esi, %esi
	jle	.LBB1_6
# %bb.1:                                # %.preheader.lr.ph
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset %rbx, -16
	movl	%esi, %eax
	leaq	4(%rdx), %rcx
	xorl	%esi, %esi
.LBB1_2:                                # %.lr.ph
                                        # =>This Loop Header: Depth=1
                                        #     Child Loop BB1_3 Depth 2
	leaq	(%rsi,%rsi,2), %r8
	leaq	(%rdx,%r8,8), %r8
	movq	(%rdi,%rsi,8), %r9
	movq	%rcx, %r10
	xorl	%r11d, %r11d
.LBB1_3:                                #   Parent Loop BB1_2 Depth=1
                                        # =>  This Inner Loop Header: Depth=2
	movss	(%r8), %xmm0                    # xmm0 = mem[0],zero,zero,zero
	movss	4(%r8), %xmm1                   # xmm1 = mem[0],zero,zero,zero
	subss	-4(%r10), %xmm0
	cvtss2sd	%xmm0, %xmm0
	subss	(%r10), %xmm1
	mulsd	%xmm0, %xmm0
	cvtss2sd	%xmm1, %xmm1
	mulsd	%xmm1, %xmm1
	addsd	%xmm0, %xmm1
	xorps	%xmm0, %xmm0
	sqrtsd	%xmm1, %xmm0
	cvtsd2ss	%xmm0, %xmm0
	movss	%xmm0, (%r9,%r11,4)
	movq	(%rdi,%r11,8), %rbx
	movss	%xmm0, (%rbx,%rsi,4)
	incq	%r11
	addq	$24, %r10
	cmpq	%r11, %rax
	jne	.LBB1_3
# %bb.4:                                # %._crit_edge
                                        #   in Loop: Header=BB1_2 Depth=1
	incq	%rsi
	cmpq	%rax, %rsi
	jne	.LBB1_2
# %bb.5:
	popq	%rbx
	.cfi_def_cfa_offset 8
	.cfi_restore %rbx
.LBB1_6:                                # %._crit_edge22
	retq
.Lfunc_end1:
	.size	_Z24fill_euclidean_distancesPPfiPK6item_s, .Lfunc_end1-_Z24fill_euclidean_distancesPPfiPK6item_s
	.cfi_endproc
                                        # -- End function
	.globl	_Z24generate_distance_matrixiPK6item_s # -- Begin function _Z24generate_distance_matrixiPK6item_s
	.type	_Z24generate_distance_matrixiPK6item_s,@function
_Z24generate_distance_matrixiPK6item_s: # @_Z24generate_distance_matrixiPK6item_s
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%r13
	.cfi_def_cfa_offset 40
	pushq	%r12
	.cfi_def_cfa_offset 48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	pushq	%rax
	.cfi_def_cfa_offset 64
	.cfi_offset %rbx, -56
	.cfi_offset %r12, -48
	.cfi_offset %r13, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movq	%rsi, %r14
	movl	%edi, %ebp
	movslq	%edi, %r15
	movl	$8, %esi
	movq	%r15, %rdi
	callq	calloc
	testq	%rax, %rax
	je	.LBB2_10
# %bb.1:                                # %.preheader
	movq	%rax, %rbx
	testl	%ebp, %ebp
	jle	.LBB2_9
# %bb.2:                                # %.lr.ph.preheader
	movl	%ebp, %r13d
	xorl	%r12d, %r12d
.LBB2_3:                                # %.lr.ph
                                        # =>This Inner Loop Header: Depth=1
	movl	$4, %esi
	movq	%r15, %rdi
	callq	calloc
	movq	%rax, (%rbx,%r12,8)
	testq	%rax, %rax
	je	.LBB2_4
# %bb.8:                                #   in Loop: Header=BB2_3 Depth=1
	incq	%r12
	cmpq	%r12, %r13
	jne	.LBB2_3
.LBB2_9:                                # %._crit_edge
	movq	%rbx, %rdi
	movl	%ebp, %esi
	movq	%r14, %rdx
	callq	_Z24fill_euclidean_distancesPPfiPK6item_s
.LBB2_11:
	movq	%rbx, %rax
	addq	$8, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%r12
	.cfi_def_cfa_offset 40
	popq	%r13
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.LBB2_10:
	.cfi_def_cfa_offset 64
	movq	stderr(%rip), %rdi
	xorl	%ebx, %ebx
	movl	$.L.str, %esi
	movl	$.L.str.2, %edx
	xorl	%eax, %eax
	callq	fprintf
	jmp	.LBB2_11
.LBB2_4:
	movq	stderr(%rip), %rdi
	movl	$.L.str, %esi
	movl	$.L.str.1, %edx
	xorl	%eax, %eax
	callq	fprintf
	testq	%r12, %r12
	je	.LBB2_7
# %bb.5:                                # %.lr.ph36.preheader
	xorl	%r14d, %r14d
.LBB2_6:                                # %.lr.ph36
                                        # =>This Inner Loop Header: Depth=1
	movq	(%rbx,%r14,8), %rdi
	callq	free
	incq	%r14
	cmpq	%r14, %r12
	jne	.LBB2_6
.LBB2_7:                                # %.thread
	movq	%rbx, %rdi
	callq	free
	xorl	%ebx, %ebx
	jmp	.LBB2_11
.Lfunc_end2:
	.size	_Z24generate_distance_matrixiPK6item_s, .Lfunc_end2-_Z24generate_distance_matrixiPK6item_s
	.cfi_endproc
                                        # -- End function
	.section	.rodata.cst4,"aM",@progbits,4
	.p2align	2, 0x0                          # -- Begin function _Z14single_linkagePPfPKiS2_ii
.LCPI3_0:
	.long	0x7f7fffff                      # float 3.40282347E+38
	.text
	.globl	_Z14single_linkagePPfPKiS2_ii
	.type	_Z14single_linkagePPfPKiS2_ii,@function
_Z14single_linkagePPfPKiS2_ii:          # @_Z14single_linkagePPfPKiS2_ii
	.cfi_startproc
# %bb.0:
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset %rbx, -16
	testl	%ecx, %ecx
	jle	.LBB3_1
# %bb.2:                                # %.preheader.lr.ph
	movl	%ecx, %eax
	movl	%r8d, %ecx
	movss	.LCPI3_0(%rip), %xmm1           # xmm1 = mem[0],zero,zero,zero
	xorl	%r9d, %r9d
.LBB3_3:                                # %.preheader
                                        # =>This Loop Header: Depth=1
                                        #     Child Loop BB3_8 Depth 2
	testl	%r8d, %r8d
	jle	.LBB3_4
# %bb.7:                                # %.lr.ph
                                        #   in Loop: Header=BB3_3 Depth=1
	movslq	(%rsi,%r9,4), %r10
	movq	(%rdi,%r10,8), %r10
	xorl	%r11d, %r11d
.LBB3_8:                                #   Parent Loop BB3_3 Depth=1
                                        # =>  This Inner Loop Header: Depth=2
	movslq	(%rdx,%r11,4), %rbx
	movss	(%r10,%rbx,4), %xmm0            # xmm0 = mem[0],zero,zero,zero
	minss	%xmm1, %xmm0
	incq	%r11
	movaps	%xmm0, %xmm1
	cmpq	%r11, %rcx
	jne	.LBB3_8
	jmp	.LBB3_5
.LBB3_4:                                #   in Loop: Header=BB3_3 Depth=1
	movaps	%xmm1, %xmm0
.LBB3_5:                                # %._crit_edge
                                        #   in Loop: Header=BB3_3 Depth=1
	incq	%r9
	movaps	%xmm0, %xmm1
	cmpq	%rax, %r9
	jne	.LBB3_3
	jmp	.LBB3_6
.LBB3_1:
	movss	.LCPI3_0(%rip), %xmm0           # xmm0 = mem[0],zero,zero,zero
.LBB3_6:                                # %._crit_edge21
	popq	%rbx
	.cfi_def_cfa_offset 8
	retq
.Lfunc_end3:
	.size	_Z14single_linkagePPfPKiS2_ii, .Lfunc_end3-_Z14single_linkagePPfPKiS2_ii
	.cfi_endproc
                                        # -- End function
	.globl	_Z16complete_linkagePPfPKiS2_ii # -- Begin function _Z16complete_linkagePPfPKiS2_ii
	.type	_Z16complete_linkagePPfPKiS2_ii,@function
_Z16complete_linkagePPfPKiS2_ii:        # @_Z16complete_linkagePPfPKiS2_ii
	.cfi_startproc
# %bb.0:
	testl	%ecx, %ecx
	jle	.LBB4_1
# %bb.3:                                # %.preheader.lr.ph
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset %rbx, -16
	movl	%ecx, %eax
	movl	%r8d, %ecx
	xorps	%xmm1, %xmm1
	xorl	%r9d, %r9d
.LBB4_4:                                # %.preheader
                                        # =>This Loop Header: Depth=1
                                        #     Child Loop BB4_9 Depth 2
	testl	%r8d, %r8d
	jle	.LBB4_5
# %bb.8:                                # %.lr.ph
                                        #   in Loop: Header=BB4_4 Depth=1
	movslq	(%rsi,%r9,4), %r10
	movq	(%rdi,%r10,8), %r10
	xorl	%r11d, %r11d
.LBB4_9:                                #   Parent Loop BB4_4 Depth=1
                                        # =>  This Inner Loop Header: Depth=2
	movslq	(%rdx,%r11,4), %rbx
	movss	(%r10,%rbx,4), %xmm0            # xmm0 = mem[0],zero,zero,zero
	maxss	%xmm1, %xmm0
	incq	%r11
	movaps	%xmm0, %xmm1
	cmpq	%r11, %rcx
	jne	.LBB4_9
	jmp	.LBB4_6
.LBB4_5:                                #   in Loop: Header=BB4_4 Depth=1
	movaps	%xmm1, %xmm0
.LBB4_6:                                # %._crit_edge
                                        #   in Loop: Header=BB4_4 Depth=1
	incq	%r9
	movaps	%xmm0, %xmm1
	cmpq	%rax, %r9
	jne	.LBB4_4
# %bb.7:
	popq	%rbx
	.cfi_def_cfa_offset 8
	.cfi_restore %rbx
	retq
.LBB4_1:
	xorps	%xmm0, %xmm0
	retq
.Lfunc_end4:
	.size	_Z16complete_linkagePPfPKiS2_ii, .Lfunc_end4-_Z16complete_linkagePPfPKiS2_ii
	.cfi_endproc
                                        # -- End function
	.globl	_Z15average_linkagePPfPKiS2_ii  # -- Begin function _Z15average_linkagePPfPKiS2_ii
	.type	_Z15average_linkagePPfPKiS2_ii,@function
_Z15average_linkagePPfPKiS2_ii:         # @_Z15average_linkagePPfPKiS2_ii
	.cfi_startproc
# %bb.0:
	testl	%ecx, %ecx
	jle	.LBB5_1
# %bb.3:                                # %.preheader.lr.ph
	pushq	%r14
	.cfi_def_cfa_offset 16
	pushq	%rbx
	.cfi_def_cfa_offset 24
	.cfi_offset %rbx, -24
	.cfi_offset %r14, -16
	movl	%ecx, %eax
	movl	%r8d, %r9d
	xorps	%xmm0, %xmm0
	xorl	%r10d, %r10d
.LBB5_4:                                # %.preheader
                                        # =>This Loop Header: Depth=1
                                        #     Child Loop BB5_6 Depth 2
	testl	%r8d, %r8d
	jle	.LBB5_7
# %bb.5:                                # %.lr.ph
                                        #   in Loop: Header=BB5_4 Depth=1
	movslq	(%rsi,%r10,4), %r11
	movq	(%rdi,%r11,8), %r11
	xorl	%ebx, %ebx
.LBB5_6:                                #   Parent Loop BB5_4 Depth=1
                                        # =>  This Inner Loop Header: Depth=2
	movslq	(%rdx,%rbx,4), %r14
	addss	(%r11,%r14,4), %xmm0
	incq	%rbx
	cmpq	%rbx, %r9
	jne	.LBB5_6
.LBB5_7:                                # %._crit_edge
                                        #   in Loop: Header=BB5_4 Depth=1
	incq	%r10
	cmpq	%rax, %r10
	jne	.LBB5_4
# %bb.8:
	popq	%rbx
	.cfi_def_cfa_offset 16
	popq	%r14
	.cfi_def_cfa_offset 8
	.cfi_restore %rbx
	.cfi_restore %r14
	jmp	.LBB5_2
.LBB5_1:
	xorps	%xmm0, %xmm0
.LBB5_2:                                # %._crit_edge21
	imull	%ecx, %r8d
	cvtsi2ss	%r8d, %xmm1
	divss	%xmm1, %xmm0
	retq
.Lfunc_end5:
	.size	_Z15average_linkagePPfPKiS2_ii, .Lfunc_end5-_Z15average_linkagePPfPKiS2_ii
	.cfi_endproc
                                        # -- End function
	.globl	_Z16centroid_linkagePPfPKiS2_ii # -- Begin function _Z16centroid_linkagePPfPKiS2_ii
	.type	_Z16centroid_linkagePPfPKiS2_ii,@function
_Z16centroid_linkagePPfPKiS2_ii:        # @_Z16centroid_linkagePPfPKiS2_ii
	.cfi_startproc
# %bb.0:
	xorps	%xmm0, %xmm0
	retq
.Lfunc_end6:
	.size	_Z16centroid_linkagePPfPKiS2_ii, .Lfunc_end6-_Z16centroid_linkagePPfPKiS2_ii
	.cfi_endproc
                                        # -- End function
	.globl	_Z12get_distanceP9cluster_sii   # -- Begin function _Z12get_distanceP9cluster_sii
	.type	_Z12get_distanceP9cluster_sii,@function
_Z12get_distanceP9cluster_sii:          # @_Z12get_distanceP9cluster_sii
	.cfi_startproc
# %bb.0:
	movl	(%rdi), %ecx
	movslq	%esi, %rax
	cmpl	%esi, %ecx
	jle	.LBB7_3
# %bb.1:
	cmpl	%edx, %ecx
	jle	.LBB7_3
# %bb.2:
	movq	24(%rdi), %rcx
	movq	(%rcx,%rax,8), %rax
	movslq	%edx, %rcx
	movss	(%rax,%rcx,4), %xmm0            # xmm0 = mem[0],zero,zero,zero
	retq
.LBB7_3:
	movq	16(%rdi), %r8
	movslq	%edx, %r9
	movq	distance_fptr(%rip), %r11
	cmpq	$_Z16centroid_linkagePPfPKiS2_ii, %r11
	je	.LBB7_4
# %bb.6:
	movq	24(%rdi), %rdi
	shlq	$6, %rax
	movq	48(%r8,%rax), %rsi
	shlq	$6, %r9
	movq	48(%r8,%r9), %rdx
	movl	40(%r8,%rax), %ecx
	movl	40(%r8,%r9), %r8d
	jmpq	*%r11                           # TAILCALL
.LBB7_4:
	shlq	$6, %rax
	shlq	$6, %r9
	movss	12(%r8,%rax), %xmm0             # xmm0 = mem[0],zero,zero,zero
	movss	16(%r8,%rax), %xmm1             # xmm1 = mem[0],zero,zero,zero
	subss	12(%r8,%r9), %xmm0
	cvtss2sd	%xmm0, %xmm0
	mulsd	%xmm0, %xmm0
	subss	16(%r8,%r9), %xmm1
	cvtss2sd	%xmm1, %xmm1
	mulsd	%xmm1, %xmm1
	addsd	%xmm0, %xmm1
	xorps	%xmm0, %xmm0
	sqrtsd	%xmm1, %xmm0
	cvtsd2ss	%xmm0, %xmm0
	retq
.Lfunc_end7:
	.size	_Z12get_distanceP9cluster_sii, .Lfunc_end7-_Z12get_distanceP9cluster_sii
	.cfi_endproc
                                        # -- End function
	.globl	_Z15free_neighboursP11neighbour_s # -- Begin function _Z15free_neighboursP11neighbour_s
	.type	_Z15free_neighboursP11neighbour_s,@function
_Z15free_neighboursP11neighbour_s:      # @_Z15free_neighboursP11neighbour_s
	.cfi_startproc
# %bb.0:
	testq	%rdi, %rdi
	je	.LBB8_4
# %bb.1:                                # %.lr.ph.preheader
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset %rbx, -16
.LBB8_2:                                # %.lr.ph
                                        # =>This Inner Loop Header: Depth=1
	movq	8(%rdi), %rbx
	callq	free
	movq	%rbx, %rdi
	testq	%rbx, %rbx
	jne	.LBB8_2
# %bb.3:
	popq	%rbx
	.cfi_def_cfa_offset 8
	.cfi_restore %rbx
.LBB8_4:                                # %._crit_edge
	retq
.Lfunc_end8:
	.size	_Z15free_neighboursP11neighbour_s, .Lfunc_end8-_Z15free_neighboursP11neighbour_s
	.cfi_endproc
                                        # -- End function
	.globl	_Z18free_cluster_nodesP9cluster_s # -- Begin function _Z18free_cluster_nodesP9cluster_s
	.type	_Z18free_cluster_nodesP9cluster_s,@function
_Z18free_cluster_nodesP9cluster_s:      # @_Z18free_cluster_nodesP9cluster_s
	.cfi_startproc
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%r12
	.cfi_def_cfa_offset 32
	pushq	%rbx
	.cfi_def_cfa_offset 40
	pushq	%rax
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -40
	.cfi_offset %r12, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	movq	%rdi, %rbx
	cmpl	$0, 8(%rdi)
	jle	.LBB9_11
# %bb.1:                                # %.lr.ph
	xorl	%r14d, %r14d
.LBB9_2:                                # =>This Loop Header: Depth=1
                                        #     Child Loop BB9_9 Depth 2
	movq	16(%rbx), %r15
	movq	%r14, %r12
	shlq	$6, %r12
	movq	24(%r15,%r12), %rdi
	testq	%rdi, %rdi
	je	.LBB9_4
# %bb.3:                                #   in Loop: Header=BB9_2 Depth=1
	callq	free
.LBB9_4:                                #   in Loop: Header=BB9_2 Depth=1
	movq	32(%r15,%r12), %rdi
	testq	%rdi, %rdi
	je	.LBB9_6
# %bb.5:                                #   in Loop: Header=BB9_2 Depth=1
	callq	free
.LBB9_6:                                #   in Loop: Header=BB9_2 Depth=1
	movq	48(%r15,%r12), %rdi
	testq	%rdi, %rdi
	je	.LBB9_8
# %bb.7:                                #   in Loop: Header=BB9_2 Depth=1
	callq	free
.LBB9_8:                                #   in Loop: Header=BB9_2 Depth=1
	movq	56(%r15,%r12), %rdi
	testq	%rdi, %rdi
	je	.LBB9_10
.LBB9_9:                                # %.lr.ph.i
                                        #   Parent Loop BB9_2 Depth=1
                                        # =>  This Inner Loop Header: Depth=2
	movq	8(%rdi), %r15
	callq	free
	movq	%r15, %rdi
	testq	%r15, %r15
	jne	.LBB9_9
.LBB9_10:                               # %_Z15free_neighboursP11neighbour_s.exit
                                        #   in Loop: Header=BB9_2 Depth=1
	incq	%r14
	movslq	8(%rbx), %rax
	cmpq	%rax, %r14
	jl	.LBB9_2
.LBB9_11:                               # %._crit_edge
	movq	16(%rbx), %rdi
	addq	$8, %rsp
	.cfi_def_cfa_offset 40
	popq	%rbx
	.cfi_def_cfa_offset 32
	popq	%r12
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	jmp	free                            # TAILCALL
.Lfunc_end9:
	.size	_Z18free_cluster_nodesP9cluster_s, .Lfunc_end9-_Z18free_cluster_nodesP9cluster_s
	.cfi_endproc
                                        # -- End function
	.globl	_Z11FreeClusterP9cluster_s      # -- Begin function _Z11FreeClusterP9cluster_s
	.type	_Z11FreeClusterP9cluster_s,@function
_Z11FreeClusterP9cluster_s:             # @_Z11FreeClusterP9cluster_s
	.cfi_startproc
# %bb.0:
	testq	%rdi, %rdi
	je	.LBB10_10
# %bb.1:
	pushq	%r14
	.cfi_def_cfa_offset 16
	pushq	%rbx
	.cfi_def_cfa_offset 24
	pushq	%rax
	.cfi_def_cfa_offset 32
	.cfi_offset %rbx, -24
	.cfi_offset %r14, -16
	movq	%rdi, %rbx
	cmpq	$0, 16(%rdi)
	je	.LBB10_3
# %bb.2:
	movq	%rbx, %rdi
	callq	_Z18free_cluster_nodesP9cluster_s
.LBB10_3:
	movq	24(%rbx), %rdi
	testq	%rdi, %rdi
	je	.LBB10_9
# %bb.4:                                # %.preheader
	cmpl	$0, (%rbx)
	jle	.LBB10_8
# %bb.5:                                # %.lr.ph.preheader
	xorl	%r14d, %r14d
.LBB10_6:                               # %.lr.ph
                                        # =>This Inner Loop Header: Depth=1
	movq	24(%rbx), %rax
	movq	(%rax,%r14,8), %rdi
	callq	free
	incq	%r14
	movslq	(%rbx), %rax
	cmpq	%rax, %r14
	jl	.LBB10_6
# %bb.7:                                # %._crit_edge.loopexit
	movq	24(%rbx), %rdi
.LBB10_8:                               # %._crit_edge
	callq	free
.LBB10_9:
	movq	%rbx, %rdi
	addq	$8, %rsp
	.cfi_def_cfa_offset 24
	popq	%rbx
	.cfi_def_cfa_offset 16
	popq	%r14
	.cfi_def_cfa_offset 8
	jmp	free                            # TAILCALL
.LBB10_10:
	.cfi_restore %rbx
	.cfi_restore %r14
	retq
.Lfunc_end10:
	.size	_Z11FreeClusterP9cluster_s, .Lfunc_end10-_Z11FreeClusterP9cluster_s
	.cfi_endproc
                                        # -- End function
	.globl	_Z13insert_beforeP11neighbour_sS0_P14cluster_node_s # -- Begin function _Z13insert_beforeP11neighbour_sS0_P14cluster_node_s
	.type	_Z13insert_beforeP11neighbour_sS0_P14cluster_node_s,@function
_Z13insert_beforeP11neighbour_sS0_P14cluster_node_s: # @_Z13insert_beforeP11neighbour_sS0_P14cluster_node_s
	.cfi_startproc
# %bb.0:
	movq	%rdi, 8(%rsi)
	movq	16(%rdi), %rax
	testq	%rax, %rax
	je	.LBB11_2
# %bb.1:
	movq	%rsi, 8(%rax)
	movq	%rax, 16(%rsi)
	jmp	.LBB11_3
.LBB11_2:
	movq	%rsi, 56(%rdx)
.LBB11_3:
	movq	%rsi, 16(%rdi)
	retq
.Lfunc_end11:
	.size	_Z13insert_beforeP11neighbour_sS0_P14cluster_node_s, .Lfunc_end11-_Z13insert_beforeP11neighbour_sS0_P14cluster_node_s
	.cfi_endproc
                                        # -- End function
	.globl	_Z11InsertAfterP11neighbour_sS0_ # -- Begin function _Z11InsertAfterP11neighbour_sS0_
	.type	_Z11InsertAfterP11neighbour_sS0_,@function
_Z11InsertAfterP11neighbour_sS0_:       # @_Z11InsertAfterP11neighbour_sS0_
	.cfi_startproc
# %bb.0:
	movq	%rdi, 16(%rsi)
	movq	%rsi, 8(%rdi)
	retq
.Lfunc_end12:
	.size	_Z11InsertAfterP11neighbour_sS0_, .Lfunc_end12-_Z11InsertAfterP11neighbour_sS0_
	.cfi_endproc
                                        # -- End function
	.globl	_Z13insert_sortedP14cluster_node_sP11neighbour_s # -- Begin function _Z13insert_sortedP14cluster_node_sP11neighbour_s
	.type	_Z13insert_sortedP14cluster_node_sP11neighbour_s,@function
_Z13insert_sortedP14cluster_node_sP11neighbour_s: # @_Z13insert_sortedP14cluster_node_sP11neighbour_s
	.cfi_startproc
# %bb.0:
	movq	56(%rdi), %rcx
.LBB13_1:                               # =>This Inner Loop Header: Depth=1
	movq	%rcx, %rax
	movq	8(%rcx), %rcx
	testq	%rcx, %rcx
	je	.LBB13_5
# %bb.2:                                #   in Loop: Header=BB13_1 Depth=1
	movss	4(%rax), %xmm0                  # xmm0 = mem[0],zero,zero,zero
	ucomiss	4(%rsi), %xmm0
	jb	.LBB13_1
	jmp	.LBB13_3
.LBB13_5:
	movss	4(%rax), %xmm0                  # xmm0 = mem[0],zero,zero,zero
	ucomiss	4(%rsi), %xmm0
	jbe	.LBB13_6
.LBB13_3:
	movq	%rax, 8(%rsi)
	movq	16(%rax), %rcx
	addq	$16, %rax
	testq	%rcx, %rcx
	je	.LBB13_8
# %bb.4:
	movq	%rsi, 8(%rcx)
	movq	%rcx, 16(%rsi)
	jmp	.LBB13_7
.LBB13_8:
	movq	%rsi, 56(%rdi)
	jmp	.LBB13_7
.LBB13_6:
	movq	%rax, 16(%rsi)
	addq	$8, %rax
.LBB13_7:                               # %_Z13insert_beforeP11neighbour_sS0_P14cluster_node_s.exit
	movq	%rsi, (%rax)
	retq
.Lfunc_end13:
	.size	_Z13insert_sortedP14cluster_node_sP11neighbour_s, .Lfunc_end13-_Z13insert_sortedP14cluster_node_sP11neighbour_s
	.cfi_endproc
                                        # -- End function
	.globl	_Z13add_neighbourP9cluster_sii  # -- Begin function _Z13add_neighbourP9cluster_sii
	.type	_Z13add_neighbourP9cluster_sii,@function
_Z13add_neighbourP9cluster_sii:         # @_Z13add_neighbourP9cluster_sii
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%rbx
	.cfi_def_cfa_offset 40
	pushq	%rax
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movl	%edx, %r15d
	movl	%esi, %ebp
	movq	%rdi, %r14
	movl	$1, %edi
	movl	$24, %esi
	callq	calloc
	movq	%rax, %rbx
	testq	%rax, %rax
	je	.LBB14_4
# %bb.1:
	movl	%r15d, (%rbx)
	movq	%r14, %rdi
	movl	%ebp, %esi
	movl	%r15d, %edx
	callq	_Z12get_distanceP9cluster_sii
	movss	%xmm0, 4(%rbx)
	movq	16(%r14), %rdi
	movslq	%ebp, %rax
	shlq	$6, %rax
	cmpq	$0, 56(%rdi,%rax)
	je	.LBB14_3
# %bb.2:
	addq	%rax, %rdi
	movq	%rbx, %rsi
	callq	_Z13insert_sortedP14cluster_node_sP11neighbour_s
	jmp	.LBB14_5
.LBB14_3:
	addq	%rdi, %rax
	addq	$56, %rax
	movq	%rbx, (%rax)
.LBB14_5:
	movq	%rbx, %rax
	addq	$8, %rsp
	.cfi_def_cfa_offset 40
	popq	%rbx
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.LBB14_4:
	.cfi_def_cfa_offset 48
	movq	stderr(%rip), %rdi
	movl	$.L.str, %esi
	movl	$.L.str.3, %edx
	xorl	%eax, %eax
	callq	fprintf
	jmp	.LBB14_5
.Lfunc_end14:
	.size	_Z13add_neighbourP9cluster_sii, .Lfunc_end14-_Z13add_neighbourP9cluster_sii
	.cfi_endproc
                                        # -- End function
	.globl	_Z17update_neighboursP9cluster_si # -- Begin function _Z17update_neighboursP9cluster_si
	.type	_Z17update_neighboursP9cluster_si,@function
_Z17update_neighboursP9cluster_si:      # @_Z17update_neighboursP9cluster_si
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%r12
	.cfi_def_cfa_offset 40
	pushq	%rbx
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -48
	.cfi_offset %r12, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movl	%esi, %r14d
	movq	16(%rdi), %rax
	movslq	%esi, %r15
	shlq	$6, %r15
	cmpl	$0, (%rax,%r15)
	je	.LBB15_7
# %bb.1:                                # %.preheader
	movq	%rdi, %rbx
	movl	4(%rdi), %eax
	cmpl	$2, %eax
	jl	.LBB15_8
# %bb.2:                                # %.lr.ph.preheader
	leal	-1(%r14), %ebp
	addq	$-60, %r15
	movl	$1, %r12d
.LBB15_3:                               # %.lr.ph
                                        # =>This Inner Loop Header: Depth=1
	movq	16(%rbx), %rcx
	cmpl	$0, -4(%rcx,%r15)
	je	.LBB15_7
# %bb.4:                                #   in Loop: Header=BB15_3 Depth=1
	cmpl	$0, (%rcx,%r15)
	je	.LBB15_6
# %bb.5:                                #   in Loop: Header=BB15_3 Depth=1
	incl	%r12d
	movq	%rbx, %rdi
	movl	%r14d, %esi
	movl	%ebp, %edx
	callq	_Z13add_neighbourP9cluster_sii
	movl	4(%rbx), %eax
.LBB15_6:                               #   in Loop: Header=BB15_3 Depth=1
	decl	%ebp
	addq	$-64, %r15
	cmpl	%eax, %r12d
	jl	.LBB15_3
.LBB15_8:                               # %.loopexit
	movq	%rbx, %rax
	popq	%rbx
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.LBB15_7:                               # %.loopexit.sink.split
	.cfi_def_cfa_offset 48
	movq	stderr(%rip), %rdi
	xorl	%ebx, %ebx
	movl	$.L.str.4, %esi
	movl	%r14d, %edx
	xorl	%eax, %eax
	callq	fprintf
	jmp	.LBB15_8
.Lfunc_end15:
	.size	_Z17update_neighboursP9cluster_si, .Lfunc_end15-_Z17update_neighboursP9cluster_si
	.cfi_endproc
                                        # -- End function
	.globl	_Z8add_leafP9cluster_sPK6item_s # -- Begin function _Z8add_leafP9cluster_sPK6item_s
	.type	_Z8add_leafP9cluster_sPK6item_s,@function
_Z8add_leafP9cluster_sPK6item_s:        # @_Z8add_leafP9cluster_sPK6item_s
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%r13
	.cfi_def_cfa_offset 40
	pushq	%r12
	.cfi_def_cfa_offset 48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	subq	$24, %rsp
	.cfi_def_cfa_offset 80
	.cfi_offset %rbx, -56
	.cfi_offset %r12, -48
	.cfi_offset %r13, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movq	%rsi, %rbp
	movq	%rdi, %rbx
	movq	16(%rdi), %r15
	movslq	8(%rdi), %r12
	shlq	$6, %r12
	leaq	8(%rsi), %rdi
	movq	%rdi, 16(%rsp)                  # 8-byte Spill
	callq	strlen
	incl	%eax
	movslq	%eax, %r13
	movl	$1, %esi
	movq	%r13, %rdi
	callq	calloc
	movq	%rax, 24(%r15,%r12)
	testq	%rax, %rax
	je	.LBB16_4
# %bb.1:
	movq	%rax, %r14
	movq	%rbp, 8(%rsp)                   # 8-byte Spill
	movl	$1, %edi
	movl	$4, %esi
	callq	calloc
	movq	%rax, 48(%r15,%r12)
	testq	%rax, %rax
	je	.LBB16_3
# %bb.2:
	movq	%rax, %rbp
	leaq	(%r15,%r12), %rax
	movq	%r14, %rdi
	movq	%rax, %r14
	movq	16(%rsp), %rsi                  # 8-byte Reload
	movq	%r13, %rdx
	callq	strncpy
	movq	8(%rsp), %rax                   # 8-byte Reload
	movq	(%rax), %rax
	movq	%rax, 12(%r15,%r12)
	movl	$1, %eax
	movl	%eax, (%r14)
	movq	$1, 4(%r15,%r12)
	movl	%eax, 40(%r15,%r12)
	movl	8(%rbx), %eax
	leal	1(%rax), %ecx
	movl	%ecx, 8(%rbx)
	movl	%eax, (%rbp)
	incl	4(%rbx)
.LBB16_5:
	movq	%r14, %rax
	addq	$24, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%r12
	.cfi_def_cfa_offset 40
	popq	%r13
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.LBB16_4:
	.cfi_def_cfa_offset 80
	movq	stderr(%rip), %rdi
	xorl	%r14d, %r14d
	movl	$.L.str, %esi
	movl	$.L.str.6, %edx
	xorl	%eax, %eax
	callq	fprintf
	jmp	.LBB16_5
.LBB16_3:
	leaq	(%r15,%r12), %rbx
	addq	$24, %rbx
	movq	stderr(%rip), %rdi
	xorl	%r14d, %r14d
	movl	$.L.str, %esi
	movl	$.L.str.5, %edx
	xorl	%eax, %eax
	callq	fprintf
	movq	(%rbx), %rdi
	callq	free
	jmp	.LBB16_5
.Lfunc_end16:
	.size	_Z8add_leafP9cluster_sPK6item_s, .Lfunc_end16-_Z8add_leafP9cluster_sPK6item_s
	.cfi_endproc
                                        # -- End function
	.globl	_Z10add_leavesP9cluster_sP6item_s # -- Begin function _Z10add_leavesP9cluster_sP6item_s
	.type	_Z10add_leavesP9cluster_sP6item_s,@function
_Z10add_leavesP9cluster_sP6item_s:      # @_Z10add_leavesP9cluster_sP6item_s
	.cfi_startproc
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset %rbx, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	movq	%rdi, %rbx
	cmpl	$0, (%rdi)
	jle	.LBB17_5
# %bb.1:                                # %.lr.ph.preheader
	movq	%rsi, %r14
	xorl	%r15d, %r15d
.LBB17_2:                               # %.lr.ph
                                        # =>This Inner Loop Header: Depth=1
	movq	%rbx, %rdi
	movq	%r14, %rsi
	callq	_Z8add_leafP9cluster_sPK6item_s
	testq	%rax, %rax
	je	.LBB17_3
# %bb.4:                                #   in Loop: Header=BB17_2 Depth=1
	movq	%rbx, %rdi
	movl	%r15d, %esi
	callq	_Z17update_neighboursP9cluster_si
	incq	%r15
	movslq	(%rbx), %rax
	addq	$24, %r14
	cmpq	%rax, %r15
	jl	.LBB17_2
	jmp	.LBB17_5
.LBB17_3:
	xorl	%ebx, %ebx
.LBB17_5:                               # %._crit_edge
	movq	%rbx, %rax
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	retq
.Lfunc_end17:
	.size	_Z10add_leavesP9cluster_sP6item_s, .Lfunc_end17-_Z10add_leavesP9cluster_sP6item_s
	.cfi_endproc
                                        # -- End function
	.globl	_Z19print_cluster_itemsP9cluster_si # -- Begin function _Z19print_cluster_itemsP9cluster_si
	.type	_Z19print_cluster_itemsP9cluster_si,@function
_Z19print_cluster_itemsP9cluster_si:    # @_Z19print_cluster_itemsP9cluster_si
	.cfi_startproc
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%r12
	.cfi_def_cfa_offset 32
	pushq	%rbx
	.cfi_def_cfa_offset 40
	pushq	%rax
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -40
	.cfi_offset %r12, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	movq	%rdi, %rbx
	movq	16(%rdi), %r15
	movslq	%esi, %r12
	movq	stdout(%rip), %rcx
	movl	$.L.str.7, %edi
	movl	$7, %esi
	movl	$1, %edx
	callq	fwrite@PLT
	shlq	$6, %r12
	cmpl	$0, 40(%r15,%r12)
	jle	.LBB18_4
# %bb.1:
	leaq	(%r15,%r12), %r14
	addq	$40, %r14
	movq	stdout(%rip), %rsi
	movq	16(%rbx), %rax
	movq	8(%r14), %rcx
	movslq	(%rcx), %rcx
	shlq	$6, %rcx
	movq	24(%rax,%rcx), %rdi
	callq	fputs@PLT
	cmpl	$2, (%r14)
	jl	.LBB18_4
# %bb.2:                                # %.lr.ph.preheader
	addq	%r12, %r15
	addq	$48, %r15
	movl	$1, %r12d
.LBB18_3:                               # %.lr.ph
                                        # =>This Inner Loop Header: Depth=1
	movq	stdout(%rip), %rdi
	movq	16(%rbx), %rax
	movq	(%r15), %rcx
	movslq	(%rcx,%r12,4), %rcx
	shlq	$6, %rcx
	movq	24(%rax,%rcx), %rdx
	movl	$.L.str.9, %esi
	xorl	%eax, %eax
	callq	fprintf
	incq	%r12
	movslq	(%r14), %rax
	cmpq	%rax, %r12
	jl	.LBB18_3
.LBB18_4:                               # %.loopexit
	movq	stdout(%rip), %rsi
	movl	$10, %edi
	addq	$8, %rsp
	.cfi_def_cfa_offset 40
	popq	%rbx
	.cfi_def_cfa_offset 32
	popq	%r12
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	jmp	fputc@PLT                       # TAILCALL
.Lfunc_end18:
	.size	_Z19print_cluster_itemsP9cluster_si, .Lfunc_end18-_Z19print_cluster_itemsP9cluster_si
	.cfi_endproc
                                        # -- End function
	.globl	_Z18print_cluster_nodeP9cluster_si # -- Begin function _Z18print_cluster_nodeP9cluster_si
	.type	_Z18print_cluster_nodeP9cluster_si,@function
_Z18print_cluster_nodeP9cluster_si:     # @_Z18print_cluster_nodeP9cluster_si
	.cfi_startproc
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%r12
	.cfi_def_cfa_offset 32
	pushq	%rbx
	.cfi_def_cfa_offset 40
	pushq	%rax
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -40
	.cfi_offset %r12, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	movl	%esi, %ebx
	movq	%rdi, %r14
	movq	16(%rdi), %r15
	movslq	%esi, %rdx
	movq	stdout(%rip), %rdi
	movq	%rdx, %r12
	shlq	$6, %r12
	movl	8(%r15,%r12), %ecx
	cvtss2sd	12(%r15,%r12), %xmm0
	cvtss2sd	16(%r15,%r12), %xmm1
	movl	$.L.str.11, %esi
                                        # kill: def $edx killed $edx killed $rdx
	movb	$2, %al
	callq	fprintf
	movq	24(%r15,%r12), %rdx
	movq	stdout(%rip), %rdi
	testq	%rdx, %rdx
	je	.LBB19_2
# %bb.1:
	movl	$.L.str.12, %esi
	xorl	%eax, %eax
	callq	fprintf
	jmp	.LBB19_3
.LBB19_2:
	movq	32(%r15,%r12), %rax
	movl	(%rax), %edx
	movl	4(%rax), %ecx
	movl	$.L.str.13, %esi
	xorl	%eax, %eax
	callq	fprintf
.LBB19_3:
	movq	%r14, %rdi
	movl	%ebx, %esi
	callq	_Z19print_cluster_itemsP9cluster_si
	movq	stdout(%rip), %rcx
	movl	$.L.str.14, %edi
	movl	$13, %esi
	movl	$1, %edx
	callq	fwrite@PLT
	movq	56(%r15,%r12), %rbx
.LBB19_5:                               # %.lr.ph
                                        # =>This Inner Loop Header: Depth=1
	testq	%rbx, %rbx
	je	.LBB19_6
# %bb.4:                                # %.lr.ph
                                        #   in Loop: Header=BB19_5 Depth=1
	movq	stdout(%rip), %rdi
	movl	(%rbx), %edx
	xorps	%xmm0, %xmm0
	cvtss2sd	4(%rbx), %xmm0
	movl	$.L.str.15, %esi
	movb	$1, %al
	callq	fprintf
	movq	8(%rbx), %rbx
	jmp	.LBB19_5
.LBB19_6:                               # %._crit_edge
	movq	stdout(%rip), %rsi
	movl	$10, %edi
	addq	$8, %rsp
	.cfi_def_cfa_offset 40
	popq	%rbx
	.cfi_def_cfa_offset 32
	popq	%r12
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	jmp	fputc@PLT                       # TAILCALL
.Lfunc_end19:
	.size	_Z18print_cluster_nodeP9cluster_si, .Lfunc_end19-_Z18print_cluster_nodeP9cluster_si
	.cfi_endproc
                                        # -- End function
	.globl	_Z11merge_itemsP9cluster_sP14cluster_node_sPS2_ # -- Begin function _Z11merge_itemsP9cluster_sP14cluster_node_sPS2_
	.type	_Z11merge_itemsP9cluster_sP14cluster_node_sPS2_,@function
_Z11merge_itemsP9cluster_sP14cluster_node_sPS2_: # @_Z11merge_itemsP9cluster_sP14cluster_node_sPS2_
	.cfi_startproc
# %bb.0:
	movabsq	$4294967298, %rax               # imm = 0x100000002
	movq	%rax, (%rsi)
	movl	$-1, 8(%rsi)
	xorps	%xmm0, %xmm0
	xorl	%edi, %edi
	movb	$1, %al
	xorl	%ecx, %ecx
	xorps	%xmm1, %xmm1
.LBB20_1:                               # =>This Loop Header: Depth=1
                                        #     Child Loop BB20_6 Depth 2
	movq	(%rdx,%rdi,8), %rdi
	movl	$0, 4(%rdi)
	movl	8(%rsi), %r9d
	movl	8(%rdi), %r8d
	cmpl	$-1, %r9d
	je	.LBB20_3
# %bb.2:                                #   in Loop: Header=BB20_1 Depth=1
	cmpl	%r8d, %r9d
	jge	.LBB20_4
.LBB20_3:                               # %._crit_edge54
                                        #   in Loop: Header=BB20_1 Depth=1
	movl	%r8d, 8(%rsi)
.LBB20_4:                               #   in Loop: Header=BB20_1 Depth=1
	movl	40(%rdi), %r8d
	testl	%r8d, %r8d
	jle	.LBB20_8
# %bb.5:                                # %.lr.ph
                                        #   in Loop: Header=BB20_1 Depth=1
	movq	48(%rdi), %r9
	movslq	%ecx, %r10
	shlq	$2, %r10
	addq	48(%rsi), %r10
	xorl	%r11d, %r11d
.LBB20_6:                               #   Parent Loop BB20_1 Depth=1
                                        # =>  This Inner Loop Header: Depth=2
	movl	(%r9,%r11,4), %r8d
	movl	%r8d, (%r10,%r11,4)
	incq	%r11
	movslq	40(%rdi), %r8
	cmpq	%r8, %r11
	jl	.LBB20_6
# %bb.7:                                # %._crit_edge.loopexit
                                        #   in Loop: Header=BB20_1 Depth=1
	addl	%r11d, %ecx
.LBB20_8:                               # %._crit_edge
                                        #   in Loop: Header=BB20_1 Depth=1
	xorps	%xmm2, %xmm2
	cvtsi2ss	%r8d, %xmm2
	movss	12(%rdi), %xmm3                 # xmm3 = mem[0],zero,zero,zero
	mulss	%xmm2, %xmm3
	addss	%xmm3, %xmm1
	mulss	16(%rdi), %xmm2
	addss	%xmm2, %xmm0
	movl	$1, %edi
	testb	$1, %al
	movl	$0, %eax
	jne	.LBB20_1
# %bb.9:
	xorps	%xmm2, %xmm2
	cvtsi2ss	%ecx, %xmm2
	divss	%xmm2, %xmm1
	movss	%xmm1, 12(%rsi)
	divss	%xmm2, %xmm0
	movss	%xmm0, 16(%rsi)
	incl	8(%rsi)
	retq
.Lfunc_end20:
	.size	_Z11merge_itemsP9cluster_sP14cluster_node_sPS2_, .Lfunc_end20-_Z11merge_itemsP9cluster_sP14cluster_node_sPS2_
	.cfi_endproc
                                        # -- End function
	.globl	_Z5mergeP9cluster_sii           # -- Begin function _Z5mergeP9cluster_sii
	.type	_Z5mergeP9cluster_sii,@function
_Z5mergeP9cluster_sii:                  # @_Z5mergeP9cluster_sii
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%r13
	.cfi_def_cfa_offset 40
	pushq	%r12
	.cfi_def_cfa_offset 48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	subq	$24, %rsp
	.cfi_def_cfa_offset 80
	.cfi_offset %rbx, -56
	.cfi_offset %r12, -48
	.cfi_offset %r13, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movl	%edx, %ebp
	movl	%esi, %r12d
	movq	%rdi, %r15
	movslq	8(%rdi), %r14
	movq	16(%rdi), %rbx
	movq	%r14, %r13
	shlq	$6, %r13
	movl	$2, %edi
	movl	$4, %esi
	callq	calloc
	movq	%rax, 32(%rbx,%r13)
	testq	%rax, %rax
	je	.LBB21_4
# %bb.1:
	movslq	%r12d, %rcx
	movl	%ecx, (%rax)
	shlq	$6, %rcx
	leaq	(%rbx,%rcx), %rdx
	movq	%rdx, (%rsp)
	movslq	%ebp, %rdx
	movl	%edx, 4(%rax)
	shlq	$6, %rdx
	leaq	(%rbx,%rdx), %rax
	movq	%rax, 8(%rsp)
	movslq	40(%rbx,%rcx), %rax
	movslq	40(%rbx,%rdx), %rdi
	addq	%rax, %rdi
	movl	%edi, 40(%rbx,%r13)
	movl	$4, %esi
	callq	calloc
	movq	%rax, 48(%rbx,%r13)
	testq	%rax, %rax
	je	.LBB21_3
# %bb.2:
	addq	%r13, %rbx
	movq	%rsp, %rdx
	movq	%rbx, %rsi
	callq	_Z11merge_itemsP9cluster_sP14cluster_node_sPS2_
	incl	8(%r15)
	decl	4(%r15)
	movq	%r15, %rdi
	movl	%r14d, %esi
	callq	_Z17update_neighboursP9cluster_si
.LBB21_5:
	movq	%rbx, %rax
	addq	$24, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%r12
	.cfi_def_cfa_offset 40
	popq	%r13
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.LBB21_4:
	.cfi_def_cfa_offset 80
	movq	stderr(%rip), %rdi
	xorl	%ebx, %ebx
	movl	$.L.str, %esi
	movl	$.L.str.17, %edx
	xorl	%eax, %eax
	callq	fprintf
	jmp	.LBB21_5
.LBB21_3:
	leaq	(%rbx,%r13), %r14
	addq	$32, %r14
	movq	stderr(%rip), %rdi
	xorl	%ebx, %ebx
	movl	$.L.str, %esi
	movl	$.L.str.16, %edx
	xorl	%eax, %eax
	callq	fprintf
	movq	(%r14), %rdi
	callq	free
	jmp	.LBB21_5
.Lfunc_end21:
	.size	_Z5mergeP9cluster_sii, .Lfunc_end21-_Z5mergeP9cluster_sii
	.cfi_endproc
                                        # -- End function
	.globl	_Z25FindBestDistanceNeighbourP14cluster_node_siP11neighbour_sPfPiS4_ # -- Begin function _Z25FindBestDistanceNeighbourP14cluster_node_siP11neighbour_sPfPiS4_
	.type	_Z25FindBestDistanceNeighbourP14cluster_node_siP11neighbour_sPfPiS4_,@function
_Z25FindBestDistanceNeighbourP14cluster_node_siP11neighbour_sPfPiS4_: # @_Z25FindBestDistanceNeighbourP14cluster_node_siP11neighbour_sPfPiS4_
	.cfi_startproc
# %bb.0:
.LBB22_1:                               # =>This Inner Loop Header: Depth=1
	testq	%rdx, %rdx
	je	.LBB22_6
# %bb.2:                                # %.lr.ph
                                        #   in Loop: Header=BB22_1 Depth=1
	movslq	(%rdx), %rax
	shlq	$6, %rax
	cmpl	$0, 4(%rdi,%rax)
	jne	.LBB22_3
# %bb.7:                                #   in Loop: Header=BB22_1 Depth=1
	movq	8(%rdx), %rdx
	jmp	.LBB22_1
.LBB22_3:
	cmpl	$-1, (%r8)
	movss	4(%rdx), %xmm0                  # xmm0 = mem[0],zero,zero,zero
	je	.LBB22_5
# %bb.4:
	movss	(%rcx), %xmm1                   # xmm1 = mem[0],zero,zero,zero
	ucomiss	%xmm0, %xmm1
	jbe	.LBB22_6
.LBB22_5:                               # %._crit_edge
	movl	%esi, (%r8)
	movl	(%rdx), %eax
	movl	%eax, (%r9)
	movss	%xmm0, (%rcx)
.LBB22_6:                               # %.loopexit
	retq
.Lfunc_end22:
	.size	_Z25FindBestDistanceNeighbourP14cluster_node_siP11neighbour_sPfPiS4_, .Lfunc_end22-_Z25FindBestDistanceNeighbourP14cluster_node_siP11neighbour_sPfPiS4_
	.cfi_endproc
                                        # -- End function
	.globl	_Z20FinalClustersToMergeP9cluster_sPiS1_ # -- Begin function _Z20FinalClustersToMergeP9cluster_sPiS1_
	.type	_Z20FinalClustersToMergeP9cluster_sPiS1_,@function
_Z20FinalClustersToMergeP9cluster_sPiS1_: # @_Z20FinalClustersToMergeP9cluster_sPiS1_
	.cfi_startproc
# %bb.0:
	movslq	8(%rdi), %rax
	movl	$-1, (%rsi)
	movl	4(%rdi), %r8d
	testl	%r8d, %r8d
	jle	.LBB23_1
# %bb.2:                                # %.lr.ph
	movq	16(%rdi), %rcx
	xorps	%xmm0, %xmm0
	xorl	%r9d, %r9d
.LBB23_3:                               # =>This Loop Header: Depth=1
                                        #     Child Loop BB23_6 Depth 2
	decq	%rax
	movq	%rax, %r10
	shlq	$6, %r10
	cmpl	$0, (%rcx,%r10)
	je	.LBB23_12
# %bb.4:                                #   in Loop: Header=BB23_3 Depth=1
	cmpl	$0, 4(%rcx,%r10)
	je	.LBB23_12
# %bb.5:                                #   in Loop: Header=BB23_3 Depth=1
	incl	%r9d
	movq	56(%rcx,%r10), %r10
.LBB23_6:                               #   Parent Loop BB23_3 Depth=1
                                        # =>  This Inner Loop Header: Depth=2
	testq	%r10, %r10
	je	.LBB23_12
# %bb.7:                                # %.lr.ph.i
                                        #   in Loop: Header=BB23_6 Depth=2
	movslq	(%r10), %r11
	shlq	$6, %r11
	cmpl	$0, 4(%rcx,%r11)
	jne	.LBB23_8
# %bb.11:                               #   in Loop: Header=BB23_6 Depth=2
	movq	8(%r10), %r10
	jmp	.LBB23_6
.LBB23_8:                               #   in Loop: Header=BB23_3 Depth=1
	cmpl	$-1, (%rsi)
	movss	4(%r10), %xmm1                  # xmm1 = mem[0],zero,zero,zero
	je	.LBB23_10
# %bb.9:                                #   in Loop: Header=BB23_3 Depth=1
	ucomiss	%xmm1, %xmm0
	ja	.LBB23_10
.LBB23_12:                              #   in Loop: Header=BB23_3 Depth=1
	movaps	%xmm0, %xmm1
.LBB23_13:                              # %_Z25FindBestDistanceNeighbourP14cluster_node_siP11neighbour_sPfPiS4_.exit
                                        #   in Loop: Header=BB23_3 Depth=1
	movaps	%xmm1, %xmm0
	cmpl	%r8d, %r9d
	jl	.LBB23_3
	jmp	.LBB23_14
.LBB23_10:                              # %._crit_edge.i
                                        #   in Loop: Header=BB23_3 Depth=1
	movl	%eax, (%rsi)
	movl	(%r10), %r8d
	movl	%r8d, (%rdx)
	movl	4(%rdi), %r8d
	jmp	.LBB23_13
.LBB23_14:                              # %._crit_edge.loopexit
	movl	(%rsi), %eax
	retq
.LBB23_1:
	movl	$-1, %eax
	retq
.Lfunc_end23:
	.size	_Z20FinalClustersToMergeP9cluster_sPiS1_, .Lfunc_end23-_Z20FinalClustersToMergeP9cluster_sPiS1_
	.cfi_endproc
                                        # -- End function
	.globl	_Z14merge_clustersP9cluster_s   # -- Begin function _Z14merge_clustersP9cluster_s
	.type	_Z14merge_clustersP9cluster_s,@function
_Z14merge_clustersP9cluster_s:          # @_Z14merge_clustersP9cluster_s
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%rbx
	.cfi_def_cfa_offset 40
	pushq	%rax
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movq	%rdi, %rbx
	movl	4(%rdi), %ebp
	cmpl	$2, %ebp
	jl	.LBB24_5
# %bb.1:                                # %.lr.ph.preheader
	leaq	4(%rsp), %r14
	movq	%rsp, %r15
.LBB24_2:                               # %.lr.ph
                                        # =>This Inner Loop Header: Depth=1
	movq	%rbx, %rdi
	movq	%r14, %rsi
	movq	%r15, %rdx
	callq	_Z20FinalClustersToMergeP9cluster_sPiS1_
	cmpl	$-1, %eax
	je	.LBB24_4
# %bb.3:                                #   in Loop: Header=BB24_2 Depth=1
	movl	4(%rsp), %esi
	movl	(%rsp), %edx
	movq	%rbx, %rdi
	callq	_Z5mergeP9cluster_sii
	movl	4(%rbx), %ebp
.LBB24_4:                               #   in Loop: Header=BB24_2 Depth=1
	cmpl	$1, %ebp
	jg	.LBB24_2
.LBB24_5:                               # %._crit_edge
	movq	%rbx, %rax
	addq	$8, %rsp
	.cfi_def_cfa_offset 40
	popq	%rbx
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.Lfunc_end24:
	.size	_Z14merge_clustersP9cluster_s, .Lfunc_end24-_Z14merge_clustersP9cluster_s
	.cfi_endproc
                                        # -- End function
	.globl	_Z11agglomerateiP6item_s        # -- Begin function _Z11agglomerateiP6item_s
	.type	_Z11agglomerateiP6item_s,@function
_Z11agglomerateiP6item_s:               # @_Z11agglomerateiP6item_s
	.cfi_startproc
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset %rbx, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	movq	%rsi, %r14
	movl	%edi, %r15d
	movl	$1, %edi
	movl	$32, %esi
	callq	calloc
	testq	%rax, %rax
	je	.LBB25_5
# %bb.1:
	movq	%rax, %rbx
	leal	-1(,%r15,2), %eax
	movslq	%eax, %rdi
	movl	$64, %esi
	callq	calloc
	movq	%rax, 16(%rbx)
	testq	%rax, %rax
	je	.LBB25_6
# %bb.2:
	movl	%r15d, %edi
	movq	%r14, %rsi
	callq	_Z24generate_distance_matrixiPK6item_s
	movq	%rax, 24(%rbx)
	testq	%rax, %rax
	je	.LBB25_7
# %bb.3:
	movl	%r15d, (%rbx)
	movq	$0, 4(%rbx)
	movq	%rbx, %rdi
	movq	%r14, %rsi
	callq	_Z10add_leavesP9cluster_sP6item_s
	testq	%rax, %rax
	je	.LBB25_7
# %bb.4:
	movq	%rbx, %rdi
	callq	_Z14merge_clustersP9cluster_s
	jmp	.LBB25_8
.LBB25_5:
	movq	stderr(%rip), %rdi
	xorl	%ebx, %ebx
	movl	$.L.str, %esi
	movl	$.L.str.19, %edx
	xorl	%eax, %eax
	callq	fprintf
	jmp	.LBB25_8
.LBB25_6:
	movq	stderr(%rip), %rdi
	movl	$.L.str, %esi
	movl	$.L.str.18, %edx
	xorl	%eax, %eax
	callq	fprintf
.LBB25_7:
	movq	%rbx, %rdi
	callq	_Z11FreeClusterP9cluster_s
	xorl	%ebx, %ebx
.LBB25_8:
	movq	%rbx, %rax
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	retq
.Lfunc_end25:
	.size	_Z11agglomerateiP6item_s, .Lfunc_end25-_Z11agglomerateiP6item_s
	.cfi_endproc
                                        # -- End function
	.globl	_Z17PrintRootChildernP9cluster_sii # -- Begin function _Z17PrintRootChildernP9cluster_sii
	.type	_Z17PrintRootChildernP9cluster_sii,@function
_Z17PrintRootChildernP9cluster_sii:     # @_Z17PrintRootChildernP9cluster_sii
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%r12
	.cfi_def_cfa_offset 40
	pushq	%rbx
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -48
	.cfi_offset %r12, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movq	16(%rdi), %rax
	movslq	%esi, %rcx
	shlq	$6, %rcx
	xorl	%ebp, %ebp
	cmpl	$2, (%rax,%rcx)
	jne	.LBB26_5
# %bb.1:                                # %.preheader
	movl	%edx, %ebx
	movq	%rdi, %r14
	leaq	(%rax,%rcx), %r15
	addq	$32, %r15
	xorl	%eax, %eax
	movb	$1, %r12b
	xorl	%ebp, %ebp
.LBB26_2:                               # =>This Inner Loop Header: Depth=1
	movq	(%r15), %rcx
	movl	(%rcx,%rax,4), %esi
	cmpl	%ebx, %esi
	jge	.LBB26_4
# %bb.3:                                #   in Loop: Header=BB26_2 Depth=1
	movq	%r14, %rdi
	callq	_Z19print_cluster_itemsP9cluster_si
	incl	%ebp
.LBB26_4:                               #   in Loop: Header=BB26_2 Depth=1
	movl	$1, %eax
	testb	$1, %r12b
	movl	$0, %r12d
	jne	.LBB26_2
.LBB26_5:                               # %.loopexit
	movl	%ebp, %eax
	popq	%rbx
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.Lfunc_end26:
	.size	_Z17PrintRootChildernP9cluster_sii, .Lfunc_end26-_Z17PrintRootChildernP9cluster_sii
	.cfi_endproc
                                        # -- End function
	.globl	_Z13GetKthClusterP9cluster_si   # -- Begin function _Z13GetKthClusterP9cluster_si
	.type	_Z13GetKthClusterP9cluster_si,@function
_Z13GetKthClusterP9cluster_si:          # @_Z13GetKthClusterP9cluster_si
	.cfi_startproc
# %bb.0:
	testl	%esi, %esi
	jle	.LBB27_8
# %bb.1:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%rbx
	.cfi_def_cfa_offset 40
	pushq	%rax
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movl	%esi, %ebx
	movq	%rdi, %r14
	movl	(%rdi), %eax
	cmpl	%esi, %eax
	cmovll	%eax, %ebx
	testl	%eax, %eax
	je	.LBB27_7
# %bb.2:                                # %.lr.ph.preheader
	movl	8(%r14), %r15d
	movl	%r15d, %ebp
	subl	%ebx, %ebp
	incl	%ebp
.LBB27_3:                               # %.lr.ph
                                        # =>This Inner Loop Header: Depth=1
	movl	%r15d, %eax
	leal	-1(%rax), %r15d
	movq	%r14, %rdi
	movl	%r15d, %esi
	cmpl	%ebp, %eax
	jle	.LBB27_4
# %bb.5:                                #   in Loop: Header=BB27_3 Depth=1
	movl	%ebp, %edx
	callq	_Z17PrintRootChildernP9cluster_sii
	jmp	.LBB27_6
.LBB27_4:                               #   in Loop: Header=BB27_3 Depth=1
	callq	_Z19print_cluster_itemsP9cluster_si
	movl	$1, %eax
.LBB27_6:                               #   in Loop: Header=BB27_3 Depth=1
	subl	%eax, %ebx
	jne	.LBB27_3
.LBB27_7:
	addq	$8, %rsp
	.cfi_def_cfa_offset 40
	popq	%rbx
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	.cfi_restore %rbx
	.cfi_restore %r14
	.cfi_restore %r15
	.cfi_restore %rbp
.LBB27_8:                               # %.loopexit
	retq
.Lfunc_end27:
	.size	_Z13GetKthClusterP9cluster_si, .Lfunc_end27-_Z13GetKthClusterP9cluster_si
	.cfi_endproc
                                        # -- End function
	.globl	_Z13print_clusterP9cluster_s    # -- Begin function _Z13print_clusterP9cluster_s
	.type	_Z13print_clusterP9cluster_s,@function
_Z13print_clusterP9cluster_s:           # @_Z13print_clusterP9cluster_s
	.cfi_startproc
# %bb.0:
	cmpl	$0, 8(%rdi)
	jle	.LBB28_4
# %bb.1:                                # %.lr.ph.preheader
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%rbx
	.cfi_def_cfa_offset 24
	pushq	%rax
	.cfi_def_cfa_offset 32
	.cfi_offset %rbx, -24
	.cfi_offset %rbp, -16
	movq	%rdi, %rbx
	xorl	%ebp, %ebp
.LBB28_2:                               # %.lr.ph
                                        # =>This Inner Loop Header: Depth=1
	movq	%rbx, %rdi
	movl	%ebp, %esi
	callq	_Z18print_cluster_nodeP9cluster_si
	incl	%ebp
	cmpl	8(%rbx), %ebp
	jl	.LBB28_2
# %bb.3:
	addq	$8, %rsp
	.cfi_def_cfa_offset 24
	popq	%rbx
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	.cfi_restore %rbx
	.cfi_restore %rbp
.LBB28_4:                               # %._crit_edge
	retq
.Lfunc_end28:
	.size	_Z13print_clusterP9cluster_s, .Lfunc_end28-_Z13print_clusterP9cluster_s
	.cfi_endproc
                                        # -- End function
	.globl	_Z10read_itemsiP6item_sP8_IO_FILE # -- Begin function _Z10read_itemsiP6item_sP8_IO_FILE
	.type	_Z10read_itemsiP6item_sP8_IO_FILE,@function
_Z10read_itemsiP6item_sP8_IO_FILE:      # @_Z10read_itemsiP6item_sP8_IO_FILE
	.cfi_startproc
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%r13
	.cfi_def_cfa_offset 32
	pushq	%r12
	.cfi_def_cfa_offset 40
	pushq	%rbx
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -48
	.cfi_offset %r12, -40
	.cfi_offset %r13, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	movl	%edi, %ebx
	testl	%edi, %edi
	jle	.LBB29_1
# %bb.2:                                # %.lr.ph.preheader
	movq	%rdx, %r14
	movq	%rsi, %r15
	movl	%ebx, %r13d
	xorl	%r12d, %r12d
.LBB29_3:                               # %.lr.ph
                                        # =>This Inner Loop Header: Depth=1
	leaq	8(%r15), %rdx
	leaq	4(%r15), %r8
	movl	$.L.str.20, %esi
	movq	%r14, %rdi
	movq	%r15, %rcx
	xorl	%eax, %eax
	callq	__isoc23_fscanf
	testl	%eax, %eax
	je	.LBB29_4
# %bb.5:                                #   in Loop: Header=BB29_3 Depth=1
	incq	%r12
	addq	$24, %r15
	cmpq	%r12, %r13
	jne	.LBB29_3
# %bb.6:                                # %.loopexit.loopexit
	movl	%r13d, %r12d
	jmp	.LBB29_7
.LBB29_1:
	xorl	%r12d, %r12d
.LBB29_7:                               # %.loopexit
	cmpl	%ebx, %r12d
	cmovll	%r12d, %ebx
	movl	%ebx, %eax
	popq	%rbx
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	retq
.LBB29_4:                               # %.thread
	.cfi_def_cfa_offset 48
	movq	stderr(%rip), %rdi
	movl	$.L.str.21, %esi
	movl	$.L.str.22, %edx
	xorl	%eax, %eax
	callq	fprintf
	jmp	.LBB29_7
.Lfunc_end29:
	.size	_Z10read_itemsiP6item_sP8_IO_FILE, .Lfunc_end29-_Z10read_itemsiP6item_sP8_IO_FILE
	.cfi_endproc
                                        # -- End function
	.globl	_Z17ReadItemsFromFilePP6item_sP8_IO_FILE # -- Begin function _Z17ReadItemsFromFilePP6item_sP8_IO_FILE
	.type	_Z17ReadItemsFromFilePP6item_sP8_IO_FILE,@function
_Z17ReadItemsFromFilePP6item_sP8_IO_FILE: # @_Z17ReadItemsFromFilePP6item_sP8_IO_FILE
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%rbx
	.cfi_def_cfa_offset 40
	pushq	%rax
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movq	%rsi, %r14
	movq	%rdi, %rbx
	xorl	%ebp, %ebp
	leaq	4(%rsp), %rdx
	movl	$.L.str.23, %esi
	movq	%r14, %rdi
	xorl	%eax, %eax
	callq	__isoc23_fscanf
	testl	%eax, %eax
	je	.LBB30_1
# %bb.2:
	movslq	4(%rsp), %r15
	testq	%r15, %r15
	je	.LBB30_7
# %bb.3:
	movl	$24, %esi
	movq	%r15, %rdi
	callq	calloc
	movq	%rax, (%rbx)
	testq	%rax, %rax
	je	.LBB30_6
# %bb.4:
	movl	%r15d, %edi
	movq	%rax, %rsi
	movq	%r14, %rdx
	callq	_Z10read_itemsiP6item_sP8_IO_FILE
	movl	%eax, %ebp
	movl	4(%rsp), %r14d
	cmpl	%r14d, %eax
	je	.LBB30_7
# %bb.5:
	movq	%rbx, %rdi
	callq	free
	movl	%r14d, %ebp
.LBB30_7:
	movl	%ebp, %eax
	addq	$8, %rsp
	.cfi_def_cfa_offset 40
	popq	%rbx
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.LBB30_1:
	.cfi_def_cfa_offset 48
	movq	stderr(%rip), %rdi
	xorl	%ebp, %ebp
	movl	$.L.str.21, %esi
	movl	$.L.str.24, %edx
	xorl	%eax, %eax
	callq	fprintf
	jmp	.LBB30_7
.LBB30_6:
	movq	stderr(%rip), %rdi
	movl	$.L.str, %esi
	movl	$.L.str.25, %edx
	xorl	%eax, %eax
	callq	fprintf
	movl	4(%rsp), %ebp
	jmp	.LBB30_7
.Lfunc_end30:
	.size	_Z17ReadItemsFromFilePP6item_sP8_IO_FILE, .Lfunc_end30-_Z17ReadItemsFromFilePP6item_sP8_IO_FILE
	.cfi_endproc
                                        # -- End function
	.globl	_Z10SetLinkagec                 # -- Begin function _Z10SetLinkagec
	.type	_Z10SetLinkagec,@function
_Z10SetLinkagec:                        # @_Z10SetLinkagec
	.cfi_startproc
# %bb.0:
	cmpl	$97, %edi
	je	.LBB31_1
# %bb.2:
	cmpl	$116, %edi
	je	.LBB31_5
# %bb.3:
	cmpl	$99, %edi
	jne	.LBB31_6
# %bb.4:
	movl	$_Z16complete_linkagePPfPKiS2_ii, %eax
	jmp	.LBB31_7
.LBB31_5:
	movl	$_Z16centroid_linkagePPfPKiS2_ii, %eax
	jmp	.LBB31_7
.LBB31_1:
	movl	$_Z15average_linkagePPfPKiS2_ii, %eax
	jmp	.LBB31_7
.LBB31_6:
	movl	$_Z14single_linkagePPfPKiS2_ii, %eax
.LBB31_7:
	movq	%rax, distance_fptr(%rip)
	retq
.Lfunc_end31:
	.size	_Z10SetLinkagec, .Lfunc_end31-_Z10SetLinkagec
	.cfi_endproc
                                        # -- End function
	.globl	_Z12ProcessInputPP6item_sPKc    # -- Begin function _Z12ProcessInputPP6item_sPKc
	.type	_Z12ProcessInputPP6item_sPKc,@function
_Z12ProcessInputPP6item_sPKc:           # @_Z12ProcessInputPP6item_sPKc
	.cfi_startproc
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset %rbx, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	movq	%rsi, %rbx
	movq	%rdi, %r14
	movl	$.L.str.26, %esi
	movq	%rbx, %rdi
	callq	fopen
	testq	%rax, %rax
	je	.LBB32_2
# %bb.1:
	movq	%rax, %r15
	movq	%r14, %rdi
	movq	%rax, %rsi
	callq	_Z17ReadItemsFromFilePP6item_sP8_IO_FILE
	movl	%eax, %ebx
	movq	%r15, %rdi
	callq	fclose
	movl	%ebx, %eax
.LBB32_3:
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	retq
.LBB32_2:
	.cfi_def_cfa_offset 32
	movq	stderr(%rip), %rdi
	movl	$.L.str.27, %esi
	movq	%rbx, %rdx
	xorl	%eax, %eax
	callq	fprintf
	xorl	%eax, %eax
	jmp	.LBB32_3
.Lfunc_end32:
	.size	_Z12ProcessInputPP6item_sPKc, .Lfunc_end32-_Z12ProcessInputPP6item_sPKc
	.cfi_endproc
                                        # -- End function
	.globl	main                            # -- Begin function main
	.type	main,@function
main:                                   # @main
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%rbx
	.cfi_def_cfa_offset 40
	pushq	%rax
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movq	%rsi, %rbx
	cmpl	$4, %edi
	jne	.LBB33_15
# %bb.1:
	movq	%rsp, %rdi
	movq	$0, (%rdi)
	movq	8(%rbx), %rsi
	callq	_Z12ProcessInputPP6item_sPKc
	movq	24(%rbx), %rcx
	movzbl	(%rcx), %ecx
	cmpl	$97, %ecx
	je	.LBB33_2
# %bb.3:
	cmpl	$116, %ecx
	je	.LBB33_6
# %bb.4:
	cmpl	$99, %ecx
	jne	.LBB33_7
# %bb.5:
	movl	$_Z16complete_linkagePPfPKiS2_ii, %ecx
	jmp	.LBB33_8
.LBB33_6:
	movl	$_Z16centroid_linkagePPfPKiS2_ii, %ecx
	jmp	.LBB33_8
.LBB33_2:
	movl	$_Z15average_linkagePPfPKiS2_ii, %ecx
	jmp	.LBB33_8
.LBB33_7:
	movl	$_Z14single_linkagePPfPKiS2_ii, %ecx
.LBB33_8:                               # %_Z10SetLinkagec.exit
	movq	%rcx, distance_fptr(%rip)
	testl	%eax, %eax
	je	.LBB33_14
# %bb.9:
	movq	(%rsp), %r15
	movl	%eax, %edi
	movq	%r15, %rsi
	callq	_Z11agglomerateiP6item_s
	movq	%rax, %r14
	movq	%r15, %rdi
	callq	free
	testq	%r14, %r14
	je	.LBB33_14
# %bb.10:
	movq	stdout(%rip), %rcx
	movl	$.L.str.29, %edi
	movl	$39, %esi
	movl	$1, %edx
	callq	fwrite@PLT
	cmpl	$0, 8(%r14)
	jle	.LBB33_13
# %bb.11:                               # %.lr.ph.i.preheader
	xorl	%ebp, %ebp
.LBB33_12:                              # %.lr.ph.i
                                        # =>This Inner Loop Header: Depth=1
	movq	%r14, %rdi
	movl	%ebp, %esi
	callq	_Z18print_cluster_nodeP9cluster_si
	incl	%ebp
	cmpl	8(%r14), %ebp
	jl	.LBB33_12
.LBB33_13:                              # %_Z13print_clusterP9cluster_s.exit
	movq	16(%rbx), %rdi
	callq	atoi
	movl	%eax, %ebx
	movq	stdout(%rip), %rdi
	movl	$.L.str.30, %esi
	movl	%eax, %edx
	xorl	%eax, %eax
	callq	fprintf
	movq	%r14, %rdi
	movl	%ebx, %esi
	callq	_Z13GetKthClusterP9cluster_si
	movq	%r14, %rdi
	callq	_Z11FreeClusterP9cluster_s
.LBB33_14:
	xorl	%eax, %eax
	addq	$8, %rsp
	.cfi_def_cfa_offset 40
	popq	%rbx
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.LBB33_15:
	.cfi_def_cfa_offset 48
	movq	stderr(%rip), %rdi
	movq	(%rbx), %rdx
	movl	$.L.str.28, %esi
	xorl	%eax, %eax
	callq	fprintf
	movl	$1, %edi
	callq	exit
.Lfunc_end33:
	.size	main, .Lfunc_end33-main
	.cfi_endproc
                                        # -- End function
	.type	distance_fptr,@object           # @distance_fptr
	.bss
	.globl	distance_fptr
	.p2align	3, 0x0
distance_fptr:
	.quad	0
	.size	distance_fptr, 8

	.type	.L.str,@object                  # @.str
	.section	.rodata.str1.1,"aMS",@progbits,1
.L.str:
	.asciz	"Failed to allocate memory for %s.\n"
	.size	.L.str, 35

	.type	.L.str.1,@object                # @.str.1
.L.str.1:
	.asciz	"distance matrix row"
	.size	.L.str.1, 20

	.type	.L.str.2,@object                # @.str.2
.L.str.2:
	.asciz	"distance matrix"
	.size	.L.str.2, 16

	.type	.L.str.3,@object                # @.str.3
.L.str.3:
	.asciz	"neighbour node"
	.size	.L.str.3, 15

	.type	.L.str.4,@object                # @.str.4
.L.str.4:
	.asciz	"Invalid cluster node at index %d.\n"
	.size	.L.str.4, 35

	.type	.L.str.5,@object                # @.str.5
.L.str.5:
	.asciz	"node items"
	.size	.L.str.5, 11

	.type	.L.str.6,@object                # @.str.6
.L.str.6:
	.asciz	"node label"
	.size	.L.str.6, 11

	.type	.L.str.7,@object                # @.str.7
.L.str.7:
	.asciz	"Items: "
	.size	.L.str.7, 8

	.type	.L.str.9,@object                # @.str.9
.L.str.9:
	.asciz	", %s"
	.size	.L.str.9, 5

	.type	.L.str.11,@object               # @.str.11
.L.str.11:
	.asciz	"Node %d - height: %d, centroid: (%5.3f, %5.3f)\n"
	.size	.L.str.11, 48

	.type	.L.str.12,@object               # @.str.12
.L.str.12:
	.asciz	"\tLeaf: %s\n\t"
	.size	.L.str.12, 12

	.type	.L.str.13,@object               # @.str.13
.L.str.13:
	.asciz	"\tMerged: %d, %d\n\t"
	.size	.L.str.13, 18

	.type	.L.str.14,@object               # @.str.14
.L.str.14:
	.asciz	"\tNeighbours: "
	.size	.L.str.14, 14

	.type	.L.str.15,@object               # @.str.15
.L.str.15:
	.asciz	"\n\t\t%2d: %5.3f"
	.size	.L.str.15, 14

	.type	.L.str.16,@object               # @.str.16
.L.str.16:
	.asciz	"array of merged items"
	.size	.L.str.16, 22

	.type	.L.str.17,@object               # @.str.17
.L.str.17:
	.asciz	"array of merged nodes"
	.size	.L.str.17, 22

	.type	.L.str.18,@object               # @.str.18
.L.str.18:
	.asciz	"cluster nodes"
	.size	.L.str.18, 14

	.type	.L.str.19,@object               # @.str.19
.L.str.19:
	.asciz	"cluster"
	.size	.L.str.19, 8

	.type	.L.str.20,@object               # @.str.20
.L.str.20:
	.asciz	"%[^|]| %10f %10f\n"
	.size	.L.str.20, 18

	.type	.L.str.21,@object               # @.str.21
.L.str.21:
	.asciz	"Failed to read %s from file.\n"
	.size	.L.str.21, 30

	.type	.L.str.22,@object               # @.str.22
.L.str.22:
	.asciz	"item line"
	.size	.L.str.22, 10

	.type	.L.str.23,@object               # @.str.23
.L.str.23:
	.asciz	"%5d\n"
	.size	.L.str.23, 5

	.type	.L.str.24,@object               # @.str.24
.L.str.24:
	.asciz	"number of lines"
	.size	.L.str.24, 16

	.type	.L.str.25,@object               # @.str.25
.L.str.25:
	.asciz	"items array"
	.size	.L.str.25, 12

	.type	.L.str.26,@object               # @.str.26
.L.str.26:
	.asciz	"r"
	.size	.L.str.26, 2

	.type	.L.str.27,@object               # @.str.27
.L.str.27:
	.asciz	"Failed to open input file %s.\n"
	.size	.L.str.27, 31

	.type	.L.str.28,@object               # @.str.28
.L.str.28:
	.asciz	"Usage: %s <input file> <num clusters> <linkage type>\n"
	.size	.L.str.28, 54

	.type	.L.str.29,@object               # @.str.29
.L.str.29:
	.asciz	"CLUSTER HIERARCHY\n--------------------\n"
	.size	.L.str.29, 40

	.type	.L.str.30,@object               # @.str.30
.L.str.30:
	.asciz	"\n\n%d CLUSTERS\n--------------------\n"
	.size	.L.str.30, 36

	.type	__hip_cuid_,@object             # @__hip_cuid_
	.bss
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               # 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym _Z14single_linkagePPfPKiS2_ii
	.addrsig_sym _Z16complete_linkagePPfPKiS2_ii
	.addrsig_sym _Z15average_linkagePPfPKiS2_ii
	.addrsig_sym _Z16centroid_linkagePPfPKiS2_ii
	.addrsig_sym __hip_cuid_

	.text
	.p2alignl 7, 3214868480
	.fill 96, 4, 3214868480
	.type	__hip_cuid_,@object             ; @__hip_cuid_
	.section	.bss,"aw",@nobits
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               ; 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_
	.amdgcn_target "amdgcn-amd-amdhsa--gfx1100"
	.amdgpu_metadata
---
amdhsa.kernels:  []
amdhsa.target:   amdgcn-amd-amdhsa--gfx1100
amdhsa.version:
  - 1
  - 2
...

	.end_amdgpu_metadata
