001: /*******************************************************************************
002: * Copyright (c) 2006 IBM Corporation and others.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * IBM Corporation - initial API and implementation
010: ******************************************************************************/package org.eclipse.ui.internal.ide.misc;
011:
012: import java.util.HashMap;
013: import java.util.Iterator;
014: import java.util.List;
015:
016: /**
017: * A disjoint set is a generic data structure that represents a collection of
018: * sets that are assumed to be disjoint (no object exists in more than
019: * one set).
020: * <p>
021: * This disjoint set implementation represents the disjoint set as a forest,
022: * where the nodes of each tree all belong to the same set. This implementation
023: * uses path compression in the findSet implementation to flatten each tree
024: * to a constant depth. A rank is maintained for each tree that is used when
025: * performing union operations to ensure the tree remains balanced.
026: * <p>
027: * Ref: Cormen, Leiserson, and Rivest <it>Introduction to Algorithms</it>,
028: * McGraw-Hill, 1990. The disjoint set forest implementation in section 22.3.
029: * </p>
030: * @since 3.2
031: */
032: public class DisjointSet {
033: /**
034: * A node in the disjoint set forest. Each tree in the forest is
035: * a disjoint set, where the root of the tree is the set representative.
036: */
037: private static class Node {
038: /** The node rank used for union by rank optimization */
039: int rank;
040: /** The parent of this node in the tree. */
041: Object parent;
042:
043: Node(Object parent, int rank) {
044: this .parent = parent;
045: this .rank = rank;
046: }
047: }
048:
049: /**
050: * Map of Object -> Node, where each key is an object in the
051: * disjoint set, and the Node represents its position and rank
052: * within the set.
053: */
054: private final HashMap objectsToNodes = new HashMap();
055:
056: /**
057: * Returns the set token for the given object, or null if the
058: * object does not belong to any set. All object
059: * in the same set have an identical set token.
060: * @param o The object to return the set token for
061: * @return The set token, or <code>null</code>
062: */
063: public Object findSet(Object o) {
064: DisjointSet.Node node = (DisjointSet.Node) objectsToNodes
065: .get(o);
066: if (node == null)
067: return null;
068: if (o != node.parent)
069: node.parent = findSet(node.parent);
070: return node.parent;
071: }
072:
073: /**
074: * Adds a new set to the group of disjoint sets for the given object.
075: * It is assumed that the object does not yet belong to any set.
076: * @param o The object to add to the set
077: */
078: public void makeSet(Object o) {
079: objectsToNodes.put(o, new Node(o, 0));
080: }
081:
082: /**
083: * Removes all elements belonging to the set of the given object.
084: * @param o The object to remove
085: */
086: public void removeSet(Object o) {
087: Object set = findSet(o);
088: if (set == null)
089: return;
090: for (Iterator it = objectsToNodes.keySet().iterator(); it
091: .hasNext();) {
092: Object next = it.next();
093: //remove the set representative last, otherwise findSet will fail
094: if (next != set && findSet(next) == set)
095: it.remove();
096: }
097: objectsToNodes.remove(set);
098: }
099:
100: /**
101: * Copies all objects in the disjoint set to the provided list
102: * @param list The list to copy objects into
103: */
104: public void toList(List list) {
105: list.addAll(objectsToNodes.keySet());
106: }
107:
108: /**
109: * Unions the set represented by token x with the set represented by
110: * token y. Has no effect if either x or y is not in the disjoint set, or
111: * if they already belong to the same set.
112: * @param x The first set to union
113: * @param y The second set to union
114: */
115: public void union(Object x, Object y) {
116: Object setX = findSet(x);
117: Object setY = findSet(y);
118: if (setX == null || setY == null || setX == setY)
119: return;
120: DisjointSet.Node nodeX = (DisjointSet.Node) objectsToNodes
121: .get(setX);
122: DisjointSet.Node nodeY = (DisjointSet.Node) objectsToNodes
123: .get(setY);
124: //join the two sets by pointing the root of one at the root of the other
125: if (nodeX.rank > nodeY.rank) {
126: nodeY.parent = x;
127: } else {
128: nodeX.parent = y;
129: if (nodeX.rank == nodeY.rank)
130: nodeY.rank++;
131: }
132: }
133: }
|