#include <stdlib.h>
#include "UnionFind.h"



static int *nodes = NULL;
static int capacity = 0;

int UnionFindSetup(int cap)
{
    int i;
    if (nodes) free(nodes);
    capacity = cap;
    nodes = malloc(capacity * sizeof *nodes);
    if (nodes == NULL) {
        return -1;
    }
    for (i=0; i < capacity; ++i) {
        nodes[i] = i;
    }
    return 0;
}

void UnionFindDone(void)
{
    free(nodes);
    nodes = NULL;
}


int UnionFindAdd(int n)
{
    if (n < capacity) {
        return 0;
    }
    else {
        int newcap = n+10;
        int *tmp = realloc(nodes, sizeof *nodes * newcap);
        int i;
        if (tmp == NULL) {
            return -1;
        }
        nodes = tmp;
        for (i = capacity; i < newcap; ++i) {
            nodes[i] = i;
        }
        capacity = newcap;
        return 0;
    }
}


void UnionFindJoin(int u, int v)
{
    nodes[UnionFindParent(u)] = UnionFindParent(v);
}


void UnionFindJoinLeastParent(int u, int v)
{
    /* Joins the trees such that the least value is the parent */
    u = UnionFindParent(u);
    v = UnionFindParent(v);
    if (u < v) nodes[v] = u;
    else nodes[u] = v;
}


int UnionFindParent(int n)
{
    while (nodes[n] != n) {
        n = nodes[n];
    }
    return n;
}