// This may look like C code, but it is really -*- C++ -*-

#ifndef _UNIONFIND_H_
#define _UNIONFIND_H_

class UnionFind {

  int *_setID;
  int _numSets;

public:

  /* This data structure is used to determine set membership.  Initially,
     it contains N singleton sets; the setUnion operation can then be used
     to take the union of these sets.  The find() method then returns the
     "ID" for the set containing a particular element.  The ID is somewhat
     arbitrary; nothing should be assumed about it, beyond the fact that
     two elements will have the same ID if they are in the same set, and
     different IDs otherwise. */

  UnionFind(int num_sets);
  ~UnionFind();

  /* Returns the number elements in the UF data structure. */
  int numElements(void);

  /* This function unions the set containing idx1 with the set containing
     idx2. */
  void setUnion(int idx1, int idx2);

  /* This returns the ID of the element with the given index.  idx
     should be between 0 and num_sets - 1. */
  int find(int idx);
  
  /* This restores the data structure to the state in which all of
     the elements are in their own singleton sets. */
  void reset(void);
};

#endif