UnionFind.h
1 /************************************************************
2 * (C) Voxel Farm Inc. 2015
3 */
4 
5 
6 #pragma once
7 
8 #include <stdint.h>
9 
10 namespace VoxelFarm
11 {
12 
13  /****************************
14  * *
15  * Union Find *
16  * (Fast Classification) *
17  * *
18  ****************************/
19  template <typename idxType>
20  class CUnionFind
21  {
22  public:
23  CUnionFind() {};
24  CUnionFind(idxType N);
25  ~CUnionFind();
26  idxType Find(idxType id);
27  void Union(idxType id1, idxType id2);
28  void Reset();
29  protected:
30  struct node
31  {
32  idxType parent;
33  idxType rank;
34  };
35  node* uf;
36  idxType size;
37  };
38 
39  template <typename idxType>
41  {
42  this->size = N;
43  this->uf = VF_ALLOC(node, N);
44  for (idxType i = 0; i < N; i++)
45  {
46  uf[i].parent = i;
47  uf[i].rank = 0;
48  }
49  }
50 
51  template <typename idxType>
52  CUnionFind<idxType>::~CUnionFind()
53  {
54  VF_FREE(uf);
55  }
56 
57  template <typename idxType>
58  idxType CUnionFind<idxType>::Find(idxType id)
59  {
60  if (uf[id].parent != id)
61  {
62  uf[id].parent = Find(uf[id].parent);
63  }
64  return uf[id].parent;
65  }
66 
67  template <typename idxType>
68  void CUnionFind<idxType>::Union(idxType id1, idxType id2)
69  {
70  if (id1 == id2)
71  {
72  return;
73  }
74 
75  idxType id1Root = Find(id1);
76  idxType id2Root = Find(id2);
77 
78  if (id1Root == id2Root)
79  {
80  return;
81  }
82 
83  if (uf[id1Root].rank < uf[id2Root].rank)
84  {
85  uf[id1Root].parent = id2Root;
86  }
87 
88  else if (uf[id1Root].rank > uf[id2Root].rank)
89  {
90  uf[id2Root].parent = id1Root;
91  }
92 
93  else
94  {
95  uf[id2Root].parent = id1Root;
96  uf[id1Root].rank++;
97  }
98  }
99 
100  template <typename idxType>
101  void CUnionFind<idxType>::Reset()
102  {
103  for (idxType i = 0; i < this->size; i++)
104  {
105  uf[i].parent = i;
106  uf[i].rank = 0;
107  }
108  }
109 
110  typedef CUnionFind<uint16_t> CUnionFind16;
111  typedef CUnionFind<uint32_t> CUnionFind32;
112 }
Contains all classes and functions for the VoxelFarm engine.