moab
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>

List of all members.

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 37 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 51 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 50 of file RangeMap.hpp.

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

Definition at line 40 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 49 of file RangeMap.hpp.

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

Definition at line 41 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 56 of file RangeMap.hpp.

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

Definition at line 99 of file RangeMap.hpp.

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

Definition at line 128 of file RangeMap.hpp.

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

Definition at line 53 of file RangeMap.hpp.

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

Definition at line 100 of file RangeMap.hpp.

{ 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 122 of file RangeMap.hpp.

    { 
      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 271 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;
}
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 254 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;
}
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 229 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;
}
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 240 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;
}
template<typename KeyType, typename ValType, ValType NullVal = 0>
const Range& moab::RangeMap< KeyType, ValType, NullVal >::front ( ) const [inline]

Definition at line 58 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 136 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);
}
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 262 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;
}
template<typename KeyType, typename ValType, ValType NullVal = 0>
iterator moab::RangeMap< KeyType, ValType, NullVal >::lower_bound ( KeyType  key) const [inline]

Definition at line 101 of file RangeMap.hpp.

    { 
      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 106 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 192 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;    
}
template<typename KeyType, typename ValType, ValType NullVal = 0>
unsigned moab::RangeMap< KeyType, ValType, NullVal >::num_ranges ( ) const [inline]

Definition at line 97 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 111 of file RangeMap.hpp.

    { 
      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 116 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 131 of file RangeMap.hpp.

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