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 }