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