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 org.conqat.lib.commons.collections.ManagedIntArray;
020
021/**
022 * Implementation of a simple union find data structure. It implements the
023 * "partial path compression" heuristic but does not use "union by rank" but
024 * instead uses randomization.
025 * 
026 * @author hummelb
027 */
028public class UnionFind extends ManagedIntArray {
029
030        /** Flag that indicated whether random merge order should be used. */
031        private final boolean noRandom;
032
033        /** Constructor using random merge order. */
034        public UnionFind() {
035                this(false);
036        }
037
038        /**
039         * Constructor.
040         * 
041         * @param noRandom
042         *            if this is set to true, randomized merging is disabled. In
043         *            general, randomization should be used, as it prevents a linear
044         *            time worst case (for each union). However, if the order of
045         *            elements passed to the union method is already random (due to
046         *            the underlying data) or the size of the union size set is very
047         *            small, disabling randomization might cause a huge gain in
048         *            performance.
049         */
050        public UnionFind(boolean noRandom) {
051                this.noRandom = noRandom;
052        }
053
054        /** Finds and returns the representative for the given element. */
055        public int find(int element) {
056                if (element >= size) {
057                        throw new IllegalArgumentException("Unknown element!");
058                }
059
060                while (element != array[element]) {
061                        int next = array[element];
062                        array[element] = array[next];
063                        element = next;
064                }
065
066                return element;
067        }
068
069        /**
070         * Merges the classes in which element1 and element2 are, by giving them the
071         * same representative.
072         */
073        public void union(int element1, int element2) {
074                if (element1 >= size || element2 >= size) {
075                        throw new IllegalArgumentException("Unknown elements!");
076                }
077
078                // locate representatives
079                element1 = find(element1);
080                element2 = find(element2);
081
082                if (element1 != element2) {
083                        if (noRandom || Math.random() > .5) {
084                                connectToRepresentative(element1, element2);
085                        } else {
086                                connectToRepresentative(element2, element1);
087                        }
088                }
089        }
090
091        /**
092         * Connects the given element (must also be representative) to the given
093         * representative.
094         */
095        protected void connectToRepresentative(int element, int representative) {
096                array[element] = representative;
097        }
098
099        /**
100         * Adds a new element to this union find structure and returns its index.
101         */
102        public int addElement() {
103                int index = size;
104                addArrayElement();
105                array[index] = index;
106                return index;
107        }
108}