/home/marcvs/Desktop/working/pa-materiale/pa/codeBase/C++/include/DisjointSets.h

#ifndef __DISJOINTSETS_H__
#define __DISJOINTSETS_H__

#pragma once

#include <iostream>
#include <fstream>
#include <vector>

class DisjointSets {

private:
        unsigned int n;

        std::vector<int> set;
        std::vector<int> rank;

        inline int get_ID(int n) {
                int query = n;
                while (set[n] != n) {
                        n = set[n];
                }
                set[query] = n;
                return n;
        }

        inline void merge_sets(int ID_set_a, int ID_set_b) {
                if (rank[ID_set_a] < rank[ID_set_b]) {
                        set[ID_set_a] = ID_set_b;
                } else if (rank[ID_set_a] > rank[ID_set_b]) {
                        set[ID_set_b] = ID_set_a;
                } else {
                        set[ID_set_a] = ID_set_b;
                        rank[ID_set_b]++;
                }
        }

public: 
        inline DisjointSets(unsigned int n) :
                n(n)
        {
                for (unsigned int i = 0; i < n; i++) {
                        set.push_back(i);
                        rank.push_back(0);
                }
        }
        
        inline unsigned int get_n() const {
                return n;
        }

        inline void merge_sets_of(int ID_node_a, int ID_node_b) {
                int ID_set_a = get_ID(ID_node_a);
                int ID_set_b = get_ID(ID_node_b);
                if (ID_set_a != ID_set_b) {
                        merge_sets(ID_set_a, ID_set_b);
                }
        }
        
        inline bool same_set(int ID_node_a, int ID_node_b) {
                return get_ID(ID_node_a) == get_ID(ID_node_b);
        }
        
        friend class Maze;
};

#endif