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