disjoint_set.hpp

浏览该文件的文档.

/*
 * @Description: 并查集 头文件及其实现
 * @Version:
 * @Autor: dreamy-xay
 * @date: 2023-12-31
 * @LastEditors: dreamy-xay
 * @LastEditTime: 2024-03-06
 */
 
#ifndef COMMON_DISJOINT_SET_HPP
#define COMMON_DISJOINT_SET_HPP
 
#include <iostream>
#include <unordered_map>
#include <vector>
 
#include "common/base/list.hpp"
#include "common/enum.h"
#include "common/macro.h"
#include "common/type.h"
 
namespace cm {
 
template <typename T>
class DisjointSet {
   private:
    std::vector<T> data;         // 原始数据
    std::vector<size_t> parent;  // 指定索引原始所在的集合的根节点数组
    std::vector<size_t> count;   // 以指定索引为根所对应的集合的大小数组
 
    T* data_ptr;         // 原始数据指针（加速访问）
    size_t* parent_ptr;  // 根节点数组指针（加速访问）
    size_t* count_ptr;   // 集合大小数组指针（加速访问）
 
   public:
    DisjointSet();
    explicit DisjointSet(const std::vector<T>& list);
    template <typename ITERATOR>
    explicit DisjointSet(ITERATOR start_iterator, ITERATOR end_iterator);
    DisjointSet(const std::initializer_list<T>& inital_list);
    DisjointSet(const DisjointSet& disjoint_set) = default;
    ~DisjointSet();
 
    DisjointSet& Reserve(size_t size);
    DisjointSet& Resize(size_t size);
    DisjointSet& Assign(const std::vector<T>& list);
    template <typename ITERATOR>
    DisjointSet<T>& Assign(ITERATOR start_iterator, ITERATOR end_iterator);
    DisjointSet& Swap(DisjointSet<T>& disjoint_set);
    DisjointSet& Clear();
    size_t Size() const;
    T* Data();
    const T* Data() const;
 
    size_t RootIndex(size_t index);
    bool IsUnion(size_t index1, size_t index2);
    DisjointSet& Union(size_t index1, size_t index2);
    size_t CollectionSize(size_t index);
    size_t CollectionsSize();
    template <typename FUNC>
    DisjointSet<T>& UnionAll(const FUNC& is_union);
    List<List<T>> GetAllCollections();
};
 
template <typename T>
inline DisjointSet<T>::DisjointSet() : data_ptr(nullptr), parent_ptr(nullptr), count_ptr(nullptr) {}
 
template <typename T>
inline DisjointSet<T>::DisjointSet(const std::vector<T>& list) : data_ptr(nullptr), parent_ptr(nullptr), count_ptr(nullptr) {
    this->Assign(list);
}
 
template <typename T>
template <typename ITERATOR>
inline DisjointSet<T>::DisjointSet(ITERATOR start_iterator, ITERATOR end_iterator) : data_ptr(nullptr), parent_ptr(nullptr), count_ptr(nullptr) {
    this->Assign(start_iterator, end_iterator);
}
 
template <typename T>
inline DisjointSet<T>::DisjointSet(const std::initializer_list<T>& inital_list) : data_ptr(nullptr), parent_ptr(nullptr), count_ptr(nullptr) {
    this->Assign(inital_list.begin(), inital_list.end());
}
 
template <typename T>
inline DisjointSet<T>::~DisjointSet() {}
 
template <typename T>
inline DisjointSet<T>& DisjointSet<T>::Reserve(size_t size) {
    data.reserve(size);
    parent.reserve(size);
    count.reserve(size);
 
    return *this;
}
 
template <typename T>
inline DisjointSet<T>& DisjointSet<T>::Resize(size_t size) {
    data.resize(size);
    parent.resize(size);
    count.resize(size);
 
    return *this;
}
 
template <typename T>
inline DisjointSet<T>& DisjointSet<T>::Assign(const std::vector<T>& list) {
    this->Clear();  // 如果存在数据则清空原来数据
 
    this->Resize(list.size());
 
    int list_len = list.size();
 
    // 加速索引
    const T* list_ptr = list.data();
 
    // 初始化原始数据指针
    data_ptr = data.data();
    parent_ptr = parent.data();
    count_ptr = count.data();
 
    // 初始化所有值
    for (size_t i = 0; i < list_len; ++i) {
        data_ptr[i] = list_ptr[i];
        parent_ptr[i] = i;
        count_ptr[i] = 1;
    }
 
    return *this;
}
 
template <typename T>
template <typename ITERATOR>
inline DisjointSet<T>& DisjointSet<T>::Assign(ITERATOR start_iterator, ITERATOR end_iterator) {
    this->Clear();  // 如果存在数据则清空原来数据
 
    // 初始化所有值
    for (size_t i = 0; start_iterator < end_iterator; ++i, ++start_iterator) {
        data.emplace(*start_iterator);
        parent.emplace_back(i);
        count.emplace_back(1);
    }
 
    // 初始化原始数据指针
    data_ptr = data.data();
    parent_ptr = parent.data();
    count_ptr = count.data();
 
    return *this;
}
 
template <typename T>
inline DisjointSet<T>& DisjointSet<T>::Swap(DisjointSet<T>& disjoint_set) {
    data.swap(disjoint_set.data);
    parent.swap(disjoint_set.parent);
    count.swap(disjoint_set.count);
 
    return *this;
}
 
template <typename T>
inline DisjointSet<T>& DisjointSet<T>::Clear() {
    data.clear();
    parent.clear();
    count.clear();
 
    return *this;
}
 
template <typename T>
inline size_t DisjointSet<T>::Size() const {
    return data.size();
}
 
template <typename T>
inline T* DisjointSet<T>::Data() {
    return data.data();
}
 
template <typename T>
inline const T* DisjointSet<T>::Data() const {
    return data.data();
}
 
template <typename T>
inline size_t DisjointSet<T>::RootIndex(size_t index) {
    if (index != parent_ptr[index])
        parent_ptr[index] = this->RootIndex(parent_ptr[index]);  // 路径压缩
 
    return parent_ptr[index];
}
 
template <typename T>
inline bool DisjointSet<T>::IsUnion(size_t index1, size_t index2) {
    return this->RootIndex(index1) == this->RootIndex(index2);
}
 
template <typename T>
inline DisjointSet<T>& DisjointSet<T>::Union(size_t index1, size_t index2) {
    // 获取 指定索引数据项 所对应的集合 的根节点数据索引
    size_t index1_root = this->RootIndex(index1);
    size_t index2_root = this->RootIndex(index2);
 
    // 如果不在同一个集合中，则合并
    if (index1_root != index2_root) {
        parent_ptr[index1_root] = index2_root;
        count_ptr[index1_root] += 1;  // 更新集合大小
    }
 
    return *this;
}
 
template <typename T>
inline size_t DisjointSet<T>::CollectionSize(size_t index) {
    return count_ptr[this->RootIndex(index)];
}
 
template <typename T>
inline size_t DisjointSet<T>::CollectionsSize() {
    size_t size = 0;  // 并查集集合数量
 
    // 先根据每个集合的根节点创建集合列表
    for (int i = int(data.size()) - 1; i >= 0; --i)
        size += this->RootIndex(i) == i;
 
    return size;
}
 
template <typename T>
template <typename FUNC>
inline DisjointSet<T>& DisjointSet<T>::UnionAll(const FUNC& is_union) {
    // 数据长度
    int data_len = data.size();
 
    // 遍历全部数据项组合（一对数据项）
    for (size_t i = 0; i < data_len; ++i)
        for (size_t j = i + 1; j < data_len; ++j)
            if (is_union(data_ptr[i], data_ptr[j]))
                this->Union(i, j);  // 合并数据项
 
    return *this;
}
 
template <typename T>
inline List<List<T>> DisjointSet<T>::GetAllCollections() {
    List<List<T>> all_collections;                        // 所有集合列表
    std::unordered_map<size_t, size_t> collection_index;  // 每个集合根节点数据索引 在 all_collections 中对应的集合索引
 
    // 数据长度
    int data_len = data.size();
 
    // 先根据每个集合的根节点创建集合列表
    for (int i = 0; i < data_len; ++i)
        if (this->RootIndex(i) == i) {
            collection_index[i] = all_collections.size();
            all_collections.push_back(std::vector<T>({data_ptr[i]}));
        }
 
    // 再在每个集合中添加集合非根节点数据项
    for (int i = 0; i < data_len; ++i)
        if (parent_ptr[i] != i)
            all_collections[collection_index[parent_ptr[i]]].emplace_back(data_ptr[i]);
 
    // 返回所有集合列表
    return std::move(all_collections);
}
 
}  // namespace cm
 
#endif