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