moab
|
00001 00016 /**************************************************** 00017 * File : Range.cpp 00018 * 00019 * Purpose : Stores contiguous or partially 00020 * contiguous values in an optimized 00021 * fashion. Partially contiguous 00022 * accessing patterns is also optimized. 00023 * 00024 * Creator : Clinton Stimpson 00025 * 00026 * Date : 15 April 2002 00027 * 00028 *******************************************************/ 00029 00030 00031 #include <assert.h> 00032 #include "moab/Range.hpp" 00033 #include "Internals.hpp" 00034 #include "moab/CN.hpp" 00035 #include <iostream> 00036 #include <string> 00037 00038 #ifdef HAVE_BOOST_POOL_SINGLETON_POOL_HPP 00039 # include <boost/pool/singleton_pool.hpp> 00040 typedef boost::singleton_pool< moab::Range::PairNode , sizeof(moab::Range::PairNode) > 00041 PairAlloc; 00042 // static inline moab::Range::PairNode* alloc_pair() 00043 // { return new (PairAlloc::malloc()) moab::Range::PairNode; } 00044 static inline moab::Range::PairNode* alloc_pair(moab::Range::PairNode* n, moab::Range::PairNode* p, moab::EntityHandle f, moab::EntityHandle s) 00045 { return new (PairAlloc::malloc()) moab::Range::PairNode(n,p,f,s); } 00046 static inline void free_pair( moab::Range::PairNode* node ) 00047 { node->~PairNode(); PairAlloc::free( node ); } 00048 #else 00049 // static inline moab::Range::PairNode* alloc_pair() 00050 // { return new moab::Range::PairNode; } 00051 static inline moab::Range::PairNode* alloc_pair(moab::Range::PairNode* n, moab::Range::PairNode* p, moab::EntityHandle f, moab::EntityHandle s) 00052 { return new moab::Range::PairNode(n,p,f,s); } 00053 static inline void free_pair( moab::Range::PairNode* node ) 00054 { delete node; } 00055 #endif 00056 00057 namespace moab { 00058 00062 size_t Range::size() const 00063 { 00064 // go through each pair and add up the number of values 00065 // we have. 00066 size_t sz=0; 00067 for(PairNode* iter = mHead.mNext; iter != &mHead; iter = iter->mNext) 00068 { 00069 sz += ((iter->second - iter->first) + 1); 00070 } 00071 return sz; 00072 } 00073 00077 Range::const_iterator& Range::const_iterator::operator+=( EntityID sstep ) 00078 { 00079 // Check negative now to avoid infinite loop below. 00080 if (sstep < 0) 00081 { 00082 return operator-=( -sstep ); 00083 } 00084 EntityHandle step = sstep; 00085 00086 // Handle current PairNode. Either step is within the current 00087 // node or need to remove the remainder of the current node 00088 // from step. 00089 EntityHandle this_node_rem = mNode->second - mValue; 00090 if (this_node_rem >= step) 00091 { 00092 mValue += step; 00093 return *this; 00094 } 00095 step -= this_node_rem + 1; 00096 00097 // For each node we are stepping past, decrement step 00098 // by the size of the node. 00099 PairNode* node = mNode->mNext; 00100 EntityHandle node_size = node->second - node->first + 1; 00101 while (step >= node_size) 00102 { 00103 step -= node_size; 00104 node = node->mNext; 00105 node_size = node->second - node->first + 1; 00106 } 00107 00108 // Advance into the resulting node by whatever is 00109 // left in step. 00110 mNode = node; 00111 mValue = mNode->first + step; 00112 return *this; 00113 } 00114 00115 00116 00120 Range::const_iterator& Range::const_iterator::operator-=( EntityID sstep ) 00121 { 00122 // Check negative now to avoid infinite loop below. 00123 if (sstep < 0) 00124 { 00125 return operator+=( -sstep ); 00126 } 00127 EntityHandle step = sstep; 00128 00129 // Handle current PairNode. Either step is within the current 00130 // node or need to remove the remainder of the current node 00131 // from step. 00132 EntityHandle this_node_rem = mValue - mNode->first; 00133 if (this_node_rem >= step) 00134 { 00135 mValue -= step; 00136 return *this; 00137 } 00138 step -= this_node_rem + 1; 00139 00140 // For each node we are stepping past, decrement step 00141 // by the size of the node. 00142 PairNode* node = mNode->mPrev; 00143 EntityHandle node_size = node->second - node->first + 1; 00144 while (step >= node_size) 00145 { 00146 step -= node_size; 00147 node = node->mPrev; 00148 node_size = node->second - node->first + 1; 00149 } 00150 00151 // Advance into the resulting node by whatever is 00152 // left in step. 00153 mNode = node; 00154 mValue = mNode->second - step; 00155 return *this; 00156 } 00157 00158 00159 00160 00162 Range::Range( EntityHandle val1, EntityHandle val2 ) 00163 { 00164 mHead.mNext = mHead.mPrev = alloc_pair(&mHead, &mHead, val1, val2); 00165 mHead.first = mHead.second = 0; 00166 } 00167 00169 Range::Range(const Range& copy) 00170 { 00171 // set the head node to point to itself 00172 mHead.mNext = mHead.mPrev = &mHead; 00173 mHead.first = mHead.second = 0; 00174 00175 const PairNode* copy_node = copy.mHead.mNext; 00176 PairNode* new_node = &mHead; 00177 for(; copy_node != &(copy.mHead); copy_node = copy_node->mNext) 00178 { 00179 PairNode* tmp_node = alloc_pair(new_node->mNext, new_node, copy_node->first, 00180 copy_node->second); 00181 new_node->mNext->mPrev = tmp_node; 00182 new_node->mNext = tmp_node; 00183 new_node = tmp_node; 00184 } 00185 } 00186 00188 void Range::clear() 00189 { 00190 PairNode* tmp_node = mHead.mNext; 00191 while(tmp_node != &mHead) 00192 { 00193 PairNode* to_delete = tmp_node; 00194 tmp_node = tmp_node->mNext; 00195 free_pair( to_delete ); 00196 } 00197 mHead.mNext = &mHead; 00198 mHead.mPrev = &mHead; 00199 } 00200 00201 Range& Range::operator=(const Range& copy) 00202 { 00203 clear(); 00204 const PairNode* copy_node = copy.mHead.mNext; 00205 PairNode* new_node = &mHead; 00206 for(; copy_node != &(copy.mHead); copy_node = copy_node->mNext) 00207 { 00208 PairNode* tmp_node = alloc_pair(new_node->mNext, new_node, copy_node->first, 00209 copy_node->second); 00210 new_node->mNext->mPrev = tmp_node; 00211 new_node->mNext = tmp_node; 00212 new_node = tmp_node; 00213 } 00214 return *this; 00215 } 00216 00217 00222 Range::iterator Range::insert( Range::iterator hint, EntityHandle val ) 00223 { 00224 // don't allow zero-valued handles in Range 00225 if(val == 0) 00226 return end(); 00227 00228 // if this is empty, just add it and return an iterator to it 00229 if(&mHead == mHead.mNext) 00230 { 00231 mHead.mNext = mHead.mPrev = alloc_pair(&mHead, &mHead, val, val); 00232 return iterator(mHead.mNext, val); 00233 } 00234 00235 // find the location in the list where we can safely insert 00236 // new items and keep it ordered 00237 PairNode* hter = hint.mNode; 00238 PairNode* jter = hter->first <= val ? hter : mHead.mNext; 00239 for( ; (jter != &mHead) && (jter->second < val); jter=jter->mNext); 00240 PairNode* iter = jter; 00241 jter = jter->mPrev; 00242 00243 // if this val is already in the list 00244 if( (iter->first <= val && iter->second >= val) && (iter != &mHead) ) 00245 { 00246 // return an iterator pointing to this location 00247 return iterator( iter, val ); 00248 } 00249 00250 // one of a few things can happen at this point 00251 // 1. this range needs to be backwardly extended 00252 // 2. the previous range needs to be forwardly extended 00253 // 3. a new range needs to be added 00254 00255 00256 // extend this range back a bit 00257 else if( (iter->first == (val+1)) && (iter != &mHead) ) 00258 { 00259 iter->first = val; 00260 // see if we need to merge two ranges 00261 if( (iter != mHead.mNext) && (jter->second == (val-1))) 00262 { 00263 jter->second = iter->second; 00264 iter->mPrev->mNext = iter->mNext; 00265 iter->mNext->mPrev = iter->mPrev; 00266 free_pair( iter ); 00267 return iterator( jter, val ); 00268 } 00269 else 00270 { 00271 return iterator( iter, val ); 00272 } 00273 00274 } 00275 // extend the previous range forward a bit 00276 else if( (jter->second == (val-1)) && (iter != mHead.mNext) ) 00277 { 00278 jter->second = val; 00279 return iterator(jter, val); 00280 } 00281 // make a new range 00282 else 00283 { 00284 PairNode* new_node = alloc_pair(iter, iter->mPrev, val, val); 00285 iter->mPrev = new_node->mPrev->mNext = new_node; 00286 return iterator(new_node, val); 00287 } 00288 00289 } 00290 00291 Range::iterator Range::insert( Range::iterator prev, 00292 EntityHandle val1, 00293 EntityHandle val2 ) 00294 { 00295 if(val1 == 0 || val1 > val2) 00296 return end(); 00297 00298 // Empty 00299 if (mHead.mNext == &mHead) 00300 { 00301 assert( prev == end() ); 00302 PairNode* new_node = alloc_pair( &mHead, &mHead, val1, val2 ); 00303 mHead.mNext = mHead.mPrev = new_node; 00304 return iterator( mHead.mNext, val1 ); 00305 } 00306 00307 PairNode* iter = prev.mNode; 00308 // If iterator is at end, set it to last. 00309 // Thus if the hint was to append, we start searching 00310 // at the end of the list. 00311 if (iter == &mHead) 00312 iter = mHead.mPrev; 00313 // if hint (prev) is past insert position, reset it to the beginning. 00314 if (iter != &mHead && iter->first > val2+1) 00315 iter = mHead.mNext; 00316 00317 // If hint is bogus then search backwards 00318 while (iter != mHead.mNext && iter->mPrev->second >= val1-1) 00319 iter = iter->mPrev; 00320 00321 // Input range is before beginning? 00322 if (iter->mPrev == &mHead && val2 < iter->first - 1) 00323 { 00324 PairNode* new_node = alloc_pair( iter, &mHead, val1, val2 ); 00325 mHead.mNext = iter->mPrev = new_node; 00326 return iterator( mHead.mNext, val1 ); 00327 } 00328 00329 // Find first intersecting list entry, or the next entry 00330 // if none intersects. 00331 while (iter != &mHead && iter->second+1 < val1) 00332 iter = iter->mNext; 00333 00334 // Need to insert new pair (don't intersect any existing pair)? 00335 if (iter == &mHead || iter->first-1 > val2) 00336 { 00337 PairNode* new_node = alloc_pair( iter, iter->mPrev, val1, val2 ); 00338 iter->mPrev = iter->mPrev->mNext = new_node; 00339 return iterator( iter->mPrev, val1 ); 00340 } 00341 00342 // Make the first intersecting pair the union of itself with [val1,val2] 00343 if (iter->first > val1) 00344 iter->first = val1; 00345 if (iter->second >= val2) 00346 return iterator( iter, val1 ); 00347 iter->second = val2; 00348 00349 // Merge any remaining pairs that intersect [val1,val2] 00350 while (iter->mNext != &mHead && iter->mNext->first <= val2 + 1) 00351 { 00352 PairNode* dead = iter->mNext; 00353 iter->mNext = dead->mNext; 00354 dead->mNext->mPrev = iter; 00355 00356 if (dead->second > val2) 00357 iter->second = dead->second; 00358 free_pair( dead ); 00359 } 00360 00361 return iterator( iter, val1 ); 00362 } 00363 00364 00369 Range::iterator Range::erase(iterator iter) 00370 { 00371 // one of a few things could happen 00372 // 1. shrink a range 00373 // 2. split a range 00374 // 3. remove a range 00375 00376 if(iter == end()) 00377 return end(); 00378 00379 // the iterator most likely to be returned 00380 iterator new_iter = iter; 00381 ++new_iter; 00382 00383 PairNode* kter = iter.mNode; 00384 00385 // just remove the range 00386 if(kter->first == kter->second) 00387 { 00388 kter->mNext->mPrev = kter->mPrev; 00389 kter->mPrev->mNext = kter->mNext; 00390 free_pair( kter ); 00391 return new_iter; 00392 } 00393 // shrink it 00394 else if(kter->first == iter.mValue) 00395 { 00396 kter->first++; 00397 return new_iter; 00398 } 00399 // shrink it the other way 00400 else if(kter->second == iter.mValue) 00401 { 00402 kter->second--; 00403 return new_iter; 00404 } 00405 // split the range 00406 else 00407 { 00408 PairNode* new_node = alloc_pair(iter.mNode->mNext, iter.mNode, iter.mValue+1, kter->second); 00409 new_node->mPrev->mNext = new_node->mNext->mPrev = new_node; 00410 iter.mNode->second = iter.mValue - 1; 00411 new_iter = const_iterator(new_node, new_node->first); 00412 return new_iter; 00413 } 00414 00415 } 00416 00417 00419 Range::iterator Range::erase( iterator iter1, iterator iter2) 00420 { 00421 iterator result; 00422 00423 if (iter1.mNode == iter2.mNode) { 00424 if (iter2.mValue <= iter1.mValue) { 00425 // empty range OK, otherwise invalid input 00426 return iter2; 00427 } 00428 00429 // If both iterators reference the same pair node, then 00430 // we're either removing values from the front of the 00431 // node or splitting the node. We can never be removing 00432 // the last value in the node in this case because iter2 00433 // points *after* the last entry to be removed. 00434 00435 PairNode* node = iter1.mNode; 00436 if (iter1.mValue == node->first) { 00437 node->first = iter2.mValue; 00438 result = iter2; 00439 } 00440 else { 00441 PairNode* new_node = alloc_pair( node->mNext, node, iter2.mValue, node->second ); 00442 new_node->mNext->mPrev = new_node; 00443 new_node->mPrev->mNext = new_node; 00444 node->second = iter1.mValue - 1; 00445 result = iterator( new_node, new_node->first ); 00446 } 00447 } 00448 else { 00449 if (iter1.mNode == &mHead) 00450 return iter1; 00451 PairNode* dn = iter1.mNode; 00452 if (iter1.mValue > dn->first) { 00453 dn->second = iter1.mValue-1; 00454 dn = dn->mNext; 00455 } 00456 if (iter2.mNode != &mHead) 00457 iter2.mNode->first = iter2.mValue; 00458 while (dn != iter2.mNode) { 00459 PairNode* dead = dn; 00460 dn = dn->mNext; 00461 00462 dead->mPrev->mNext = dead->mNext; 00463 dead->mNext->mPrev = dead->mPrev; 00464 dead->mPrev = dead->mNext = 0; 00465 delete dead; 00466 } 00467 00468 result = iter2; 00469 } 00470 00471 return result; 00472 } 00473 00474 void Range::delete_pair_node( PairNode* node ) 00475 { 00476 if (node != &mHead) { // pop_front() and pop_back() rely on this check 00477 node->mPrev->mNext = node->mNext; 00478 node->mNext->mPrev = node->mPrev; 00479 free_pair( node ); 00480 } 00481 } 00482 00484 EntityHandle Range::pop_front() 00485 { 00486 EntityHandle retval = front(); 00487 if (mHead.mNext->first == mHead.mNext->second) // need to remove pair from range 00488 delete_pair_node( mHead.mNext ); 00489 else 00490 ++(mHead.mNext->first); // otherwise just adjust start value of pair 00491 00492 return retval; 00493 } 00494 00496 EntityHandle Range::pop_back() 00497 { 00498 EntityHandle retval = back(); 00499 if (mHead.mPrev->first == mHead.mPrev->second) // need to remove pair from range 00500 delete_pair_node( mHead.mPrev ); 00501 else 00502 --(mHead.mPrev->second); // otherwise just adjust end value of pair 00503 00504 return retval; 00505 } 00506 00512 Range::const_iterator Range::find(EntityHandle val) const 00513 { 00514 // iterator through the list 00515 PairNode* iter = mHead.mNext; 00516 for( ; iter != &mHead && (val > iter->second); iter=iter->mNext ); 00517 return ((iter->second >= val) && (iter->first <= val)) ? const_iterator(iter,val) : end(); 00518 } 00519 00524 void Range::insert( Range::const_iterator begini, 00525 Range::const_iterator endi ) 00526 { 00527 if (begini == endi) 00528 return; 00529 00530 PairNode* node = begini.mNode; 00531 if (endi.mNode == node) 00532 { 00533 insert( *begini, (*endi)-1 ); 00534 return; 00535 } 00536 00537 Range::iterator hint = insert( *begini, node->second ); 00538 node = node->mNext; 00539 while (node != endi.mNode) 00540 { 00541 hint = insert( hint, node->first, node->second ); 00542 node = node->mNext; 00543 } 00544 00545 if (*endi > node->first) 00546 { 00547 if (*endi <= node->second) 00548 insert( hint, node->first, *(endi) - 1 ); 00549 else 00550 insert( hint, node->first, node->second ); 00551 } 00552 } 00553 00554 00555 00556 00557 #include <algorithm> 00558 00559 00560 // checks the range to make sure everything is A-Ok. 00561 void Range::sanity_check() const 00562 { 00563 if(empty()) 00564 return; 00565 00566 const PairNode* node = mHead.mNext; 00567 std::vector<const PairNode*> seen_before; 00568 bool stop_it = false; 00569 00570 for(; stop_it == false; node = node->mNext) 00571 { 00572 // have we seen this node before? 00573 assert(std::find(seen_before.begin(), seen_before.end(), node) == seen_before.end()); 00574 seen_before.push_back(node); 00575 00576 // is the connection correct? 00577 assert(node->mNext->mPrev == node); 00578 00579 // are the values right? 00580 assert(node->first <= node->second); 00581 if(node != &mHead && node->mPrev != &mHead) 00582 assert(node->mPrev->second < node->first); 00583 00584 if(node == &mHead) 00585 stop_it = true; 00586 00587 } 00588 00589 } 00590 00591 // for debugging 00592 void Range::print(const char *indent_prefix) const 00593 { 00594 print(std::cout, indent_prefix); 00595 } 00596 00597 void Range::print(std::ostream& stream, const char *indent_prefix) const 00598 { 00599 std::string indent_prefix_str; 00600 if (NULL != indent_prefix) indent_prefix_str += indent_prefix; 00601 00602 if (empty()) { 00603 stream << indent_prefix_str << "\tempty" << std::endl; 00604 return; 00605 } 00606 00607 for (const_pair_iterator i = const_pair_begin(); i != const_pair_end(); ++i) { 00608 EntityType t1 = TYPE_FROM_HANDLE( i->first ); 00609 EntityType t2 = TYPE_FROM_HANDLE( i->second ); 00610 00611 stream << indent_prefix_str << "\t" << CN::EntityTypeName( t1 ) << " " 00612 << ID_FROM_HANDLE( i->first ); 00613 if(i->first != i->second) { 00614 stream << " - "; 00615 if (t1 != t2) 00616 stream << CN::EntityTypeName( t2 ) << " "; 00617 stream << ID_FROM_HANDLE( i->second ); 00618 } 00619 stream << std::endl; 00620 } 00621 } 00622 00623 // intersect two ranges, placing the results in the return range 00624 #define MAX(a,b) (a < b ? b : a) 00625 #define MIN(a,b) (a > b ? b : a) 00626 Range intersect(const Range &range1, const Range &range2) 00627 { 00628 Range::const_pair_iterator r_it[2] = { range1.const_pair_begin(), 00629 range2.const_pair_begin() }; 00630 EntityHandle low_it, high_it; 00631 00632 Range lhs; 00633 Range::iterator hint = lhs.begin(); 00634 00635 // terminate the while loop when at least one "start" iterator is at the 00636 // end of the list 00637 while (r_it[0] != range1.end() && r_it[1] != range2.end()) { 00638 00639 if (r_it[0]->second < r_it[1]->first) 00640 // 1st subrange completely below 2nd subrange 00641 r_it[0]++; 00642 else if (r_it[1]->second < r_it[0]->first) 00643 // 2nd subrange completely below 1st subrange 00644 r_it[1]++; 00645 00646 else { 00647 // else ranges overlap; first find greater start and lesser end 00648 low_it = MAX(r_it[0]->first, r_it[1]->first); 00649 high_it = MIN(r_it[0]->second, r_it[1]->second); 00650 00651 // insert into result 00652 hint = lhs.insert(hint, low_it, high_it); 00653 00654 // now find bounds of this insertion and increment corresponding iterator 00655 if (high_it == r_it[0]->second) r_it[0]++; 00656 if (high_it == r_it[1]->second) r_it[1]++; 00657 } 00658 } 00659 00660 return lhs; 00661 } 00662 00663 Range subtract(const Range &range1, const Range &range2) 00664 { 00665 const bool braindead = false; 00666 00667 if (braindead) { 00668 // brain-dead implementation right now 00669 Range res( range1 ); 00670 for (Range::const_iterator rit = range2.begin(); rit != range2.end(); rit++) 00671 res.erase(*rit); 00672 00673 return res; 00674 } 00675 else { 00676 Range lhs( range1 ); 00677 00678 Range::pair_iterator r_it0 = lhs.pair_begin(); 00679 Range::const_pair_iterator r_it1 = range2.const_pair_begin(); 00680 00681 // terminate the while loop when at least one "start" iterator is at the 00682 // end of the list 00683 while (r_it0 != lhs.end() && r_it1 != range2.end()) { 00684 // case a: pair wholly within subtracted pair 00685 if (r_it0->first >= r_it1->first && r_it0->second <= r_it1->second) { 00686 Range::PairNode *rtmp = r_it0.node(); 00687 r_it0++; 00688 lhs.delete_pair_node(rtmp); 00689 } 00690 // case b: pair overlaps upper part of subtracted pair 00691 else if (r_it0->first <= r_it1->second && 00692 r_it0->first >= r_it1->first) { 00693 r_it0->first = r_it1->second + 1; 00694 r_it1++; 00695 } 00696 // case c: pair overlaps lower part of subtracted pair 00697 else if (r_it0->second >= r_it1->first && 00698 r_it0->second <= r_it1->second) { 00699 r_it0->second = r_it1->first - 1; 00700 r_it0++; 00701 } 00702 // case d: pair completely surrounds subtracted pair 00703 else if (r_it0->first < r_it1->first && 00704 r_it0->second > r_it1->second) { 00705 Range::PairNode* new_node = alloc_pair(r_it0.node(), r_it0.node()->mPrev, 00706 r_it0->first, r_it1->first - 1); 00707 new_node->mPrev->mNext = new_node->mNext->mPrev = new_node; 00708 r_it0.node()->first = r_it1->second+1; 00709 r_it1++; 00710 } 00711 else { 00712 while (r_it0->second < r_it1->first && r_it0 != lhs.end()) r_it0++; 00713 if (r_it0 == lhs.end()) break; 00714 while (r_it1->second < r_it0->first && r_it1 != range2.end()) r_it1++; 00715 } 00716 } 00717 00718 return lhs; 00719 } 00720 } 00721 00722 Range &Range::operator-=(const Range &range2) 00723 { 00724 const bool braindead = false; 00725 00726 if (braindead) { 00727 // brain-dead implementation right now 00728 Range res( *this ); 00729 for (Range::const_iterator rit = range2.begin(); rit != range2.end(); rit++) 00730 res.erase(*rit); 00731 00732 return *this; 00733 } 00734 else { 00735 Range::pair_iterator r_it0 = this->pair_begin(); 00736 Range::const_pair_iterator r_it1 = range2.const_pair_begin(); 00737 00738 // terminate the while loop when at least one "start" iterator is at the 00739 // end of the list 00740 while (r_it0 != this->end() && r_it1 != range2.end()) { 00741 // case a: pair wholly within subtracted pair 00742 if (r_it0->first >= r_it1->first && r_it0->second <= r_it1->second) { 00743 Range::PairNode *rtmp = r_it0.node(); 00744 r_it0++; 00745 this->delete_pair_node(rtmp); 00746 } 00747 // case b: pair overlaps upper part of subtracted pair 00748 else if (r_it0->first <= r_it1->second && 00749 r_it0->first >= r_it1->first) { 00750 r_it0->first = r_it1->second + 1; 00751 r_it1++; 00752 } 00753 // case c: pair overlaps lower part of subtracted pair 00754 else if (r_it0->second >= r_it1->first && 00755 r_it0->second <= r_it1->second) { 00756 r_it0->second = r_it1->first - 1; 00757 r_it0++; 00758 } 00759 // case d: pair completely surrounds subtracted pair 00760 else if (r_it0->first < r_it1->first && 00761 r_it0->second > r_it1->second) { 00762 Range::PairNode* new_node = alloc_pair(r_it0.node(), r_it0.node()->mPrev, 00763 r_it0->first, r_it1->first - 1); 00764 new_node->mPrev->mNext = new_node->mNext->mPrev = new_node; 00765 r_it0.node()->first = r_it1->second+1; 00766 r_it1++; 00767 } 00768 else { 00769 while (r_it0->second < r_it1->first && r_it0 != this->end()) r_it0++; 00770 if (r_it0 == this->end()) break; 00771 while (r_it1->second < r_it0->first && r_it1 != range2.end()) r_it1++; 00772 } 00773 } 00774 return *this; 00775 } 00776 } 00777 00778 00779 EntityID 00780 operator-( const Range::const_iterator& it2, const Range::const_iterator& it1 ) 00781 { 00782 assert( !it2.mValue || *it2 >= *it1 ); 00783 if (it2.mNode == it1.mNode) { 00784 return *it2 - *it1; 00785 } 00786 00787 EntityID result = it1.mNode->second - it1.mValue + 1; 00788 for (Range::PairNode* n = it1.mNode->mNext; n != it2.mNode; n = n->mNext) 00789 result += n->second - n->first + 1; 00790 if (it2.mValue) // (it2.mNode != &mHead) 00791 result += it2.mValue - it2.mNode->first; 00792 return result; 00793 } 00794 00795 00796 Range::const_iterator Range::lower_bound(Range::const_iterator first, 00797 Range::const_iterator last, 00798 EntityHandle val) 00799 { 00800 // Find the first pair whose end is >= val 00801 PairNode* iter; 00802 for (iter = first.mNode; iter != last.mNode; iter = iter->mNext) 00803 { 00804 if (iter->second >= val) 00805 { 00806 // This is the correct pair. Either 'val' is in the range, or 00807 // the range starts before 'val' and iter->first IS the lower_bound. 00808 if (iter->first > val) 00809 return const_iterator(iter, iter->first); 00810 return const_iterator(iter, val); 00811 } 00812 } 00813 00814 if (iter->first >= val) 00815 return const_iterator( iter, iter->first ); 00816 else if(*last > val) 00817 return const_iterator( iter, val ); 00818 else 00819 return last; 00820 } 00821 00822 Range::const_iterator Range::upper_bound(Range::const_iterator first, 00823 Range::const_iterator last, 00824 EntityHandle val) 00825 { 00826 Range::const_iterator result = lower_bound( first, last, val ); 00827 if (result != last && *result == val) 00828 ++result; 00829 return result; 00830 } 00831 00832 Range::const_iterator Range::lower_bound( EntityType type ) const 00833 { 00834 int err; 00835 EntityHandle handle = CREATE_HANDLE( type, 0, err ); 00836 return err ? end() : lower_bound( begin(), end(), handle ); 00837 } 00838 Range::const_iterator Range::lower_bound( EntityType type, 00839 const_iterator first ) const 00840 { 00841 int err; 00842 EntityHandle handle = CREATE_HANDLE( type, 0, err ); 00843 return err ? end() : lower_bound( first, end(), handle ); 00844 } 00845 00846 Range::const_iterator Range::upper_bound( EntityType type ) const 00847 { 00848 // if (type+1) overflows, err will be true and we return end(). 00849 int err; 00850 EntityHandle handle = CREATE_HANDLE( type + 1, 0, err ); 00851 return err ? end() : lower_bound( begin(), end(), handle ); 00852 } 00853 Range::const_iterator Range::upper_bound( EntityType type, 00854 const_iterator first ) const 00855 { 00856 // if (type+1) overflows, err will be true and we return end(). 00857 int err; 00858 EntityHandle handle = CREATE_HANDLE( type + 1, 0, err ); 00859 return err ? end() : lower_bound( first, end(), handle ); 00860 } 00861 00862 std::pair<Range::const_iterator, Range::const_iterator> 00863 Range::equal_range( EntityType type ) const 00864 { 00865 std::pair<Range::const_iterator, Range::const_iterator> result; 00866 int err; 00867 EntityHandle handle = CREATE_HANDLE( type, 0, err ); 00868 result.first = err ? end() : lower_bound( begin(), end(), handle ); 00869 // if (type+1) overflows, err will be true and we return end(). 00870 handle = CREATE_HANDLE( type+1, 0, err ); 00871 result.second = err ? end() : lower_bound( result.first, end(), handle ); 00872 return result; 00873 } 00874 00875 bool Range::all_of_type( EntityType type ) const 00876 { 00877 return empty() 00878 || (TYPE_FROM_HANDLE(front()) == type 00879 && TYPE_FROM_HANDLE(back()) == type); 00880 } 00881 00882 bool Range::all_of_dimension( int dimension ) const 00883 { 00884 return empty() 00885 || (CN::Dimension(TYPE_FROM_HANDLE(front())) == dimension 00886 && CN::Dimension(TYPE_FROM_HANDLE(back())) == dimension); 00887 } 00888 00889 unsigned Range::num_of_type( EntityType type ) const 00890 { 00891 const_pair_iterator iter = const_pair_begin(); 00892 while(iter != const_pair_end() && TYPE_FROM_HANDLE((*iter).second) < type) 00893 ++iter; 00894 00895 unsigned count = 0; 00896 for ( ; iter != const_pair_end(); ++iter) 00897 { 00898 EntityType start_type = TYPE_FROM_HANDLE((*iter).first); 00899 EntityType end_type = TYPE_FROM_HANDLE((*iter).second); 00900 if (start_type > type) 00901 break; 00902 00903 int sid = start_type < type ? 1 : ID_FROM_HANDLE((*iter).first); 00904 int eid = end_type > type ? MB_END_ID : ID_FROM_HANDLE((*iter).second); 00905 count += eid - sid + 1; 00906 } 00907 00908 return count; 00909 } 00910 00911 unsigned Range::num_of_dimension( int dim ) const 00912 { 00913 const_pair_iterator iter = const_pair_begin(); 00914 while(iter != const_pair_end() && CN::Dimension(TYPE_FROM_HANDLE((*iter).second)) < dim) 00915 ++iter; 00916 00917 int junk; 00918 unsigned count = 0; 00919 for ( ; iter != const_pair_end(); ++iter) 00920 { 00921 int start_dim = CN::Dimension(TYPE_FROM_HANDLE((*iter).first)); 00922 int end_dim = CN::Dimension(TYPE_FROM_HANDLE((*iter).second)); 00923 if (start_dim > dim) 00924 break; 00925 00926 EntityHandle sh = start_dim < dim ? 00927 CREATE_HANDLE( CN::TypeDimensionMap[dim].first, 1, junk ) : 00928 (*iter).first; 00929 EntityHandle eh = end_dim > dim ? 00930 CREATE_HANDLE( CN::TypeDimensionMap[dim].second, MB_END_ID, junk ) : 00931 (*iter).second; 00932 count += eh - sh + 1; 00933 } 00934 00935 return count; 00936 } 00937 00938 00939 00940 00944 void Range::swap( Range &range ) 00945 { 00946 // update next/prev nodes of head of both ranges 00947 bool range_empty = (range.mHead.mNext == &(range.mHead)); 00948 bool this_empty = (mHead.mNext == &mHead); 00949 00950 range.mHead.mNext->mPrev = (range_empty ? &(range.mHead) : &mHead); 00951 range.mHead.mPrev->mNext = (range_empty ? &(range.mHead) : &mHead); 00952 mHead.mNext->mPrev = (this_empty ? &mHead : &(range.mHead)); 00953 mHead.mPrev->mNext = (this_empty ? &mHead : &(range.mHead)); 00954 00955 // switch data in head nodes of both ranges 00956 PairNode *range_next = range.mHead.mNext, *range_prev = range.mHead.mPrev; 00957 range.mHead.mNext = (this_empty ? &(range.mHead) : mHead.mNext); 00958 range.mHead.mPrev = (this_empty ? &(range.mHead) : mHead.mPrev); 00959 mHead.mNext = (range_empty ? &mHead : range_next); 00960 mHead.mPrev = (range_empty ? &mHead : range_prev); 00961 00962 } 00963 00965 Range Range::subset_by_type(EntityType t) const 00966 { 00967 Range result; 00968 std::pair<const_iterator, const_iterator> iters = equal_range(t); 00969 result.insert( iters.first, iters.second ); 00970 return result; 00971 } 00972 00974 Range Range::subset_by_dimension( int d ) const 00975 { 00976 EntityHandle handle1 = CREATE_HANDLE( CN::TypeDimensionMap[d].first, 0 ); 00977 iterator st = lower_bound( begin(), end(), handle1 ); 00978 00979 iterator en; 00980 if (d < 4) { // dimension 4 is MBENTITYSET 00981 EntityHandle handle2 = CREATE_HANDLE( CN::TypeDimensionMap[d+1].first, 0 ); 00982 en = lower_bound( st, end(), handle2 ); 00983 } 00984 else { 00985 en = end(); 00986 } 00987 00988 Range result; 00989 result.insert( st, en ); 00990 return result; 00991 } 00992 00993 bool operator==( const Range& r1, const Range& r2 ) 00994 { 00995 Range::const_pair_iterator i1, i2; 00996 i1 = r1.const_pair_begin(); 00997 i2 = r2.const_pair_begin(); 00998 for ( ; i1 != r1.const_pair_end(); ++i1, ++i2) 00999 if (i2 == r2.const_pair_end() || 01000 i1->first != i2->first || 01001 i1->second != i2->second) 01002 return false; 01003 return i2 == r2.const_pair_end(); 01004 } 01005 01006 unsigned long Range::get_memory_use() const 01007 { 01008 unsigned long result = 0; 01009 for (const PairNode* n = mHead.mNext; n != &mHead; n = n->mNext) 01010 result += sizeof(PairNode); 01011 return result; 01012 } 01013 01014 bool Range::contains( const Range& othr ) const 01015 { 01016 if (othr.empty()) 01017 return true; 01018 if (empty()) 01019 return false; 01020 01021 // neither range is empty, so both have valid pair nodes 01022 // other than dummy mHead 01023 const PairNode* this_node = mHead.mNext; 01024 const PairNode* othr_node = othr.mHead.mNext; 01025 for(;;) { 01026 // Loop while the node in this list is entirely before 01027 // the node in the other list. 01028 while (this_node->second < othr_node->first) { 01029 this_node = this_node->mNext; 01030 if (this_node == &mHead) 01031 return false; 01032 } 01033 // If other node is not entirely contained in this node 01034 // then other list is not contained in this list 01035 if (this_node->first > othr_node->first) 01036 break; 01037 // Loop while other node is entirely contained in this node. 01038 while (othr_node->second <= this_node->second) { 01039 othr_node = othr_node->mNext; 01040 if (othr_node == &othr.mHead) 01041 return true; 01042 } 01043 // If other node overlapped end of this node 01044 if (othr_node->first <= this_node->second) 01045 break; 01046 } 01047 01048 // should be unreachable 01049 return false; 01050 } 01051 01052 } // namespace moab 01053