moab::range_tool< pair_iter_t > Class Template Reference

Methods to insert/remove range-based data from contents list. Templatized to operate on both Range and set-based MeshSets. More...

Static Public Member Functions
static ErrorCode	ranged_insert_entities (MeshSet::Count &count, MeshSet::CompactList &clist, pair_iter_t begin, pair_iter_t end, EntityHandle my_handle, AEntityFactory *adj)
static ErrorCode	ranged_remove_entities (MeshSet::Count &count, MeshSet::CompactList &clist, pair_iter_t begin, pair_iter_t end, EntityHandle my_handle, AEntityFactory *adj)
static ErrorCode	vector_insert_entities (MeshSet::Count &count, MeshSet::CompactList &clist, pair_iter_t begin, pair_iter_t end, EntityHandle my_handle, AEntityFactory *adj)

Detailed Description

template<typename pair_iter_t>
class moab::range_tool< pair_iter_t >

Methods to insert/remove range-based data from contents list. Templatized to operate on both Range and set-based MeshSets.

Definition at line 37 of file MeshSet.cpp.

Member Function Documentation

ranged_insert_entities()

template<typename pair_iter_t >

ErrorCode moab::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  )

inlinestatic

Insert range-based data into range-based MeshSet

Definition at line 441 of file MeshSet.cpp.

{
 // 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;
}

References moab::AEntityFactory::add_adjacency(), moab::MeshSet::CompactList::hnd, moab::MeshSet::MANY, MB_SUCCESS, moab::MeshSet::CompactList::ptr, and moab::resize_compact_list().

Referenced by moab::MeshSet::insert_entity_vector().

ranged_remove_entities()

template<typename pair_iter_t >

ErrorCode moab::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  )

inlinestatic

Remove range-based data from range-based MeshSet

Definition at line 687 of file MeshSet.cpp.

{
 // 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;
}

References moab::MeshSet::CompactList::hnd, moab::MeshSet::MANY, MB_SUCCESS, moab::MeshSet::CompactList::ptr, moab::AEntityFactory::remove_adjacency(), and moab::resize_compact_list().

Referenced by moab::MeshSet::remove_entity_ranges(), and moab::MeshSet::remove_entity_vector().

vector_insert_entities()

template<typename pair_iter_t >

ErrorCode moab::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  )

inlinestatic

Insert range-based data into list-based MeshSet

Definition at line 886 of file MeshSet.cpp.

{
 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;
}

References moab::AEntityFactory::add_adjacency(), moab::MeshSet::MANY, MB_SUCCESS, moab::MeshSet::CompactList::ptr, and moab::resize_compact_list().

Referenced by moab::MeshSet::insert_entity_ranges().

---

The documentation for this class was generated from the following file:

• MeshSet.cpp