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