flow_disjoint_set.h

Go to the documentation of this file.

#pragma once
#include "flow_vector.h"
 
namespace flow {

  template <typename T, typename Allocator = PolymorphicAllocator<T>>
  class DisjointSet {
    struct Node {
      std::size_t groupId;
      std::size_t rank;
      T value;
    };
 
  public:
    using value_type = T;
    using reference = T&;
    using const_reference = const T&;
    using pointer = T*;
    using const_pointer = const T*;
    using iterator = T*;
    using const_iterator = const T*;
    using difference_type = std::ptrdiff_t;
    using allocator_type = std::allocator_traits<Allocator>::template rebind_alloc<Node>;
    using container_type = Vector<Node, allocator_type>;
 
  private:
    std::size_t groupSize_;
    container_type data_;
 
  public:
    constexpr DisjointSet()
      noexcept(noexcept(container_type()))
      : groupSize_(0), data_() {
    }
 
    explicit constexpr DisjointSet(const allocator_type& allocator)
      noexcept(noexcept(container_type(allocator)))
      : groupSize_(0), data_(allocator) {
    }
 
    constexpr DisjointSet(const DisjointSet&) = default;
    constexpr DisjointSet(const DisjointSet& rhs, const allocator_type& allocator)
      : groupSize_(rhs.groupSize_), data_(rhs.data_, allocator) {
    }
 
    constexpr DisjointSet(DisjointSet&&) = default;
    constexpr DisjointSet(DisjointSet&& rhs, const allocator_type& allocator)
      noexcept(noexcept(container_type(std::move(rhs.data_), allocator)))
      : groupSize_(rhs.groupSize_), data_(std::move(rhs.data_), allocator) {
      // rhs groupSize may not match up with the actual group size (0).
      // That's fine, because we won't use that value after the move.
      // Hopefully it won't come back and bite me in the future.
      // Put a cat girl ascii here for good luck:
      /*
      ⣿⡟⠙⠛⠋⠩⠭⣉⡛⢛⠫⠭⠄⠒⠄⠄⠄⠈⠉⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿
      ⣿⡇⠄⠄⠄⠄⣠⠖⠋⣀⡤⠄⠒⠄⠄⠄⠄⠄⠄⠄⠄⠄⣈⡭⠭⠄⠄⠄⠉⠙
      ⣿⡇⠄⠄⢀⣞⣡⠴⠚⠁⠄⠄⢀⠠⠄⠄⠄⠄⠄⠄⠄⠉⠄⠄⠄⠄⠄⠄⠄⠄
      ⣿⡇⠄⡴⠁⡜⣵⢗⢀⠄⢠⡔⠁⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
      ⣿⡇⡜⠄⡜⠄⠄⠄⠉⣠⠋⠠⠄⢀⡄⠄⠄⣠⣆⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢸
      ⣿⠸⠄⡼⠄⠄⠄⠄⢰⠁⠄⠄⠄⠈⣀⣠⣬⣭⣛⠄⠁⠄⡄⠄⠄⠄⠄⠄⢀⣿
      ⣏⠄⢀⠁⠄⠄⠄⠄⠇⢀⣠⣴⣶⣿⣿⣿⣿⣿⣿⡇⠄⠄⡇⠄⠄⠄⠄⢀⣾⣿
      ⣿⣸⠈⠄⠄⠰⠾⠴⢾⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⢁⣾⢀⠁⠄⠄⠄⢠⢸⣿⣿
      ⣿⣿⣆⠄⠆⠄⣦⣶⣦⣌⣿⣿⣿⣿⣷⣋⣀⣈⠙⠛⡛⠌⠄⠄⠄⠄⢸⢸⣿⣿
      ⣿⣿⣿⠄⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠈⠄⠄⠄⠄⠄⠈⢸⣿⣿
      ⣿⣿⣿⠄⠄⠄⠘⣿⣿⣿⡆⢀⣈⣉⢉⣿⣿⣯⣄⡄⠄⠄⠄⠄⠄⠄⠄⠈⣿⣿
      ⣿⣿⡟⡜⠄⠄⠄⠄⠙⠿⣿⣧⣽⣍⣾⣿⠿⠛⠁⠄⠄⠄⠄⠄⠄⠄⠄⠃⢿⣿
      ⣿⡿⠰⠄⠄⠄⠄⠄⠄⠄⠄⠈⠉⠩⠔⠒⠉⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠐⠘⣿
      ⣿⠃⠃⠄⠄⠄⠄⠄⠄⣀⢀⠄⠄⡀⡀⢀⣤⣴⣤⣤⣀⣀⠄⠄⠄⠄⠄⠄⠁⢹
      */
    }

    template <std::forward_iterator It>
    explicit constexpr DisjointSet(It first, It last, const allocator_type& allocator = {})
      : groupSize_(std::distance(first, last)), data_(allocator) {
      data_.reserve(groupSize_);
      for (std::size_t i = 0; i < groupSize_; ++i) {
        data_.pushBack(Node{ i, 0, *first });
        ++first;
      }
    }

    explicit constexpr DisjointSet(std::initializer_list<T> list, const allocator_type& allocator = {})
      : DisjointSet(list.begin(), list.end(), allocator) {
    }
 
    ~DisjointSet() = default;
 
    // Allocator.
    allocator_type get_allocator() const noexcept {
      return data_.get_allocator();
    }
 
    // Accessor.

    constexpr std::size_t size() const {
      return data_.size();
    }

    constexpr std::size_t groupSize() const {
      return groupSize_;
    }

    constexpr bool empty() const {
      return data_.empty();
    }

    void reserve(std::size_t n) {
      data_.reserve(n);
    }

    constexpr void add(const T& value) {
      data_.pushBack(Node{ data_.size(), 0, value });
      ++groupSize_;
    }

    constexpr void add(T&& value) {
      data_.pushBack(Node{ data_.size(), 0, std::move(value) });
      ++groupSize_;
    }

    constexpr const T& operator[](std::size_t i) const {
      return data_[i].value;
    }

    constexpr T& operator[](std::size_t i) {
      return data_[i].value;
    }

    constexpr std::size_t find(std::size_t i) {
      // Can switch to two passes using loop if overflows.
      if (data_[i].groupId == i) {
        return i;
      }
      return data_[i].groupId = find(data_[i].groupId);
    }

    constexpr bool isSameGroup(std::size_t i, std::size_t j) {
      return find(i) == find(j);
    }

    constexpr bool merge(std::size_t i, std::size_t j) {
      std::size_t p1 = find(i);
      std::size_t p2 = find(j);
      if (p1 == p2) {
        return false;
      }
 
      if (data_[p1].rank <= data_[p2].rank) {
        data_[p1].groupId = p2;
        if (data_[p1].rank == data_[p2].rank) {
          ++data_[p2].rank;
        }
      } else {
        data_[p2].groupId = p1;
      }
 
      --groupSize_;
      return true;
    }
  };
}