|
moab
|
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) |
Methods to insert/remove range-based data from contents list. Templatized to operate on both Range and set-based MeshSets.
Definition at line 41 of file MeshSet.cpp.
| 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 | ||
| ) | [inline, static] |
Insert range-based data into range-based MeshSet
Definition at line 411 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.
list_write = std::lower_bound( list_read, list_end, i->first-1, 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;
}
| 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 | ||
| ) | [inline, static] |
Remove range-based data from range-based MeshSet
Definition at line 630 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;
}
| 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 | ||
| ) | [inline, static] |
Insert range-based data into list-based MeshSet
Definition at line 809 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;
}
1.7.6.1