00001 /**************************************************************************** 00002 * VCGLib o o * 00003 * Visual and Computer Graphics Library o o * 00004 * _ O _ * 00005 * Copyright(C) 2004 \/)\/ * 00006 * Visual Computing Lab /\/| * 00007 * ISTI - Italian National Research Council | * 00008 * \ * 00009 * All rights reserved. * 00010 * * 00011 * This program is free software; you can redistribute it and/or modify * 00012 * it under the terms of the GNU General Public License as published by * 00013 * the Free Software Foundation; either version 2 of the License, or * 00014 * (at your option) any later version. * 00015 * * 00016 * This program is distributed in the hope that it will be useful, * 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 00019 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt) * 00020 * for more details. * 00021 * * 00022 ****************************************************************************/ 00023 00024 #ifndef VCG_MATH_UNIONSET_H 00025 #define VCG_MATH_UNIONSET_H 00026 00027 #include <unordered_map> 00028 #include <vector> 00029 #include <assert.h> 00030 00031 namespace vcg 00032 { 00038 template<class OBJECT_TYPE> 00039 class DisjointSet 00040 { 00041 /************************************************* 00042 * Inner class definitions 00043 **************************************************/ 00044 struct DisjointSetNode 00045 { 00046 DisjointSetNode(OBJECT_TYPE *x) {obj=x; parent=obj; rank=0;} 00047 OBJECT_TYPE *obj; 00048 OBJECT_TYPE *parent; 00049 int rank; 00050 }; 00051 00052 typedef OBJECT_TYPE* ObjectPointer; 00053 typedef std::pair< ObjectPointer, int > hPair; 00054 00055 struct SimpleObjHashFunc{ 00056 inline size_t operator ()(const ObjectPointer &p) const {return size_t(p);} 00057 }; 00058 00059 std::unordered_map< OBJECT_TYPE*, int > inserted_objects; 00060 typedef typename std::unordered_map< OBJECT_TYPE*, int >::iterator hIterator; 00061 00062 typedef std::pair< hIterator, bool > hInsertResult; 00063 00064 00065 public: 00069 DisjointSet() {} 00070 00074 void MakeSet(OBJECT_TYPE *x) 00075 { 00076 int object_count = int(inserted_objects.size()); 00077 assert(inserted_objects.find(x)==inserted_objects.end()); //the map mustn't already contain the object x 00078 nodes.push_back(DisjointSetNode(x)); 00079 inserted_objects.insert( hPair(x,object_count) ); 00080 } 00081 00085 void Union(OBJECT_TYPE *x, OBJECT_TYPE *y) 00086 { 00087 OBJECT_TYPE *s0 = FindSet(x); 00088 OBJECT_TYPE *s1 = FindSet(y); 00089 Link(s0, s1); 00090 } 00091 00095 OBJECT_TYPE* FindSet(OBJECT_TYPE *x) 00096 { 00097 hIterator pos = inserted_objects.find(x); 00098 assert(pos!=inserted_objects.end()); 00099 DisjointSetNode *node = &nodes[pos->second]; 00100 if (node->parent!=x) 00101 node->parent = FindSet(node->parent); 00102 return node->parent; 00103 } 00104 00105 private: 00106 /* 00107 */ 00108 void Link(OBJECT_TYPE *x, OBJECT_TYPE *y) 00109 { 00110 hIterator xPos = inserted_objects.find(x); 00111 hIterator yPos = inserted_objects.find(y); 00112 assert(xPos!=inserted_objects.end() && yPos!=inserted_objects.end()); 00113 DisjointSetNode *xNode = &nodes[xPos->second]; 00114 DisjointSetNode *yNode = &nodes[yPos->second]; 00115 if (xNode->rank>yNode->rank) 00116 xNode->parent = y; 00117 else 00118 { 00119 yNode->parent = x; 00120 if (xNode->rank==yNode->rank) 00121 yNode->rank++; 00122 } 00123 } 00124 00125 protected: 00126 std::vector< DisjointSetNode > nodes; 00127 }; 00128 };// end of namespace vcg 00129 00130 #endif //VCG_MATH_UNIONSET_H