A disjoint union set that uses path compression and union by rank. More...

#include <flow_disjoint_set.h>

Classes
struct	Node

Public Types
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>

Public Member Functions
constexpr	DisjointSet () noexcept(noexcept(container_type()))
constexpr	DisjointSet (const allocator_type &allocator) noexcept(noexcept(container_type(allocator)))
constexpr	DisjointSet (const DisjointSet &)=default
constexpr	DisjointSet (const DisjointSet &rhs, const allocator_type &allocator)
constexpr	DisjointSet (DisjointSet &&)=default
constexpr	DisjointSet (DisjointSet &&rhs, const allocator_type &allocator) noexcept(noexcept(container_type(std::move(rhs.data_), allocator)))
template<std::forward_iterator It>
constexpr	DisjointSet (It first, It last, const allocator_type &allocator={})
	Iterator range constructor.
constexpr	DisjointSet (std::initializer_list< T > list, const allocator_type &allocator={})
	Initializer list constructor.
	~DisjointSet ()=default
allocator_type	get_allocator () const noexcept
constexpr std::size_t	size () const
	Return the number of input elements.
constexpr std::size_t	groupSize () const
	Return the number of group.
constexpr bool	empty () const
	Check if the disjoint set is empty.
void	reserve (std::size_t n)
	Reserve enough memory for at least n elements.
constexpr void	add (const T &value)
	Add an element to the disjoint set.
constexpr void	add (T &&value)
	Add an element to the disjoint set.
constexpr const T &	operator[] (std::size_t i) const
	Get the value of the i-th element.
constexpr T &	operator[] (std::size_t i)
	Get the value of the i-th element.
constexpr std::size_t	find (std::size_t i)
	Find the group id of the i-th node. Perform path compression along the way.
constexpr bool	isSameGroup (std::size_t i, std::size_t j)
	Check if the i-th element and the j-th element are in the same group.
constexpr bool	merge (std::size_t i, std::size_t j)
	Merge the i-th element's group with the j-th element's group. Internally, it unions them by ranking.

Private Attributes
std::size_t	groupSize_
container_type	data_

Detailed Description

template<typename T, typename Allocator = PolymorphicAllocator<T>>
class flow::DisjointSet< T, Allocator >

A disjoint union set that uses path compression and union by rank.

Template Parameters

T
Allocator

Definition at line 10 of file flow_disjoint_set.h.

Member Typedef Documentation

◆ allocator_type

template<typename T, typename Allocator = PolymorphicAllocator<T>>

using flow::DisjointSet< T, Allocator >::allocator_type = std::allocator_traits<Allocator>::template rebind_alloc<Node>

Definition at line 26 of file flow_disjoint_set.h.

◆ const_iterator

template<typename T, typename Allocator = PolymorphicAllocator<T>>

using flow::DisjointSet< T, Allocator >::const_iterator = const T*

Definition at line 24 of file flow_disjoint_set.h.

◆ const_pointer

template<typename T, typename Allocator = PolymorphicAllocator<T>>

using flow::DisjointSet< T, Allocator >::const_pointer = const T*

Definition at line 22 of file flow_disjoint_set.h.

◆ const_reference

template<typename T, typename Allocator = PolymorphicAllocator<T>>

using flow::DisjointSet< T, Allocator >::const_reference = const T&

Definition at line 20 of file flow_disjoint_set.h.

◆ container_type

template<typename T, typename Allocator = PolymorphicAllocator<T>>

using flow::DisjointSet< T, Allocator >::container_type = Vector<Node, allocator_type>

Definition at line 27 of file flow_disjoint_set.h.

◆ difference_type

template<typename T, typename Allocator = PolymorphicAllocator<T>>

using flow::DisjointSet< T, Allocator >::difference_type = std::ptrdiff_t

Definition at line 25 of file flow_disjoint_set.h.

◆ iterator

template<typename T, typename Allocator = PolymorphicAllocator<T>>

using flow::DisjointSet< T, Allocator >::iterator = T*

Definition at line 23 of file flow_disjoint_set.h.

◆ pointer

template<typename T, typename Allocator = PolymorphicAllocator<T>>

using flow::DisjointSet< T, Allocator >::pointer = T*

Definition at line 21 of file flow_disjoint_set.h.

◆ reference

template<typename T, typename Allocator = PolymorphicAllocator<T>>

using flow::DisjointSet< T, Allocator >::reference = T&

Definition at line 19 of file flow_disjoint_set.h.

◆ value_type

template<typename T, typename Allocator = PolymorphicAllocator<T>>

using flow::DisjointSet< T, Allocator >::value_type = T

Definition at line 18 of file flow_disjoint_set.h.

Constructor & Destructor Documentation

◆ DisjointSet() [1/8]

template<typename T, typename Allocator = PolymorphicAllocator<T>>

flow::DisjointSet< T, Allocator >::DisjointSet ( )

inlineconstexprnoexcept

Definition at line 34 of file flow_disjoint_set.h.

36 : groupSize_(0), data_() {

37 }

flow::DisjointSet::groupSize_

std::size_t groupSize_

Definition flow_disjoint_set.h:30

flow::DisjointSet::data_

container_type data_

Definition flow_disjoint_set.h:31

References data_, and groupSize_.

Referenced by DisjointSet(), DisjointSet(), DisjointSet(), and DisjointSet().

◆ DisjointSet() [2/8]

template<typename T, typename Allocator = PolymorphicAllocator<T>>

flow::DisjointSet< T, Allocator >::DisjointSet ( const allocator_type & allocator )

inlineexplicitconstexprnoexcept

Definition at line 39 of file flow_disjoint_set.h.

41 : groupSize_(0), data_(allocator) {

42 }

flow::DisjointSet

A disjoint union set that uses path compression and union by rank.

Definition flow_disjoint_set.h:10

References data_, and groupSize_.

◆ DisjointSet() [3/8]

template<typename T, typename Allocator = PolymorphicAllocator<T>>

flow::DisjointSet< T, Allocator >::DisjointSet ( const DisjointSet< T, Allocator > & )

constexprdefault

References DisjointSet().

◆ DisjointSet() [4/8]

template<typename T, typename Allocator = PolymorphicAllocator<T>>

flow::DisjointSet< T, Allocator >::DisjointSet	(	const DisjointSet< T, Allocator > &	rhs,
		const allocator_type &	allocator )

inlineconstexpr

Definition at line 45 of file flow_disjoint_set.h.

46 : groupSize_(rhs.groupSize_), data_(rhs.data_, allocator) {

47 }

References data_, DisjointSet(), and groupSize_.

◆ DisjointSet() [5/8]

template<typename T, typename Allocator = PolymorphicAllocator<T>>

flow::DisjointSet< T, Allocator >::DisjointSet ( DisjointSet< T, Allocator > && )

constexprdefault

References DisjointSet().

◆ DisjointSet() [6/8]

template<typename T, typename Allocator = PolymorphicAllocator<T>>

flow::DisjointSet< T, Allocator >::DisjointSet	(	DisjointSet< T, Allocator > &&	rhs,
		const allocator_type &	allocator )

inlineconstexprnoexcept

Definition at line 50 of file flow_disjoint_set.h.

      : 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:
      /*
      ⣿⡟⠙⠛⠋⠩⠭⣉⡛⢛⠫⠭⠄⠒⠄⠄⠄⠈⠉⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿
      ⣿⡇⠄⠄⠄⠄⣠⠖⠋⣀⡤⠄⠒⠄⠄⠄⠄⠄⠄⠄⠄⠄⣈⡭⠭⠄⠄⠄⠉⠙
      ⣿⡇⠄⠄⢀⣞⣡⠴⠚⠁⠄⠄⢀⠠⠄⠄⠄⠄⠄⠄⠄⠉⠄⠄⠄⠄⠄⠄⠄⠄
      ⣿⡇⠄⡴⠁⡜⣵⢗⢀⠄⢠⡔⠁⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄
      ⣿⡇⡜⠄⡜⠄⠄⠄⠉⣠⠋⠠⠄⢀⡄⠄⠄⣠⣆⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢸
      ⣿⠸⠄⡼⠄⠄⠄⠄⢰⠁⠄⠄⠄⠈⣀⣠⣬⣭⣛⠄⠁⠄⡄⠄⠄⠄⠄⠄⢀⣿
      ⣏⠄⢀⠁⠄⠄⠄⠄⠇⢀⣠⣴⣶⣿⣿⣿⣿⣿⣿⡇⠄⠄⡇⠄⠄⠄⠄⢀⣾⣿
      ⣿⣸⠈⠄⠄⠰⠾⠴⢾⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⢁⣾⢀⠁⠄⠄⠄⢠⢸⣿⣿
      ⣿⣿⣆⠄⠆⠄⣦⣶⣦⣌⣿⣿⣿⣿⣷⣋⣀⣈⠙⠛⡛⠌⠄⠄⠄⠄⢸⢸⣿⣿
      ⣿⣿⣿⠄⠄⠄⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠈⠄⠄⠄⠄⠄⠈⢸⣿⣿
      ⣿⣿⣿⠄⠄⠄⠘⣿⣿⣿⡆⢀⣈⣉⢉⣿⣿⣯⣄⡄⠄⠄⠄⠄⠄⠄⠄⠈⣿⣿
      ⣿⣿⡟⡜⠄⠄⠄⠄⠙⠿⣿⣧⣽⣍⣾⣿⠿⠛⠁⠄⠄⠄⠄⠄⠄⠄⠄⠃⢿⣿
      ⣿⡿⠰⠄⠄⠄⠄⠄⠄⠄⠄⠈⠉⠩⠔⠒⠉⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠐⠘⣿
      ⣿⠃⠃⠄⠄⠄⠄⠄⠄⣀⢀⠄⠄⡀⡀⢀⣤⣴⣤⣤⣀⣀⠄⠄⠄⠄⠄⠄⠁⢹
      */
    }

References data_, DisjointSet(), and groupSize_.

◆ DisjointSet() [7/8]

template<typename T, typename Allocator = PolymorphicAllocator<T>>

template<std::forward_iterator It>

flow::DisjointSet< T, Allocator >::DisjointSet	(	It	first,
		It	last,
		const allocator_type &	allocator = {} )

inlineexplicitconstexpr

Iterator range constructor.

Parameters

first	Iterator to first element.
last	Iterator to one-past-last element.
alloc	Allocator.

Definition at line 80 of file flow_disjoint_set.h.

                                                                                        {})
      : 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;
      }
    }

◆ DisjointSet() [8/8]

template<typename T, typename Allocator = PolymorphicAllocator<T>>

flow::DisjointSet< T, Allocator >::DisjointSet	(	std::initializer_list< T >	list,
		const allocator_type &	allocator = {} )

inlineexplicitconstexpr

Initializer list constructor.

Parameters

list	Initializer list.
alloc	Allocator.

Definition at line 92 of file flow_disjoint_set.h.

                                                                                                  {})
      : DisjointSet(list.begin(), list.end(), allocator) {
    }

◆ ~DisjointSet()

template<typename T, typename Allocator = PolymorphicAllocator<T>>

flow::DisjointSet< T, Allocator >::~DisjointSet ( )

default

Member Function Documentation

◆ add() [1/2]

template<typename T, typename Allocator = PolymorphicAllocator<T>>

void flow::DisjointSet< T, Allocator >::add ( const T & value )

inlineconstexpr

Add an element to the disjoint set.

Parameters

value The element.

Definition at line 131 of file flow_disjoint_set.h.

                                       {
      data_.pushBack(Node{ data_.size(), 0, value });
      ++groupSize_;
    }

References data_, and groupSize_.

◆ add() [2/2]

template<typename T, typename Allocator = PolymorphicAllocator<T>>

void flow::DisjointSet< T, Allocator >::add ( T && value )

inlineconstexpr

Add an element to the disjoint set.

Parameters

value The element.

Definition at line 138 of file flow_disjoint_set.h.

                                  {
      data_.pushBack(Node{ data_.size(), 0, std::move(value) });
      ++groupSize_;
    }

References data_, and groupSize_.

◆ empty()

template<typename T, typename Allocator = PolymorphicAllocator<T>>

bool flow::DisjointSet< T, Allocator >::empty ( ) const

inlineconstexpr

Check if the disjoint set is empty.

Returns: true if the disjoint set is empty.

Definition at line 119 of file flow_disjoint_set.h.

                                 {
      return data_.empty();
    }

References data_.

◆ find()

template<typename T, typename Allocator = PolymorphicAllocator<T>>

std::size_t flow::DisjointSet< T, Allocator >::find ( std::size_t i )

inlineconstexpr

Find the group id of the i-th node. Perform path compression along the way.

Parameters

i Index

Returns: The group id of the i-th node.

Definition at line 161 of file flow_disjoint_set.h.

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

References data_, and find().

Referenced by find(), isSameGroup(), and merge().

◆ get_allocator()

template<typename T, typename Allocator = PolymorphicAllocator<T>>

allocator_type flow::DisjointSet< T, Allocator >::get_allocator ( ) const

inlinenoexcept

Definition at line 99 of file flow_disjoint_set.h.

                                                  {
      return data_.get_allocator();
    }

References data_.

◆ groupSize()

template<typename T, typename Allocator = PolymorphicAllocator<T>>

std::size_t flow::DisjointSet< T, Allocator >::groupSize ( ) const

inlineconstexpr

Return the number of group.

Returns: The number of group.

Definition at line 113 of file flow_disjoint_set.h.

                                          {
      return groupSize_;
    }

References groupSize_.

◆ isSameGroup()

template<typename T, typename Allocator = PolymorphicAllocator<T>>

bool flow::DisjointSet< T, Allocator >::isSameGroup	(	std::size_t	i,
		std::size_t	j )

inlineconstexpr

Check if the i-th element and the j-th element are in the same group.

Parameters

i	The first index.
j	The second index.

Returns: True if in the same group.

Definition at line 173 of file flow_disjoint_set.h.

                                                         {
      return find(i) == find(j);
    }

References find().

◆ merge()

template<typename T, typename Allocator = PolymorphicAllocator<T>>

bool flow::DisjointSet< T, Allocator >::merge	(	std::size_t	i,
		std::size_t	j )

inlineconstexpr

Merge the i-th element's group with the j-th element's group. Internally, it unions them by ranking.

Parameters

i	The first index.
j	The second index.

Returns: True if merge successfully.

Definition at line 182 of file flow_disjoint_set.h.

                                                   {
      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;
    }

References data_, find(), and groupSize_.

◆ operator[]() [1/2]

template<typename T, typename Allocator = PolymorphicAllocator<T>>

T & flow::DisjointSet< T, Allocator >::operator[] ( std::size_t i )

inlineconstexpr

Get the value of the i-th element.

Parameters

i index

Returns: The value of the i-th element.

Definition at line 153 of file flow_disjoint_set.h.

                                         {
      return data_[i].value;
    }

References data_.

◆ operator[]() [2/2]

template<typename T, typename Allocator = PolymorphicAllocator<T>>

const T & flow::DisjointSet< T, Allocator >::operator[] ( std::size_t i ) const

inlineconstexpr

Get the value of the i-th element.

Parameters

i index

Returns: The value of the i-th element.

Definition at line 146 of file flow_disjoint_set.h.

                                                     {
      return data_[i].value;
    }

References data_.

◆ reserve()

template<typename T, typename Allocator = PolymorphicAllocator<T>>

void flow::DisjointSet< T, Allocator >::reserve ( std::size_t n )

inline

Reserve enough memory for at least n elements.

Parameters

n	The reserved size.

Definition at line 125 of file flow_disjoint_set.h.

                              {
      data_.reserve(n);
    }

References data_.

◆ size()

template<typename T, typename Allocator = PolymorphicAllocator<T>>

std::size_t flow::DisjointSet< T, Allocator >::size ( ) const

inlineconstexpr

Return the number of input elements.

Returns: The number of elements.

Definition at line 107 of file flow_disjoint_set.h.

                                     {
      return data_.size();
    }

References data_.

Member Data Documentation

◆ data_

template<typename T, typename Allocator = PolymorphicAllocator<T>>

container_type flow::DisjointSet< T, Allocator >::data_

private

Definition at line 31 of file flow_disjoint_set.h.

Referenced by add(), add(), DisjointSet(), DisjointSet(), DisjointSet(), DisjointSet(), empty(), find(), get_allocator(), merge(), operator[](), operator[](), reserve(), and size().

◆ groupSize_

template<typename T, typename Allocator = PolymorphicAllocator<T>>

std::size_t flow::DisjointSet< T, Allocator >::groupSize_

private

Definition at line 30 of file flow_disjoint_set.h.

Referenced by add(), add(), DisjointSet(), DisjointSet(), DisjointSet(), DisjointSet(), groupSize(), and merge().

The documentation for this class was generated from the following file:

flow_disjoint_set.h

Classes

Public Types

Public Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ allocator_type

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ container_type

◆ difference_type

◆ iterator

◆ pointer

◆ reference

◆ value_type

Constructor & Destructor Documentation

◆ DisjointSet() [1/8]

◆ DisjointSet() [2/8]

◆ DisjointSet() [3/8]

◆ DisjointSet() [4/8]

◆ DisjointSet() [5/8]

◆ DisjointSet() [6/8]

◆ DisjointSet() [7/8]

◆ DisjointSet() [8/8]

◆ ~DisjointSet()

Member Function Documentation

◆ add() [1/2]

◆ add() [2/2]

◆ empty()

◆ find()

◆ get_allocator()

◆ groupSize()

◆ isSameGroup()

◆ merge()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ reserve()

◆ size()

Member Data Documentation

◆ data_

◆ groupSize_