00001
00007 #include "DisjointSet.hpp"
00008 #include "Debug.hpp"
00009 #include <iostream>
00010 #include <cstring>
00011 #include <algorithm>
00012 using namespace std;
00013
00014 DisjointSet::DisjointSet( unsigned int numItems ) :
00015 mNumItems( numItems )
00016 {
00017 mParents = new unsigned int[mNumItems];
00018 mSizes = new unsigned int[mNumItems];
00019
00020
00021
00022 for( unsigned int i = 0; i < mNumItems; i++ )
00023 {
00024 mParents[i] = i;
00025 mSizes[i] = 1;
00026 }
00027 }
00028
00029 DisjointSet::DisjointSet( const DisjointSet & that )
00030 {
00031
00032 mParents = new unsigned int[that.mNumItems];
00033 mSizes = new unsigned int[that.mNumItems];
00034
00035
00036 mNumItems = that.mNumItems;
00037 memcpy( mParents, that.mParents, sizeof( unsigned int ) * mNumItems );
00038 memcpy( mSizes, that.mSizes, sizeof( unsigned int ) * mNumItems );
00039 }
00040
00041 DisjointSet::~DisjointSet()
00042 {
00043 delete [] mParents;
00044 delete [] mSizes;
00045 }
00046
00047 void DisjointSet::setUnion( unsigned int x, unsigned int y )
00048 {
00049
00050
00051 fatalAssert( x != y && x < mNumItems && y < mNumItems && find( x ) != find( y ), "Failure in setUnion()." );
00052
00053
00054 if( !isRepresentative( x ) )
00055 {
00056 rebase( x );
00057 }
00058
00059 if( !isRepresentative( y ) )
00060 {
00061 rebase( y );
00062 }
00063
00064
00065
00066
00067 if( mSizes[x] >= mSizes[y] )
00068 {
00069 mParents[y] = x;
00070 mSizes[x] += mSizes[y];
00071 }
00072
00073 else
00074 {
00075 mParents[x] = y;
00076 mSizes[y] += mSizes[x];
00077 }
00078 }
00079
00080 unsigned int DisjointSet::find( unsigned int x ) const
00081 {
00082
00083 fatalAssert( x < mNumItems, "You tried to make find() cause a segfault." );
00084
00085
00086 unsigned int curr = x;
00087 while( !isRepresentative( curr ) )
00088 {
00089 curr = mParents[curr];
00090 }
00091
00092 return curr;
00093 }
00094
00095 void DisjointSet::split( unsigned int x, unsigned int y )
00096 {
00097
00098 fatalAssert( x != y && x < mNumItems && y < mNumItems, "Failure in split()." );
00099
00100
00101
00102
00103 fatalAssert( mParents[x] == y || mParents[y] == x, "Pointless to split two sets which are already disjoint" );
00104
00105
00106 unsigned int parent = ( mParents[x] == y ? y : x );
00107 unsigned int child = ( mParents[x] == y ? x : y );
00108
00109 unsigned int curr = parent;
00110 while( !isRepresentative( curr ) )
00111 {
00112
00113 mSizes[curr] -= mSizes[child];
00114 curr = mParents[curr];
00115 }
00116 mSizes[curr] -= mSizes[x];
00117
00118
00119 mParents[child] = child;
00120 }
00121
00122 void DisjointSet::getSetSizes( std::vector<unsigned int> & sizes ) const
00123 {
00124 sizes.clear();
00125 for( unsigned int i = 0; i < mNumItems; i++ )
00126 {
00127
00128 if( isRepresentative( i ) )
00129 {
00130 sizes.push_back( mSizes[i] );
00131 }
00132 }
00133
00134
00135 std::sort( sizes.begin(), sizes.end(), std::greater<int>() );
00136 }
00137
00138 void DisjointSet::print() const
00139 {
00140 cout << ">>> Set State <<< " << endl;
00141 for( unsigned int i = 0; i < mNumItems; i++ )
00142 {
00143 cout << "Item: " << i
00144 << " (Parent: " << mParents[i]
00145 << ", Size: " << mSizes[i]
00146 << ", Representative: " << find( i ) << ")" << endl;
00147 }
00148 }
00149
00150 DisjointSet & DisjointSet::operator=( const DisjointSet & that )
00151 {
00152 if( this != &that )
00153 {
00154
00155 delete [] mParents;
00156 delete [] mSizes;
00157
00158
00159 mNumItems = that.mNumItems;
00160 mParents = new unsigned int[mNumItems];
00161 mSizes = new unsigned int[mNumItems];
00162
00163
00164 memcpy( mParents, that.mParents, sizeof( unsigned int ) * mNumItems );
00165 memcpy( mSizes, that.mSizes, sizeof( unsigned int ) * mNumItems );
00166 }
00167
00168 return *this;
00169 }
00170
00171 void DisjointSet::rebase( unsigned int x )
00172 {
00173
00174
00175 fatalAssert( !isRepresentative( x ), "Pointless to rebase a representative." );
00176
00177
00178
00179 unsigned int prev = x;
00180 unsigned int curr = x;
00181 unsigned int next = mParents[x];
00182 while( !isRepresentative( curr ) )
00183 {
00184 mParents[curr] = prev;
00185 prev = curr;
00186 curr = next;
00187 next = mParents[next];
00188 }
00189 mParents[curr] = prev;
00190
00191
00192 unsigned int formerRepSize = mSizes[curr];
00193 while( !isRepresentative( curr ) )
00194 {
00195 next = mParents[curr];
00196 mSizes[curr] = formerRepSize - mSizes[next];
00197 curr = next;
00198 }
00199 mSizes[curr] = formerRepSize;
00200 }