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 }