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