/*
Copyright (C) 2006 Pedro Felzenszwalb

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
*/

#ifndef DISJOINT_SET
#define DISJOINT_SET

// disjoint-set forests using union-by-rank and path compression (sort of).

typedef struct {
  int rank;
  int p;
  int size;
} uni_elt;
/*
class universe {
public:
  universe(int elements);
  ~universe();
  int find(int x);  
  void join(int x, int y);
  int size(int x) const { return elts[x].size; }
  int num_sets() const { return num; }

private:
  uni_elt *elts;
  int num;
};
*/
typedef struct{

  uni_elt *elts;
  int num;
}universe;

int universe_size(universe *self,int x) { return self->elts[x].size; }

int universe_num_sets(universe *self) { return self->num; }
universe * universe_construct(int elements) {
  universe *self = (universe *)malloc(sizeof(universe));
  self->elts = (uni_elt *)malloc(elements*sizeof(uni_elt));//new uni_elt[elements];
  self->num = elements;
  for (int i = 0; i < elements; i++) {
    self->elts[i].rank = 0;
    self->elts[i].size = 1;
    self->elts[i].p = i;
  }
  return self;
}
void universe_destruct(universe *self){
    free(self->elts);
}  
/*
universe::~universe() {
  delete [] elts;
}
*/
int universe_find(universe *self, int x){
  int y = x;
  while (y != self->elts[y].p)
    y = self->elts[y].p;
  self->elts[x].p = y;
  return y;

}
/*
int universe::find(int x) {
  int y = x;
  while (y != elts[y].p)
    y = elts[y].p;
  elts[x].p = y;
  return y;
}
*/

void universe_join(universe *self,int x, int y){
  if (self->elts[x].rank > self->elts[y].rank) {
    self->elts[y].p = x;
    self->elts[x].size += self->elts[y].size;
  } else {
    self->elts[x].p = y;
    self->elts[y].size += self->elts[x].size;
    if (self->elts[x].rank == self->elts[y].rank)
      self->elts[y].rank++;
  }
  self->num--;
}
/*
void universe::join(int x, int y) {
  if (elts[x].rank > elts[y].rank) {
    elts[y].p = x;
    elts[x].size += elts[y].size;
  } else {
    elts[x].p = y;
    elts[y].size += elts[x].size;
    if (elts[x].rank == elts[y].rank)
      elts[y].rank++;
  }
  num--;
}
*/
#endif