001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package EDU.purdue.cs.bloat.util;
022:
023: import java.util.*;
024:
025: /**
026: * Represents the union-find data structure.
027: *
028: * <p>
029: *
030: * Sometimes we need to group elements into disjoint sets. Two important
031: * operations of these sets are finding the set that contains a given element
032: * ("find") and uniting two sets ("union"). <tt>UnionFind</tt> provides an
033: * efficient implementation of a data structure that support these operations on
034: * disjoint sets of integers.
035: *
036: * <p>
037: *
038: * Each disjoint set is represented by a tree consisting of <tt>Node</tt>s.
039: * (This <tt>Node</tt> is a class local to <tt>UnionFind</tt> and should not
040: * be confused with <tt>tree.Node</tt>.) Each <tt>Node</tt> knows its
041: * parent and child and has a rank associated with it. The parent node is always
042: * the root node of the set tree. A <tt>Node</tt>'s rank is essentially the
043: * height of the (sub)tree rooted by that node. When the union of two trees is
044: * formed, the root with the smaller rank is made to point to the root with the
045: * larger rank. Naturally, each <tt>Node</tt> has an integer "value"
046: * associated with it.
047: *
048: * <p>
049: *
050: * A good description of union-find can be found in [Cormen, et. al. 1990].
051: */
052: public class UnionFind {
053: // The trees of Nodes that represent the disjoint sets.
054: ResizeableArrayList nodes;
055:
056: /**
057: * Constructor.
058: */
059: public UnionFind() {
060: nodes = new ResizeableArrayList();
061: }
062:
063: /**
064: * Constructor. Make a <tt>UnionFind</tt> with a given number of disjoint
065: * sets.
066: */
067: public UnionFind(final int size) {
068: nodes = new ResizeableArrayList(size);
069: }
070:
071: /**
072: * Searches the disjoint sets for a given integer. Returns the set
073: * containing the integer a. Sets are represented by a local class
074: * <tt>Node</tt>.
075: */
076: public Node findNode(final int a) {
077: nodes.ensureSize(a + 1);
078:
079: final Node na = (Node) nodes.get(a);
080:
081: if (na == null) {
082: // Start a new set with a
083: final Node root = new Node(a);
084:
085: root.child = new Node(a);
086: root.child.parent = root;
087:
088: nodes.set(a, root.child);
089:
090: return root;
091: }
092:
093: return findNode(na);
094: }
095:
096: /**
097: * Returns the integer value associated with the first <tt>Node</tt> in a
098: * set.
099: */
100: public int find(final int a) {
101: return findNode(a).value;
102: }
103:
104: /**
105: * Finds the set containing a given Node.
106: */
107: private Node findNode(Node node) {
108: final Stack stack = new Stack();
109:
110: // Find the child of the root element.
111: while (node.parent.child == null) {
112: stack.push(node);
113: node = node.parent;
114: }
115:
116: // Do path compression on the way back down.
117: final Node rootChild = node;
118:
119: while (!stack.empty()) {
120: node = (Node) stack.pop();
121: node.parent = rootChild;
122: }
123:
124: Assert.isTrue(rootChild.parent.child != null);
125:
126: return rootChild.parent;
127: }
128:
129: /**
130: * Returns true if a and b are in the same set.
131: */
132: public boolean isEquiv(final int a, final int b) {
133: return findNode(a) == findNode(b);
134: }
135:
136: /**
137: * Combines the set that contains a with the set that contains b.
138: */
139: public void union(final int a, final int b) {
140: final Node na = findNode(a);
141: final Node nb = findNode(b);
142:
143: if (na == nb) {
144: return;
145: }
146:
147: // Link the smaller tree under the larger.
148: if (na.rank > nb.rank) {
149: // Delete nb.
150: nb.child.parent = na.child;
151: na.value = b;
152:
153: } else {
154: // Delete na.
155: na.child.parent = nb.child;
156: nb.value = b;
157:
158: if (na.rank == nb.rank) {
159: nb.rank++;
160: }
161: }
162: }
163:
164: class Node {
165: Node parent; // The root of the tree in which this Node resides
166:
167: Node child;
168:
169: int value;
170:
171: int rank; // This Node's height in the tree
172:
173: public Node(final int v) {
174: value = v;
175: rank = 0;
176: }
177: }
178: }
|