Blender  V3.3
disjoint_set.h
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0
2  * Copyright 2011-2022 Blender Foundation */
3 
4 #ifndef __UTIL_DISJOINT_SET_H__
5 #define __UTIL_DISJOINT_SET_H__
6 
7 #include "util/array.h"
8 #include <utility>
9 
11 
12 class DisjointSet {
13  private:
14  array<size_t> parents;
15  array<size_t> ranks;
16 
17  public:
18  DisjointSet(size_t size) : parents(size), ranks(size)
19  {
20  for (size_t i = 0; i < size; i++) {
21  parents[i] = i;
22  ranks[i] = 0;
23  }
24  }
25 
26  size_t find(size_t x)
27  {
28  size_t root = x;
29  while (parents[root] != root) {
30  root = parents[root];
31  }
32  while (parents[x] != root) {
33  size_t parent = parents[x];
34  parents[x] = root;
35  x = parent;
36  }
37  return root;
38  }
39 
40  void join(size_t x, size_t y)
41  {
42  size_t x_root = find(x);
43  size_t y_root = find(y);
44 
45  if (x_root == y_root) {
46  return;
47  }
48 
49  if (ranks[x_root] < ranks[y_root]) {
50  std::swap(x_root, y_root);
51  }
52  parents[y_root] = x_root;
53 
54  if (ranks[x_root] == ranks[y_root]) {
55  ranks[x_root]++;
56  }
57  }
58 };
59 
61 
62 #endif /* __UTIL_DISJOINT_SET_H__ */
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
void join(size_t x, size_t y)
Definition: disjoint_set.h:40
DisjointSet(size_t size)
Definition: disjoint_set.h:18
size_t find(size_t x)
Definition: disjoint_set.h:26
#define CCL_NAMESPACE_END
Definition: cuda/compat.h:9