/*
 * File:   partition.h
 * Author: Filip Niksic, fniksic@gmail.com
 *
 * Created on 2008. sijecanj 31, 17:14
 */

#ifndef PARTITION_H
#define	PARTITION_H

#include <vector>
#include <cstddef>

class Partition {
    std::vector<std::size_t> rank;
    std::vector<std::size_t> partition;
    std::size_t nSets;
public:
    explicit Partition(size_t _n) : rank(_n), partition(_n), nSets(_n) {
        for (std::size_t i = 0; i != partition.size(); ++i)
            partition[i] = i;
    }
    /* find()
     * Vraca oznaku skupa u kojem se nalazi objekt i.
     */
    std::size_t find(std::size_t i) const;
    /* merge()
     * Spaja skupove oznacene s a i b
     */
    void merge(std::size_t a, std::size_t b);
    std::size_t numSets() const {
        return nSets;
    }
};

inline size_t Partition::find(size_t i) const {
    if (i >= partition.size())
        throw 0;
    while (partition[i] != i)
        i = partition[i];
    return i;
}

inline void Partition::merge(std::size_t a, std::size_t b) {
    // Prvo pronalazimo oznake skupova koji sadrze a, odnosno b
    a = find(a); b = find(b);
    if (a == b) // Nemamo sto spajati, a i b su u istom skupu
        return;
    else {
        if (rank[a] == rank[b]) {
            // Visine oba stabla su jednake, dodajemo b-ovo stablo u a-ovo stablo
            ++rank[a];
            partition[b] = a;
        }
        else if (rank[a] < rank[b])
            partition[a] = b;
        else
            partition[b] = a;
        --nSets; // broj skupova se upravo smanjio jer smo dva spojili u jedan
    }
}

#endif	/* PARTITION_H */