MOAB: Mesh Oriented datABase  (version 5.2.1)
Range.cpp
Go to the documentation of this file.
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 <cassert>
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines