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