001package net.automatalib.commons.util.combinatorics;
002
003public class DisjointSetForestInt {
004        
005        
006        private int[] parent;
007        private int[] rank;
008
009        public DisjointSetForestInt(int initSize) {
010                this.parent = new int[initSize];
011                for(int i = 0; i < this.parent.length; i++)
012                        this.parent[i] = -1;
013                this.rank = new int[initSize];
014        }
015        
016        
017        public int find(int a) {
018                int p = parent[a];
019                if(p == -1)
020                        return a;
021                p = find(p);
022                parent[a] = p;
023                return p;
024        }
025        
026        public int union(int a, int b) {
027                return directUnion(find(a), find(b));
028        }
029        
030        public int directUnion(int a, int b) {          
031                assert parent[a] == -1 && parent[b] == -1;
032                
033                if(a == b)
034                        return a;
035                
036                int ra = rank[a], rb = rank[b];
037                if(ra < rb) {
038                        parent[a] = b;
039                        return b;
040                }
041                if(ra == rb) {
042                        rank[a]++;
043                }
044                parent[b] = a;
045                return a;       
046        }
047        
048        public int size() {
049                return parent.length;
050        }
051        
052        
053}