Partition.java Sample

This topic inludes the source code for the Partition.java Sample.

Sample Location

This sample is located in the following directory in your WebLogic Workshop installation:

BEA_HOME/weblogic81/samples/workshop/SamplesApp/WebServices/proxy/mazegen/

Sample Source Code


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 }