/* Insiemi disgiunti */

#include <stdio.h>

typedef struct forest_frame* Forest;

typedef struct node {
	char name;
	int  rank;
	int  father;
} Node;

typedef struct forest_frame {
	int  size;
	Node*  nodearray;
} Forest_Frame;

typedef char* Set; /* trattiamo insiemi di caratteri */

typedef Forest DisjointSets;

/* Prototipi funzioni pubbliche */

DisjointSets Create(Set s);
/* pre: s e' ordinata alfabeticamente senza ripetizioni
   post: ritorna la partizione triviale dell'insieme
   di caratteri rappresentato da s */

void Union(DisjointSets d, char x, char y);
/* pre: x, y sono rappresentanti di due elementi distinti della partizione */
/* rimpiazza in d gli insiemi i cui rappresentanti sono x e y
   con la loro unione */

int Find(DisjointSets d, char x);
/* pre: x e' elemento dell'unione della partizione d
   post: ritorna l'indice del rappresentante dell'elemento di d cui
        x appartiene */

/* Implementazioni */

DisjointSets Create(Set s)
{
	int i; Forest f;
	
	f = (Forest) malloc (sizeof(Forest_Frame));
	f->size = strlen(s);
	f->nodearray = (Node*) malloc (f->size * sizeof(Node));
	for (i = 0; i < f->size; i++) {
		f->nodearray[i].name = s[i];
		f->nodearray[i].rank = 0;
		f->nodearray[i].father = i;
	};
	return f;
}

int DicSearch(char x, Node v[], int i, int j)
/* post: ritorna l'indice di x in v[i..j].name se esiste,
         -1 altrimenti */
{
	int m;

	if (i > j) return -1;
	else {
		m = (i+j) / 2;
		if (v[m].name == x) return m;
		else if (v[m].name < x) return DicSearch(x,v,m+1,j);
		else return DicSearch(x,v,i,m-1);
	}
}
	
void Link(DisjointSets d, int i, int j)
/* effettua l'unione per rango degli alberi con
   radice nei vertici di offset i e j in d->nodearray */
{
	if (d->nodearray[i].rank <= d->nodearray[j].rank) {
		d->nodearray[i].father = j;
		d->nodearray[j].rank++;
	} else d->nodearray[j].father = i;
}

void Union(DisjointSets d, char x, char y)
{
	Link(d, DicSearch(x,d->nodearray,0,d->size),
	        DicSearch(y,d->nodearray,0,d->size));
}

int find_compact(DisjointSets d, int i)
/*  pre:  i e' l'indice di un vertice in d->nodearray
    post: ritorna l'indice della radice cui appartiene
          il vertice di offset i in d->nodearray; effettua la
          compressione del find path */
{
	if (d->nodearray[i].father == i) return i;
	else {
	    d->nodearray[i].father = find_compact(d,d->nodearray[i].father);
	    return d->nodearray[i].father;
	}
}

int Find(DisjointSets d, char x)
{
	int i = DicSearch(x,d->nodearray,0,d->size);
	if (i != -1) return find_compact(d,i);
	else return -1;
}


/* Utilita' */

void WriteForest(Forest f)
{
	int i;
	
	for (i = 0; i < f->size; i++)
		printf("%d: (%c,%d,%d)\n", i,
		                     f->nodearray[i].name,
		                     f->nodearray[i].rank,
		                     f->nodearray[i].father);
	printf("\n");
}

/* eof */