1251 }
1252 #endif
1253
1254 UnionFind::UnionFind( uint max ) : _cnt(max), _max(max), _indices(NEW_RESOURCE_ARRAY(uint,max)) {
1255 Copy::zero_to_bytes( _indices, sizeof(uint)*max );
1256 }
1257
1258 void UnionFind::extend( uint from_idx, uint to_idx ) {
1259 _nesting.check();
1260 if( from_idx >= _max ) {
1261 uint size = 16;
1262 while( size <= from_idx ) size <<=1;
1263 _indices = REALLOC_RESOURCE_ARRAY( uint, _indices, _max, size );
1264 _max = size;
1265 }
1266 while( _cnt <= from_idx ) _indices[_cnt++] = 0;
1267 _indices[from_idx] = to_idx;
1268 }
1269
1270 void UnionFind::reset( uint max ) {
1271 assert( max <= max_uint, "Must fit within uint" );
1272 // Force the Union-Find mapping to be at least this large
1273 extend(max,0);
1274 // Initialize to be the ID mapping.
1275 for( uint i=0; i<max; i++ ) map(i,i);
1276 }
1277
1278 // Straight out of Tarjan's union-find algorithm
1279 uint UnionFind::Find_compress( uint idx ) {
1280 uint cur = idx;
1281 uint next = lookup(cur);
1282 while( next != cur ) { // Scan chain of equivalences
1283 assert( next < cur, "always union smaller" );
1284 cur = next; // until find a fixed-point
1285 next = lookup(cur);
1286 }
1287 // Core of union-find algorithm: update chain of
1288 // equivalences to be equal to the root.
1289 while( idx != next ) {
1290 uint tmp = lookup(idx);
1291 map(idx, next);
|
1251 }
1252 #endif
1253
1254 UnionFind::UnionFind( uint max ) : _cnt(max), _max(max), _indices(NEW_RESOURCE_ARRAY(uint,max)) {
1255 Copy::zero_to_bytes( _indices, sizeof(uint)*max );
1256 }
1257
1258 void UnionFind::extend( uint from_idx, uint to_idx ) {
1259 _nesting.check();
1260 if( from_idx >= _max ) {
1261 uint size = 16;
1262 while( size <= from_idx ) size <<=1;
1263 _indices = REALLOC_RESOURCE_ARRAY( uint, _indices, _max, size );
1264 _max = size;
1265 }
1266 while( _cnt <= from_idx ) _indices[_cnt++] = 0;
1267 _indices[from_idx] = to_idx;
1268 }
1269
1270 void UnionFind::reset( uint max ) {
1271 // Force the Union-Find mapping to be at least this large
1272 extend(max,0);
1273 // Initialize to be the ID mapping.
1274 for( uint i=0; i<max; i++ ) map(i,i);
1275 }
1276
1277 // Straight out of Tarjan's union-find algorithm
1278 uint UnionFind::Find_compress( uint idx ) {
1279 uint cur = idx;
1280 uint next = lookup(cur);
1281 while( next != cur ) { // Scan chain of equivalences
1282 assert( next < cur, "always union smaller" );
1283 cur = next; // until find a fixed-point
1284 next = lookup(cur);
1285 }
1286 // Core of union-find algorithm: update chain of
1287 // equivalences to be equal to the root.
1288 while( idx != next ) {
1289 uint tmp = lookup(idx);
1290 map(idx, next);
|