moab::RangeMap< KeyType, ValType, NullVal > Class Template Reference

Map ranges of values. More...

#include <RangeMap.hpp>

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

Collaboration 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. More...
bool	merge (const RangeMap< KeyType, ValType, NullVal > &other)
	Insert mapping between range of keys and range of values. More...
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

const_iterator

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.

iterator

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.

key_type

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.

RangeList

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.

value_type

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

back()

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.

    {
        return data.back();
    }

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

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

begin()

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.

    {
        return data.begin();
    }

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

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< KeyType, ValType, NullVal >::equal_range(), moab::RangeMap< KeyType, ValType, NullVal >::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< KeyType, ValType, NullVal >::upper_bound().

clear()

template<typename KeyType , typename ValType , ValType NullVal = 0>

void moab::RangeMap< KeyType, ValType, NullVal >::clear ( )

inline

Definition at line 145 of file RangeMap.hpp.

    {
        data.clear();
    }

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

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

empty()

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.

    {
        return data.empty();
    }

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

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

end()

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.

    {
        return data.end();
    }

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

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< KeyType, ValType, NullVal >::equal_range(), moab::ReadDamsel::get_contents(), moab::RangeMap< KeyType, ValType, NullVal >::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< KeyType, ValType, NullVal >::upper_bound().

equal_range()

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.

    {
        Range b = { key, 1, NullVal };
        return std::equal_range( begin(), end(), b );
    }

References moab::RangeMap< KeyType, ValType, NullVal >::begin(), and moab::RangeMap< KeyType, ValType, NullVal >::end().

erase()

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.

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

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

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

exists()

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.

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

Referenced by moab::set_map_intersect().

find() [1/2]

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.

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

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().

find() [2/2]

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.

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

front()

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

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

insert()

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.

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

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().

intersects()

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.

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

Referenced by moab::set_map_intersect().

lower_bound() [1/2]

template<typename KeyType , typename ValType , ValType NullVal = 0>

static iterator moab::RangeMap< KeyType, ValType, NullVal >::lower_bound ( iterator  s, iterator  e, KeyType  key  )

inlinestatic

Definition at line 124 of file RangeMap.hpp.

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

lower_bound() [2/2]

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.

    {
        Range b = { key, 1, NullVal };
        return std::lower_bound( begin(), end(), b );
    }

References moab::RangeMap< KeyType, ValType, NullVal >::begin(), and moab::RangeMap< KeyType, ValType, NullVal >::end().

Referenced by moab::ReadHDF5::convert_id_to_handle(), moab::ReadHDF5::convert_range_to_handle(), moab::ReadDamsel::get_contents(), moab::range_to_blocked_list_templ(), moab::range_to_id_list_templ(), and moab::ReadHDF5::read_dense_tag().

merge()

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.

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

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

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

num_ranges()

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

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

upper_bound() [1/2]

template<typename KeyType , typename ValType , ValType NullVal = 0>

static iterator moab::RangeMap< KeyType, ValType, NullVal >::upper_bound ( iterator  s, iterator  e, KeyType  key  )

inlinestatic

Definition at line 134 of file RangeMap.hpp.

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

upper_bound() [2/2]

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.

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

References moab::RangeMap< KeyType, ValType, NullVal >::begin(), and moab::RangeMap< KeyType, ValType, NullVal >::end().

Member Data Documentation

data

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< KeyType, ValType, NullVal >::back(), moab::RangeMap< KeyType, ValType, NullVal >::begin(), moab::RangeMap< KeyType, ValType, NullVal >::clear(), moab::RangeMap< KeyType, ValType, NullVal >::empty(), moab::RangeMap< KeyType, ValType, NullVal >::end(), moab::RangeMap< KeyType, ValType, NullVal >::front(), moab::RangeMap< KeyType, ValType, NullVal >::merge(), and moab::RangeMap< KeyType, ValType, NullVal >::num_ranges().

---

The documentation for this class was generated from the following file:

• RangeMap.hpp