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

    {
        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:

RangeMap.hpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Protected Attributes

Detailed Description

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

Member Typedef Documentation

Member Function Documentation

Member Data Documentation

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