| /******************************************************************************* |
| * Copyright (c) 2006 IBM Corporation and others. |
| * All rights reserved. This program and the accompanying materials |
| * are made available under the terms of the Eclipse Public License v1.0 |
| * which accompanies this distribution, and is available at |
| * http://www.eclipse.org/legal/epl-v10.html |
| * |
| * Contributors: |
| * IBM Corporation - initial API and implementation |
| ******************************************************************************/ |
| package org.eclipse.ui.internal.ide.misc; |
| |
| import java.util.HashMap; |
| import java.util.Iterator; |
| import java.util.List; |
| |
| /** |
| * A disjoint set is a generic data structure that represents a collection of |
| * sets that are assumed to be disjoint (no object exists in more than |
| * one set). |
| * <p> |
| * This disjoint set implementation represents the disjoint set as a forest, |
| * where the nodes of each tree all belong to the same set. This implementation |
| * uses path compression in the findSet implementation to flatten each tree |
| * to a constant depth. A rank is maintained for each tree that is used when |
| * performing union operations to ensure the tree remains balanced. |
| * <p> |
| * Ref: Cormen, Leiserson, and Rivest <it>Introduction to Algorithms</it>, |
| * McGraw-Hill, 1990. The disjoint set forest implementation in section 22.3. |
| * </p> |
| * @since 3.2 |
| */ |
| public class DisjointSet { |
| /** |
| * A node in the disjoint set forest. Each tree in the forest is |
| * a disjoint set, where the root of the tree is the set representative. |
| */ |
| private static class Node { |
| /** The node rank used for union by rank optimization */ |
| int rank; |
| /** The parent of this node in the tree. */ |
| Object parent; |
| |
| Node(Object parent, int rank) { |
| this.parent = parent; |
| this.rank = rank; |
| } |
| } |
| |
| /** |
| * Map of Object -> Node, where each key is an object in the |
| * disjoint set, and the Node represents its position and rank |
| * within the set. |
| */ |
| private final HashMap objectsToNodes = new HashMap(); |
| |
| /** |
| * Returns the set token for the given object, or null if the |
| * object does not belong to any set. All object |
| * in the same set have an identical set token. |
| * @param o The object to return the set token for |
| * @return The set token, or <code>null</code> |
| */ |
| public Object findSet(Object o) { |
| DisjointSet.Node node = (DisjointSet.Node) objectsToNodes.get(o); |
| if (node == null) |
| return null; |
| if (o != node.parent) |
| node.parent = findSet(node.parent); |
| return node.parent; |
| } |
| |
| /** |
| * Adds a new set to the group of disjoint sets for the given object. |
| * It is assumed that the object does not yet belong to any set. |
| * @param o The object to add to the set |
| */ |
| public void makeSet(Object o) { |
| objectsToNodes.put(o, new Node(o, 0)); |
| } |
| |
| /** |
| * Removes all elements belonging to the set of the given object. |
| * @param o The object to remove |
| */ |
| public void removeSet(Object o) { |
| Object set = findSet(o); |
| if (set == null) |
| return; |
| for (Iterator it = objectsToNodes.keySet().iterator(); it.hasNext();) { |
| Object next = it.next(); |
| //remove the set representative last, otherwise findSet will fail |
| if (next != set && findSet(next) == set) |
| it.remove(); |
| } |
| objectsToNodes.remove(set); |
| } |
| |
| /** |
| * Copies all objects in the disjoint set to the provided list |
| * @param list The list to copy objects into |
| */ |
| public void toList(List list) { |
| list.addAll(objectsToNodes.keySet()); |
| } |
| |
| /** |
| * Unions the set represented by token x with the set represented by |
| * token y. Has no effect if either x or y is not in the disjoint set, or |
| * if they already belong to the same set. |
| * @param x The first set to union |
| * @param y The second set to union |
| */ |
| public void union(Object x, Object y) { |
| Object setX = findSet(x); |
| Object setY = findSet(y); |
| if (setX == null || setY == null || setX == setY) |
| return; |
| DisjointSet.Node nodeX = (DisjointSet.Node) objectsToNodes.get(setX); |
| DisjointSet.Node nodeY = (DisjointSet.Node) objectsToNodes.get(setY); |
| //join the two sets by pointing the root of one at the root of the other |
| if (nodeX.rank > nodeY.rank) { |
| nodeY.parent = x; |
| } else { |
| nodeX.parent = y; |
| if (nodeX.rank == nodeY.rank) |
| nodeY.rank++; |
| } |
| } |
| } |