public class EqRel {      
//created with the diagonal relation; can strengthen relation
    
    int size;
    int [][] classes;

    public EqRel(int size)        //linear time
    {
        this.size = size;
        classes = new int[size][1];    
/* This allows the EqRel to live in O(size) space.
   These short rows will be replaced with longer ones as needed.  */
        for (int i = 0; i < size; i++) 
          classes[i][0] = i;
    }

    public boolean related(int x, int y)        //linear time
    {
        for(int i = 0; i < classes[x].length ; i++) 
           if (classes[x][i] == y)
                return true;
        return false;
    }

    public void relate(int x, int y)        //linear time
    {
        int lx = classes[x].length;
        int ly = classes[y].length;
        int i, j, k, row;
        int [] newRow;

        if (related(x, y))
            return;
        newRow = new int[lx + ly];             //allocate new equivalence class
        i = 0;
        j = 0;
        k = 0;

    //copy the classes of x and y into the new class in numerical order 
       while (i < lx && j < ly)
            if (classes[x][i] < classes[y][j])      
                newRow[k++] = classes[x][i++];
            else
                newRow[k++] = classes[y][j++];
        while (i < lx)
            newRow[k++] = classes[x][i++];
        while (j < ly)
            newRow[k++] = classes[y][j++];          
 
        for (k = 0; k < lx + ly; k++) {
            row = newRow[k];
            classes[row] = newRow;   
           //the new class is now the class of each of its members
            }
    }

    public int [] classOf(int x)               //constant time
    {
        return classes[x];
    }

    public int representative(int x)             //constant time
    {
        return (classes[x][0]);
    }

    public int [] repSet(IntCell count, int elementCount)    
  /*Returns a set of class representatives.  The first parameter holds 
the number of representatives.  The second tells the method how many of the 
elements should be considered valid.              linear time          */ 
    {
        boolean [] used = new boolean[elementCount];
        int [] answer = new int[elementCount];
        int theCount = 0;

        for (int i = 0; i < elementCount; i++)
            if (!used[classes[i][0]]) {
                answer[theCount++] = classes[i][0];
                for (int j = 0; j < classes[i].length; j++)
                    used[classes[i][j]] = true;
            }
        count.myInt = theCount;
        return answer;
    }

    public int countClasses(int elementCount)          //linear time
    {
        boolean [] used = new boolean[elementCount];
        int answer = 0;

        for (int i = 0; i < elementCount; i++)
            if (!used[classes[i][0]]) {
                answer++;
                for (int j = 0; j < classes[i].length; j++)
                    used[classes[i][j]] = true;
            }
        return answer;
    }

    void resize(int newSize)           //linear time
    {
        int [][] temp;

        if (newSize <= size)
            return;
        temp = classes;
        classes = new int[newSize][1];
        for (int i = 0; i < size; i++)
            classes[i] = temp[i];
        for (int i = size; i < newSize; i++)
            classes[i][0] = i;
        size = newSize;
    }
} //class EqRel