Mesh Oriented datABase  (version 5.5.1)
An array-based unstructured mesh library
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< RangeRangeList
 
typedef RangeList::const_iterator iterator
 
typedef RangeList::const_iterator const_iterator
 

Public Member Functions

bool empty () const
 
const Rangeback () const
 
const Rangefront () 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, iteratorequal_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.

63  {
64  return data.back();
65  }

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

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

◆ begin()

◆ clear()

template<typename KeyType , typename ValType , ValType NullVal = 0>
void moab::RangeMap< KeyType, ValType, NullVal >::clear ( )
inline

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

58  {
59  return data.empty();
60  }

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

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

◆ end()

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

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

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.

299 {
300  Range search = { key, 1, NullVal };
301  typename RangeList::iterator i, j;
302  i = std::lower_bound( data.begin(), data.end(), search );
303 
304  if( i == data.end() ) return i;
305 
306  if( key > i->begin )
307  {
308  KeyType offset = key - i->begin;
309  // special case - split existing entry
310  if( ( offset + count ) < i->count )
311  {
312  Range ins = { i->begin, offset, i->value };
313  offset += count;
314  i->begin += offset;
315  i->value += offset;
316  i->count -= offset;
317  return data.insert( i, ins ) + 1;
318  }
319  // otherwise remove the latter part of i
320  i->count = offset;
321  ++i;
322  }
323 
324  // remove any entries entirely convered by the input range
325  for( j = i; j != data.end() && ( j->begin + j->count ) <= ( key + count ); ++j )
326  ;
327  i = data.erase( i, j );
328 
329  // remove beginning of last block
330  if( i != data.end() && ( key + count ) >= i->begin )
331  {
332  KeyType offset = key + count - i->begin;
333  i->begin += offset;
334  i->value += offset;
335  i->count -= offset;
336  }
337 
338  return i;
339 }

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.

281 {
282  Range search = { key, 1, NullVal };
283  typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
284  return i != data.end() && key >= i->begin;
285 }

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.

256 {
257  Range search = { key, 1, NullVal };
258  typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
259  if( i == data.end() || i->begin > key ) return NullVal;
260 
261  return i->value + key - i->begin;
262 }

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.

266 {
267  Range search = { key, 1, NullVal };
268  typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
269  if( i == data.end() || i->begin > key )
270  {
271  val = NullVal;
272  return false;
273  }
274 
275  val = i->value + key - i->begin;
276  return true;
277 }

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

67  {
68  return data.front();
69  }

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.

159 {
160  Range block = { first_key, count, first_val };
161  typename RangeList::iterator i = std::lower_bound( data.begin(), data.end(), block );
162 
163  if( i == data.end() )
164  {
165  if( i != data.begin() )
166  {
167  --i;
168  if( i->begin + i->count == first_key && i->value + i->count == first_val )
169  {
170  i->count += count;
171  return std::pair< iterator, bool >( i, true );
172  }
173  }
174  data.push_back( block );
175  return std::pair< iterator, bool >( data.end() - 1, true );
176  }
177 
178  if( i->begin < first_key + count ) return std::pair< iterator, bool >( i, false );
179 
180  if( i->begin == first_key + count && i->value == first_val + count )
181  {
182  i->begin = first_key;
183  i->value = first_val;
184  i->count += count;
185  if( i != data.begin() )
186  {
187  count = i->count;
188  --i;
189  if( i->begin + i->count == first_key && i->value + i->count == first_val )
190  {
191  i->count += count;
192  ++i;
193  i = data.erase( i );
194  --i;
195  }
196  }
197  return std::pair< iterator, bool >( i, true );
198  }
199 
200  if( i != data.begin() )
201  {
202  --i;
203  if( i->begin + i->count == first_key && i->value + i->count == first_val )
204  {
205  i->count += count;
206  return std::pair< iterator, bool >( i, true );
207  }
208  ++i;
209  }
210 
211  return std::pair< iterator, bool >( data.insert( i, block ), true );
212 }

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.

289 {
290  Range search = { start, count, NullVal };
291  typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
292  return i != data.end() && start + count > i->begin && i->begin + i->count > start;
293 }

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.

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

◆ lower_bound() [2/2]

template<typename KeyType , typename ValType , ValType NullVal = 0>
iterator moab::RangeMap< KeyType, ValType, NullVal >::lower_bound ( KeyType  key) const
inline

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

216 {
217  // grow map sufficiently to hold new ranges
218  RangeList new_data;
219  new_data.reserve( other.data.size() + data.size() );
220 
221  // merge
222  typename RangeList::const_iterator i = other.data.begin();
223  typename RangeList::const_iterator j = data.begin();
224  typename RangeList::const_iterator k;
225  while( i != other.data.end() || j != data.end() )
226  {
227  if( j != data.end() && ( i == other.data.end() || j->begin < i->begin ) )
228  {
229  k = j;
230  ++j;
231  }
232  else if( i != other.data.end() )
233  {
234  k = i;
235  ++i;
236  }
237 
238  // check if we need to merge with the end of the previous block
239  if( new_data.empty() )
240  new_data.push_back( *k );
241  else if( new_data.back().begin + new_data.back().count > k->begin )
242  return false;
243  else if( new_data.back().begin + new_data.back().count == k->begin &&
244  new_data.back().value + new_data.back().count == k->value )
245  new_data.back().count += k->count;
246  else
247  new_data.push_back( *k );
248  }
249 
250  data.swap( new_data );
251  return true;
252 }

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.

107  {
108  return data.size();
109  }

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.

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

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

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

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

Member Data Documentation

◆ data


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