DisjointSetForest.java

//Disjunktne mnozice implementirane kot gozd
 
public class DisjointSetForest implements DisjointSet {
 
  public DisjointSetForest() {
    makenull() ;
  }
 
  public void makenull() {
  }
 
  public DisjointSubset makeset(Object x) {
     DisjointSubset newEl = new DisjointSubset() ;
     newEl.value = x ;
     newEl.noNodes = 1 ;
     newEl.parent = newEl ;
     return newEl ;
  }
 
 
  public DisjointSubset findUnoptimal(DisjointSubset x) {
    if (x == x.parent)
      return x ;
    else return find(x.parent) ;
  }
 
  public DisjointSubset find(DisjointSubset x) {
    if (x == x.parent)
      return x ;
    else {
      x.parent = find(x.parent) ; // prevezava
      return x.parent ;  // in hkrati rezultat
    }
  }
 
  public void union(DisjointSubset a1, DisjointSubset a2) {
    DisjointSubset s1 = find(a1) ;
    DisjointSubset s2 = find(a2) ;
    if (s1.noNodes >= s2.noNodes) {
      s2.parent = s1 ;
      s1.noNodes += s2.noNodes ;
    }
    else {
      s1.parent = s2 ;
      s2.noNodes += s1.noNodes ;
    }
  }
 
  public static boolean equivalent(DisjointSubset s1, DisjointSubset s2) {
  // an example of equivalence function
  // sets are equivalent if they have either even or odd elements
   if (((Integer)s1.value).intValue() % 2 == ((Integer)s2.value).intValue() % 2)
     return true ;
   else return false ;
  }
 
  public static List equivalenceClasses(Set a) {
    DisjointSet dsf = new DisjointSetForest() ;
    List list = new ListLinked() ;
    for (Object iter= a.first() ; ! a.overEnd(iter) ; iter=a.next(iter))
        list.insert(dsf.makeset(a.retrieve(iter))) ;
    boolean joint ;
    DisjointSubset s1, s2 ;
    Object loc1, loc2 ;
    do {
       joint = false ;
       for (loc1 = list.first() ; !list.overEnd(loc1) ; loc1 = list.next(loc1)) {
         s1 = (DisjointSubset) list.retrieve(loc1);
         for (loc2 = list.next(loc1); ! list.overEnd(loc2) ; loc2 = list.next(loc2)) {
            s2 = (DisjointSubset) list.retrieve(loc2);
            if (loc1 != loc2 && equivalent(s1, s2)) {
              joint = true;
              list.delete(loc2);
              list.delete(loc1);
              dsf.union(s1, s2);
              list.insert(dsf.find(s1));
              break ;
           }
         }
         if (joint) break ;
       }
    } while (joint) ;
    return list ;
  }
 
 
  public static void main(String[] args) {
    // DisjointSetForest disset = new DisjointSetForest();
    Set a = new SetLinked() ;
    for (int i = 1 ; i < 10 ; i++)
      a.insert(new Integer(i));
    System.out.print("Original set:");
    a.printSet() ;
    System.out.println("Disjoint sets by odd/even equivalence classes");
    List list = equivalenceClasses(a) ;
    System.out.print("Items (we can count them): ");
    list.printList();
  }
}