1 /*========================== begin_copyright_notice ============================ 2 3 Copyright (C) 2019-2021 Intel Corporation 4 5 SPDX-License-Identifier: MIT 6 7 ============================= end_copyright_notice ===========================*/ 8 9 #pragma once 10 11 #include "Object.h" 12 #include "Queue.h" 13 14 namespace iSTD 15 { 16 17 /*****************************************************************************\ 18 Struct: IsDisjointSetTypeSupported 19 \*****************************************************************************/ 20 template<typename T> 21 struct IsDisjointSetTypeSupported { enum { value = false }; }; 22 23 template<> 24 struct IsDisjointSetTypeSupported<bool> { enum { value = true }; }; 25 26 template<> 27 struct IsDisjointSetTypeSupported<char> { enum { value = true }; }; 28 29 template<> 30 struct IsDisjointSetTypeSupported<unsigned char> { enum { value = true }; }; 31 32 template<> 33 struct IsDisjointSetTypeSupported<int> { enum { value = true }; }; 34 35 template<> 36 struct IsDisjointSetTypeSupported<unsigned int> { enum { value = true }; }; 37 38 #ifndef __LP64__ // u/long on linux64 platform is 64-bit type and collides with U/INT64 39 template<> 40 struct IsDisjointSetTypeSupported<long> { enum { value = true }; }; 41 42 template<> 43 struct IsDisjointSetTypeSupported<unsigned long> { enum { value = true }; }; 44 #endif 45 46 template<> 47 struct IsDisjointSetTypeSupported<INT64> { enum { value = true }; }; 48 49 template<> 50 struct IsDisjointSetTypeSupported<UINT64> { enum { value = true }; }; 51 52 template<typename T> 53 struct IsDisjointSetTypeSupported<T*> { enum { value = true }; }; 54 55 /*****************************************************************************\ 56 Template Parameters 57 \*****************************************************************************/ 58 #define DisjointSetTemplateList class Type, class CAllocatorType 59 #define CDisjointSetType CDisjointSet<Type,CAllocatorType> 60 61 /*****************************************************************************\ 62 63 Class: 64 CDisjointSet 65 66 Description: 67 Implements a union find disjoint set 68 69 \*****************************************************************************/ 70 template<DisjointSetTemplateList> 71 class CDisjointSet : public CObject<CAllocatorType> 72 { 73 public: 74 75 CDisjointSet( void ); 76 virtual ~CDisjointSet( void ); 77 78 void Union( CDisjointSetType& ds ); 79 80 const Type& Find( void ); 81 void Set( const Type& item ); 82 83 C_ASSERT( IsDisjointSetTypeSupported<Type>::value == true ); 84 85 protected: 86 87 CDisjointSetType* RootRecursive( CDisjointSetType* node ); 88 CDisjointSetType* RootNonRecursive( CDisjointSetType* node ); 89 90 CDisjointSetType* m_pParent; 91 92 Type m_Item; 93 }; 94 95 /*****************************************************************************\ 96 97 Function: 98 CDisjointSet Constructor 99 100 Description: 101 Initializes the disjoint set 102 103 Input: 104 105 Output: 106 none 107 108 \*****************************************************************************/ 109 template<DisjointSetTemplateList> 110 CDisjointSetType::CDisjointSet( void ) 111 : CObject<CAllocatorType>() 112 { 113 m_pParent = this; 114 } 115 116 /*****************************************************************************\ 117 118 Function: 119 CDisjointSet Destructor 120 121 Description: 122 Frees all internal dynamic memory 123 124 Input: 125 none 126 127 Output: 128 none 129 130 \*****************************************************************************/ 131 template<DisjointSetTemplateList> 132 CDisjointSetType::~CDisjointSet( void ) 133 { 134 // Nothing! 135 } 136 137 /*****************************************************************************\ 138 139 Function: 140 CDisjointSet::Union 141 142 Description: 143 Unions this disjoint set with the passed in disjoint set 144 145 Input: 146 CDisjointSet& ds - other disjoint set 147 148 Output: 149 void 150 151 \*****************************************************************************/ 152 template<DisjointSetTemplateList> 153 void CDisjointSetType::Union( CDisjointSetType& ds ) 154 { 155 CDisjointSetType* oldRoot = RootNonRecursive( this ); 156 CDisjointSetType* newRoot = RootNonRecursive( &ds ); 157 158 if( oldRoot != newRoot ) 159 { 160 oldRoot->m_pParent = newRoot; 161 } 162 } 163 164 /*****************************************************************************\ 165 166 Function: 167 CDisjointSet::Find 168 169 Description: 170 Finds the item in this disjoint set 171 172 Input: 173 void 174 175 Output: 176 const Type& - root of this disjoint set 177 178 \*****************************************************************************/ 179 template<DisjointSetTemplateList> 180 const Type& CDisjointSetType::Find( void ) 181 { 182 CDisjointSetType* root = RootNonRecursive( this ); 183 184 return root->m_Item; 185 } 186 187 /*****************************************************************************\ 188 189 Function: 190 CDisjointSet::Set 191 192 Description: 193 Sets the item stored in this disjoint set 194 195 Input: 196 const Type& - item stored in this disjoint set 197 198 Output: 199 void 200 201 \*****************************************************************************/ 202 template<DisjointSetTemplateList> 203 void CDisjointSetType::Set( const Type& item ) 204 { 205 CDisjointSetType* root = RootNonRecursive( this ); 206 207 root->m_Item = item; 208 } 209 210 /*****************************************************************************\ 211 212 Function: 213 CDisjointSet::RootRecursive 214 215 Description: 216 Returns the root node of this disjoint set. Also performs path 217 compression using recursion. 218 219 Input: 220 void 221 222 Output: 223 CDisjointSetType* root node 224 225 \*****************************************************************************/ 226 template<DisjointSetTemplateList> 227 CDisjointSetType* CDisjointSetType::RootRecursive( 228 CDisjointSetType* node ) 229 { 230 if( node->m_pParent != node ) 231 { 232 CDisjointSetType* root = RootRecursive( node->m_pParent ); 233 node->m_pParent = root; 234 } 235 236 return node; 237 } 238 239 /*****************************************************************************\ 240 241 Function: 242 CDisjointSet::RootNonRecursive 243 244 Description: 245 Returns the root node of this disjoint set. Also performs path 246 compression without using recursion. The actual path compression isn't 247 quite as good as the recursive version but it's pretty good and the 248 speed gains from not using recursion might be more important. 249 250 Input: 251 void 252 253 Output: 254 CDisjointSetType* root node 255 256 \*****************************************************************************/ 257 template<DisjointSetTemplateList> 258 CDisjointSetType* CDisjointSetType::RootNonRecursive( 259 CDisjointSetType* node ) 260 { 261 while( node->m_pParent != node ) 262 { 263 node->m_pParent = node->m_pParent->m_pParent; 264 node = node->m_pParent; 265 } 266 267 return node; 268 } 269 270 } // iSTD 271