001    /*--------------------------------------------------------------------------+
002    $Id: UnionFindWithSize.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.IntList;
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 size" but
025     * instead uses randomization. Additionally the size of union clusters is
026     * managed.
027     * 
028     * @author hummelb
029     * @author $Author: juergens $
030     * @version $Rev: 26283 $
031     * @levd.rating GREEN Hash: 71910668F1546351D03C7BCCEED97CB6
032     */
033    public class UnionFindWithSize extends UnionFind {
034    
035            /** The sizes for the individual clusters. */
036            private IntList unionSizes = new IntList();
037    
038            /** {@inheritDoc} */
039            @Override
040            public int addElement() {
041                    unionSizes.add(1);
042                    return super.addElement();
043            }
044    
045            /** {@inheritDoc} */
046            @Override
047            protected void connectToRepresentative(int element, int representative) {
048                    super.connectToRepresentative(element, representative);
049                    int connectedSize = unionSizes.get(representative)
050                                    + unionSizes.get(element);
051                    unionSizes.set(representative, connectedSize);
052            }
053    
054            /** Returns the size of the union cluster containing the given element. */
055            public int getClusterSize(int element) {
056                    return unionSizes.get(find(element));
057            }
058    }