01 package proxy.mazegen;
02
03 /**
04 * This class implements a data structure for partitioning a set of numbers into groups.
05 * It supports quickly determining if two numbers are in the same group and also joining
06 * two groups together. Initially, each number is in its own group.
07 */
08 public class Partition
09 {
10 /** Stores the parent of a given node in its tree. */
11 private int[] parent;
12
13 /**
14 * Creates a partition of the numbers 0 to size-1. Initially, each number is in its
15 * own partition.
16 */
17 public Partition(int size)
18 {
19 parent = new int[size];
20
21 for (int i = 0; i < parent.length; i++)
22 parent[i] = i;
23 }
24
25 /** Determines if the given numbers are in the same group. */
26 public boolean inSameGroup(int num1, int num2)
27 {
28 // These two numbers are in the same tree if the have the same root.
29 return root(num1) == root(num2);
30 }
31
32 /** Returns the root of the tree containing this number. */
33 private int root(int num)
34 {
35 // Find the root of the tree containing this number.
36
37 int root = num;
38
39 while (parent[root] != root)
40 root = parent[root];
41
42 // Set the parent of every node from num up in its tree to have root
43 // as its parent.
44
45 while (num != root)
46 {
47 // Retrieve the original parent of this number.
48 int next = parent[num];
49
50 // Change the parent to point to the top of this tree.
51 parent[num] = root;
52
53 // Next, do the same to the original parent of this node.
54 num = next;
55 }
56
57 // Return the root that was found.
58 return root;
59 }
60
61 /** Join the groups containing the two given numbers into the same group. */
62 public void joinGroups(int num1, int num2)
63 {
64 // Set the parent of num2's tree to be the root of num1's tree. This
65 // groups them into the same tree.
66 parent[root(num2)] = root(num1);
67 }
68 }
|