1   package kiasan.examples.disjsets;
2   
3   // DisjSetsFast class
4   //
5   // CONSTRUCTION: with int representing initial number of sets
6   //
7   // ******************PUBLIC OPERATIONS*********************
8   // void union( root1, root2 ) --> Merge two sets
9   // int find( x )              --> Return set containing x
10  // ******************ERRORS********************************
11  // No error checking is performed
12  
13  /**
14   * Disjoint set class, using union by rank and path compression. Elements in the
15   * set are numbered starting at 0.
16   * 
17   * @author Mark Allen Weiss
18   */
19  public class DisjSetsFast {
20    // Test main; all finds on same output line should be identical
21    public static void main(final String[] args) {
22      final int NumElements = 128;
23      final int NumInSameSet = 16;
24  
25      final DisjSetsFast ds = new DisjSetsFast(NumElements);
26      int set1, set2;
27  
28      for (int k = 1; k < NumInSameSet; k *= 2) {
29        for (int j = 0; j + k < NumElements; j += 2 * k) {
30          set1 = ds.find(j);
31          set2 = ds.find(j + k);
32          ds.union(set1, set2);
33        }
34      }
35  
36      for (int i = 0; i < NumElements; i++) {
37        System.out.print(ds.find(i) + "*");
38        if (i % NumInSameSet == NumInSameSet - 1) {
39          System.out.println();
40        }
41      }
42      System.out.println();
43    }
44  
45    private final int[] s;
46  
47    /**
48     * Construct the disjoint sets object.
49     * 
50     * @param numElements
51     *          the initial number of disjoint sets.
52     */
53    public DisjSetsFast(final int numElements) {
54      this.s = new int[numElements];
55      for (int i = 0; i < this.s.length; i++) {
56        this.s[i] = -1;
57      }
58    }
59  
60    boolean acyclic() {
64      }
66  
75              }
76            }
81          }
82        }
83      }
85    }
86  
87    public int find(final int x) {
90      } else {
92      }
93    }
94  
95    /**
96     * Perform a find with path compression. Error checks omitted again for
97     * simplicity.
98     * 
99     * @param x
100    *          the element being searched for.
101    * @return the set containing x.
102    */
103   //@ requires (this.s != null) && this.goodValues() && this.acyclic() && (x >= 0) && (x < this.s.length);
104   //@ ensures this.s[\result] < 0;
105   public int Find(final int x) {
107   }
108 
109   boolean goodValues() {
116       }
117     }
119   }
120 
121   /**
122    * Union two disjoint sets using the height heuristic. For simplicity, we
123    * assume root1 and root2 are distinct and represent set names.
124    * 
125    * @param root1
126    *          the root of set 1.
127    * @param root2
128    *          the root of set 2.
129    */
130   //@ requires (this.s != null) && this.goodValues() && this.acyclic() && (root1 >= 0) && (root1 < this.s.length) && (root2 >= 0) && (root2 < this.s.length) && (root1 != root2) && (this.s[root1] < 0) && (this.s[root2] < 0);
131   //@ ensures this.find(root1) == this.find(root2);
132   public void union(final int root1, final int root2) {
135     } else {
138       }
140     }
142 }