MeshSet.cpp

Go to the documentation of this file.

#ifdef WIN32
#ifdef _DEBUG
// turn off warnings that say they debugging identifier has been truncated
// this warning comes up when using some STL containers
#pragma warning( disable : 4786 )
#endif
#endif
 
#include "MeshSet.hpp"
#include "AEntityFactory.hpp"
 
namespace moab
{
 
/*****************************************************************************************
 * Helper Function Declarations *
 *****************************************************************************************/
 
/**\brief Insert into parent/child list */
static inline MeshSet::Count insert_in_vector( const MeshSet::Count count,
 MeshSet::CompactList& list,
 const EntityHandle h,
 int& result );
 
/**\brief Remvoe from parent/child list */
static inline MeshSet::Count remove_from_vector( const MeshSet::Count count,
 MeshSet::CompactList& list,
 const EntityHandle h,
 int& result );
 
/**\brief Resize MeshSet::CompactList. Returns pointer to storage */
static EntityHandle* resize_compact_list( MeshSet::Count& count, MeshSet::CompactList& clist, size_t new_list_size );
/**\brief Methods to insert/remove range-based data from contents list.
 * Templatized to operate on both Range and set-based MeshSets.
 */
template < typename pair_iter_t >
class range_tool
{
 public:
 /** Insert range-based data into range-based MeshSet */
 inline static ErrorCode ranged_insert_entities( MeshSet::Count& count,
 MeshSet::CompactList& clist,
 pair_iter_t begin,
 pair_iter_t end,
 EntityHandle my_handle,
 AEntityFactory* adj );
 
 /** Remove range-based data from range-based MeshSet */
 inline static ErrorCode ranged_remove_entities( MeshSet::Count& count,
 MeshSet::CompactList& clist,
 pair_iter_t begin,
 pair_iter_t end,
 EntityHandle my_handle,
 AEntityFactory* adj );
 
 /** Insert range-based data into list-based MeshSet */
 inline static ErrorCode vector_insert_entities( MeshSet::Count& count,
 MeshSet::CompactList& clist,
 pair_iter_t begin,
 pair_iter_t end,
 EntityHandle my_handle,
 AEntityFactory* adj );
};
 
/** Remove Range of handles fromr vector-based MeshSet */
static ErrorCode vector_remove_range( MeshSet::Count& count,
 MeshSet::CompactList& clist,
 const Range& range,
 EntityHandle my_handle,
 AEntityFactory* adj );
 
/** Remove range-based MeshSet contents from vector-based MeshSet */
static ErrorCode vector_remove_ranges( MeshSet::Count& count,
 MeshSet::CompactList& clist,
 const EntityHandle* pair_list,
 size_t num_pairs,
 EntityHandle my_handle,
 AEntityFactory* adj );
 
/** Remove unsorted array of handles from vector-based MeshSet */
static ErrorCode vector_remove_vector( MeshSet::Count& count,
 MeshSet::CompactList& clist,
 const EntityHandle* vect,
 size_t vect_size,
 EntityHandle my_handle,
 AEntityFactory* adj );
 
/** Insert unsorted array of handles into vector-based MeshSet */
static ErrorCode vector_insert_vector( MeshSet::Count& count,
 MeshSet::CompactList& clist,
 const EntityHandle* vect,
 size_t vect_size,
 EntityHandle my_handle,
 AEntityFactory* adj );
 
/** Convert unsorted array of handles into array of ranged [begin,end] pairs */
static void convert_to_ranges( const EntityHandle* vect_in, size_t vect_in_len, std::vector< EntityHandle >& vect_out );
 
/*****************************************************************************************
 * Parent/Child Operations *
 *****************************************************************************************/
 
static inline MeshSet::Count insert_in_vector( const MeshSet::Count count,
 MeshSet::CompactList& list,
 const EntityHandle h,
 int& result )
{
 switch( count )
 {
 case MeshSet::ZERO:
 list.hnd[0] = h;
 result = true;
 return MeshSet::ONE;
 case MeshSet::ONE:
 if( list.hnd[0] == h )
 {
 result = false;
 return MeshSet::ONE;
 }
 else
 {
 result = true;
 list.hnd[1] = h;
 return MeshSet::TWO;
 }
 case MeshSet::TWO:
 if( list.hnd[0] == h || list.hnd[1] == h )
 {
 result = false;
 return MeshSet::TWO;
 }
 else
 {
 EntityHandle* ptr = (EntityHandle*)malloc( 3 * sizeof( EntityHandle ) );
 ptr[0] = list.hnd[0];
 ptr[1] = list.hnd[1];
 ptr[2] = h;
 list.ptr[0] = ptr;
 list.ptr[1] = ptr + 3;
 result = true;
 return MeshSet::MANY;
 }
 case MeshSet::MANY:
 if( std::find( list.ptr[0], list.ptr[1], h ) != list.ptr[1] )
 {
 result = false;
 }
 else
 {
 int size = list.ptr[1] - list.ptr[0];
 list.ptr[0] = (EntityHandle*)realloc( list.ptr[0], ( size + 1 ) * sizeof( EntityHandle ) );
 list.ptr[0][size] = h;
 list.ptr[1] = list.ptr[0] + size + 1;
 result = true;
 }
 return MeshSet::MANY;
 }
 
 return MeshSet::ZERO;
}
 
static inline MeshSet::Count remove_from_vector( const MeshSet::Count count,
 MeshSet::CompactList& list,
 const EntityHandle h,
 int& result )
{
 switch( count )
 {
 case MeshSet::ZERO:
 result = false;
 return MeshSet::ZERO;
 case MeshSet::ONE:
 if( h == list.hnd[0] )
 {
 result = true;
 return MeshSet::ZERO;
 }
 else
 {
 result = false;
 return MeshSet::ONE;
 }
 case MeshSet::TWO:
 if( h == list.hnd[0] )
 {
 list.hnd[0] = list.hnd[1];
 result = true;
 return MeshSet::ONE;
 }
 else if( h == list.hnd[1] )
 {
 result = true;
 return MeshSet::ONE;
 }
 else
 {
 result = false;
 return MeshSet::TWO;
 }
 case MeshSet::MANY: {
 EntityHandle *i, *j, *p;
 i = std::find( list.ptr[0], list.ptr[1], h );
 if( i == list.ptr[1] )
 {
 result = false;
 return MeshSet::MANY;
 }
 
 result = true;
 p = list.ptr[1] - 1;
 while( i != p )
 {
 j = i + 1;
 *i = *j;
 i = j;
 }
 int size = p - list.ptr[0];
 if( size == 2 )
 {
 p = list.ptr[0];
 list.hnd[0] = p[0];
 list.hnd[1] = p[1];
 free( p );
 return MeshSet::TWO;
 }
 else
 {
 list.ptr[0] = (EntityHandle*)realloc( list.ptr[0], size * sizeof( EntityHandle ) );
 list.ptr[1] = list.ptr[0] + size;
 return MeshSet::MANY;
 }
 }
 }
 
 return MeshSet::ZERO;
}
 
int MeshSet::add_parent( EntityHandle parent )
{
 int result = 0;
 mParentCount = insert_in_vector( (Count)mParentCount, parentMeshSets, parent, result );
 return result;
}
int MeshSet::add_child( EntityHandle child )
{
 int result = 0;
 mChildCount = insert_in_vector( (Count)mChildCount, childMeshSets, child, result );
 return result;
}
 
int MeshSet::remove_parent( EntityHandle parent )
{
 int result = 0;
 mParentCount = remove_from_vector( (Count)mParentCount, parentMeshSets, parent, result );
 return result;
}
int MeshSet::remove_child( EntityHandle child )
{
 int result = 0;
 mChildCount = remove_from_vector( (Count)mChildCount, childMeshSets, child, result );
 return result;
}
 
/*****************************************************************************************
 * Flag Conversion Operations *
 *****************************************************************************************/
 
ErrorCode MeshSet::convert( unsigned flg, EntityHandle my_handle, AEntityFactory* adj )
{
 ErrorCode rval = MB_SUCCESS;
 if( ( mFlags & MESHSET_TRACK_OWNER ) && !( flg & MESHSET_TRACK_OWNER ) )
 rval = remove_adjacencies( my_handle, adj );
 else if( !( mFlags & MESHSET_TRACK_OWNER ) && ( flg & MESHSET_TRACK_OWNER ) )
 rval = create_adjacencies( my_handle, adj );
 if( MB_SUCCESS != rval ) return rval;
 
 if( !( mFlags & MESHSET_ORDERED ) && ( flg & MESHSET_ORDERED ) )
 {
 size_t datalen;
 EntityHandle* data = get_contents( datalen );
 if( datalen )
 {
 std::vector< EntityHandle > list( datalen );
 memcpy( &list[0], data, datalen * sizeof( EntityHandle ) );
 int num_ents = num_entities();
 Count count = (Count)mContentCount;
 data = resize_compact_list( count, contentList, num_ents );
 mContentCount = count;
 assert( list.size() % 2 == 0 );
 std::vector< EntityHandle >::iterator i = list.begin();
 while( i != list.end() )
 {
 EntityHandle h = *i;
 ++i;
 EntityHandle e = *i;
 ++i;
 for( ; h <= e; ++h )
 {
 *data = h;
 ++data;
 }
 }
 }
 }
 else if( ( mFlags & MESHSET_ORDERED ) && !( flg & MESHSET_ORDERED ) )
 {
 size_t datalen;
 EntityHandle* data = get_contents( datalen );
 if( datalen )
 {
 std::vector< EntityHandle > ranges;
 convert_to_ranges( data, datalen, ranges );
 Count count = (Count)mContentCount;
 data = resize_compact_list( count, contentList, ranges.size() );
 mContentCount = count;
 memcpy( data, &ranges[0], ranges.size() * sizeof( EntityHandle ) );
 }
 }
 
 return MB_SUCCESS;
}
 
ErrorCode MeshSet::create_adjacencies( EntityHandle my_handle, AEntityFactory* adj )
{
 ErrorCode rval = MB_SUCCESS;
 ;
 size_t count;
 const EntityHandle* const ptr = get_contents( count );
 const EntityHandle* const end = ptr + count;
 if( vector_based() )
 {
 for( const EntityHandle* i = ptr; i != end; ++i )
 {
 rval = adj->add_adjacency( *i, my_handle, false );
 if( MB_SUCCESS != rval )
 {
 for( const EntityHandle* j = ptr; j != i; ++j )
 adj->remove_adjacency( *j, my_handle );
 return rval;
 }
 }
 }
 else
 {
 assert( 0 == count % 2 );
 for( const EntityHandle* i = ptr; i != end; i += 2 )
 {
 for( EntityHandle h = i[0]; h <= i[1]; ++h )
 {
 rval = adj->add_adjacency( h, my_handle, false );
 if( MB_SUCCESS != rval )
 {
 for( EntityHandle j = i[0]; j < h; ++j )
 adj->remove_adjacency( j, my_handle );
 for( const EntityHandle* j = ptr; j != i; j += 2 )
 for( EntityHandle k = j[0]; k <= j[1]; ++k )
 adj->remove_adjacency( k, my_handle );
 return rval;
 }
 }
 }
 }
 return MB_SUCCESS;
}
 
ErrorCode MeshSet::remove_adjacencies( EntityHandle my_handle, AEntityFactory* adj )
{
 size_t count;
 const EntityHandle* const ptr = get_contents( count );
 const EntityHandle* const end = ptr + count;
 if( vector_based() )
 {
 for( const EntityHandle* i = ptr; i != end; ++i )
 adj->remove_adjacency( *i, my_handle );
 }
 else
 {
 assert( 0 == count % 2 );
 for( const EntityHandle* i = ptr; i != end; i += 2 )
 for( EntityHandle h = i[0]; h <= i[1]; ++h )
 adj->remove_adjacency( h, my_handle );
 }
 return MB_SUCCESS;
}
 
/*****************************************************************************************
 * Contents Modifiction Methods *
 *****************************************************************************************/
 
static EntityHandle* resize_compact_list( MeshSet::Count& count, MeshSet::CompactList& clist, size_t new_list_size )
{
 if( count <= 2 )
 {
 if( new_list_size <= 2 )
 {
 count = (MeshSet::Count)new_list_size;
 return clist.hnd;
 }
 else
 {
 EntityHandle* list = (EntityHandle*)malloc( new_list_size * sizeof( EntityHandle ) );
 list[0] = clist.hnd[0];
 list[1] = clist.hnd[1];
 clist.ptr[0] = list;
 clist.ptr[1] = list + new_list_size;
 count = MeshSet::MANY;
 return list;
 }
 }
 else if( new_list_size > 2 )
 {
 if( new_list_size > (size_t)( clist.ptr[1] - clist.ptr[0] ) )
 clist.ptr[0] = (EntityHandle*)realloc( clist.ptr[0], new_list_size * sizeof( EntityHandle ) );
 clist.ptr[1] = clist.ptr[0] + new_list_size;
 count = MeshSet::MANY;
 return clist.ptr[0];
 }
 else
 {
 EntityHandle* list = clist.ptr[0];
 clist.hnd[0] = list[0];
 clist.hnd[1] = list[1];
 free( list );
 count = (MeshSet::Count)new_list_size;
 return clist.hnd;
 }
}
 
typedef std::pair< EntityHandle, EntityHandle > MeshSetRange;
 
class MeshSetRComp
{
 public:
 bool operator()( const MeshSetRange& r, const MeshSetRange& h )
 {
 return r.second < h.first;
 }
};
 
template < typename pair_iter_t >
inline ErrorCode range_tool< pair_iter_t >::ranged_insert_entities( MeshSet::Count& count,
 MeshSet::CompactList& clist,
 pair_iter_t begin,
 pair_iter_t end,
 EntityHandle my_handle,
 AEntityFactory* adj )
{
 // first pass:
 // 1) merge existing ranges
 // 2) count number of new ranges that must be inserted
 EntityHandle* list_ptr;
 size_t list_size;
 if( count < MeshSet::MANY )
 {
 list_ptr = clist.hnd;
 list_size = count;
 }
 else
 {
 list_ptr = clist.ptr[0];
 list_size = clist.ptr[1] - clist.ptr[0];
 }
 
 MeshSetRange* list = reinterpret_cast< MeshSetRange* >( list_ptr );
 assert( 0 == list_size % 2 );
 assert( 2 * sizeof( EntityHandle ) == sizeof( MeshSetRange ) );
 list_size /= 2;
 MeshSetRange* const list_end = list + list_size;
 MeshSetRange *list_read = list, *list_write = list;
 pair_iter_t i = begin;
 
 // count number of range pairs that are straight insertions
 // (don't overlap any range pair in the current set) that
 // could not be inserted during the first pass.
 size_t insert_count = 0;
 
 // merge lists
 while( i != end )
 {
 // find first range that intersects the current input range
 
 // do binary search if no holes in current set contents
 if( list_read == list_write )
 {
 // subtract one from i->first because if it is one greater
 // then the the last value of some block, then we want that
 // block to append to.
 MeshSetRange tmp;
 tmp.first = i->first - 1;
 tmp.second = i->second;
 list_write = std::lower_bound( list_read, list_end, tmp, MeshSetRComp() );
 list_read = list_write;
 }
 // otherwise shift down until we find where we find a range block
 // that intersects
 else
 while( list_read != list_end && list_read->second + 1 < i->first )
 {
 *list_write = *list_read;
 ++list_write;
 ++list_read;
 }
 
 // handle any straight insertions of range blocks
 for( ; i != end && ( list_read == list_end || i->second + 1 < list_read->first ); ++i )
 {
 // If we haven't removed any range pairs, we don't have space to
 // insert here. Defer the insertion until later.
 if( list_read == list_write )
 {
 ++insert_count;
 }
 else
 {
 if( adj )
 for( EntityHandle j = i->first; j <= i->second; ++j )
 adj->add_adjacency( j, my_handle, false );
 
 list_write->first = i->first;
 list_write->second = i->second;
 ++list_write;
 }
 }
 
 // merge all the stuff that gets merged into a single range pair
 // from both the input list and the existing set data
 if( list_read != list_end )
 {
 MeshSetRange working = *list_read; // copy because might be the same as list_write
 ++list_read;
 
 // Check if we need to prepend to the existing block.
 // We only need to check this for the first input range because
 // after this working.first will always be the first possible handle
 // in the merged set of ranges.
 if( i != end && i->first < working.first && i->second + 1 >= working.first )
 {
 if( adj )
 for( EntityHandle h = i->first; h < working.first; ++h )
 adj->add_adjacency( h, my_handle, false );
 working.first = i->first;
 }
 
 // Now append from the input list and the remaining set contents
 // until we've consolidated all overlapping/touching ranges.
 bool done = false;
 while( !done )
 {
 // does next set contents range touch working range?
 bool set_overlap = list_read != list_end && list_read->first <= working.second + 1;
 // does next input range touch working range?
 bool inp_overlap = i != end && i->first <= working.second + 1;
 
 // if both ranges touch...
 if( inp_overlap && set_overlap )
 {
 // if next set range is contained in working, skip it
 if( list_read->second <= working.second ) ++list_read;
 // if next input range is contained in working, skip it
 else if( i->second <= working.second )
 ++i;
 // Otherwise set the working end to the smaller of the two
 // ends: either the next set end or the next input end.
 // We want the smaller of the two because the larger might
 // intersect additional ranges in the other list.
 else if( list_read->second <= i->second )
 {
 working.second = list_read->second;
 ++list_read;
 }
 else
 {
 working.second = i->second;
 ++i;
 }
 }
 // If only the input range intersect the current working range...
 else if( inp_overlap )
 {
 // Would it be more efficient to just extent 'working' to
 // the end of the current input range? We'd end up adding
 // adjacencies for for entities that are already in the tracking
 // set and therefore already have the adjacency.
 EntityHandle last = i->second;
 if( list_read != list_end && list_read->first < last )
 last = list_read->first - 1;
 else
 ++i;
 
 if( last > working.second )
 {
 if( adj )
 for( EntityHandle h = working.second + 1; h <= last; ++h )
 adj->add_adjacency( h, my_handle, false );
 
 working.second = last;
 }
 }
 else if( set_overlap )
 {
 if( working.second < list_read->second ) working.second = list_read->second;
 ++list_read;
 }
 else
 {
 done = true;
 }
 }
 
 assert( list_write < list_read );
 *list_write = working;
 ++list_write;
 }
 }
 
 // shuffle down entries to fill holes
 if( list_read == list_write )
 list_read = list_write = list_end;
 else
 while( list_read < list_end )
 {
 *list_write = *list_read;
 ++list_read;
 ++list_write;
 }
 
 // adjust allocated array size
 const size_t occupied_size = list_write - list;
 const size_t new_list_size = occupied_size + insert_count;
 list_ptr = resize_compact_list( count, clist, 2 * new_list_size );
 // done?
 if( !insert_count ) return MB_SUCCESS;
 list = reinterpret_cast< MeshSetRange* >( list_ptr );
 
 // Second pass: insert non-mergable range pairs
 // All range pairs in the input are either completely disjoint from
 // the ones in the mesh set and must be inserted or are entirely contained
 // within a range pair in the mesh set.
 assert( begin != end ); // can't have items to insert if given empty input list
 pair_iter_t ri = end;
 --ri;
 list_write = list + new_list_size - 1;
 list_read = list + occupied_size - 1;
 for( ; list_write >= list; --list_write )
 {
 if( list_read >= list )
 {
 while( ri->first >= list_read->first && ri->second <= list_read->second )
 {
 assert( ri != begin );
 --ri;
 }
 
 if( list_read->first > ri->second )
 {
 *list_write = *list_read;
 --list_read;
 continue;
 }
 }
 
 assert( insert_count > 0 );
 if( adj )
 for( EntityHandle h = ri->first; h <= ri->second; ++h )
 adj->add_adjacency( h, my_handle, false );
 list_write->first = ri->first;
 list_write->second = ri->second;
 
 // don't have reverse iterator, so check before decrement
 // if insert_count isn't zero, must be more in range
 if( 0 == --insert_count )
 {
 assert( list_read == list_write - 1 );
 break;
 }
 else
 {
 --ri;
 }
 }
 
 assert( !insert_count );
 return MB_SUCCESS;
}
 
template < typename pair_iter_t >
inline ErrorCode range_tool< pair_iter_t >::ranged_remove_entities( MeshSet::Count& count,
 MeshSet::CompactList& clist,
 pair_iter_t begin,
 pair_iter_t end,
 EntityHandle my_handle,
 AEntityFactory* adj )
{
 // first pass:
 // 1) remove (from) existing ranges
 // 2) count number of ranges that must be split
 ptrdiff_t split_count = 0;
 EntityHandle* list;
 size_t list_size;
 if( count < MeshSet::MANY )
 {
 list = clist.hnd;
 list_size = count;
 }
 else
 {
 list = clist.ptr[0];
 list_size = clist.ptr[1] - clist.ptr[0];
 }
 
 EntityHandle* list_write = list;
 EntityHandle *const list_end = list + list_size, *list_read = list;
 pair_iter_t i = begin;
 
 while( list_read != list_end && i != end )
 {
 
 while( i != end && i->second < list_read[0] )
 ++i;
 if( i == end ) break;
 
 // if there are holes in the current array, shuffle blocks
 // down until we find the next block to remove
 if( list_read != list_write )
 {
 while( list_read != list_end && i->second < list_read[0] )
 {
 list_write[0] = list_read[0];
 list_write[1] = list_read[1];
 list_write += 2;
 list_read += 2;
 }
 }
 // otherwise do a binary search
 else
 {
 list_write = std::lower_bound( list_write, list_end, i->first );
 // if in middle of range block (odd index), back up to start of block
 list_write -= ( list_write - list ) % 2;
 list_read = list_write;
 }
 
 // if everything remaning is past end of set contents...
 if( list_read == list_end ) break;
 
 // skip any remove pairs that aren't in the list
 if( i->second < list_read[0] )
 {
 ++i;
 continue;
 }
 
 // Begin by assuming that we will keep the entire block
 list_write[0] = list_read[0];
 list_write[1] = list_read[1];
 list_read += 2;
 
 for( ; i != end && i->first <= list_write[1]; ++i )
 {
 if( i->first <= list_write[0] )
 {
 // remove whole block
 if( i->second >= list_write[1] )
 {
 if( adj )
 for( EntityHandle h = list_write[0]; h <= list_write[1]; ++h )
 adj->remove_adjacency( h, my_handle );
 list_write -= 2;
 break;
 }
 // remove from start of block
 else if( i->second >= list_write[0] )
 {
 if( adj )
 for( EntityHandle h = list_write[0]; h <= i->second; ++h )
 adj->remove_adjacency( h, my_handle );
 list_write[0] = i->second + 1;
 }
 }
 else if( i->first <= list_write[1] )
 {
 // remove from end of block
 if( i->second >= list_write[1] )
 {
 if( adj )
 for( EntityHandle h = i->first; h <= list_write[1]; ++h )
 adj->remove_adjacency( h, my_handle );
 list_write[1] = i->first - 1;
 // list_write += 2;
 break;
 }
 // split block
 else
 {
 if( adj )
 for( EntityHandle h = i->first; h <= i->second; ++h )
 adj->remove_adjacency( h, my_handle );
 
 if( list_read - list_write <= 2 )
 {
 ++split_count;
 continue;
 }
 else
 {
 list_write[3] = list_write[1];
 list_write[1] = i->first - 1;
 list_write[2] = i->second + 1;
 list_write += 2;
 }
 }
 }
 }
 list_write += 2;
 }
 
 // shuffle down entries to fill holes
 if( list_read == list_write )
 list_read = list_write = list_end;
 else
 while( list_read < list_end )
 {
 list_write[0] = list_read[0];
 list_write[1] = list_read[1];
 list_read += 2;
 list_write += 2;
 }
 
 // adjust allocated array size
 const size_t occupied_size = list_write - list;
 const size_t new_list_size = occupied_size + 2 * split_count;
 list = resize_compact_list( count, clist, new_list_size );
 // done?
 if( !split_count ) return MB_SUCCESS;
 
 // Second pass: split range pairs
 // All range pairs in the input are either already removed or
 // require one of the existing range pairs to be split
 assert( begin != end ); // can't have ranges to split if given empty input list
 pair_iter_t ri = end;
 --ri;
 list_write = list + new_list_size - 2;
 list_read = list + occupied_size - 2;
 for( ; list_write >= list; list_write -= 2 )
 {
 if( list_read >= list )
 {
 while( ri->second > list_read[1] )
 {
 assert( ri != begin );
 --ri;
 }
 
 if( list_read[0] > ri->second )
 {
 list_write[0] = list_read[0];
 list_write[1] = list_read[1];
 list_read -= 2;
 continue;
 }
 }
 
 assert( split_count > 0 );
 list_write[0] = ri->second + 1;
 list_write[1] = list_read[1];
 list_read[1] = ri->first - 1;
 
 // don't have reverse iterator, so check before decrement
 // if insert_count isn't zero, must be more in range
 if( 0 == --split_count )
 {
 assert( list_read == list_write - 2 );
 break;
 }
 else
 {
 --ri;
 }
 }
 
 assert( !split_count );
 return MB_SUCCESS;
}
 
template < typename pair_iter_t >
inline ErrorCode range_tool< pair_iter_t >::vector_insert_entities( MeshSet::Count& count,
 MeshSet::CompactList& clist,
 pair_iter_t begin,
 pair_iter_t end,
 EntityHandle my_handle,
 AEntityFactory* adj )
{
 const size_t init_size = count < MeshSet::MANY ? (int)count : clist.ptr[1] - clist.ptr[0];
 size_t add_size = 0;
 for( pair_iter_t i = begin; i != end; ++i )
 add_size += i->second - i->first + 1;
 EntityHandle* list = resize_compact_list( count, clist, init_size + add_size );
 EntityHandle* li = list + init_size;
 
 for( pair_iter_t i = begin; i != end; ++i )
 {
 for( EntityHandle h = i->first; h <= i->second; ++h )
 {
 if( adj ) adj->add_adjacency( h, my_handle, false );
 *li = h;
 ++li;
 }
 }
 
 return MB_SUCCESS;
}
 
static ErrorCode vector_remove_range( MeshSet::Count& count,
 MeshSet::CompactList& clist,
 const Range& range,
 EntityHandle my_handle,
 AEntityFactory* adj )
{
 EntityHandle* list;
 size_t list_size;
 if( count < MeshSet::MANY )
 {
 list = clist.hnd;
 list_size = count;
 }
 else
 {
 list = clist.ptr[0];
 list_size = clist.ptr[1] - clist.ptr[0];
 }
 
 const EntityHandle* const list_end = list + list_size;
 EntityHandle* list_write = list;
 for( const EntityHandle* list_read = list; list_read != list_end; ++list_read )
 {
 if( range.find( *list_read ) == range.end() )
 { // keep
 *list_write = *list_read;
 ++list_write;
 }
 else if( adj )
 {
 adj->remove_adjacency( *list_read, my_handle );
 }
 }
 
 resize_compact_list( count, clist, list_write - list );
 return MB_SUCCESS;
}
 
static ErrorCode vector_remove_ranges( MeshSet::Count& count,
 MeshSet::CompactList& clist,
 const EntityHandle* pair_list,
 size_t num_pairs,
 EntityHandle my_handle,
 AEntityFactory* adj )
{
 EntityHandle* list;
 size_t list_size;
 if( count < MeshSet::MANY )
 {
 list = clist.hnd;
 list_size = count;
 }
 else
 {
 list = clist.ptr[0];
 list_size = clist.ptr[1] - clist.ptr[0];
 }
 
 const EntityHandle *const list_end = list + list_size, *const input_end = pair_list + 2 * num_pairs;
 EntityHandle* list_write = list;
 for( const EntityHandle* list_read = list; list_read != list_end; ++list_read )
 {
 const EntityHandle* ptr = std::lower_bound( pair_list, input_end, *list_read );
 if( ( ptr != input_end && ( *ptr == *list_read || ( ptr - pair_list ) % 2 ) ) && // if in delete list
 std::find( list_read + 1, list_end, *list_read ) == list_end )
 { // and is last occurance in list
 // only remove adj if no previous occurance
 if( adj && std::find( list, list_write, *list_read ) == list_write )
 adj->remove_adjacency( *list_read, my_handle );
 }
 else
 {
 *list_write = *list_read;
 ++list_write;
 }
 }
 
 resize_compact_list( count, clist, list_write - list );
 return MB_SUCCESS;
}
 
static ErrorCode vector_remove_vector( MeshSet::Count& count,
 MeshSet::CompactList& clist,
 const EntityHandle* vect,
 size_t vect_size,
 EntityHandle my_handle,
 AEntityFactory* adj )
{
 EntityHandle* list;
 size_t list_size;
 if( count < MeshSet::MANY )
 {
 list = clist.hnd;
 list_size = count;
 }
 else
 {
 list = clist.ptr[0];
 list_size = clist.ptr[1] - clist.ptr[0];
 }
 
 const EntityHandle *const list_end = list + list_size, *const input_end = vect + vect_size;
 EntityHandle* list_write = list;
 for( const EntityHandle* list_read = list; list_read != list_end; ++list_read )
 {
 if( std::find( vect, input_end, *list_read ) != input_end && // if in delete list
 std::find( list_read + 1, list_end, *list_read ) == list_end )
 { // and is last occurance in list
 // only remove adj if no previous occurance?
 if( adj ) // && std::find(list, list_write, *list_read) == list_write)
 adj->remove_adjacency( *list_read, my_handle );
 }
 else
 {
 *list_write = *list_read;
 ++list_write;
 }
 }
 
 resize_compact_list( count, clist, list_write - list );
 return MB_SUCCESS;
}
 
static ErrorCode vector_insert_vector( MeshSet::Count& count,
 MeshSet::CompactList& clist,
 const EntityHandle* vect,
 size_t vect_size,
 EntityHandle my_handle,
 AEntityFactory* adj )
{
 const size_t orig_size = count < MeshSet::MANY ? (int)count : clist.ptr[1] - clist.ptr[0];
 EntityHandle* list = resize_compact_list( count, clist, orig_size + vect_size );
 if( adj )
 for( size_t i = 0; i < vect_size; ++i )
 adj->add_adjacency( vect[i], my_handle, false );
 memcpy( list + orig_size, vect, sizeof( EntityHandle ) * vect_size );
 return MB_SUCCESS;
}
 
ErrorCode MeshSet::insert_entity_ranges( const EntityHandle* range_vect,
 size_t len,
 EntityHandle my_h,
 AEntityFactory* adj )
{
 typedef const std::pair< EntityHandle, EntityHandle >* pair_vect_t;
 pair_vect_t pair_vect = reinterpret_cast< pair_vect_t >( range_vect );
 MeshSet::Count count = static_cast< MeshSet::Count >( mContentCount );
 ErrorCode rval;
 if( !vector_based() )
 rval = range_tool< pair_vect_t >::ranged_insert_entities( count, contentList, pair_vect, pair_vect + len / 2,
 my_h, tracking() ? adj : 0 );
 else
 rval = range_tool< pair_vect_t >::vector_insert_entities( count, contentList, pair_vect, pair_vect + len / 2,
 my_h, tracking() ? adj : 0 );
 mContentCount = count;
 return rval;
}
 
ErrorCode MeshSet::insert_entity_ranges( const Range& range, EntityHandle my_h, AEntityFactory* adj )
{
 ErrorCode rval;
 MeshSet::Count count = static_cast< MeshSet::Count >( mContentCount );
 if( !vector_based() )
 rval = range_tool< Range::const_pair_iterator >::ranged_insert_entities(
 count, contentList, range.const_pair_begin(), range.const_pair_end(), my_h, tracking() ? adj : 0 );
 else
 rval = range_tool< Range::const_pair_iterator >::vector_insert_entities(
 count, contentList, range.const_pair_begin(), range.const_pair_end(), my_h, tracking() ? adj : 0 );
 mContentCount = count;
 return rval;
}
 
ErrorCode MeshSet::remove_entity_ranges( const EntityHandle* range_vect,
 size_t len,
 EntityHandle my_h,
 AEntityFactory* adj )
{
 ErrorCode rval;
 MeshSet::Count count = static_cast< MeshSet::Count >( mContentCount );
 if( vector_based() )
 rval = vector_remove_ranges( count, contentList, range_vect, len / 2, my_h, tracking() ? adj : 0 );
 else
 {
 typedef const std::pair< EntityHandle, EntityHandle >* pair_vect_t;
 pair_vect_t pair_vect = reinterpret_cast< pair_vect_t >( range_vect );
 rval = range_tool< pair_vect_t >::ranged_remove_entities( count, contentList, pair_vect, pair_vect + len / 2,
 my_h, tracking() ? adj : 0 );
 }
 mContentCount = count;
 return rval;
}
 
ErrorCode MeshSet::remove_entity_ranges( const Range& range, EntityHandle my_h, AEntityFactory* adj )
{
 ErrorCode rval;
 MeshSet::Count count = static_cast< MeshSet::Count >( mContentCount );
 if( vector_based() )
 rval = vector_remove_range( count, contentList, range, my_h, tracking() ? adj : 0 );
 else
 rval = range_tool< Range::const_pair_iterator >::ranged_remove_entities(
 count, contentList, range.const_pair_begin(), range.const_pair_end(), my_h, tracking() ? adj : 0 );
 mContentCount = count;
 return rval;
}
 
ErrorCode MeshSet::intersect( const MeshSet* other, EntityHandle my_handle, AEntityFactory* adj )
{
 ErrorCode rval;
 if( !vector_based() && !other->vector_based() )
 {
 size_t other_count = 0;
 const EntityHandle* other_vect = other->get_contents( other_count );
 if( !other_count ) return clear( my_handle, adj );
 assert( 0 == other_count % 2 );
 
 std::vector< EntityHandle > compliment;
 compliment.reserve( other_count + 4 );
 if( *other_vect > 0 )
 {
 compliment.push_back( 0 );
 compliment.push_back( *other_vect - 1 );
 }
 ++other_vect;
 const EntityHandle* const other_end = other_vect + other_count - 2;
 for( ; other_vect < other_end; other_vect += 2 )
 {
 compliment.push_back( other_vect[0] + 1 );
 compliment.push_back( other_vect[1] - 1 );
 }
 if( *other_vect < ~(EntityHandle)0 )
 {
 compliment.push_back( *other_vect + 1 );
 compliment.push_back( ~(EntityHandle)0 );
 }
 
 return remove_entity_ranges( &compliment[0], compliment.size(), my_handle, adj );
 }
 else
 {
 Range my_ents, other_ents;
 rval = get_entities( my_ents );
 if( MB_SUCCESS != rval ) return rval;
 rval = other->get_entities( other_ents );
 return remove_entities( moab::subtract( my_ents, other_ents ), my_handle, adj );
 }
}
 
static void convert_to_ranges( const EntityHandle* vect_in, size_t vect_in_len, std::vector< EntityHandle >& vect_out )
{
 vect_out.reserve( 2 * vect_in_len );
 vect_out.resize( vect_in_len );
 std::copy( vect_in, vect_in + vect_in_len, vect_out.begin() );
 std::sort( vect_out.begin(), vect_out.end() );
 vect_out.erase( std::unique( vect_out.begin(), vect_out.end() ), vect_out.end() );
 
 // duplicate all entries
 vect_out.resize( vect_out.size() * 2 );
 for( long i = vect_out.size() - 1; i >= 0; --i )
 vect_out[i] = vect_out[i / 2];
 
 // compact adjacent ranges
 std::vector< EntityHandle >::iterator r = vect_out.begin(), w = vect_out.begin();
 while( r != vect_out.end() )
 {
 *w = *r;
 ++w;
 ++r;
 *w = *r;
 ++r;
 
 while( r != vect_out.end() && *w + 1 == *r )
 {
 ++r;
 *w = *r;
 ++r;
 }
 ++w;
 }
 
 // remove extra space
 vect_out.erase( w, vect_out.end() );
}
 
ErrorCode MeshSet::insert_entity_vector( const EntityHandle* vect, size_t len, EntityHandle my_h, AEntityFactory* adj )
{
 MeshSet::Count count = static_cast< MeshSet::Count >( mContentCount );
 ErrorCode rval;
 if( vector_based() )
 rval = vector_insert_vector( count, contentList, vect, len, my_h, tracking() ? adj : 0 );
 else
 {
 std::vector< EntityHandle > rangevect;
 convert_to_ranges( vect, len, rangevect );
 typedef const std::pair< EntityHandle, EntityHandle >* pair_vect_t;
 pair_vect_t pair_vect = ( rangevect.empty() ) ? NULL : reinterpret_cast< pair_vect_t >( &rangevect[0] );
 rval = range_tool< pair_vect_t >::ranged_insert_entities(
 count, contentList, pair_vect, pair_vect + rangevect.size() / 2, my_h, tracking() ? adj : 0 );
 }
 mContentCount = count;
 return rval;
}
 
ErrorCode MeshSet::remove_entity_vector( const EntityHandle* vect, size_t len, EntityHandle my_h, AEntityFactory* adj )
{
 MeshSet::Count count = static_cast< MeshSet::Count >( mContentCount );
 ErrorCode rval;
 if( vector_based() )
 rval = vector_remove_vector( count, contentList, vect, len, my_h, tracking() ? adj : 0 );
 else
 {
 std::vector< EntityHandle > rangevect;
 convert_to_ranges( vect, len, rangevect );
 typedef const std::pair< EntityHandle, EntityHandle >* pair_vect_t;
 pair_vect_t pair_vect = ( rangevect.empty() ) ? NULL : reinterpret_cast< pair_vect_t >( &rangevect[0] );
 rval = range_tool< pair_vect_t >::ranged_remove_entities(
 count, contentList, pair_vect, pair_vect + rangevect.size() / 2, my_h, tracking() ? adj : 0 );
 }
 mContentCount = count;
 return rval;
}
 
ErrorCode MeshSet::replace_entities( EntityHandle my_handle,
 const EntityHandle* old_entities,
 const EntityHandle* new_entities,
 size_t num_ents,
 AEntityFactory* adjfact )
{
 if( vector_based() )
 {
 ErrorCode result = MB_SUCCESS;
 size_t count;
 EntityHandle* vect = get_contents( count );
 EntityHandle* const vect_end = vect + count;
 for( size_t i = 0; i < num_ents; ++i )
 {
 EntityHandle* p = std::find( vect, vect_end, old_entities[i] );
 if( p == vect_end )
 {
 result = MB_ENTITY_NOT_FOUND;
 }
 else
 do
 {
 if( tracking() )
 {
 adjfact->remove_adjacency( *p, my_handle );
 adjfact->add_adjacency( new_entities[i], my_handle, false );
 }
 *p = new_entities[i];
 p = std::find( p + 1, vect_end, old_entities[i] );
 } while( p != vect_end );
 }
 return result;
 }
 else
 {
 ErrorCode r1 = remove_entities( old_entities, num_ents, my_handle, adjfact );
 ErrorCode r2 = add_entities( new_entities, num_ents, my_handle, adjfact );
 return ( MB_SUCCESS == r2 ) ? r1 : r2;
 }
}
 
/*****************************************************************************************
 * Misc. Methods *
 *****************************************************************************************/
 
unsigned long MeshSet::get_memory_use() const
{
 unsigned long result = 0;
 if( mParentCount == MANY ) result += parentMeshSets.ptr[1] - parentMeshSets.ptr[0];
 if( mChildCount == MANY ) result += childMeshSets.ptr[1] - childMeshSets.ptr[0];
 if( mContentCount == MANY ) result += contentList.ptr[1] - contentList.ptr[0];
 return sizeof( EntityHandle ) * result;
}
 
} // namespace moab