001/* Copyright (C) 2013 TU Dortmund
002 * This file is part of AutomataLib, http://www.automatalib.net/.
003 * 
004 * AutomataLib is free software; you can redistribute it and/or
005 * modify it under the terms of the GNU Lesser General Public
006 * License version 3.0 as published by the Free Software Foundation.
007 * 
008 * AutomataLib is distributed in the hope that it will be useful,
009 * but WITHOUT ANY WARRANTY; without even the implied warranty of
010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
011 * Lesser General Public License for more details.
012 * 
013 * You should have received a copy of the GNU Lesser General Public
014 * License along with AutomataLib; if not, see
015 * http://www.gnu.de/documents/lgpl.en.html.
016 */
017package net.automatalib.commons.util;
018
019/**
020 * The well-known disjoint-set forest data structure for dealing with partitions
021 * on a fixed-range integer domain.
022 * 
023 * @author fhowar
024 * @author Malte Isberner <malte.isberner@gmail.com>
025 */
026public final class UnionFind {
027
028        private final int[] p;
029        private final int[] rank;
030
031        /**
032         * Initializes the disjoint-set data structure.
033         * @param n the overall size of the domain
034         */
035        public UnionFind(int n) {
036                p = new int[n];
037                rank = new int[n];
038
039                for(int i = 0; i < n; i++) {
040                        // primitive arrays are always zero initialized
041                        // rank[i] = 0;
042                        p[i] = i;
043                }
044        }
045
046        /**
047         * Unites the sets containing the two given elements.
048         * @param p the first element
049         * @param q the second element
050         * @return the identifier of the resulting set
051         */
052        public int union(int p, int q) {
053                return link(find(p), find(q));
054        }
055
056        /**
057         * Unites two given sets. Note that the behavior of this method is not specified
058         * if the given parameters are normal elements and no set identifiers.
059         * @param x the first set
060         * @param y the second set
061         * @return the identifier of the resulting set (either <tt>x</tt> or <tt>y</tt>)
062         */
063        public int link(int x, int y) {
064                if(rank[x] > rank[y]) {
065                        p[y] = x;
066                        return x;
067                }
068                p[x] = y;
069                if(rank[x] == rank[y])
070                        rank[y]++;
071                return y;
072        }
073
074        /**
075         * Finds the set of a given element, and compresses the path to the root node.
076         * @param x the element
077         * @return the identifier of the set which contains the given element
078         */
079        public int find(int x) {
080                int r = p[x];
081                if(x != r)
082                        p[x] = r = find(r);
083
084                return r;
085        }
086
087        // public synchronized boolean findAndUnite(int x, int y)
088        // {
089        // int r1 = find(x);
090        // int r2 = find(y);
091        //
092        // if (r1 == r2)
093        // return false;
094        //
095        // union(r1, r2);
096        // return true;
097        // }
098}