/*
 * The Union Find implementation using up-trees.
 */

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include "lib/unionfind.h"
#include "lib/graph.h"
#include "lib/pixel.h"
#include <math.h>

int min(int p1, int p2) {
	if (p1>p2)
		return p2;
	return p1;
}

int max(int p1, int p2) {
	if (p1>p2)
		return p1;
	return p2;
}
/*pixelID root(int x, int y, pixelID parentID[ROWS][COLS]) {
	while ()
} */

/* Find and return the index of the root of the pixel with pixelID idx. */
pixelID up_trees_find(pixelID parentID[ROWS][COLS], unsigned int w, pixelID idx) {
    int x = get_x_coord(idx,w);
    int y = get_y_coord(idx,w);
    if (parentID[y][x] == -1)
    	return get_pixel_id(x,y,idx);
    printf("%d\n",parentID[y][x] );
    int cx = get_x_coord(parentID[y][x],w);
    int cy = get_y_coord(parentID[y][x],w);
    return up_trees_find(parentID, w, get_pixel_id(cx,cy,w));
}

/* Merge the two groups to which pixel p1 and pixel p2 belong. */
void up_trees_union(pixelID parentID[ROWS][COLS], unsigned int w, pixelID p1, pixelID p2) {
    pixelID f1 = min(p1,p2);
    pixelID f2 = max(p1,p2);
    f1 = up_trees_find(parentID, w, f1);
    f2 = up_trees_find(parentID, w, f2);
    int x = get_x_coord(f2,w);
    int y = get_y_coord(f2,w);
    parentID[y][x] = f1;
}

/* Store forest of up-trees in the array parentID, given the graph G. */
void up_trees_new(graph G, pixelID parentID[ROWS][COLS]) {
   for (unsigned y =0; y<(*G).image_height; y++){
   	for (unsigned x =0; x<(*G).image_width; x++) {
    	parentID[y][x] = -1;
   	 }
	}
}

/*
 * Run UNION-FIND, and store the final forest of up-trees in array parentID,
 * where count is a boolean flag indicating whether to print out the count.
 */
void run_union_find(graph G, pixelID parentID[ROWS][COLS], bool count) {
	int calls = 0;
	//test and debug up trees find
	int g = (*G).image_height;
	for (unsigned y = 0; y < (*G).image_height; y++) {
		for (unsigned x = 0; x < (*G).image_width; x++) {
			if (((x+1<(*G).image_width) && (equal_colors((*G).pixels[y][x],(*G).pixels[y][x+1])))) {
				if (up_trees_find(parentID, (*G).image_width , get_pixel_id(x,y,g)) != up_trees_find(parentID, (*G).image_width, get_pixel_id(x+1,y,g) )) {
					up_trees_union(parentID, (*G).image_width, get_pixel_id(x,y,g), get_pixel_id(x+1,y,g));
					calls++;
				}
			}
			if ( (y+1<(*G).image_height) && (equal_colors((*G).pixels[y][x],(*G).pixels[y+1][x]))) {
				if (up_trees_find(parentID, (*G).image_width ,get_pixel_id(x,y,g)) != up_trees_find(parentID, (*G).image_width, get_pixel_id(x,y+1,g)) ) {
					up_trees_union(parentID, (*G).image_width, get_pixel_id(x,y,g), get_pixel_id(x,y+1,g));
					calls++;
				}
			}
		}
	}
	if (count == true)
		 printf("The number of times that the method UNION was called for this image is: %d\n",calls );
    return;
}