Blender  V3.3
BLI_disjoint_set.hh
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #pragma once
4 
11 #include "BLI_array.hh"
12 
13 namespace blender {
14 
15 class DisjointSet {
16  private:
17  Array<int64_t> parents_;
18  Array<int64_t> ranks_;
19 
20  public:
24  DisjointSet(int64_t size) : parents_(size), ranks_(size, 0)
25  {
26  BLI_assert(size >= 0);
27  for (int64_t i = 0; i < size; i++) {
28  parents_[i] = i;
29  }
30  }
31 
37  {
38  int64_t root1 = this->find_root(x);
39  int64_t root2 = this->find_root(y);
40 
41  /* x and y are in the same set already. */
42  if (root1 == root2) {
43  return;
44  }
45 
46  /* Implement union by rank heuristic. */
47  if (ranks_[root1] < ranks_[root2]) {
48  std::swap(root1, root2);
49  }
50  parents_[root2] = root1;
51 
52  if (ranks_[root1] == ranks_[root2]) {
53  ranks_[root1]++;
54  }
55  }
56 
61  {
62  int64_t root1 = this->find_root(x);
63  int64_t root2 = this->find_root(y);
64  return root1 == root2;
65  }
66 
71  {
72  /* Find root by following parents. */
73  int64_t root = x;
74  while (parents_[root] != root) {
75  root = parents_[root];
76  }
77 
78  /* Compress path. */
79  while (parents_[x] != root) {
80  int64_t parent = parents_[x];
81  parents_[x] = root;
82  x = parent;
83  }
84 
85  return root;
86  }
87 };
88 
89 } // namespace blender
#define BLI_assert(a)
Definition: BLI_assert.h:46
void swap(T &a, T &b)
Definition: Common.h:19
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint y
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
int64_t find_root(int64_t x)
void join(int64_t x, int64_t y)
DisjointSet(int64_t size)
bool in_same_set(int64_t x, int64_t y)
__int64 int64_t
Definition: stdint.h:89