KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > ui > internal > ide > misc > DisjointSet


1 /*******************************************************************************
2  * Copyright (c) 2006 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  ******************************************************************************/
11 package org.eclipse.ui.internal.ide.misc;
12
13 import java.util.HashMap JavaDoc;
14 import java.util.Iterator JavaDoc;
15 import java.util.List JavaDoc;
16
17 /**
18  * A disjoint set is a generic data structure that represents a collection of
19  * sets that are assumed to be disjoint (no object exists in more than
20  * one set).
21  * <p>
22  * This disjoint set implementation represents the disjoint set as a forest,
23  * where the nodes of each tree all belong to the same set. This implementation
24  * uses path compression in the findSet implementation to flatten each tree
25  * to a constant depth. A rank is maintained for each tree that is used when
26  * performing union operations to ensure the tree remains balanced.
27  * <p>
28  * Ref: Cormen, Leiserson, and Rivest <it>Introduction to Algorithms</it>,
29  * McGraw-Hill, 1990. The disjoint set forest implementation in section 22.3.
30  * </p>
31  * @since 3.2
32  */
33 public class DisjointSet {
34     /**
35      * A node in the disjoint set forest. Each tree in the forest is
36      * a disjoint set, where the root of the tree is the set representative.
37      */
38     private static class Node {
39         /** The node rank used for union by rank optimization */
40         int rank;
41         /** The parent of this node in the tree. */
42         Object JavaDoc parent;
43
44         Node(Object JavaDoc parent, int rank) {
45             this.parent = parent;
46             this.rank = rank;
47         }
48     }
49
50     /**
51      * Map of Object -> Node, where each key is an object in the
52      * disjoint set, and the Node represents its position and rank
53      * within the set.
54      */
55     private final HashMap JavaDoc objectsToNodes = new HashMap JavaDoc();
56
57     /**
58      * Returns the set token for the given object, or null if the
59      * object does not belong to any set. All object
60      * in the same set have an identical set token.
61      * @param o The object to return the set token for
62      * @return The set token, or <code>null</code>
63      */
64     public Object JavaDoc findSet(Object JavaDoc o) {
65         DisjointSet.Node node = (DisjointSet.Node) objectsToNodes.get(o);
66         if (node == null)
67             return null;
68         if (o != node.parent)
69             node.parent = findSet(node.parent);
70         return node.parent;
71     }
72
73     /**
74      * Adds a new set to the group of disjoint sets for the given object.
75      * It is assumed that the object does not yet belong to any set.
76      * @param o The object to add to the set
77      */
78     public void makeSet(Object JavaDoc o) {
79         objectsToNodes.put(o, new Node(o, 0));
80     }
81
82     /**
83      * Removes all elements belonging to the set of the given object.
84      * @param o The object to remove
85      */
86     public void removeSet(Object JavaDoc o) {
87         Object JavaDoc set = findSet(o);
88         if (set == null)
89             return;
90         for (Iterator JavaDoc it = objectsToNodes.keySet().iterator(); it.hasNext();) {
91             Object JavaDoc next = it.next();
92             //remove the set representative last, otherwise findSet will fail
93 if (next != set && findSet(next) == set)
94                 it.remove();
95         }
96         objectsToNodes.remove(set);
97     }
98
99     /**
100      * Copies all objects in the disjoint set to the provided list
101      * @param list The list to copy objects into
102      */
103     public void toList(List JavaDoc list) {
104         list.addAll(objectsToNodes.keySet());
105     }
106
107     /**
108      * Unions the set represented by token x with the set represented by
109      * token y. Has no effect if either x or y is not in the disjoint set, or
110      * if they already belong to the same set.
111      * @param x The first set to union
112      * @param y The second set to union
113      */
114     public void union(Object JavaDoc x, Object JavaDoc y) {
115         Object JavaDoc setX = findSet(x);
116         Object JavaDoc setY = findSet(y);
117         if (setX == null || setY == null || setX == setY)
118             return;
119         DisjointSet.Node nodeX = (DisjointSet.Node) objectsToNodes.get(setX);
120         DisjointSet.Node nodeY = (DisjointSet.Node) objectsToNodes.get(setY);
121         //join the two sets by pointing the root of one at the root of the other
122 if (nodeX.rank > nodeY.rank) {
123             nodeY.parent = x;
124         } else {
125             nodeX.parent = y;
126             if (nodeX.rank == nodeY.rank)
127                 nodeY.rank++;
128         }
129     }
130 }
Popular Tags