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 }