MOAB: Mesh Oriented datABase  (version 5.4.1)
Classes | Public Types | Public Member Functions | Static Public Member Functions | Protected Attributes
moab::RangeMap< KeyType, ValType, NullVal > Class Template Reference

Map ranges of values. More...

#include <RangeMap.hpp>

+ Inheritance diagram for moab::RangeMap< KeyType, ValType, NullVal >:

Classes

struct  Range

Public Types

typedef KeyType key_type
typedef ValType value_type
typedef std::vector< Range > RangeList
typedef RangeList::const_iterator iterator
typedef RangeList::const_iterator const_iterator

Public Member Functions

bool empty () const
const Range & back () const
const Range & front () const
std::pair< iterator, bool > insert (KeyType first_key, ValType first_val, KeyType count)
 Insert mapping between range of keys and range of values.
bool merge (const RangeMap< KeyType, ValType, NullVal > &other)
 Insert mapping between range of keys and range of values.
ValType find (KeyType key) const
bool find (KeyType key, ValType &val_out) const
bool exists (KeyType key) const
bool intersects (KeyType start, KeyType count) const
iterator erase (KeyType beg, KeyType count)
unsigned num_ranges () const
iterator begin () const
iterator end () const
iterator lower_bound (KeyType key) const
iterator upper_bound (KeyType key) const
std::pair< iterator, iterator > equal_range (KeyType key) const
void clear ()

Static Public Member Functions

static iterator lower_bound (iterator s, iterator e, KeyType key)
static iterator upper_bound (iterator s, iterator e, KeyType key)

Protected Attributes

RangeList data

Detailed Description

template<typename KeyType, typename ValType, ValType NullVal = 0>
class moab::RangeMap< KeyType, ValType, NullVal >

Map ranges of values.

This class provides a map between ranges of values, such as a map between file IDs and EntityHandles. It is intended for use in situations where there are relatively few insertions of large contiguous ranges of values.

Definition at line 38 of file RangeMap.hpp.

Member Typedef Documentation

template<typename KeyType, typename ValType, ValType NullVal = 0>
typedef RangeList::const_iterator moab::RangeMap< KeyType, ValType, NullVal >::const_iterator

Definition at line 55 of file RangeMap.hpp.

template<typename KeyType, typename ValType, ValType NullVal = 0>
typedef RangeList::const_iterator moab::RangeMap< KeyType, ValType, NullVal >::iterator

Definition at line 54 of file RangeMap.hpp.

template<typename KeyType, typename ValType, ValType NullVal = 0>
typedef KeyType moab::RangeMap< KeyType, ValType, NullVal >::key_type

Definition at line 41 of file RangeMap.hpp.

template<typename KeyType, typename ValType, ValType NullVal = 0>
typedef std::vector< Range > moab::RangeMap< KeyType, ValType, NullVal >::RangeList

Definition at line 53 of file RangeMap.hpp.

template<typename KeyType, typename ValType, ValType NullVal = 0>
typedef ValType moab::RangeMap< KeyType, ValType, NullVal >::value_type

Definition at line 42 of file RangeMap.hpp.

Member Function Documentation

template<typename KeyType, typename ValType, ValType NullVal = 0>
const Range& moab::RangeMap< KeyType, ValType, NullVal >::back ( ) const [inline]

Definition at line 62 of file RangeMap.hpp.

Referenced by moab::ReadHDF5::insert_in_id_map(), and moab::range_to_blocked_list_templ().

    {
        return data.back();
    }
template<typename KeyType, typename ValType, ValType NullVal = 0>
iterator moab::RangeMap< KeyType, ValType, NullVal >::begin ( ) const [inline]

Definition at line 111 of file RangeMap.hpp.

Referenced by moab::SharedSetData::append_local_handles(), moab::ReadNASTRAN::assign_ids(), moab::ReadHDF5::convert_id_to_handle(), moab::ReadHDF5::convert_range_to_handle(), moab::ReadHDF5::delete_non_side_elements(), moab::RangeMap< damsel_handle, EntityHandle, 0 >::equal_range(), moab::RangeMap< damsel_handle, EntityHandle, 0 >::lower_bound(), moab::WriteHDF5::print_id_map(), moab::range_to_blocked_list_templ(), moab::range_to_id_list_templ(), moab::ReadHDF5::store_file_ids(), moab::ReadHDF5::store_sets_file_ids(), and moab::RangeMap< damsel_handle, EntityHandle, 0 >::upper_bound().

    {
        return data.begin();
    }
template<typename KeyType, typename ValType, ValType NullVal = 0>
void moab::RangeMap< KeyType, ValType, NullVal >::clear ( ) [inline]

Definition at line 145 of file RangeMap.hpp.

Referenced by moab::ReadHDF5::init(), moab::WriteHDF5::init(), moab::ReadNASTRAN::load_file(), and moab::WriteHDF5::write_finished().

    {
        data.clear();
    }
template<typename KeyType, typename ValType, ValType NullVal = 0>
bool moab::RangeMap< KeyType, ValType, NullVal >::empty ( ) const [inline]

Definition at line 57 of file RangeMap.hpp.

Referenced by moab::ReadHDF5::insert_in_id_map(), and moab::set_map_intersect().

    {
        return data.empty();
    }
template<typename KeyType, typename ValType, ValType NullVal = 0>
iterator moab::RangeMap< KeyType, ValType, NullVal >::end ( ) const [inline]

Definition at line 115 of file RangeMap.hpp.

Referenced by moab::SharedSetData::append_local_handles(), moab::ReadNASTRAN::assign_ids(), moab::ReadHDF5::convert_id_to_handle(), moab::ReadHDF5::convert_range_to_handle(), moab::ReadHDF5::delete_non_side_elements(), moab::RangeMap< damsel_handle, EntityHandle, 0 >::equal_range(), moab::ReadDamsel::get_contents(), moab::RangeMap< damsel_handle, EntityHandle, 0 >::lower_bound(), moab::WriteHDF5::print_id_map(), moab::range_to_blocked_list_templ(), moab::range_to_id_list_templ(), moab::ReadHDF5::read_dense_tag(), moab::ReadHDF5::store_file_ids(), moab::ReadHDF5::store_sets_file_ids(), and moab::RangeMap< damsel_handle, EntityHandle, 0 >::upper_bound().

    {
        return data.end();
    }
template<typename KeyType, typename ValType, ValType NullVal = 0>
std::pair< iterator, iterator > moab::RangeMap< KeyType, ValType, NullVal >::equal_range ( KeyType  key) const [inline]

Definition at line 139 of file RangeMap.hpp.

Referenced by moab::RangeMap< damsel_handle, EntityHandle, 0 >::equal_range().

    {
        Range b = { key, 1, NullVal };
        return std::equal_range( begin(), end(), b );
    }
template<typename KeyType, typename ValType , ValType NullVal>
RangeMap< KeyType, ValType, NullVal >::iterator moab::RangeMap< KeyType, ValType, NullVal >::erase ( KeyType  beg,
KeyType  count 
) [inline]

Remove a block of values

Definition at line 296 of file RangeMap.hpp.

References moab::RangeMap< KeyType, ValType, NullVal >::Range::begin.

Referenced by moab::ReadHDF5::delete_non_side_elements().

{
    Range search = { key, 1, NullVal };
    typename RangeList::iterator i, j;
    i = std::lower_bound( data.begin(), data.end(), search );

    if( i == data.end() ) return i;

    if( key > i->begin )
    {
        KeyType offset = key - i->begin;
        // special case - split existing entry
        if( ( offset + count ) < i->count )
        {
            Range ins = { i->begin, offset, i->value };
            offset += count;
            i->begin += offset;
            i->value += offset;
            i->count -= offset;
            return data.insert( i, ins ) + 1;
        }
        // otherwise remove the latter part of i
        i->count = offset;
        ++i;
    }

    // remove any entries entirely convered by the input range
    for( j = i; j != data.end() && ( j->begin + j->count ) <= ( key + count ); ++j )
        ;
    i = data.erase( i, j );

    // remove beginning of last block
    if( i != data.end() && ( key + count ) >= i->begin )
    {
        KeyType offset = key + count - i->begin;
        i->begin += offset;
        i->value += offset;
        i->count -= offset;
    }

    return i;
}
template<typename KeyType, typename ValType , ValType NullVal>
bool moab::RangeMap< KeyType, ValType, NullVal >::exists ( KeyType  key) const [inline]

Check if range contains key

Definition at line 280 of file RangeMap.hpp.

References moab::RangeMap< KeyType, ValType, NullVal >::Range::begin.

Referenced by moab::set_map_intersect().

{
    Range search                         = { key, 1, NullVal };
    typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
    return i != data.end() && key >= i->begin;
}
template<typename KeyType, typename ValType , ValType NullVal>
ValType moab::RangeMap< KeyType, ValType, NullVal >::find ( KeyType  key) const [inline]

Find the value corresponding to the specified key. Returns NullVal if not found

Definition at line 255 of file RangeMap.hpp.

References moab::RangeMap< KeyType, ValType, NullVal >::Range::value.

Referenced by moab::WriteHDF5Parallel::communicate_shared_set_ids(), moab::WriteHDF5::convert_handle_tag(), moab::ReadHDF5::convert_id_to_handle(), moab::WriteHDF5Parallel::exchange_file_ids(), moab::WriteHDF5::get_adjacencies(), moab::ReadDamsel::get_contents(), moab::WriteHDF5Parallel::print_set_sharing_data(), moab::ReadHDF5::read_adjacencies(), moab::ReadNASTRAN::read_element(), moab::ReadHDF5::read_node_adj_elems(), moab::WriteHDF5::vector_to_id_list(), moab::WriteHDF5::write_adjacencies(), and moab::WriteHDF5::write_elems().

{
    Range search                         = { key, 1, NullVal };
    typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
    if( i == data.end() || i->begin > key ) return NullVal;

    return i->value + key - i->begin;
}
template<typename KeyType, typename ValType, ValType NullVal>
bool moab::RangeMap< KeyType, ValType, NullVal >::find ( KeyType  key,
ValType &  val_out 
) const [inline]

Find the value corresponding to the specified key. Returns false if not found

Definition at line 265 of file RangeMap.hpp.

References moab::RangeMap< KeyType, ValType, NullVal >::Range::value.

{
    Range search                         = { key, 1, NullVal };
    typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
    if( i == data.end() || i->begin > key )
    {
        val = NullVal;
        return false;
    }

    val = i->value + key - i->begin;
    return true;
}
template<typename KeyType, typename ValType, ValType NullVal = 0>
const Range& moab::RangeMap< KeyType, ValType, NullVal >::front ( ) const [inline]

Definition at line 66 of file RangeMap.hpp.

    {
        return data.front();
    }
template<typename KeyType, typename ValType, ValType NullVal>
std::pair< typename RangeMap< KeyType, ValType, NullVal >::iterator, bool > moab::RangeMap< KeyType, ValType, NullVal >::insert ( KeyType  first_key,
ValType  first_val,
KeyType  count 
) [inline]

Insert mapping between range of keys and range of values.

Insert mapping from [first_key, first_key+count) to [first_val, first_val+count)

Input range of keys many not overlap any other input range. If it does overlap an existing range, the second value of the pair will be returned as false and the iterator will point to (one of) the overlapping ranges.

Definition at line 158 of file RangeMap.hpp.

References moab::RangeMap< KeyType, ValType, NullVal >::Range::count.

Referenced by moab::WriteHDF5::assign_ids(), moab::WriteHDF5Parallel::communicate_shared_set_ids(), moab::WriteHDF5Parallel::exchange_file_ids(), moab::ReadHDF5::insert_in_id_map(), moab::ReadNASTRAN::load_file(), moab::ParallelComm::pack_range_map(), moab::ReadDamsel::process_ent_info(), moab::ReadNASTRAN::read_element(), and moab::ReadHDF5::read_node_adj_elems().

{
    Range block                    = { first_key, count, first_val };
    typename RangeList::iterator i = std::lower_bound( data.begin(), data.end(), block );

    if( i == data.end() )
    {
        if( i != data.begin() )
        {
            --i;
            if( i->begin + i->count == first_key && i->value + i->count == first_val )
            {
                i->count += count;
                return std::pair< iterator, bool >( i, true );
            }
        }
        data.push_back( block );
        return std::pair< iterator, bool >( data.end() - 1, true );
    }

    if( i->begin < first_key + count ) return std::pair< iterator, bool >( i, false );

    if( i->begin == first_key + count && i->value == first_val + count )
    {
        i->begin = first_key;
        i->value = first_val;
        i->count += count;
        if( i != data.begin() )
        {
            count = i->count;
            --i;
            if( i->begin + i->count == first_key && i->value + i->count == first_val )
            {
                i->count += count;
                ++i;
                i = data.erase( i );
                --i;
            }
        }
        return std::pair< iterator, bool >( i, true );
    }

    if( i != data.begin() )
    {
        --i;
        if( i->begin + i->count == first_key && i->value + i->count == first_val )
        {
            i->count += count;
            return std::pair< iterator, bool >( i, true );
        }
        ++i;
    }

    return std::pair< iterator, bool >( data.insert( i, block ), true );
}
template<typename KeyType, typename ValType , ValType NullVal>
bool moab::RangeMap< KeyType, ValType, NullVal >::intersects ( KeyType  start,
KeyType  count 
) const [inline]

Check if range contains key

Definition at line 288 of file RangeMap.hpp.

References moab::RangeMap< KeyType, ValType, NullVal >::Range::begin.

Referenced by moab::set_map_intersect().

{
    Range search                         = { start, count, NullVal };
    typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
    return i != data.end() && start + count > i->begin && i->begin + i->count > start;
}
template<typename KeyType, typename ValType, ValType NullVal = 0>
iterator moab::RangeMap< KeyType, ValType, NullVal >::lower_bound ( KeyType  key) const [inline]

Definition at line 119 of file RangeMap.hpp.

Referenced by moab::ReadHDF5::convert_id_to_handle(), moab::ReadHDF5::convert_range_to_handle(), moab::ReadDamsel::get_contents(), moab::RangeMap< damsel_handle, EntityHandle, 0 >::lower_bound(), moab::range_to_blocked_list_templ(), moab::range_to_id_list_templ(), and moab::ReadHDF5::read_dense_tag().

    {
        Range b = { key, 1, NullVal };
        return std::lower_bound( begin(), end(), b );
    }
template<typename KeyType, typename ValType, ValType NullVal = 0>
static iterator moab::RangeMap< KeyType, ValType, NullVal >::lower_bound ( iterator  s,
iterator  e,
KeyType  key 
) [inline, static]

Definition at line 124 of file RangeMap.hpp.

    {
        Range b = { key, 1, NullVal };
        return std::lower_bound( s, e, b );
    }
template<typename KeyType, typename ValType, ValType NullVal>
bool moab::RangeMap< KeyType, ValType, NullVal >::merge ( const RangeMap< KeyType, ValType, NullVal > &  other) [inline]

Insert mapping between range of keys and range of values.

Insert mapping from [first_key, first_key+count) to [first_val, first_val+count)

Input range of keys many not overlap any other input range. If it does overlap an existing range, the second value of the pair will be returned as false and the iterator will point to (one of) the overlapping ranges.

Definition at line 215 of file RangeMap.hpp.

References moab::RangeMap< KeyType, ValType, NullVal >::data.

Referenced by moab::ReadHDF5::insert_in_id_map().

{
    // grow map sufficiently to hold new ranges
    RangeList new_data;
    new_data.reserve( other.data.size() + data.size() );

    // merge
    typename RangeList::const_iterator i = other.data.begin();
    typename RangeList::const_iterator j = data.begin();
    typename RangeList::const_iterator k;
    while( i != other.data.end() || j != data.end() )
    {
        if( j != data.end() && ( i == other.data.end() || j->begin < i->begin ) )
        {
            k = j;
            ++j;
        }
        else if( i != other.data.end() )
        {
            k = i;
            ++i;
        }

        // check if we need to merge with the end of the previous block
        if( new_data.empty() )
            new_data.push_back( *k );
        else if( new_data.back().begin + new_data.back().count > k->begin )
            return false;
        else if( new_data.back().begin + new_data.back().count == k->begin &&
                 new_data.back().value + new_data.back().count == k->value )
            new_data.back().count += k->count;
        else
            new_data.push_back( *k );
    }

    data.swap( new_data );
    return true;
}
template<typename KeyType, typename ValType, ValType NullVal = 0>
unsigned moab::RangeMap< KeyType, ValType, NullVal >::num_ranges ( ) const [inline]

Definition at line 106 of file RangeMap.hpp.

    {
        return data.size();
    }
template<typename KeyType, typename ValType, ValType NullVal = 0>
iterator moab::RangeMap< KeyType, ValType, NullVal >::upper_bound ( KeyType  key) const [inline]

Definition at line 129 of file RangeMap.hpp.

Referenced by moab::RangeMap< damsel_handle, EntityHandle, 0 >::upper_bound().

    {
        Range b = { key, 1, NullVal };
        return std::upper_bound( begin(), end(), b );
    }
template<typename KeyType, typename ValType, ValType NullVal = 0>
static iterator moab::RangeMap< KeyType, ValType, NullVal >::upper_bound ( iterator  s,
iterator  e,
KeyType  key 
) [inline, static]

Definition at line 134 of file RangeMap.hpp.

    {
        Range b = { key, 1, NullVal };
        return std::upper_bound( s, e, b );
    }

Member Data Documentation

template<typename KeyType, typename ValType, ValType NullVal = 0>
RangeList moab::RangeMap< KeyType, ValType, NullVal >::data [protected]

Definition at line 151 of file RangeMap.hpp.

Referenced by moab::RangeMap< damsel_handle, EntityHandle, 0 >::back(), moab::RangeMap< damsel_handle, EntityHandle, 0 >::begin(), moab::RangeMap< damsel_handle, EntityHandle, 0 >::clear(), moab::RangeMap< damsel_handle, EntityHandle, 0 >::empty(), moab::RangeMap< damsel_handle, EntityHandle, 0 >::end(), moab::RangeMap< damsel_handle, EntityHandle, 0 >::front(), moab::RangeMap< KeyType, ValType, NullVal >::merge(), and moab::RangeMap< damsel_handle, EntityHandle, 0 >::num_ranges().

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