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