Mesh Oriented datABase  (version 5.4.1)
Array-based unstructured mesh datastructure
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

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

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

{
    // 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 >
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 687 of file MeshSet.cpp.

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

{
    // 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 886 of file MeshSet.cpp.

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

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

List of all members.


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