moab
MeshSet.cpp
Go to the documentation of this file.
00001 #ifdef WIN32
00002 #ifdef _DEBUG
00003 // turn off warnings that say they debugging identifier has been truncated
00004 // this warning comes up when using some STL containers
00005 #pragma warning(disable : 4786)
00006 #endif
00007 #endif
00008 
00009 #include "MeshSet.hpp"
00010 #include "AEntityFactory.hpp"
00011 
00012 namespace moab {
00013 
00014 
00015 /*****************************************************************************************
00016  *                          Helper Function Declarations                                 *
00017  *****************************************************************************************/
00018 
00020 static inline 
00021 MeshSet::Count insert_in_vector( const MeshSet::Count count, 
00022                                    MeshSet::CompactList& list,
00023                                    const EntityHandle h,
00024                                    int &result );
00025 
00027 static inline
00028 MeshSet::Count remove_from_vector( const MeshSet::Count count, 
00029                                      MeshSet::CompactList& list,
00030                                      const EntityHandle h,
00031                                      int &result );
00032 
00033 
00035 static EntityHandle* resize_compact_list( MeshSet::Count& count,
00036                                             MeshSet::CompactList& clist,
00037                                             size_t new_list_size );
00041 template <typename pair_iter_t> class range_tool
00042 {
00043 public:
00045   inline static ErrorCode ranged_insert_entities( MeshSet::Count& count, 
00046                                                     MeshSet::CompactList& clist, 
00047                                                     pair_iter_t begin, 
00048                                                     pair_iter_t end, 
00049                                                     EntityHandle my_handle, 
00050                                                     AEntityFactory* adj );
00051   
00053   inline static ErrorCode ranged_remove_entities( MeshSet::Count& count, 
00054                                                     MeshSet::CompactList& clist, 
00055                                                     pair_iter_t begin, 
00056                                                     pair_iter_t end, 
00057                                                     EntityHandle my_handle, 
00058                                                     AEntityFactory* adj );
00059 
00061   inline static ErrorCode vector_insert_entities( MeshSet::Count& count, 
00062                                                     MeshSet::CompactList& clist, 
00063                                                     pair_iter_t begin, 
00064                                                     pair_iter_t end, 
00065                                                     EntityHandle my_handle, 
00066                                                     AEntityFactory* adj );
00067 };
00068 
00070 static ErrorCode vector_remove_range( MeshSet::Count& count, 
00071                                         MeshSet::CompactList& clist, 
00072                                         const Range& range, 
00073                                         EntityHandle my_handle, 
00074                                         AEntityFactory* adj );
00075 
00077 static ErrorCode vector_remove_ranges( MeshSet::Count& count, 
00078                                          MeshSet::CompactList& clist, 
00079                                          const EntityHandle* pair_list,
00080                                          size_t num_pairs,
00081                                          EntityHandle my_handle, 
00082                                          AEntityFactory* adj );
00083 
00085 static ErrorCode vector_remove_vector( MeshSet::Count& count, 
00086                                          MeshSet::CompactList& clist, 
00087                                          const EntityHandle* vect,
00088                                          size_t vect_size,
00089                                          EntityHandle my_handle, 
00090                                          AEntityFactory* adj );
00091 
00093 static ErrorCode vector_insert_vector( MeshSet::Count& count, 
00094                                          MeshSet::CompactList& clist, 
00095                                          const EntityHandle* vect,
00096                                          size_t vect_size,
00097                                          EntityHandle my_handle, 
00098                                          AEntityFactory* adj );
00099 
00101 static void convert_to_ranges( const EntityHandle* vect_in, size_t vect_in_len,
00102                                std::vector<EntityHandle>& vect_out );
00103 
00104 
00105 /*****************************************************************************************
00106  *                             Parent/Child Operations                                   *
00107  *****************************************************************************************/
00108 
00109 static inline 
00110 MeshSet::Count insert_in_vector( const MeshSet::Count count, 
00111                                 MeshSet::CompactList& list,
00112                                 const EntityHandle h,
00113                                 int &result )
00114 {
00115   switch (count) {
00116     case MeshSet::ZERO:
00117       list.hnd[0] = h;
00118       result = true;
00119       return MeshSet::ONE;
00120     case MeshSet::ONE:
00121       if (list.hnd[0] == h) {
00122         result = false;
00123         return MeshSet::ONE;
00124       }
00125       else {
00126         result = true;
00127         list.hnd[1] = h;
00128         return MeshSet::TWO;
00129       }
00130     case MeshSet::TWO:
00131       if (list.hnd[0] == h || list.hnd[1] == h) {
00132         result = false;
00133         return MeshSet::TWO;
00134       }
00135       else {
00136         EntityHandle* ptr = (EntityHandle*)malloc(3*sizeof(EntityHandle));
00137         ptr[0] = list.hnd[0];
00138         ptr[1] = list.hnd[1];
00139         ptr[2] = h;
00140         list.ptr[0] = ptr;
00141         list.ptr[1] = ptr + 3;
00142         result = true;
00143         return MeshSet::MANY;
00144       }
00145     case MeshSet::MANY:
00146       if (std::find( list.ptr[0], list.ptr[1], h ) != list.ptr[1]) {
00147         result = false;
00148       }
00149       else {
00150         int size = list.ptr[1] - list.ptr[0];
00151         list.ptr[0] = (EntityHandle*)realloc( list.ptr[0], (size+1)*sizeof(EntityHandle) );
00152         list.ptr[0][size] = h;
00153         list.ptr[1] = list.ptr[0] + size + 1;
00154         result = true;
00155       }
00156       return MeshSet::MANY;
00157   }
00158 
00159   return MeshSet::ZERO;
00160 }
00161 
00162 static inline
00163 MeshSet::Count remove_from_vector( const MeshSet::Count count, 
00164                                   MeshSet::CompactList& list,
00165                                   const EntityHandle h,
00166                                   int &result )
00167 {
00168   switch (count) {
00169     case MeshSet::ZERO:
00170       result = false;
00171       return MeshSet::ZERO;
00172     case MeshSet::ONE:
00173       if (h == list.hnd[0]) {
00174         result = true;
00175         return MeshSet::ZERO;
00176       }
00177       else {
00178         result = false;
00179         return MeshSet::ONE;
00180       }
00181     case MeshSet::TWO:
00182       if (h == list.hnd[0]) {
00183         list.hnd[0] = list.hnd[1];
00184         result = true;
00185         return MeshSet::ONE;
00186       } 
00187       else if (h == list.hnd[1]) {
00188         result = true;
00189         return MeshSet::ONE;
00190       }
00191       else {
00192         result = false;
00193         return MeshSet::TWO;
00194       }
00195     case MeshSet::MANY: {
00196       EntityHandle *i, *j, *p;
00197       i = std::find( list.ptr[0], list.ptr[1], h );
00198       if (i == list.ptr[1]) {
00199         result = false;
00200         return MeshSet::MANY;
00201       }
00202       
00203       result = true;
00204       p = list.ptr[1] - 1;
00205       while (i != p) {
00206         j = i + 1;
00207         *i = *j;
00208         i = j;
00209       }
00210       int size = p - list.ptr[0];
00211       if (size == 2) {
00212         p = list.ptr[0];
00213         list.hnd[0] = p[0];
00214         list.hnd[1] = p[1];
00215         free( p );
00216         return MeshSet::TWO;
00217       }
00218       else {
00219         list.ptr[0] = (EntityHandle*)realloc( list.ptr[0], size*sizeof(EntityHandle) );
00220         list.ptr[1] = list.ptr[0] + size;
00221         return MeshSet::MANY;
00222       }
00223     }
00224   }
00225 
00226   return MeshSet::ZERO;
00227 }
00228 
00229 
00230 int MeshSet::add_parent( EntityHandle parent )
00231 { 
00232   int result = 0;
00233   mParentCount = insert_in_vector( (Count)mParentCount, parentMeshSets, parent, result );
00234   return result;
00235 }
00236 int MeshSet::add_child( EntityHandle child )
00237 { 
00238   int result = 0;
00239   mChildCount = insert_in_vector( (Count)mChildCount, childMeshSets, child, result );
00240   return result;
00241 }
00242 
00243 int MeshSet::remove_parent( EntityHandle parent )
00244 { 
00245   int result = 0;
00246   mParentCount = remove_from_vector( (Count)mParentCount, parentMeshSets, parent, result );
00247   return result;
00248 }
00249 int MeshSet::remove_child( EntityHandle child )
00250 { 
00251   int result = 0;
00252   mChildCount = remove_from_vector( (Count)mChildCount, childMeshSets, child, result );
00253   return result;
00254 }
00255 
00256 
00257 /*****************************************************************************************
00258  *                          Flag Conversion Operations                                   *
00259  *****************************************************************************************/
00260 
00261 ErrorCode MeshSet::convert( unsigned flg, EntityHandle my_handle, AEntityFactory* adj )
00262 {
00263   ErrorCode rval = MB_SUCCESS;
00264   if ((mFlags & MESHSET_TRACK_OWNER) && !(flg & MESHSET_TRACK_OWNER))
00265     rval = remove_adjacencies( my_handle, adj );
00266   else if (!(mFlags & MESHSET_TRACK_OWNER) && (flg & MESHSET_TRACK_OWNER))
00267     rval = create_adjacencies( my_handle, adj );
00268   if (MB_SUCCESS != rval)
00269     return rval;
00270 
00271   if (!(mFlags & MESHSET_ORDERED) && (flg & MESHSET_ORDERED)) {
00272     size_t datalen;
00273     EntityHandle* data = get_contents(datalen);
00274     if (datalen) {
00275       std::vector<EntityHandle> list( datalen );
00276       memcpy( &list[0], data, datalen*sizeof(EntityHandle) );
00277       int num_ents = num_entities();
00278       Count count = (Count)mContentCount;
00279       data = resize_compact_list( count, contentList, num_ents );
00280       mContentCount = count;
00281       assert( list.size() % 2 == 0 );
00282       std::vector<EntityHandle>::iterator i = list.begin();
00283       while (i != list.end()) {
00284         EntityHandle h = *i; ++i;
00285         EntityHandle e = *i; ++i;
00286         for (; h <= e; ++h) {
00287           *data = h; 
00288           ++data;
00289         }
00290       }
00291     }
00292   }
00293   else if ((mFlags & MESHSET_ORDERED) && !(flg & MESHSET_ORDERED)) {
00294     size_t datalen;
00295     EntityHandle* data = get_contents(datalen);
00296     if (datalen) {
00297       std::vector<EntityHandle> ranges;
00298       convert_to_ranges( data, datalen, ranges );
00299       Count count = (Count)mContentCount;
00300       data = resize_compact_list( count, contentList, ranges.size() );
00301       mContentCount = count;
00302       memcpy( data, &ranges[0], ranges.size()*sizeof(EntityHandle) );
00303     }
00304   }
00305   
00306   return MB_SUCCESS;
00307 }
00308 
00309 ErrorCode MeshSet::create_adjacencies( EntityHandle my_handle, AEntityFactory* adj )
00310 {
00311   ErrorCode rval = MB_SUCCESS;;
00312   size_t count;
00313   const EntityHandle *const ptr = get_contents( count );
00314   const EntityHandle *const end = ptr + count;
00315   if (vector_based()) {
00316     for (const EntityHandle* i = ptr; i != end; ++i) {
00317       rval = adj->add_adjacency( *i, my_handle, false );
00318       if (MB_SUCCESS != rval) {
00319         for (const EntityHandle* j = ptr; j != i; ++j) 
00320           adj->remove_adjacency( *j, my_handle );
00321         return rval;
00322       }
00323     }
00324   }
00325   else {
00326     assert( 0 == count % 2 );
00327     for (const EntityHandle* i = ptr; i != end; i += 2) {
00328       for (EntityHandle h = i[0]; h <= i[1]; ++h) {
00329         rval = adj->add_adjacency( h, my_handle, false );
00330         if (MB_SUCCESS != rval) {
00331           for (EntityHandle j = i[0]; j < h; ++j)
00332             adj->remove_adjacency( j, my_handle );
00333           for (const EntityHandle* j = ptr; j != i; j += 2)
00334             for (EntityHandle k = j[0]; k <= j[1]; ++k)
00335               adj->remove_adjacency( k, my_handle );
00336           return rval;
00337         }
00338       }
00339     }
00340   }
00341   return MB_SUCCESS;
00342 }
00343 
00344 ErrorCode MeshSet::remove_adjacencies( EntityHandle my_handle, AEntityFactory* adj )
00345 {
00346   size_t count;
00347   const EntityHandle *const ptr = get_contents( count );
00348   const EntityHandle *const end = ptr + count;
00349   if (vector_based()) {
00350     for (const EntityHandle* i = ptr; i != end; ++i)
00351       adj->remove_adjacency( *i, my_handle );
00352   }
00353   else {
00354     assert( 0 == count % 2 );
00355     for (const EntityHandle* i = ptr; i != end; i += 2)
00356       for (EntityHandle h = i[0]; h <= i[1]; ++h)
00357         adj->remove_adjacency( h, my_handle );
00358   }
00359   return MB_SUCCESS;
00360 }
00361 
00362 
00363 /*****************************************************************************************
00364  *                          Contents Modifiction Methods                                 *
00365  *****************************************************************************************/
00366 
00367 static EntityHandle* resize_compact_list( MeshSet::Count& count,
00368                                             MeshSet::CompactList& clist,
00369                                             size_t new_list_size )
00370 {
00371   if (count <= 2) {
00372     if (new_list_size <= 2) {
00373       count = (MeshSet::Count)new_list_size;
00374       return clist.hnd;
00375     }
00376     else {
00377       EntityHandle* list = (EntityHandle*)malloc( new_list_size*sizeof(EntityHandle) );
00378       list[0] = clist.hnd[0];
00379       list[1] = clist.hnd[1];
00380       clist.ptr[0] = list;
00381       clist.ptr[1] = list + new_list_size;
00382       count = MeshSet::MANY;
00383       return list;
00384     }
00385   }
00386   else if (new_list_size > 2) {
00387     if (new_list_size > (size_t)(clist.ptr[1] - clist.ptr[0]))
00388       clist.ptr[0] = (EntityHandle*)realloc( clist.ptr[0], new_list_size*sizeof(EntityHandle) );
00389     clist.ptr[1] = clist.ptr[0] + new_list_size;
00390     count = MeshSet::MANY;
00391     return clist.ptr[0];
00392   }
00393   else {
00394     EntityHandle* list = clist.ptr[0];
00395     clist.hnd[0] = list[0];
00396     clist.hnd[1] = list[1];
00397     free(list);
00398     count = (MeshSet::Count)new_list_size;
00399     return clist.hnd;
00400   }
00401 }
00402 
00403 typedef std::pair<EntityHandle,EntityHandle> MeshSetRange;
00404 
00405 class MeshSetRComp {
00406   public: bool operator()( const MeshSetRange& r, EntityHandle h )
00407     { return r.second < h; }
00408 };
00409 
00410 template <typename pair_iter_t> inline ErrorCode
00411 range_tool<pair_iter_t>::ranged_insert_entities( MeshSet::Count& count, 
00412                                                  MeshSet::CompactList& clist, 
00413                                                  pair_iter_t begin, 
00414                                                  pair_iter_t end, 
00415                                                  EntityHandle my_handle, 
00416                                                  AEntityFactory* adj )
00417 {
00418      //first pass:
00419     // 1) merge existing ranges 
00420     // 2) count number of new ranges that must be inserted
00421   EntityHandle *list_ptr;
00422   size_t list_size;
00423   if (count < MeshSet::MANY) {
00424     list_ptr = clist.hnd;
00425     list_size = count;
00426   }
00427   else {
00428     list_ptr = clist.ptr[0];
00429     list_size = clist.ptr[1] - clist.ptr[0];
00430   }
00431   
00432   MeshSetRange* list = reinterpret_cast<MeshSetRange*>(list_ptr);
00433   assert(0 == list_size % 2);
00434   assert(2*sizeof(EntityHandle) == sizeof(MeshSetRange));
00435   list_size /= 2;
00436   MeshSetRange *const list_end = list + list_size;
00437   MeshSetRange *list_read = list, *list_write = list;
00438   pair_iter_t i = begin;
00439   
00440     // count number of range pairs that are straight insertions
00441     // (don't overlap any range pair in the current set) that 
00442     // could not be inserted during the first pass.
00443   size_t insert_count = 0;
00444   
00445    // merge lists
00446   while(i != end) {
00447     // find first range that intersects the current input range
00448     
00449     // do binary search if no holes in current set contents
00450     if (list_read == list_write) {
00451         // subtract one from i->first because if it is one greater
00452         // then the the last value of some block, then we want that
00453         // block to append to.
00454       list_write = std::lower_bound( list_read, list_end, i->first-1, MeshSetRComp() );
00455       list_read = list_write;
00456     }
00457     // otherwise shift down until we find where we find a range block
00458     // that intersects
00459     else while (list_read != list_end && list_read->second + 1 < i->first) {
00460       *list_write = *list_read;
00461       ++list_write;
00462       ++list_read;
00463     }
00464     
00465       // handle any straight insertions of range blocks
00466     for ( ; i != end && (list_read == list_end || i->second+1 < list_read->first); ++i) {
00467         // If we haven't removed any range pairs, we don't have space to
00468         // insert here.  Defer the insertion until later.
00469       if (list_read == list_write) {
00470         ++insert_count;
00471       }
00472       else {
00473         if (adj) 
00474           for (EntityHandle j = i->first; j <= i->second; ++j)
00475             adj->add_adjacency( j, my_handle, false );
00476 
00477         list_write->first = i->first;
00478         list_write->second = i->second;
00479         ++list_write;
00480       }
00481     }
00482     
00483       // merge all the stuff that gets merged into a single range pair
00484       // from both the input list and the existing set data
00485     if (list_read != list_end) {
00486       MeshSetRange working = *list_read; // copy because might be the same as list_write
00487       ++list_read;
00488       
00489         // Check if we need to prepend to the existing block.
00490         // We only need to check this for the first input range because
00491         // after this working.first will always be the first possible handle
00492         // in the merged set of ranges.
00493       if (i != end && i->first < working.first && i->second+1 >= working.first) {
00494         if (adj)
00495           for (EntityHandle h = i->first; h < working.first; ++h)
00496             adj->add_adjacency( h, my_handle, false );
00497         working.first = i->first;
00498       }
00499       
00500         // Now append from the input list and the remaining set contents
00501         // until we've consolidated all overlapping/touching ranges.
00502       bool done = false;
00503       while (!done) {
00504           // does next set contents range touch working range?
00505         bool set_overlap = list_read != list_end && list_read->first <= working.second+1;
00506           // does next input range touch working range?
00507         bool inp_overlap = i != end && i->first <= working.second+1;
00508         
00509           // if both ranges touch...
00510         if (inp_overlap && set_overlap) {
00511             // if next set range is contained in working, skip it
00512           if (list_read->second <= working.second)
00513             ++list_read;
00514             // if next input range is contained in working, skip it
00515           else if (i->second <= working.second)
00516             ++i;
00517             // Otherwise set the working end to the smaller of the two 
00518             // ends: either the next set end or the next input end.
00519             // We want the smaller of the two because the larger might
00520             // intersect additional ranges in the other list.
00521           else if (list_read->second <= i->second) {
00522             working.second = list_read->second;
00523             ++list_read;
00524           }
00525           else {
00526             working.second = i->second;
00527             ++i;
00528           }
00529         }
00530           // If only the input range intersect the current working range...
00531         else if (inp_overlap) {
00532             // Would it be more efficient to just extent 'working' to 
00533             // the end of the current input range?  We'd end up adding
00534             // adjacencies for for entities that are already in the tracking
00535             // set and therefore already have the adjacency.
00536           EntityHandle last = i->second;
00537           if (list_read != list_end && list_read->first < last)
00538             last = list_read->first-1;
00539           else
00540             ++i;
00541           
00542           if (last > working.second) {
00543             if (adj)
00544               for (EntityHandle h = working.second + 1; h <= last; ++h)
00545                 adj->add_adjacency( h, my_handle, false );
00546 
00547             working.second = last;
00548           }
00549         }
00550         else if (set_overlap) {
00551           if (working.second < list_read->second)
00552             working.second = list_read->second;
00553           ++list_read;
00554         }
00555         else {
00556           done = true;
00557         }
00558       }
00559       
00560       assert(list_write < list_read);
00561       *list_write = working;
00562       ++list_write;
00563     }
00564   }
00565   
00566 
00567     // shuffle down entries to fill holes
00568   if (list_read == list_write) 
00569     list_read = list_write = list_end;
00570   else while(list_read < list_end) {
00571     *list_write = *list_read;
00572     ++list_read;
00573     ++list_write;
00574   }
00575 
00576     // adjust allocated array size
00577   const size_t occupied_size = list_write - list;
00578   const size_t new_list_size = occupied_size + insert_count;
00579   list_ptr = resize_compact_list( count, clist, 2*new_list_size );
00580     // done?
00581   if (!insert_count)
00582     return MB_SUCCESS;
00583   list = reinterpret_cast<MeshSetRange*>(list_ptr);
00584 
00585     // Second pass: insert non-mergable range pairs
00586     // All range pairs in the input are either completely disjoint from
00587     // the ones in the mesh set and must be inserted or are entirely contained
00588     // within a range pair in the mesh set.
00589   assert( begin != end ); // can't have items to insert if given empty input list
00590   pair_iter_t ri = end; --ri;
00591   list_write = list + new_list_size - 1;
00592   list_read = list + occupied_size - 1;
00593   for ( ; list_write >= list; --list_write ) {
00594     if (list_read >= list) {
00595       while (ri->first >= list_read->first && ri->second <= list_read->second) {
00596         assert(ri != begin);
00597         --ri;
00598       }
00599     
00600       if (list_read->first > ri->second) {
00601         *list_write = *list_read;
00602         --list_read;
00603         continue;
00604       }
00605     }
00606     
00607     assert( insert_count > 0 );
00608     if (adj) 
00609       for (EntityHandle h = ri->first; h <= ri->second; ++h) 
00610         adj->add_adjacency( h, my_handle, false );
00611     list_write->first = ri->first;
00612     list_write->second = ri->second;
00613 
00614       // don't have reverse iterator, so check before decrement
00615       // if insert_count isn't zero, must be more in range
00616     if (0 == --insert_count) {
00617       assert( list_read == list_write-1 );
00618       break;
00619     }
00620     else {
00621       --ri;
00622     }
00623   }
00624 
00625   assert(!insert_count);
00626   return MB_SUCCESS;
00627 }
00628  
00629 template <typename pair_iter_t> inline ErrorCode
00630 range_tool<pair_iter_t>::ranged_remove_entities( MeshSet::Count& count, 
00631                                                  MeshSet::CompactList& clist, 
00632                                                  pair_iter_t begin, 
00633                                                  pair_iter_t end, 
00634                                                  EntityHandle my_handle, 
00635                                                  AEntityFactory* adj )
00636 {
00637     //first pass:
00638     // 1) remove (from) existing ranges 
00639     // 2) count number of ranges that must be split
00640   ptrdiff_t split_count = 0;
00641   EntityHandle *list;
00642   size_t list_size;
00643   if (count < MeshSet::MANY) {
00644     list = clist.hnd;
00645     list_size = count;
00646   }
00647   else {
00648     list = clist.ptr[0];
00649     list_size = clist.ptr[1] - clist.ptr[0];
00650   }
00651 
00652   EntityHandle* list_write = list;
00653   EntityHandle *const list_end = list + list_size, *list_read = list;
00654   pair_iter_t i = begin;
00655   
00656   while(list_read != list_end && i != end) {
00657     
00658     while (i != end && i->second < list_read[0])
00659       ++i;
00660     if (i == end)
00661       break;
00662     
00663       // if there are holes in the current array, shuffle blocks 
00664       // down until we find the next block to remove
00665     if (list_read != list_write) {
00666       while (list_read != list_end && i->second < list_read[0]) {
00667         list_write[0] = list_read[0];
00668         list_write[1] = list_read[1];
00669         list_write += 2;
00670         list_read += 2;
00671       }
00672     }
00673       // otherwise do a binary search
00674     else {
00675       list_write = std::lower_bound( list_write, list_end, i->first );
00676         // if in middle of range block (odd index), back up to start of block
00677       list_write -= (list_write - list)%2;
00678       list_read = list_write;
00679     }
00680     
00681       // if everything remaning is past end of set contents...
00682     if (list_read == list_end) 
00683       break;
00684       
00685       // skip any remove pairs that aren't in the list
00686     if (i->second < list_read[0]) {
00687       ++i;
00688       continue;
00689     }
00690     
00691       // Begin by assuming that we will keep the entire block
00692     list_write[0] = list_read[0];
00693     list_write[1] = list_read[1];
00694     list_read += 2;
00695     
00696     for (; i != end && i->first <= list_write[1]; ++i) {
00697       if (i->first <= list_write[0]) {
00698           // remove whole block
00699         if (i->second >= list_write[1]) {
00700           if (adj)
00701             for (EntityHandle h = list_write[0]; h <= list_write[1]; ++h)
00702               adj->remove_adjacency( h, my_handle );
00703           list_write -= 2;
00704           break;
00705         }
00706           // remove from start of block
00707         else if (i->second >= list_write[0]) {
00708           if (adj)
00709             for (EntityHandle h = list_write[0]; h <= i->second; ++h)
00710               adj->remove_adjacency( h, my_handle );
00711           list_write[0] = i->second + 1;
00712         }
00713       }
00714       else if (i->first <= list_write[1]) {
00715           // remove from end of block
00716         if (i->second >= list_write[1]) {
00717           if (adj)
00718             for (EntityHandle h = i->first; h <= list_write[1]; ++h)
00719               adj->remove_adjacency( h, my_handle );
00720           list_write[1] = i->first - 1;
00721           //list_write += 2;
00722           break;
00723         }
00724           // split block
00725         else {
00726           if (adj)
00727             for (EntityHandle h = i->first; h <= i->second; ++h)
00728               adj->remove_adjacency( h, my_handle );
00729 
00730           if (list_read - list_write <= 2) {
00731             ++split_count;
00732             continue;
00733           }
00734           else {
00735             list_write[3] = list_write[1];
00736             list_write[1] = i->first - 1;
00737             list_write[2] = i->second + 1;
00738             list_write += 2;
00739           }
00740         }
00741       }
00742     }
00743     list_write += 2;
00744   }
00745 
00746     // shuffle down entries to fill holes
00747   if (list_read == list_write) 
00748     list_read = list_write = list_end;
00749   else 
00750     while(list_read < list_end) {
00751       list_write[0] = list_read[0];
00752       list_write[1] = list_read[1];
00753       list_read += 2;
00754       list_write += 2;
00755     }
00756 
00757     // adjust allocated array size
00758   const size_t occupied_size = list_write - list;
00759   const size_t new_list_size = occupied_size + 2*split_count;
00760   list = resize_compact_list( count, clist, new_list_size );
00761     // done?
00762   if (!split_count)
00763     return MB_SUCCESS;
00764 
00765     // Second pass: split range pairs
00766     // All range pairs in the input are either already removed or
00767     // require one of the existing range pairs to be split
00768   assert( begin != end ); // can't have ranges to split if given empty input list
00769   pair_iter_t ri = end; --ri;
00770   list_write = list + new_list_size - 2;
00771   list_read = list + occupied_size - 2;
00772   for ( ; list_write >= list; list_write -= 2 ) {
00773     if (list_read >= list) {
00774       while (ri->second > list_read[1]) {
00775         assert(ri != begin);
00776         --ri;
00777       }
00778     
00779       if (list_read[0] > ri->second) {
00780         list_write[0] = list_read[0];
00781         list_write[1] = list_read[1];
00782         list_read -= 2;
00783         continue;
00784       }
00785     }
00786     
00787     assert( split_count > 0 );
00788     list_write[0] = ri->second + 1;
00789     list_write[1] = list_read[1];
00790     list_read[1] = ri->first - 1;
00791 
00792       // don't have reverse iterator, so check before decrement
00793       // if insert_count isn't zero, must be more in range
00794     if (0 == --split_count) {
00795       assert( list_read == list_write-2 );
00796       break;
00797     }
00798     else {
00799       --ri;
00800     }
00801   }
00802 
00803   assert(!split_count);
00804   return MB_SUCCESS;
00805 }
00806 
00807 
00808 template <typename pair_iter_t> inline ErrorCode
00809 range_tool<pair_iter_t>::vector_insert_entities( MeshSet::Count& count, 
00810                                                  MeshSet::CompactList& clist, 
00811                                                  pair_iter_t begin, 
00812                                                  pair_iter_t end, 
00813                                                  EntityHandle my_handle, 
00814                                                  AEntityFactory* adj )
00815 {
00816   const size_t init_size = count < MeshSet::MANY ? (int)count : clist.ptr[1] - clist.ptr[0];
00817   size_t add_size = 0;
00818   for (pair_iter_t i = begin; i != end; ++i)
00819     add_size += i->second - i->first + 1;
00820   EntityHandle* list = resize_compact_list( count, clist, init_size + add_size );
00821   EntityHandle* li = list + init_size;
00822 
00823   for (pair_iter_t i = begin; i != end; ++i) {
00824     for (EntityHandle h = i->first; h <= i->second; ++h) {
00825       if (adj)
00826         adj->add_adjacency( h, my_handle, false );
00827       *li = h;
00828       ++li;
00829     }
00830   }
00831 
00832   return MB_SUCCESS;
00833 }
00834 
00835 static ErrorCode vector_remove_range( MeshSet::Count& count, 
00836                                         MeshSet::CompactList& clist, 
00837                                         const Range& range, 
00838                                         EntityHandle my_handle, 
00839                                         AEntityFactory* adj )
00840 {
00841   EntityHandle *list;
00842   size_t list_size;
00843   if (count < MeshSet::MANY) {
00844     list = clist.hnd;
00845     list_size = count;
00846   }
00847   else {
00848     list = clist.ptr[0];
00849     list_size = clist.ptr[1] - clist.ptr[0];
00850   }
00851 
00852   const EntityHandle * const list_end = list + list_size;
00853   EntityHandle* list_write = list;
00854   for (const EntityHandle* list_read = list; list_read != list_end; ++list_read) {
00855     if (range.find(*list_read) == range.end()) { // keep
00856       *list_write = *list_read;
00857       ++list_write;
00858     }
00859     else if (adj) {    
00860       adj->remove_adjacency( *list_read, my_handle );
00861     }
00862   }
00863 
00864   resize_compact_list( count, clist, list_write - list );
00865   return MB_SUCCESS;
00866 }
00867 
00868 static ErrorCode vector_remove_ranges( MeshSet::Count& count, 
00869                                          MeshSet::CompactList& clist, 
00870                                          const EntityHandle* pair_list,
00871                                          size_t num_pairs,
00872                                          EntityHandle my_handle, 
00873                                          AEntityFactory* adj )
00874 {
00875   EntityHandle *list;
00876   size_t list_size;
00877   if (count < MeshSet::MANY) {
00878     list = clist.hnd;
00879     list_size = count;
00880   }
00881   else {
00882     list = clist.ptr[0];
00883     list_size = clist.ptr[1] - clist.ptr[0];
00884   }
00885 
00886   const EntityHandle *const list_end = list + list_size, 
00887                        *const input_end = pair_list + 2*num_pairs;
00888   EntityHandle* list_write = list;
00889   for (const EntityHandle* list_read = list; list_read != list_end; ++list_read) {
00890     const EntityHandle* ptr = std::lower_bound( pair_list, input_end, *list_read );
00891     if ((ptr != input_end && (*ptr == *list_read || (ptr - pair_list)%2)) && // if in delete list
00892         std::find(list_read+1, list_end, *list_read) == list_end) { // and is last occurance in list 
00893         // only remove adj if no previous occurance
00894       if (adj && std::find(list, list_write, *list_read) == list_write)
00895         adj->remove_adjacency( *list_read, my_handle );
00896     }
00897     else {
00898       *list_write = *list_read;
00899       ++list_write;
00900     }
00901   }
00902 
00903   resize_compact_list( count, clist, list_write - list );
00904   return MB_SUCCESS;
00905 }
00906 
00907 static ErrorCode vector_remove_vector( MeshSet::Count& count, 
00908                                          MeshSet::CompactList& clist, 
00909                                          const EntityHandle* vect,
00910                                          size_t vect_size,
00911                                          EntityHandle my_handle, 
00912                                          AEntityFactory* adj )
00913 {
00914   EntityHandle *list;
00915   size_t list_size;
00916   if (count < MeshSet::MANY) {
00917     list = clist.hnd;
00918     list_size = count;
00919   }
00920   else {
00921     list = clist.ptr[0];
00922     list_size = clist.ptr[1] - clist.ptr[0];
00923   }
00924 
00925   const EntityHandle *const list_end = list + list_size, 
00926                        *const input_end = vect + vect_size;
00927   EntityHandle* list_write = list;
00928   for (const EntityHandle* list_read = list; list_read != list_end; ++list_read) {
00929     if (std::find(vect, input_end, *list_read) != input_end && // if in delete list
00930         std::find(list_read+1, list_end, *list_read) == list_end) { // and is last occurance in list 
00931         // only remove adj if no previous occurance?
00932       if (adj ) // && std::find(list, list_write, *list_read) == list_write)
00933         adj->remove_adjacency( *list_read, my_handle );
00934     }
00935     else {
00936       *list_write = *list_read;
00937       ++list_write;
00938     }
00939   }
00940 
00941   resize_compact_list( count, clist, list_write - list );
00942   return MB_SUCCESS;
00943 }
00944 
00945 static ErrorCode vector_insert_vector( MeshSet::Count& count, 
00946                                          MeshSet::CompactList& clist, 
00947                                          const EntityHandle* vect,
00948                                          size_t vect_size,
00949                                          EntityHandle my_handle, 
00950                                          AEntityFactory* adj )
00951 {
00952   const size_t orig_size = count < MeshSet::MANY ? (int)count : clist.ptr[1] - clist.ptr[0];
00953   EntityHandle* list = resize_compact_list( count, clist, orig_size + vect_size );
00954   if (adj) 
00955     for (size_t i = 0; i < vect_size; ++i)
00956       adj->add_adjacency( vect[i], my_handle, false );
00957   memcpy( list+orig_size, vect, sizeof(EntityHandle)*vect_size );
00958   return MB_SUCCESS;
00959 }
00960 
00961 ErrorCode MeshSet::insert_entity_ranges( const EntityHandle* range_vect, size_t len, EntityHandle my_h, AEntityFactory* adj )
00962 {
00963   typedef const std::pair<EntityHandle,EntityHandle>* pair_vect_t;
00964   pair_vect_t pair_vect = reinterpret_cast<pair_vect_t>(range_vect);
00965   MeshSet::Count count = static_cast<MeshSet::Count>(mContentCount);
00966   ErrorCode rval;
00967   if (!vector_based())
00968     rval = range_tool<pair_vect_t>::ranged_insert_entities( count, contentList,  pair_vect, 
00969                                              pair_vect + len/2, my_h, tracking() ? adj : 0 );
00970   else
00971     rval = range_tool<pair_vect_t>::vector_insert_entities( count, contentList,  pair_vect, 
00972                                              pair_vect + len/2, my_h, tracking() ? adj : 0 );
00973   mContentCount = count;
00974   return rval;
00975 }
00976 
00977 ErrorCode MeshSet::insert_entity_ranges( const Range& range, EntityHandle my_h, AEntityFactory* adj )
00978 {
00979   ErrorCode rval;
00980   MeshSet::Count count = static_cast<MeshSet::Count>(mContentCount);
00981   if (!vector_based())
00982     rval = range_tool<Range::const_pair_iterator>::ranged_insert_entities( count, 
00983                              contentList, range.const_pair_begin(), range.const_pair_end(), 
00984                              my_h, tracking() ? adj : 0 );
00985   else
00986     rval = range_tool<Range::const_pair_iterator>::vector_insert_entities( count, 
00987                              contentList, range.const_pair_begin(), range.const_pair_end(), 
00988                              my_h, tracking() ? adj : 0 );
00989   mContentCount = count;
00990   return rval;
00991 }
00992 
00993 ErrorCode MeshSet::remove_entity_ranges( const EntityHandle* range_vect, size_t len, EntityHandle my_h, AEntityFactory* adj )
00994 {
00995   ErrorCode rval;
00996   MeshSet::Count count = static_cast<MeshSet::Count>(mContentCount);
00997   if (vector_based()) 
00998     rval = vector_remove_ranges( count, contentList, range_vect, len/2, my_h, 
00999                                  tracking() ? adj : 0 );
01000   else {
01001     typedef const std::pair<EntityHandle,EntityHandle>* pair_vect_t;
01002     pair_vect_t pair_vect = reinterpret_cast<pair_vect_t>(range_vect);
01003     rval = range_tool<pair_vect_t>::ranged_remove_entities( count, contentList, pair_vect, 
01004                                            pair_vect + len/2, my_h, tracking() ? adj : 0 );
01005   }
01006   mContentCount = count;
01007   return rval;
01008 }
01009 
01010 ErrorCode MeshSet::remove_entity_ranges( const Range& range, EntityHandle my_h, AEntityFactory* adj )
01011 {
01012   ErrorCode rval;
01013   MeshSet::Count count = static_cast<MeshSet::Count>(mContentCount);
01014   if (vector_based()) 
01015     rval = vector_remove_range( count, contentList, range, my_h, tracking() ? adj : 0 );
01016   else 
01017     rval = range_tool<Range::const_pair_iterator>::ranged_remove_entities( count, 
01018                          contentList, range.const_pair_begin(), range.const_pair_end(), 
01019                          my_h, tracking() ? adj : 0 );
01020   mContentCount = count;
01021   return rval;
01022 }
01023 
01024 
01025 ErrorCode MeshSet::intersect( const MeshSet* other, EntityHandle my_handle, AEntityFactory* adj )
01026 {
01027   ErrorCode rval;
01028   if (!vector_based() && !other->vector_based()) {
01029     size_t other_count = 0;
01030     const EntityHandle* other_vect = other->get_contents( other_count );
01031     if (!other_count)
01032       return clear( my_handle, adj );
01033     assert(0 == other_count%2);
01034     
01035     std::vector<EntityHandle> compliment;
01036     compliment.reserve( other_count + 4 );
01037     if (*other_vect > 0) {
01038       compliment.push_back( 0 );
01039       compliment.push_back( *other_vect - 1 );
01040     }
01041     ++other_vect;
01042     const EntityHandle *const other_end = other_vect + other_count - 2;
01043     for (; other_vect < other_end; other_vect += 2) {
01044       compliment.push_back( other_vect[0] + 1 );
01045       compliment.push_back( other_vect[1] - 1 );
01046     }
01047     if (*other_vect < ~(EntityHandle)0) {
01048       compliment.push_back( *other_vect + 1 );
01049       compliment.push_back( ~(EntityHandle)0 );
01050     }
01051     
01052     return remove_entity_ranges( &compliment[0], compliment.size(), my_handle, adj );
01053   }
01054   else {
01055     Range my_ents, other_ents;
01056     rval = get_entities(my_ents);
01057     if (MB_SUCCESS != rval)
01058       return rval;
01059     rval = other->get_entities(other_ents);
01060     return remove_entities( moab::subtract(my_ents, other_ents), my_handle, adj );
01061   }
01062 }
01063 
01064 static void convert_to_ranges( const EntityHandle* vect_in, size_t vect_in_len,
01065                                std::vector<EntityHandle>& vect_out )
01066 {
01067   vect_out.reserve( 2*vect_in_len );
01068   vect_out.resize( vect_in_len );
01069   std::copy( vect_in, vect_in+vect_in_len, vect_out.begin() );
01070   std::sort( vect_out.begin(), vect_out.end() );
01071   vect_out.erase( std::unique( vect_out.begin(), vect_out.end() ), vect_out.end() );
01072 
01073     // duplicate all entries
01074   vect_out.resize( vect_out.size() * 2 );
01075   for (long i = vect_out.size() - 1; i >= 0; --i) 
01076     vect_out[i] = vect_out[i/2];
01077    
01078     // compact adjacent ranges
01079   std::vector<EntityHandle>::iterator r = vect_out.begin(), w = vect_out.begin();
01080   while (r != vect_out.end()) {
01081     *w = *r;
01082     ++w; 
01083     ++r;
01084     *w = *r;
01085     ++r;
01086     
01087     while (r != vect_out.end() && *w + 1 == *r) {
01088       ++r;
01089       *w = *r;
01090       ++r;
01091     }
01092     ++w;
01093   }
01094   
01095     // remove extra space
01096   vect_out.erase( w, vect_out.end() );
01097 }
01098 
01099 ErrorCode MeshSet::insert_entity_vector( const EntityHandle* vect, size_t len, EntityHandle my_h, AEntityFactory* adj )
01100 {
01101   MeshSet::Count count = static_cast<MeshSet::Count>(mContentCount);
01102   ErrorCode rval;
01103   if (vector_based())
01104     rval = vector_insert_vector( count, contentList, vect, len, my_h, tracking() ? adj : 0 );
01105   else {
01106     std::vector<EntityHandle> rangevect;
01107     convert_to_ranges( vect, len, rangevect );
01108     typedef const std::pair<EntityHandle,EntityHandle>* pair_vect_t;
01109     pair_vect_t pair_vect = reinterpret_cast<pair_vect_t>(&rangevect[0]);
01110     rval = range_tool<pair_vect_t>::ranged_insert_entities( count, contentList, pair_vect, 
01111                                  pair_vect + rangevect.size()/2, my_h, tracking() ? adj : 0 );
01112   }
01113   mContentCount = count;
01114   return rval;
01115 }
01116 
01117 ErrorCode MeshSet::remove_entity_vector( const EntityHandle* vect, size_t len, EntityHandle my_h, AEntityFactory* adj )
01118 {
01119   MeshSet::Count count = static_cast<MeshSet::Count>(mContentCount);
01120   ErrorCode rval;
01121   if (vector_based())
01122     rval = vector_remove_vector( count, contentList, vect, len, my_h, tracking() ? adj : 0 );
01123   else {
01124     std::vector<EntityHandle> rangevect;
01125     convert_to_ranges( vect, len, rangevect );
01126     typedef const std::pair<EntityHandle,EntityHandle>* pair_vect_t;
01127     pair_vect_t pair_vect = reinterpret_cast<pair_vect_t>(&rangevect[0]);
01128     rval = range_tool<pair_vect_t>::ranged_remove_entities( count, contentList, pair_vect, 
01129                                 pair_vect + rangevect.size()/2, my_h, tracking() ? adj : 0 );
01130   }
01131   mContentCount = count;
01132   return rval;
01133 }
01134 
01135 
01136 
01137 ErrorCode MeshSet::replace_entities( EntityHandle my_handle,
01138                                          const EntityHandle* old_entities,
01139                                          const EntityHandle* new_entities,
01140                                          size_t num_ents,
01141                                          AEntityFactory* adjfact )
01142 {
01143   if (vector_based()) {
01144     ErrorCode result = MB_SUCCESS;
01145     size_t count;
01146     EntityHandle* vect = get_contents( count );
01147     EntityHandle* const vect_end = vect+count;
01148     for (size_t i = 0; i < num_ents; ++i) {
01149       EntityHandle* p = std::find( vect, vect_end, old_entities[i] );
01150       if (p == vect_end) {
01151         result = MB_ENTITY_NOT_FOUND;
01152       }
01153       else do {
01154         if (tracking()) {
01155           adjfact->remove_adjacency( *p, my_handle );
01156           adjfact->add_adjacency( new_entities[i], my_handle, false );
01157         }
01158         *p = new_entities[i];
01159         p = std::find( p+1, vect_end, old_entities[i] );
01160       } while (p != vect_end);
01161     }
01162     return result;
01163   }
01164   else {
01165     ErrorCode r1 = remove_entities( old_entities, num_ents, my_handle, adjfact );
01166     ErrorCode r2 = add_entities( new_entities, num_ents, my_handle, adjfact );
01167     return (MB_SUCCESS == r2) ? r1 : r2;
01168   }
01169 }
01170 
01171 
01172 /*****************************************************************************************
01173  *                                  Misc. Methods                                        *
01174  *****************************************************************************************/
01175 
01176 unsigned long MeshSet::get_memory_use() const
01177 {
01178   unsigned long result = 0;
01179   if (mParentCount == MANY)
01180     result += parentMeshSets.ptr[1] - parentMeshSets.ptr[0];
01181   if (mChildCount == MANY)
01182     result += childMeshSets.ptr[1] - childMeshSets.ptr[0];
01183   if (mContentCount == MANY)
01184     result += contentList.ptr[1] - contentList.ptr[0];
01185   return sizeof(EntityHandle)*result;
01186 }
01187   
01188 } // namespace moab
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines