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