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