001    /*--------------------------------------------------------------------------+
002    $Id: ObjectUnionFind.java 26283 2010-02-18 11:18:57Z juergens $
003    |                                                                          |
004    | Copyright 2005-2010 Technische Universitaet Muenchen                     |
005    |                                                                          |
006    | Licensed under the Apache License, Version 2.0 (the "License");          |
007    | you may not use this file except in compliance with the License.         |
008    | You may obtain a copy of the License at                                  |
009    |                                                                          |
010    |    http://www.apache.org/licenses/LICENSE-2.0                            |
011    |                                                                          |
012    | Unless required by applicable law or agreed to in writing, software      |
013    | distributed under the License is distributed on an "AS IS" BASIS,        |
014    | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
015    | See the License for the specific language governing permissions and      |
016    | limitations under the License.                                           |
017    +--------------------------------------------------------------------------*/
018    package edu.tum.cs.commons.algo;
019    
020    import java.util.ArrayList;
021    import java.util.HashMap;
022    import java.util.IdentityHashMap;
023    import java.util.List;
024    import java.util.Map;
025    
026    import edu.tum.cs.commons.assertion.CCSMAssert;
027    import edu.tum.cs.commons.assertion.CCSMPre;
028    
029    /**
030     * Implementation of a simple union find data structure working on arbitrary
031     * objects. It implements the "partial path compression" heuristic but does not
032     * use "union by size" but instead uses randomization. Additional the size of
033     * union clusters is managed.
034     * 
035     * @author hummelb
036     * @author $Author: juergens $
037     * @version $Rev: 26283 $
038     * @levd.rating GREEN Hash: 91B639154846D7F1249747DF97FF5A44
039     */
040    public class ObjectUnionFind<T> {
041    
042            /** The underlying union find. */
043            private final UnionFindWithSize unionFind = new UnionFindWithSize();
044    
045            /** The lookup map for mapping objects to integers. */
046            private final Map<T, Integer> lookup;
047    
048            /** Stores elements put into the union find struture. */
049            private final List<T> elements = new ArrayList<T>();
050    
051            /** Constructor using a HashMap as underlying lookup storage. */
052            public ObjectUnionFind() {
053                    this(new HashMap<T, Integer>());
054            }
055    
056            /**
057             * Constructor through which the the underlying map can be set.
058             * 
059             * @param lookup
060             *            the map being used for lookup (e.g. for providing a
061             *            {@link IdentityHashMap}. This map should not be used outside
062             *            afterwards!
063             */
064            public ObjectUnionFind(HashMap<T, Integer> lookup) {
065                    this.lookup = lookup;
066                    lookup.clear();
067            }
068    
069            /** Finds and returns the representative for the given element. */
070            public T find(T element) {
071                    Integer index = lookup.get(element);
072                    if (index == null) {
073                            return element;
074                    }
075                    return elements.get(unionFind.find(index));
076            }
077    
078            /**
079             * Merges the classes in which element1 and element2 are, by giving them the
080             * same representative.
081             */
082            public void union(T element1, T element2) {
083                    if (!containsElement(element1)) {
084                            addElement(element1);
085                    }
086                    if (!containsElement(element2)) {
087                            addElement(element2);
088                    }
089    
090                    unionFind.union(lookup.get(element1), lookup.get(element2));
091            }
092    
093            /**
094             * Adds a new element to this union find structure. Note that explicit
095             * adding is not required, as elements are dynamically added by
096             * {@link #union(Object, Object)} and all other method work correctly even
097             * for objects not yet added. However this method makes sure, that no object
098             * can be added a second time.
099             */
100            public void addElement(T element) {
101                    CCSMPre.isFalse(containsElement(element), "May not add element twice.");
102                    int index = unionFind.addElement();
103                    CCSMAssert.isTrue(index == elements.size(),
104                                    "Elements not managed consistently!");
105                    elements.add(element);
106                    lookup.put(element, index);
107            }
108    
109            /**
110             * Returns whether an element has been added to this stucture either by
111             * {@link #addElement(Object)} or {@link #union(Object, Object)}. Note that
112             * all methods will also work for elements for which this method returns
113             * false,
114             */
115            public boolean containsElement(T element) {
116                    return lookup.containsKey(element);
117            }
118    
119            /** Returns the size of the union cluster containing the given element. */
120            public int getClusterSize(T element) {
121                    Integer index = lookup.get(element);
122                    if (index == null) {
123                            return 1;
124                    }
125                    return unionFind.getClusterSize(index);
126            }
127    }