moab
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...

List of all members.

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 41 of file MeshSet.cpp.


Member Function Documentation

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

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines