moab
|
00001 #ifdef WIN32 00002 #ifdef _DEBUG 00003 // turn off warnings that say they debugging identifier has been truncated 00004 // this warning comes up when using some STL containers 00005 #pragma warning(disable : 4786) 00006 #endif 00007 #endif 00008 00009 #include "MeshSet.hpp" 00010 #include "AEntityFactory.hpp" 00011 00012 namespace moab { 00013 00014 00015 /***************************************************************************************** 00016 * Helper Function Declarations * 00017 *****************************************************************************************/ 00018 00020 static inline 00021 MeshSet::Count insert_in_vector( const MeshSet::Count count, 00022 MeshSet::CompactList& list, 00023 const EntityHandle h, 00024 int &result ); 00025 00027 static inline 00028 MeshSet::Count remove_from_vector( const MeshSet::Count count, 00029 MeshSet::CompactList& list, 00030 const EntityHandle h, 00031 int &result ); 00032 00033 00035 static EntityHandle* resize_compact_list( MeshSet::Count& count, 00036 MeshSet::CompactList& clist, 00037 size_t new_list_size ); 00041 template <typename pair_iter_t> class range_tool 00042 { 00043 public: 00045 inline static ErrorCode ranged_insert_entities( MeshSet::Count& count, 00046 MeshSet::CompactList& clist, 00047 pair_iter_t begin, 00048 pair_iter_t end, 00049 EntityHandle my_handle, 00050 AEntityFactory* adj ); 00051 00053 inline static ErrorCode ranged_remove_entities( MeshSet::Count& count, 00054 MeshSet::CompactList& clist, 00055 pair_iter_t begin, 00056 pair_iter_t end, 00057 EntityHandle my_handle, 00058 AEntityFactory* adj ); 00059 00061 inline static ErrorCode vector_insert_entities( MeshSet::Count& count, 00062 MeshSet::CompactList& clist, 00063 pair_iter_t begin, 00064 pair_iter_t end, 00065 EntityHandle my_handle, 00066 AEntityFactory* adj ); 00067 }; 00068 00070 static ErrorCode vector_remove_range( MeshSet::Count& count, 00071 MeshSet::CompactList& clist, 00072 const Range& range, 00073 EntityHandle my_handle, 00074 AEntityFactory* adj ); 00075 00077 static ErrorCode vector_remove_ranges( MeshSet::Count& count, 00078 MeshSet::CompactList& clist, 00079 const EntityHandle* pair_list, 00080 size_t num_pairs, 00081 EntityHandle my_handle, 00082 AEntityFactory* adj ); 00083 00085 static ErrorCode vector_remove_vector( MeshSet::Count& count, 00086 MeshSet::CompactList& clist, 00087 const EntityHandle* vect, 00088 size_t vect_size, 00089 EntityHandle my_handle, 00090 AEntityFactory* adj ); 00091 00093 static ErrorCode vector_insert_vector( MeshSet::Count& count, 00094 MeshSet::CompactList& clist, 00095 const EntityHandle* vect, 00096 size_t vect_size, 00097 EntityHandle my_handle, 00098 AEntityFactory* adj ); 00099 00101 static void convert_to_ranges( const EntityHandle* vect_in, size_t vect_in_len, 00102 std::vector<EntityHandle>& vect_out ); 00103 00104 00105 /***************************************************************************************** 00106 * Parent/Child Operations * 00107 *****************************************************************************************/ 00108 00109 static inline 00110 MeshSet::Count insert_in_vector( const MeshSet::Count count, 00111 MeshSet::CompactList& list, 00112 const EntityHandle h, 00113 int &result ) 00114 { 00115 switch (count) { 00116 case MeshSet::ZERO: 00117 list.hnd[0] = h; 00118 result = true; 00119 return MeshSet::ONE; 00120 case MeshSet::ONE: 00121 if (list.hnd[0] == h) { 00122 result = false; 00123 return MeshSet::ONE; 00124 } 00125 else { 00126 result = true; 00127 list.hnd[1] = h; 00128 return MeshSet::TWO; 00129 } 00130 case MeshSet::TWO: 00131 if (list.hnd[0] == h || list.hnd[1] == h) { 00132 result = false; 00133 return MeshSet::TWO; 00134 } 00135 else { 00136 EntityHandle* ptr = (EntityHandle*)malloc(3*sizeof(EntityHandle)); 00137 ptr[0] = list.hnd[0]; 00138 ptr[1] = list.hnd[1]; 00139 ptr[2] = h; 00140 list.ptr[0] = ptr; 00141 list.ptr[1] = ptr + 3; 00142 result = true; 00143 return MeshSet::MANY; 00144 } 00145 case MeshSet::MANY: 00146 if (std::find( list.ptr[0], list.ptr[1], h ) != list.ptr[1]) { 00147 result = false; 00148 } 00149 else { 00150 int size = list.ptr[1] - list.ptr[0]; 00151 list.ptr[0] = (EntityHandle*)realloc( list.ptr[0], (size+1)*sizeof(EntityHandle) ); 00152 list.ptr[0][size] = h; 00153 list.ptr[1] = list.ptr[0] + size + 1; 00154 result = true; 00155 } 00156 return MeshSet::MANY; 00157 } 00158 00159 return MeshSet::ZERO; 00160 } 00161 00162 static inline 00163 MeshSet::Count remove_from_vector( const MeshSet::Count count, 00164 MeshSet::CompactList& list, 00165 const EntityHandle h, 00166 int &result ) 00167 { 00168 switch (count) { 00169 case MeshSet::ZERO: 00170 result = false; 00171 return MeshSet::ZERO; 00172 case MeshSet::ONE: 00173 if (h == list.hnd[0]) { 00174 result = true; 00175 return MeshSet::ZERO; 00176 } 00177 else { 00178 result = false; 00179 return MeshSet::ONE; 00180 } 00181 case MeshSet::TWO: 00182 if (h == list.hnd[0]) { 00183 list.hnd[0] = list.hnd[1]; 00184 result = true; 00185 return MeshSet::ONE; 00186 } 00187 else if (h == list.hnd[1]) { 00188 result = true; 00189 return MeshSet::ONE; 00190 } 00191 else { 00192 result = false; 00193 return MeshSet::TWO; 00194 } 00195 case MeshSet::MANY: { 00196 EntityHandle *i, *j, *p; 00197 i = std::find( list.ptr[0], list.ptr[1], h ); 00198 if (i == list.ptr[1]) { 00199 result = false; 00200 return MeshSet::MANY; 00201 } 00202 00203 result = true; 00204 p = list.ptr[1] - 1; 00205 while (i != p) { 00206 j = i + 1; 00207 *i = *j; 00208 i = j; 00209 } 00210 int size = p - list.ptr[0]; 00211 if (size == 2) { 00212 p = list.ptr[0]; 00213 list.hnd[0] = p[0]; 00214 list.hnd[1] = p[1]; 00215 free( p ); 00216 return MeshSet::TWO; 00217 } 00218 else { 00219 list.ptr[0] = (EntityHandle*)realloc( list.ptr[0], size*sizeof(EntityHandle) ); 00220 list.ptr[1] = list.ptr[0] + size; 00221 return MeshSet::MANY; 00222 } 00223 } 00224 } 00225 00226 return MeshSet::ZERO; 00227 } 00228 00229 00230 int MeshSet::add_parent( EntityHandle parent ) 00231 { 00232 int result = 0; 00233 mParentCount = insert_in_vector( (Count)mParentCount, parentMeshSets, parent, result ); 00234 return result; 00235 } 00236 int MeshSet::add_child( EntityHandle child ) 00237 { 00238 int result = 0; 00239 mChildCount = insert_in_vector( (Count)mChildCount, childMeshSets, child, result ); 00240 return result; 00241 } 00242 00243 int MeshSet::remove_parent( EntityHandle parent ) 00244 { 00245 int result = 0; 00246 mParentCount = remove_from_vector( (Count)mParentCount, parentMeshSets, parent, result ); 00247 return result; 00248 } 00249 int MeshSet::remove_child( EntityHandle child ) 00250 { 00251 int result = 0; 00252 mChildCount = remove_from_vector( (Count)mChildCount, childMeshSets, child, result ); 00253 return result; 00254 } 00255 00256 00257 /***************************************************************************************** 00258 * Flag Conversion Operations * 00259 *****************************************************************************************/ 00260 00261 ErrorCode MeshSet::convert( unsigned flg, EntityHandle my_handle, AEntityFactory* adj ) 00262 { 00263 ErrorCode rval = MB_SUCCESS; 00264 if ((mFlags & MESHSET_TRACK_OWNER) && !(flg & MESHSET_TRACK_OWNER)) 00265 rval = remove_adjacencies( my_handle, adj ); 00266 else if (!(mFlags & MESHSET_TRACK_OWNER) && (flg & MESHSET_TRACK_OWNER)) 00267 rval = create_adjacencies( my_handle, adj ); 00268 if (MB_SUCCESS != rval) 00269 return rval; 00270 00271 if (!(mFlags & MESHSET_ORDERED) && (flg & MESHSET_ORDERED)) { 00272 size_t datalen; 00273 EntityHandle* data = get_contents(datalen); 00274 if (datalen) { 00275 std::vector<EntityHandle> list( datalen ); 00276 memcpy( &list[0], data, datalen*sizeof(EntityHandle) ); 00277 int num_ents = num_entities(); 00278 Count count = (Count)mContentCount; 00279 data = resize_compact_list( count, contentList, num_ents ); 00280 mContentCount = count; 00281 assert( list.size() % 2 == 0 ); 00282 std::vector<EntityHandle>::iterator i = list.begin(); 00283 while (i != list.end()) { 00284 EntityHandle h = *i; ++i; 00285 EntityHandle e = *i; ++i; 00286 for (; h <= e; ++h) { 00287 *data = h; 00288 ++data; 00289 } 00290 } 00291 } 00292 } 00293 else if ((mFlags & MESHSET_ORDERED) && !(flg & MESHSET_ORDERED)) { 00294 size_t datalen; 00295 EntityHandle* data = get_contents(datalen); 00296 if (datalen) { 00297 std::vector<EntityHandle> ranges; 00298 convert_to_ranges( data, datalen, ranges ); 00299 Count count = (Count)mContentCount; 00300 data = resize_compact_list( count, contentList, ranges.size() ); 00301 mContentCount = count; 00302 memcpy( data, &ranges[0], ranges.size()*sizeof(EntityHandle) ); 00303 } 00304 } 00305 00306 return MB_SUCCESS; 00307 } 00308 00309 ErrorCode MeshSet::create_adjacencies( EntityHandle my_handle, AEntityFactory* adj ) 00310 { 00311 ErrorCode rval = MB_SUCCESS;; 00312 size_t count; 00313 const EntityHandle *const ptr = get_contents( count ); 00314 const EntityHandle *const end = ptr + count; 00315 if (vector_based()) { 00316 for (const EntityHandle* i = ptr; i != end; ++i) { 00317 rval = adj->add_adjacency( *i, my_handle, false ); 00318 if (MB_SUCCESS != rval) { 00319 for (const EntityHandle* j = ptr; j != i; ++j) 00320 adj->remove_adjacency( *j, my_handle ); 00321 return rval; 00322 } 00323 } 00324 } 00325 else { 00326 assert( 0 == count % 2 ); 00327 for (const EntityHandle* i = ptr; i != end; i += 2) { 00328 for (EntityHandle h = i[0]; h <= i[1]; ++h) { 00329 rval = adj->add_adjacency( h, my_handle, false ); 00330 if (MB_SUCCESS != rval) { 00331 for (EntityHandle j = i[0]; j < h; ++j) 00332 adj->remove_adjacency( j, my_handle ); 00333 for (const EntityHandle* j = ptr; j != i; j += 2) 00334 for (EntityHandle k = j[0]; k <= j[1]; ++k) 00335 adj->remove_adjacency( k, my_handle ); 00336 return rval; 00337 } 00338 } 00339 } 00340 } 00341 return MB_SUCCESS; 00342 } 00343 00344 ErrorCode MeshSet::remove_adjacencies( EntityHandle my_handle, AEntityFactory* adj ) 00345 { 00346 size_t count; 00347 const EntityHandle *const ptr = get_contents( count ); 00348 const EntityHandle *const end = ptr + count; 00349 if (vector_based()) { 00350 for (const EntityHandle* i = ptr; i != end; ++i) 00351 adj->remove_adjacency( *i, my_handle ); 00352 } 00353 else { 00354 assert( 0 == count % 2 ); 00355 for (const EntityHandle* i = ptr; i != end; i += 2) 00356 for (EntityHandle h = i[0]; h <= i[1]; ++h) 00357 adj->remove_adjacency( h, my_handle ); 00358 } 00359 return MB_SUCCESS; 00360 } 00361 00362 00363 /***************************************************************************************** 00364 * Contents Modifiction Methods * 00365 *****************************************************************************************/ 00366 00367 static EntityHandle* resize_compact_list( MeshSet::Count& count, 00368 MeshSet::CompactList& clist, 00369 size_t new_list_size ) 00370 { 00371 if (count <= 2) { 00372 if (new_list_size <= 2) { 00373 count = (MeshSet::Count)new_list_size; 00374 return clist.hnd; 00375 } 00376 else { 00377 EntityHandle* list = (EntityHandle*)malloc( new_list_size*sizeof(EntityHandle) ); 00378 list[0] = clist.hnd[0]; 00379 list[1] = clist.hnd[1]; 00380 clist.ptr[0] = list; 00381 clist.ptr[1] = list + new_list_size; 00382 count = MeshSet::MANY; 00383 return list; 00384 } 00385 } 00386 else if (new_list_size > 2) { 00387 if (new_list_size > (size_t)(clist.ptr[1] - clist.ptr[0])) 00388 clist.ptr[0] = (EntityHandle*)realloc( clist.ptr[0], new_list_size*sizeof(EntityHandle) ); 00389 clist.ptr[1] = clist.ptr[0] + new_list_size; 00390 count = MeshSet::MANY; 00391 return clist.ptr[0]; 00392 } 00393 else { 00394 EntityHandle* list = clist.ptr[0]; 00395 clist.hnd[0] = list[0]; 00396 clist.hnd[1] = list[1]; 00397 free(list); 00398 count = (MeshSet::Count)new_list_size; 00399 return clist.hnd; 00400 } 00401 } 00402 00403 typedef std::pair<EntityHandle,EntityHandle> MeshSetRange; 00404 00405 class MeshSetRComp { 00406 public: bool operator()( const MeshSetRange& r, EntityHandle h ) 00407 { return r.second < h; } 00408 }; 00409 00410 template <typename pair_iter_t> inline ErrorCode 00411 range_tool<pair_iter_t>::ranged_insert_entities( MeshSet::Count& count, 00412 MeshSet::CompactList& clist, 00413 pair_iter_t begin, 00414 pair_iter_t end, 00415 EntityHandle my_handle, 00416 AEntityFactory* adj ) 00417 { 00418 //first pass: 00419 // 1) merge existing ranges 00420 // 2) count number of new ranges that must be inserted 00421 EntityHandle *list_ptr; 00422 size_t list_size; 00423 if (count < MeshSet::MANY) { 00424 list_ptr = clist.hnd; 00425 list_size = count; 00426 } 00427 else { 00428 list_ptr = clist.ptr[0]; 00429 list_size = clist.ptr[1] - clist.ptr[0]; 00430 } 00431 00432 MeshSetRange* list = reinterpret_cast<MeshSetRange*>(list_ptr); 00433 assert(0 == list_size % 2); 00434 assert(2*sizeof(EntityHandle) == sizeof(MeshSetRange)); 00435 list_size /= 2; 00436 MeshSetRange *const list_end = list + list_size; 00437 MeshSetRange *list_read = list, *list_write = list; 00438 pair_iter_t i = begin; 00439 00440 // count number of range pairs that are straight insertions 00441 // (don't overlap any range pair in the current set) that 00442 // could not be inserted during the first pass. 00443 size_t insert_count = 0; 00444 00445 // merge lists 00446 while(i != end) { 00447 // find first range that intersects the current input range 00448 00449 // do binary search if no holes in current set contents 00450 if (list_read == list_write) { 00451 // subtract one from i->first because if it is one greater 00452 // then the the last value of some block, then we want that 00453 // block to append to. 00454 list_write = std::lower_bound( list_read, list_end, i->first-1, MeshSetRComp() ); 00455 list_read = list_write; 00456 } 00457 // otherwise shift down until we find where we find a range block 00458 // that intersects 00459 else while (list_read != list_end && list_read->second + 1 < i->first) { 00460 *list_write = *list_read; 00461 ++list_write; 00462 ++list_read; 00463 } 00464 00465 // handle any straight insertions of range blocks 00466 for ( ; i != end && (list_read == list_end || i->second+1 < list_read->first); ++i) { 00467 // If we haven't removed any range pairs, we don't have space to 00468 // insert here. Defer the insertion until later. 00469 if (list_read == list_write) { 00470 ++insert_count; 00471 } 00472 else { 00473 if (adj) 00474 for (EntityHandle j = i->first; j <= i->second; ++j) 00475 adj->add_adjacency( j, my_handle, false ); 00476 00477 list_write->first = i->first; 00478 list_write->second = i->second; 00479 ++list_write; 00480 } 00481 } 00482 00483 // merge all the stuff that gets merged into a single range pair 00484 // from both the input list and the existing set data 00485 if (list_read != list_end) { 00486 MeshSetRange working = *list_read; // copy because might be the same as list_write 00487 ++list_read; 00488 00489 // Check if we need to prepend to the existing block. 00490 // We only need to check this for the first input range because 00491 // after this working.first will always be the first possible handle 00492 // in the merged set of ranges. 00493 if (i != end && i->first < working.first && i->second+1 >= working.first) { 00494 if (adj) 00495 for (EntityHandle h = i->first; h < working.first; ++h) 00496 adj->add_adjacency( h, my_handle, false ); 00497 working.first = i->first; 00498 } 00499 00500 // Now append from the input list and the remaining set contents 00501 // until we've consolidated all overlapping/touching ranges. 00502 bool done = false; 00503 while (!done) { 00504 // does next set contents range touch working range? 00505 bool set_overlap = list_read != list_end && list_read->first <= working.second+1; 00506 // does next input range touch working range? 00507 bool inp_overlap = i != end && i->first <= working.second+1; 00508 00509 // if both ranges touch... 00510 if (inp_overlap && set_overlap) { 00511 // if next set range is contained in working, skip it 00512 if (list_read->second <= working.second) 00513 ++list_read; 00514 // if next input range is contained in working, skip it 00515 else if (i->second <= working.second) 00516 ++i; 00517 // Otherwise set the working end to the smaller of the two 00518 // ends: either the next set end or the next input end. 00519 // We want the smaller of the two because the larger might 00520 // intersect additional ranges in the other list. 00521 else if (list_read->second <= i->second) { 00522 working.second = list_read->second; 00523 ++list_read; 00524 } 00525 else { 00526 working.second = i->second; 00527 ++i; 00528 } 00529 } 00530 // If only the input range intersect the current working range... 00531 else if (inp_overlap) { 00532 // Would it be more efficient to just extent 'working' to 00533 // the end of the current input range? We'd end up adding 00534 // adjacencies for for entities that are already in the tracking 00535 // set and therefore already have the adjacency. 00536 EntityHandle last = i->second; 00537 if (list_read != list_end && list_read->first < last) 00538 last = list_read->first-1; 00539 else 00540 ++i; 00541 00542 if (last > working.second) { 00543 if (adj) 00544 for (EntityHandle h = working.second + 1; h <= last; ++h) 00545 adj->add_adjacency( h, my_handle, false ); 00546 00547 working.second = last; 00548 } 00549 } 00550 else if (set_overlap) { 00551 if (working.second < list_read->second) 00552 working.second = list_read->second; 00553 ++list_read; 00554 } 00555 else { 00556 done = true; 00557 } 00558 } 00559 00560 assert(list_write < list_read); 00561 *list_write = working; 00562 ++list_write; 00563 } 00564 } 00565 00566 00567 // shuffle down entries to fill holes 00568 if (list_read == list_write) 00569 list_read = list_write = list_end; 00570 else while(list_read < list_end) { 00571 *list_write = *list_read; 00572 ++list_read; 00573 ++list_write; 00574 } 00575 00576 // adjust allocated array size 00577 const size_t occupied_size = list_write - list; 00578 const size_t new_list_size = occupied_size + insert_count; 00579 list_ptr = resize_compact_list( count, clist, 2*new_list_size ); 00580 // done? 00581 if (!insert_count) 00582 return MB_SUCCESS; 00583 list = reinterpret_cast<MeshSetRange*>(list_ptr); 00584 00585 // Second pass: insert non-mergable range pairs 00586 // All range pairs in the input are either completely disjoint from 00587 // the ones in the mesh set and must be inserted or are entirely contained 00588 // within a range pair in the mesh set. 00589 assert( begin != end ); // can't have items to insert if given empty input list 00590 pair_iter_t ri = end; --ri; 00591 list_write = list + new_list_size - 1; 00592 list_read = list + occupied_size - 1; 00593 for ( ; list_write >= list; --list_write ) { 00594 if (list_read >= list) { 00595 while (ri->first >= list_read->first && ri->second <= list_read->second) { 00596 assert(ri != begin); 00597 --ri; 00598 } 00599 00600 if (list_read->first > ri->second) { 00601 *list_write = *list_read; 00602 --list_read; 00603 continue; 00604 } 00605 } 00606 00607 assert( insert_count > 0 ); 00608 if (adj) 00609 for (EntityHandle h = ri->first; h <= ri->second; ++h) 00610 adj->add_adjacency( h, my_handle, false ); 00611 list_write->first = ri->first; 00612 list_write->second = ri->second; 00613 00614 // don't have reverse iterator, so check before decrement 00615 // if insert_count isn't zero, must be more in range 00616 if (0 == --insert_count) { 00617 assert( list_read == list_write-1 ); 00618 break; 00619 } 00620 else { 00621 --ri; 00622 } 00623 } 00624 00625 assert(!insert_count); 00626 return MB_SUCCESS; 00627 } 00628 00629 template <typename pair_iter_t> inline ErrorCode 00630 range_tool<pair_iter_t>::ranged_remove_entities( MeshSet::Count& count, 00631 MeshSet::CompactList& clist, 00632 pair_iter_t begin, 00633 pair_iter_t end, 00634 EntityHandle my_handle, 00635 AEntityFactory* adj ) 00636 { 00637 //first pass: 00638 // 1) remove (from) existing ranges 00639 // 2) count number of ranges that must be split 00640 ptrdiff_t split_count = 0; 00641 EntityHandle *list; 00642 size_t list_size; 00643 if (count < MeshSet::MANY) { 00644 list = clist.hnd; 00645 list_size = count; 00646 } 00647 else { 00648 list = clist.ptr[0]; 00649 list_size = clist.ptr[1] - clist.ptr[0]; 00650 } 00651 00652 EntityHandle* list_write = list; 00653 EntityHandle *const list_end = list + list_size, *list_read = list; 00654 pair_iter_t i = begin; 00655 00656 while(list_read != list_end && i != end) { 00657 00658 while (i != end && i->second < list_read[0]) 00659 ++i; 00660 if (i == end) 00661 break; 00662 00663 // if there are holes in the current array, shuffle blocks 00664 // down until we find the next block to remove 00665 if (list_read != list_write) { 00666 while (list_read != list_end && i->second < list_read[0]) { 00667 list_write[0] = list_read[0]; 00668 list_write[1] = list_read[1]; 00669 list_write += 2; 00670 list_read += 2; 00671 } 00672 } 00673 // otherwise do a binary search 00674 else { 00675 list_write = std::lower_bound( list_write, list_end, i->first ); 00676 // if in middle of range block (odd index), back up to start of block 00677 list_write -= (list_write - list)%2; 00678 list_read = list_write; 00679 } 00680 00681 // if everything remaning is past end of set contents... 00682 if (list_read == list_end) 00683 break; 00684 00685 // skip any remove pairs that aren't in the list 00686 if (i->second < list_read[0]) { 00687 ++i; 00688 continue; 00689 } 00690 00691 // Begin by assuming that we will keep the entire block 00692 list_write[0] = list_read[0]; 00693 list_write[1] = list_read[1]; 00694 list_read += 2; 00695 00696 for (; i != end && i->first <= list_write[1]; ++i) { 00697 if (i->first <= list_write[0]) { 00698 // remove whole block 00699 if (i->second >= list_write[1]) { 00700 if (adj) 00701 for (EntityHandle h = list_write[0]; h <= list_write[1]; ++h) 00702 adj->remove_adjacency( h, my_handle ); 00703 list_write -= 2; 00704 break; 00705 } 00706 // remove from start of block 00707 else if (i->second >= list_write[0]) { 00708 if (adj) 00709 for (EntityHandle h = list_write[0]; h <= i->second; ++h) 00710 adj->remove_adjacency( h, my_handle ); 00711 list_write[0] = i->second + 1; 00712 } 00713 } 00714 else if (i->first <= list_write[1]) { 00715 // remove from end of block 00716 if (i->second >= list_write[1]) { 00717 if (adj) 00718 for (EntityHandle h = i->first; h <= list_write[1]; ++h) 00719 adj->remove_adjacency( h, my_handle ); 00720 list_write[1] = i->first - 1; 00721 //list_write += 2; 00722 break; 00723 } 00724 // split block 00725 else { 00726 if (adj) 00727 for (EntityHandle h = i->first; h <= i->second; ++h) 00728 adj->remove_adjacency( h, my_handle ); 00729 00730 if (list_read - list_write <= 2) { 00731 ++split_count; 00732 continue; 00733 } 00734 else { 00735 list_write[3] = list_write[1]; 00736 list_write[1] = i->first - 1; 00737 list_write[2] = i->second + 1; 00738 list_write += 2; 00739 } 00740 } 00741 } 00742 } 00743 list_write += 2; 00744 } 00745 00746 // shuffle down entries to fill holes 00747 if (list_read == list_write) 00748 list_read = list_write = list_end; 00749 else 00750 while(list_read < list_end) { 00751 list_write[0] = list_read[0]; 00752 list_write[1] = list_read[1]; 00753 list_read += 2; 00754 list_write += 2; 00755 } 00756 00757 // adjust allocated array size 00758 const size_t occupied_size = list_write - list; 00759 const size_t new_list_size = occupied_size + 2*split_count; 00760 list = resize_compact_list( count, clist, new_list_size ); 00761 // done? 00762 if (!split_count) 00763 return MB_SUCCESS; 00764 00765 // Second pass: split range pairs 00766 // All range pairs in the input are either already removed or 00767 // require one of the existing range pairs to be split 00768 assert( begin != end ); // can't have ranges to split if given empty input list 00769 pair_iter_t ri = end; --ri; 00770 list_write = list + new_list_size - 2; 00771 list_read = list + occupied_size - 2; 00772 for ( ; list_write >= list; list_write -= 2 ) { 00773 if (list_read >= list) { 00774 while (ri->second > list_read[1]) { 00775 assert(ri != begin); 00776 --ri; 00777 } 00778 00779 if (list_read[0] > ri->second) { 00780 list_write[0] = list_read[0]; 00781 list_write[1] = list_read[1]; 00782 list_read -= 2; 00783 continue; 00784 } 00785 } 00786 00787 assert( split_count > 0 ); 00788 list_write[0] = ri->second + 1; 00789 list_write[1] = list_read[1]; 00790 list_read[1] = ri->first - 1; 00791 00792 // don't have reverse iterator, so check before decrement 00793 // if insert_count isn't zero, must be more in range 00794 if (0 == --split_count) { 00795 assert( list_read == list_write-2 ); 00796 break; 00797 } 00798 else { 00799 --ri; 00800 } 00801 } 00802 00803 assert(!split_count); 00804 return MB_SUCCESS; 00805 } 00806 00807 00808 template <typename pair_iter_t> inline ErrorCode 00809 range_tool<pair_iter_t>::vector_insert_entities( MeshSet::Count& count, 00810 MeshSet::CompactList& clist, 00811 pair_iter_t begin, 00812 pair_iter_t end, 00813 EntityHandle my_handle, 00814 AEntityFactory* adj ) 00815 { 00816 const size_t init_size = count < MeshSet::MANY ? (int)count : clist.ptr[1] - clist.ptr[0]; 00817 size_t add_size = 0; 00818 for (pair_iter_t i = begin; i != end; ++i) 00819 add_size += i->second - i->first + 1; 00820 EntityHandle* list = resize_compact_list( count, clist, init_size + add_size ); 00821 EntityHandle* li = list + init_size; 00822 00823 for (pair_iter_t i = begin; i != end; ++i) { 00824 for (EntityHandle h = i->first; h <= i->second; ++h) { 00825 if (adj) 00826 adj->add_adjacency( h, my_handle, false ); 00827 *li = h; 00828 ++li; 00829 } 00830 } 00831 00832 return MB_SUCCESS; 00833 } 00834 00835 static ErrorCode vector_remove_range( MeshSet::Count& count, 00836 MeshSet::CompactList& clist, 00837 const Range& range, 00838 EntityHandle my_handle, 00839 AEntityFactory* adj ) 00840 { 00841 EntityHandle *list; 00842 size_t list_size; 00843 if (count < MeshSet::MANY) { 00844 list = clist.hnd; 00845 list_size = count; 00846 } 00847 else { 00848 list = clist.ptr[0]; 00849 list_size = clist.ptr[1] - clist.ptr[0]; 00850 } 00851 00852 const EntityHandle * const list_end = list + list_size; 00853 EntityHandle* list_write = list; 00854 for (const EntityHandle* list_read = list; list_read != list_end; ++list_read) { 00855 if (range.find(*list_read) == range.end()) { // keep 00856 *list_write = *list_read; 00857 ++list_write; 00858 } 00859 else if (adj) { 00860 adj->remove_adjacency( *list_read, my_handle ); 00861 } 00862 } 00863 00864 resize_compact_list( count, clist, list_write - list ); 00865 return MB_SUCCESS; 00866 } 00867 00868 static ErrorCode vector_remove_ranges( MeshSet::Count& count, 00869 MeshSet::CompactList& clist, 00870 const EntityHandle* pair_list, 00871 size_t num_pairs, 00872 EntityHandle my_handle, 00873 AEntityFactory* adj ) 00874 { 00875 EntityHandle *list; 00876 size_t list_size; 00877 if (count < MeshSet::MANY) { 00878 list = clist.hnd; 00879 list_size = count; 00880 } 00881 else { 00882 list = clist.ptr[0]; 00883 list_size = clist.ptr[1] - clist.ptr[0]; 00884 } 00885 00886 const EntityHandle *const list_end = list + list_size, 00887 *const input_end = pair_list + 2*num_pairs; 00888 EntityHandle* list_write = list; 00889 for (const EntityHandle* list_read = list; list_read != list_end; ++list_read) { 00890 const EntityHandle* ptr = std::lower_bound( pair_list, input_end, *list_read ); 00891 if ((ptr != input_end && (*ptr == *list_read || (ptr - pair_list)%2)) && // if in delete list 00892 std::find(list_read+1, list_end, *list_read) == list_end) { // and is last occurance in list 00893 // only remove adj if no previous occurance 00894 if (adj && std::find(list, list_write, *list_read) == list_write) 00895 adj->remove_adjacency( *list_read, my_handle ); 00896 } 00897 else { 00898 *list_write = *list_read; 00899 ++list_write; 00900 } 00901 } 00902 00903 resize_compact_list( count, clist, list_write - list ); 00904 return MB_SUCCESS; 00905 } 00906 00907 static ErrorCode vector_remove_vector( MeshSet::Count& count, 00908 MeshSet::CompactList& clist, 00909 const EntityHandle* vect, 00910 size_t vect_size, 00911 EntityHandle my_handle, 00912 AEntityFactory* adj ) 00913 { 00914 EntityHandle *list; 00915 size_t list_size; 00916 if (count < MeshSet::MANY) { 00917 list = clist.hnd; 00918 list_size = count; 00919 } 00920 else { 00921 list = clist.ptr[0]; 00922 list_size = clist.ptr[1] - clist.ptr[0]; 00923 } 00924 00925 const EntityHandle *const list_end = list + list_size, 00926 *const input_end = vect + vect_size; 00927 EntityHandle* list_write = list; 00928 for (const EntityHandle* list_read = list; list_read != list_end; ++list_read) { 00929 if (std::find(vect, input_end, *list_read) != input_end && // if in delete list 00930 std::find(list_read+1, list_end, *list_read) == list_end) { // and is last occurance in list 00931 // only remove adj if no previous occurance? 00932 if (adj ) // && std::find(list, list_write, *list_read) == list_write) 00933 adj->remove_adjacency( *list_read, my_handle ); 00934 } 00935 else { 00936 *list_write = *list_read; 00937 ++list_write; 00938 } 00939 } 00940 00941 resize_compact_list( count, clist, list_write - list ); 00942 return MB_SUCCESS; 00943 } 00944 00945 static ErrorCode vector_insert_vector( MeshSet::Count& count, 00946 MeshSet::CompactList& clist, 00947 const EntityHandle* vect, 00948 size_t vect_size, 00949 EntityHandle my_handle, 00950 AEntityFactory* adj ) 00951 { 00952 const size_t orig_size = count < MeshSet::MANY ? (int)count : clist.ptr[1] - clist.ptr[0]; 00953 EntityHandle* list = resize_compact_list( count, clist, orig_size + vect_size ); 00954 if (adj) 00955 for (size_t i = 0; i < vect_size; ++i) 00956 adj->add_adjacency( vect[i], my_handle, false ); 00957 memcpy( list+orig_size, vect, sizeof(EntityHandle)*vect_size ); 00958 return MB_SUCCESS; 00959 } 00960 00961 ErrorCode MeshSet::insert_entity_ranges( const EntityHandle* range_vect, size_t len, EntityHandle my_h, AEntityFactory* adj ) 00962 { 00963 typedef const std::pair<EntityHandle,EntityHandle>* pair_vect_t; 00964 pair_vect_t pair_vect = reinterpret_cast<pair_vect_t>(range_vect); 00965 MeshSet::Count count = static_cast<MeshSet::Count>(mContentCount); 00966 ErrorCode rval; 00967 if (!vector_based()) 00968 rval = range_tool<pair_vect_t>::ranged_insert_entities( count, contentList, pair_vect, 00969 pair_vect + len/2, my_h, tracking() ? adj : 0 ); 00970 else 00971 rval = range_tool<pair_vect_t>::vector_insert_entities( count, contentList, pair_vect, 00972 pair_vect + len/2, my_h, tracking() ? adj : 0 ); 00973 mContentCount = count; 00974 return rval; 00975 } 00976 00977 ErrorCode MeshSet::insert_entity_ranges( const Range& range, EntityHandle my_h, AEntityFactory* adj ) 00978 { 00979 ErrorCode rval; 00980 MeshSet::Count count = static_cast<MeshSet::Count>(mContentCount); 00981 if (!vector_based()) 00982 rval = range_tool<Range::const_pair_iterator>::ranged_insert_entities( count, 00983 contentList, range.const_pair_begin(), range.const_pair_end(), 00984 my_h, tracking() ? adj : 0 ); 00985 else 00986 rval = range_tool<Range::const_pair_iterator>::vector_insert_entities( count, 00987 contentList, range.const_pair_begin(), range.const_pair_end(), 00988 my_h, tracking() ? adj : 0 ); 00989 mContentCount = count; 00990 return rval; 00991 } 00992 00993 ErrorCode MeshSet::remove_entity_ranges( const EntityHandle* range_vect, size_t len, EntityHandle my_h, AEntityFactory* adj ) 00994 { 00995 ErrorCode rval; 00996 MeshSet::Count count = static_cast<MeshSet::Count>(mContentCount); 00997 if (vector_based()) 00998 rval = vector_remove_ranges( count, contentList, range_vect, len/2, my_h, 00999 tracking() ? adj : 0 ); 01000 else { 01001 typedef const std::pair<EntityHandle,EntityHandle>* pair_vect_t; 01002 pair_vect_t pair_vect = reinterpret_cast<pair_vect_t>(range_vect); 01003 rval = range_tool<pair_vect_t>::ranged_remove_entities( count, contentList, pair_vect, 01004 pair_vect + len/2, my_h, tracking() ? adj : 0 ); 01005 } 01006 mContentCount = count; 01007 return rval; 01008 } 01009 01010 ErrorCode MeshSet::remove_entity_ranges( const Range& range, EntityHandle my_h, AEntityFactory* adj ) 01011 { 01012 ErrorCode rval; 01013 MeshSet::Count count = static_cast<MeshSet::Count>(mContentCount); 01014 if (vector_based()) 01015 rval = vector_remove_range( count, contentList, range, my_h, tracking() ? adj : 0 ); 01016 else 01017 rval = range_tool<Range::const_pair_iterator>::ranged_remove_entities( count, 01018 contentList, range.const_pair_begin(), range.const_pair_end(), 01019 my_h, tracking() ? adj : 0 ); 01020 mContentCount = count; 01021 return rval; 01022 } 01023 01024 01025 ErrorCode MeshSet::intersect( const MeshSet* other, EntityHandle my_handle, AEntityFactory* adj ) 01026 { 01027 ErrorCode rval; 01028 if (!vector_based() && !other->vector_based()) { 01029 size_t other_count = 0; 01030 const EntityHandle* other_vect = other->get_contents( other_count ); 01031 if (!other_count) 01032 return clear( my_handle, adj ); 01033 assert(0 == other_count%2); 01034 01035 std::vector<EntityHandle> compliment; 01036 compliment.reserve( other_count + 4 ); 01037 if (*other_vect > 0) { 01038 compliment.push_back( 0 ); 01039 compliment.push_back( *other_vect - 1 ); 01040 } 01041 ++other_vect; 01042 const EntityHandle *const other_end = other_vect + other_count - 2; 01043 for (; other_vect < other_end; other_vect += 2) { 01044 compliment.push_back( other_vect[0] + 1 ); 01045 compliment.push_back( other_vect[1] - 1 ); 01046 } 01047 if (*other_vect < ~(EntityHandle)0) { 01048 compliment.push_back( *other_vect + 1 ); 01049 compliment.push_back( ~(EntityHandle)0 ); 01050 } 01051 01052 return remove_entity_ranges( &compliment[0], compliment.size(), my_handle, adj ); 01053 } 01054 else { 01055 Range my_ents, other_ents; 01056 rval = get_entities(my_ents); 01057 if (MB_SUCCESS != rval) 01058 return rval; 01059 rval = other->get_entities(other_ents); 01060 return remove_entities( moab::subtract(my_ents, other_ents), my_handle, adj ); 01061 } 01062 } 01063 01064 static void convert_to_ranges( const EntityHandle* vect_in, size_t vect_in_len, 01065 std::vector<EntityHandle>& vect_out ) 01066 { 01067 vect_out.reserve( 2*vect_in_len ); 01068 vect_out.resize( vect_in_len ); 01069 std::copy( vect_in, vect_in+vect_in_len, vect_out.begin() ); 01070 std::sort( vect_out.begin(), vect_out.end() ); 01071 vect_out.erase( std::unique( vect_out.begin(), vect_out.end() ), vect_out.end() ); 01072 01073 // duplicate all entries 01074 vect_out.resize( vect_out.size() * 2 ); 01075 for (long i = vect_out.size() - 1; i >= 0; --i) 01076 vect_out[i] = vect_out[i/2]; 01077 01078 // compact adjacent ranges 01079 std::vector<EntityHandle>::iterator r = vect_out.begin(), w = vect_out.begin(); 01080 while (r != vect_out.end()) { 01081 *w = *r; 01082 ++w; 01083 ++r; 01084 *w = *r; 01085 ++r; 01086 01087 while (r != vect_out.end() && *w + 1 == *r) { 01088 ++r; 01089 *w = *r; 01090 ++r; 01091 } 01092 ++w; 01093 } 01094 01095 // remove extra space 01096 vect_out.erase( w, vect_out.end() ); 01097 } 01098 01099 ErrorCode MeshSet::insert_entity_vector( const EntityHandle* vect, size_t len, EntityHandle my_h, AEntityFactory* adj ) 01100 { 01101 MeshSet::Count count = static_cast<MeshSet::Count>(mContentCount); 01102 ErrorCode rval; 01103 if (vector_based()) 01104 rval = vector_insert_vector( count, contentList, vect, len, my_h, tracking() ? adj : 0 ); 01105 else { 01106 std::vector<EntityHandle> rangevect; 01107 convert_to_ranges( vect, len, rangevect ); 01108 typedef const std::pair<EntityHandle,EntityHandle>* pair_vect_t; 01109 pair_vect_t pair_vect = reinterpret_cast<pair_vect_t>(&rangevect[0]); 01110 rval = range_tool<pair_vect_t>::ranged_insert_entities( count, contentList, pair_vect, 01111 pair_vect + rangevect.size()/2, my_h, tracking() ? adj : 0 ); 01112 } 01113 mContentCount = count; 01114 return rval; 01115 } 01116 01117 ErrorCode MeshSet::remove_entity_vector( const EntityHandle* vect, size_t len, EntityHandle my_h, AEntityFactory* adj ) 01118 { 01119 MeshSet::Count count = static_cast<MeshSet::Count>(mContentCount); 01120 ErrorCode rval; 01121 if (vector_based()) 01122 rval = vector_remove_vector( count, contentList, vect, len, my_h, tracking() ? adj : 0 ); 01123 else { 01124 std::vector<EntityHandle> rangevect; 01125 convert_to_ranges( vect, len, rangevect ); 01126 typedef const std::pair<EntityHandle,EntityHandle>* pair_vect_t; 01127 pair_vect_t pair_vect = reinterpret_cast<pair_vect_t>(&rangevect[0]); 01128 rval = range_tool<pair_vect_t>::ranged_remove_entities( count, contentList, pair_vect, 01129 pair_vect + rangevect.size()/2, my_h, tracking() ? adj : 0 ); 01130 } 01131 mContentCount = count; 01132 return rval; 01133 } 01134 01135 01136 01137 ErrorCode MeshSet::replace_entities( EntityHandle my_handle, 01138 const EntityHandle* old_entities, 01139 const EntityHandle* new_entities, 01140 size_t num_ents, 01141 AEntityFactory* adjfact ) 01142 { 01143 if (vector_based()) { 01144 ErrorCode result = MB_SUCCESS; 01145 size_t count; 01146 EntityHandle* vect = get_contents( count ); 01147 EntityHandle* const vect_end = vect+count; 01148 for (size_t i = 0; i < num_ents; ++i) { 01149 EntityHandle* p = std::find( vect, vect_end, old_entities[i] ); 01150 if (p == vect_end) { 01151 result = MB_ENTITY_NOT_FOUND; 01152 } 01153 else do { 01154 if (tracking()) { 01155 adjfact->remove_adjacency( *p, my_handle ); 01156 adjfact->add_adjacency( new_entities[i], my_handle, false ); 01157 } 01158 *p = new_entities[i]; 01159 p = std::find( p+1, vect_end, old_entities[i] ); 01160 } while (p != vect_end); 01161 } 01162 return result; 01163 } 01164 else { 01165 ErrorCode r1 = remove_entities( old_entities, num_ents, my_handle, adjfact ); 01166 ErrorCode r2 = add_entities( new_entities, num_ents, my_handle, adjfact ); 01167 return (MB_SUCCESS == r2) ? r1 : r2; 01168 } 01169 } 01170 01171 01172 /***************************************************************************************** 01173 * Misc. Methods * 01174 *****************************************************************************************/ 01175 01176 unsigned long MeshSet::get_memory_use() const 01177 { 01178 unsigned long result = 0; 01179 if (mParentCount == MANY) 01180 result += parentMeshSets.ptr[1] - parentMeshSets.ptr[0]; 01181 if (mChildCount == MANY) 01182 result += childMeshSets.ptr[1] - childMeshSets.ptr[0]; 01183 if (mContentCount == MANY) 01184 result += contentList.ptr[1] - contentList.ptr[0]; 01185 return sizeof(EntityHandle)*result; 01186 } 01187 01188 } // namespace moab