1   package kiasan.examples.disjsets;
2   
3   // DisjSets 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. (Package friendly so not used accidentally) Does not use
15   * union heuristics or path compression. Elements in the set are numbered
16   * starting at 0.
17   * 
18   * @author Mark Allen Weiss
19   * @see DisjSetsFast
20   */
21  public class DisjSets {
22    // Test main; all finds on same output line should be identical
23    public static void main(final String[] args) {
24      final int numElements = 128;
25      final int numInSameSet = 16;
26  
27      final DisjSets ds = new DisjSets(numElements);
28      int set1, set2;
29  
30      for (int k = 1; k < numInSameSet; k *= 2) {
31        for (int j = 0; j + k < numElements; j += 2 * k) {
32          set1 = ds.find(j);
33          set2 = ds.find(j + k);
34          ds.union(set1, set2);
35        }
36      }
37      System.out.println(ds.acyclic());
38  
39      for (int i = 0; i < numElements; i++) {
40        System.out.print(ds.find(i) + "*");
41        if (i % numInSameSet == numInSameSet - 1) {
42          System.out.println();
43        }
44      }
45      System.out.println();
46    }
47  
48    private int[] s;
49  
50    public DisjSets() {
51    }
52  
53    /**
54     * Construct the disjoint sets object.
55     * 
56     * @param numElements
57     *          the initial number of disjoint sets.
58     */
59    public DisjSets(final int numElements) {
60      this.s = new int[numElements];
61      for (int i = 0; i < this.s.length; i++) {
62        this.s[i] = -1;
63      }
64    }
65  
66    private boolean acyclic() {
70      }
72  
81              }
82            }
87          }
88        }
89      }
91    }
92  
93    public int find(final int x) {
96      } else {
98      }
99    }
100 
101   /**
102    * Perform a find. Error checks omitted again for simplicity.
103    * 
104    * @param x
105    *          the element being searched for.
106    * @return the set containing x.
107    */
108   //@ requires (this.s != null) && goodValues() && acyclic() && (x >= 0) && (x < this.s.length);
109   //@ ensures this.s[\result] < 0;
110   public int Find(final int x) {
112   }
113 
114   boolean goodValues() {
121       }
122     }
124   }
125 
126   /**
127    * Union two disjoint sets. For simplicity, we assume root1 and root2 are
128    * distinct and represent set names.
129    * 
130    * @param root1
131    *          the root of set 1.
132    * @param root2
133    *          the root of set 2.
134    */
135   //@ requires (this.s != null) && goodValues() && acyclic() && (root1 >= 0) && (root1 < this.s.length) && (root2 >= 0) && (root2 < this.s.length) && (root1 != root2) && (this.s[root1] == -1) && (this.s[root2] == -1);
136   //@ ensures find(root1) == find(root2);
137   public void union(final int root1, final int root2) {
140 }