Incrementally calculating factorsets (Java class)

Recently I encountered a problem of calculating a factorset, given a set and a binary relationship. If you ask wtf is binary relationship, it is a predicate defined on pairs of elements:

interface BinaryRelationship<X, Y> extends Predicate<Pair<X, Y>> {}

Well, of course Java does not have type variables, so that one cannot interchange these two definitions... poor, poor Java programmers, poor, poor me.

But anyway.

Oh, and if you ask wtf a factorset is, let me introduce.

Definition
A binary relationship R on set A is called reflexive if aRa for all a∈A.

Definition
A binary relationship R on set A is called symmetric if aRb => bRa for all a∈A, b∈A.

Definition
A binary relationship R on set A is called transitive if aRb && bRc => aRc for all a∈A, b∈A, c∈A.

Definition
Given a set A and a reflexive, symmetric, transitive binary relationship R on A, an equivalence class over R is any such subset A1 of A that first, if x∈A1 and y∈A1 then xRy, and second, if x∈A1 and xRy then y∈A1

Definition
Given a set A and a reflexive, symmetric, transitive binary relationship R on A, a factorset A/R is defined as a set of all equivalence classes over R.

Example
Take integer numbers, and let nRm if n - m is divisible by 2. We'll have just two equivalence classes, odd numbers and even numbers. By the way, guess why two equivalence classes never intersect.

Anyway.

One can calculate a factorset even if the relationship is not symmetric, reflexive or transitive. Just produce a symmetric, reflexive transitive closure, and factor over it. The problem is, calculating a transitive closure may be costly. So, for practical reasons, I have implemented factorsets in a non-lazy way. And then I realized that, on some occasions, to provide the necessary relationship, I had to build a set of pairs, and then provide the relationship that checks if a pair is in that set, and then calculate the factorset that transitively closes the relationship. Pretty stupid, why not just do it incrementally?

That's how I got this class:

public static class FactorSet<X> {
  Set<X> set;
  Map<X, Set<X>> equivalenceClasses;

  /**
   * Builds an initial factorset, given the domain set.
   *
   * @param set domain set.
   */
  public FactorSet(Set<X> set) {
    this.set = set;
    equivalenceClasses = new HashMap<X, Set<X>>();
    for (X x : set) {
      equivalenceClasses.put(x, Set(x));
    }
  }

  /**
   * Builds a factorset of a given set, by the transitive closure of a given relationship.
   *
   * @param set base set
   * @param r binary relationship
   */
  public FactorSet(Set<X> set,  BinaryRelationship<X, X> r) {
    this(set);
    factorByRelationship(r);
  }

  /**
   * Given a <code>BinaryRelationship r</code>, merges equivalent classes if they
   * contain elements that are in <code>r</code>.
   *
   * @param r the binary relationship. Does not have to be symmetrical or transitive.
   */
  public void factorByRelationship(BinaryRelationship<X, X> r) {
    for (X x1 : set) {
      for (X x2 : set) {
        if (x1 == x2) {
          continue; // skip same value
        }
        if (equivalenceClasses.get(x1) == equivalenceClasses.get(x2)) {
          continue; // skip same class
        }
        if (r.eval(x1, x2) || r.eval(x2, x1)) {
          merge(x1, x2);
        }
      }
    }
  }

  /**
   * Merges equivalence classes for two elements
   * @param x1 first element
   * @param x2 second element
   */
  public void merge(X x1, X x2) {
    Set<X> class1 = equivalenceClasses.get(x1);
    Set<X> class2 = equivalenceClasses.get(x2);
    Set<X> merged = new HashSet<X>(class1);
    merged.addAll(class2);
    for (X x3 : merged) {
      equivalenceClasses.put(x3, merged);
    }
  }

  /**
   * @return the latest version of factorset built here.
   */
  public Set<Set<X>> factorset() {
    return new HashSet<Set<X>>(equivalenceClasses.values());
  }

  /**
   * @return the function from the domain set to the factorset.
   */
  public Function<X, Set<X>> asFunction() {
    return Functions.forMap(equivalenceClasses);
  }

  /**
   * @return the domain set.
   */
  public Set<X> domain() {
    return set;
  }
}

Neat, right? Look at this unittest:

public void testFactorSet_incremental() {
  Set<Integer> set = Set(1, 2, 3, 4, 5);
  FactorSet<Integer> factorset = new FactorSet<Integer>(set);
  factorset.merge(1, 3);
  factorset.merge(3, 5);
  factorset.merge(4, 2);
  Set<Set<Integer>> expected = Set(Set(1, 3, 5), Set(2, 4));
  assertEquals(expected, factorset.factorset());
}

(Don't get confused by the functional-programming style of set constructors. Just open The Scala Book, they do it everywhere!

If you find a better way to do this thing, please let me know.