001    /*--------------------------------------------------------------------------+
002    $Id: UnionFind.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 edu.tum.cs.commons.collections.ManagedIntArray;
021    
022    /**
023     * Implementation of a simple union find data structure. It implements the
024     * "partial path compression" heuristic but does not use "union by rank" but
025     * instead uses randomization.
026     * 
027     * @author hummelb
028     * @author $Author: juergens $
029     * @version $Rev: 26283 $
030     * @levd.rating GREEN Hash: CF81A002CA0755AAD2BB6B1A6C75BA03
031     */
032    public class UnionFind extends ManagedIntArray {
033    
034            /** Finds and returns the representative for the given element. */
035            public int find(int element) {
036                    if (element >= size) {
037                            throw new IllegalArgumentException("Unknown element!");
038                    }
039    
040                    while (element != array[element]) {
041                            int next = array[element];
042                            array[element] = array[next];
043                            element = next;
044                    }
045    
046                    return element;
047            }
048    
049            /**
050             * Merges the classes in which element1 and element2 are, by giving them the
051             * same representative.
052             */
053            public void union(int element1, int element2) {
054                    if (element1 >= size || element2 >= size) {
055                            throw new IllegalArgumentException("Unknown elements!");
056                    }
057    
058                    // locate representatives
059                    element1 = find(element1);
060                    element2 = find(element2);
061    
062                    if (element1 != element2) {
063                            if (Math.random() > .5) {
064                                    connectToRepresentative(element1, element2);
065                            } else {
066                                    connectToRepresentative(element2, element1);
067                            }
068                    }
069            }
070    
071            /**
072             * Connects the given element (must also be representative) to the given
073             * representative.
074             */
075            protected void connectToRepresentative(int element, int representative) {
076                    array[element] = representative;
077            }
078    
079            /** Adds a new element to this union find structure and returns its index. */
080            public int addElement() {
081                    int index = size;
082                    addArrayElement();
083                    array[index] = index;
084                    return index;
085            }
086    }