moab
RangeMap.hpp
Go to the documentation of this file.
00001 /*
00002  * MOAB, a Mesh-Oriented datABase, is a software component for creating,
00003  * storing and accessing finite element mesh data.
00004  * 
00005  * Copyright 2004 Sandia Corporation.  Under the terms of Contract
00006  * DE-AC04-94AL85000 with Sandia Coroporation, the U.S. Government
00007  * retains certain rights in this software.
00008  * 
00009  * This library is free software; you can redistribute it and/or
00010  * modify it under the terms of the GNU Lesser General Public
00011  * License as published by the Free Software Foundation; either
00012  * version 2.1 of the License, or (at your option) any later version.
00013  * 
00014  */
00015 
00021 #ifndef MOAB_RANGE_MAP_HPP
00022 #define MOAB_RANGE_MAP_HPP
00023 
00024 #include <vector>
00025 #include <algorithm>
00026 
00027 namespace moab {
00028 
00036 template <typename KeyType, typename ValType, ValType NullVal = 0>
00037 class RangeMap 
00038 {
00039 public:
00040   typedef KeyType key_type;
00041   typedef ValType value_type;
00042 
00043   struct Range {
00044     KeyType begin, count;
00045     ValType value;
00046     bool operator<( const Range& other ) const
00047       { return begin + count <= other.begin; } // equal if overlapping!
00048   };
00049   typedef typename std::vector<Range> RangeList;
00050   typedef typename RangeList::const_iterator iterator;
00051   typedef typename RangeList::const_iterator const_iterator;
00052   
00053   inline bool empty() const
00054     { return data.empty(); }
00055     
00056   inline const Range& back() const
00057     { return data.back(); }
00058   inline const Range& front() const
00059     { return data.front(); }
00060   
00069   inline std::pair<iterator,bool>
00070   insert( KeyType first_key, ValType first_val, KeyType count );
00071   
00080   inline bool merge( const RangeMap<KeyType,ValType,NullVal>& other );
00081   
00083   inline ValType find( KeyType key ) const;
00084   
00086   inline bool find( KeyType key, ValType& val_out ) const;
00087   
00089   inline bool exists( KeyType key ) const;
00090   
00092   inline bool intersects( KeyType start, KeyType count ) const;
00093 
00095   inline iterator erase( KeyType beg, KeyType count );
00096 
00097   inline unsigned num_ranges() const { return data.size(); }
00098   
00099   inline iterator begin() const { return data.begin(); }
00100   inline iterator end() const { return data.end(); }
00101   inline iterator lower_bound( KeyType key ) const 
00102     { 
00103       Range b = { key, 1, NullVal }; 
00104       return std::lower_bound( begin(), end(), b );
00105     }
00106   static inline iterator lower_bound( iterator s, iterator e, KeyType key )
00107     { 
00108       Range b = { key, 1, NullVal }; 
00109       return std::lower_bound( s, e, b );
00110     }
00111   inline iterator upper_bound( KeyType key ) const
00112     { 
00113       Range b = { key, 1, NullVal }; 
00114       return std::upper_bound( begin(), end(), b );
00115     }
00116   static inline iterator upper_bound( iterator s, iterator e, KeyType key )
00117     { 
00118       Range b = { key, 1, NullVal }; 
00119       return std::upper_bound( s, e, b );
00120     }
00121   inline std::pair<iterator,iterator>
00122     equal_range( KeyType key ) const
00123     { 
00124       Range b = { key, 1, NullVal }; 
00125       return std::equal_range( begin(), end(), b );
00126     }
00127     
00128   inline void clear() { data.clear(); }
00129 
00130 protected:
00131   RangeList data;
00132 };
00133 
00134 template <typename KeyType, typename ValType, ValType NullVal> 
00135 inline std::pair<typename RangeMap<KeyType,ValType,NullVal>::iterator,bool>
00136 RangeMap<KeyType,ValType,NullVal>::insert( KeyType first_key, ValType first_val, KeyType count )
00137 {
00138   Range block = { first_key, count, first_val };
00139   typename RangeList::iterator i = std::lower_bound( data.begin(), data.end(), block );
00140   
00141   if (i == data.end()) {
00142     if (i != data.begin()) {
00143       --i;
00144       if (i->begin + i->count == first_key && 
00145           i->value + i->count == first_val) {
00146         i->count += count;
00147         return std::pair<iterator,bool>(i,true);
00148       }
00149     }
00150     data.push_back( block );
00151     return std::pair<iterator,bool>(data.end() - 1,true);
00152   }
00153   
00154   if (i->begin < first_key + count)
00155     return std::pair<iterator,bool>(i,false);
00156   
00157   if (i->begin == first_key + count &&
00158       i->value == first_val + count) {
00159     i->begin = first_key;
00160     i->value = first_val;
00161     i->count += count;
00162     if (i != data.begin()) {
00163       count = i->count;
00164       --i;
00165       if (i->begin + i->count == first_key &&
00166           i->value + i->count == first_val) {
00167         i->count += count;
00168         ++i;
00169         i = data.erase(i);
00170         --i;
00171       }
00172     }
00173     return std::pair<iterator,bool>(i,true);
00174   }
00175   
00176   if (i != data.begin()) {
00177     --i;
00178     if (i->begin + i->count == first_key &&
00179         i->value + i->count == first_val) {
00180       i->count += count;
00181       return std::pair<iterator,bool>(i,true);
00182     }
00183     ++i;
00184   }
00185   
00186   return std::pair<iterator,bool>(data.insert( i, block ),true);
00187 }
00188 
00189 
00190 template <typename KeyType, typename ValType, ValType NullVal>
00191 inline bool
00192 RangeMap<KeyType,ValType,NullVal>::merge( const RangeMap<KeyType,ValType,NullVal>& other )
00193 {
00194     // grow map sufficiently to hold new ranges
00195   RangeList new_data;
00196   new_data.reserve( other.data.size() + data.size() );
00197   
00198     // merge
00199   typename RangeList::const_iterator i = other.data.begin();
00200   typename RangeList::const_iterator j = data.begin();
00201   typename RangeList::const_iterator k;
00202   while (i != other.data.end() || j != data.end()) {
00203     if (j != data.end() && (i == other.data.end() || j->begin < i->begin)) {
00204       k = j; 
00205       ++j;
00206     }
00207     else if (i != other.data.end()) {
00208       k = i; 
00209       ++i;
00210     }
00211       
00212       // check if we need to merge with the end of the previous block
00213     if (new_data.empty()) 
00214       new_data.push_back(*k);
00215     else if (new_data.back().begin + new_data.back().count > k->begin)
00216       return false;
00217     else if (new_data.back().begin + new_data.back().count == k->begin
00218           && new_data.back().value + new_data.back().count == k->value)
00219       new_data.back().count += k->count;
00220     else
00221       new_data.push_back( *k );
00222   }
00223   
00224   data.swap( new_data );
00225   return true;    
00226 }
00227 
00228 template <typename KeyType, typename ValType, ValType NullVal> inline
00229 ValType RangeMap<KeyType,ValType,NullVal>::find( KeyType key ) const
00230 {
00231   Range search = { key, 1, NullVal };
00232   typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
00233   if (i == data.end() || i->begin > key)
00234     return NullVal;
00235   
00236   return i->value + key - i->begin;
00237 }
00238 
00239 template <typename KeyType, typename ValType, ValType NullVal> inline
00240 bool RangeMap<KeyType,ValType,NullVal>::find( KeyType key, ValType& val ) const
00241 {
00242   Range search = { key, 1, NullVal };
00243   typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
00244   if (i == data.end() || i->begin > key) {
00245     val = NullVal;
00246     return false;
00247   }
00248   
00249   val = i->value + key - i->begin;
00250   return true;
00251 }
00252 
00253 template <typename KeyType, typename ValType, ValType NullVal> inline
00254 bool RangeMap<KeyType,ValType,NullVal>::exists( KeyType key ) const
00255 {
00256   Range search = { key, 1, NullVal };
00257   typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
00258   return i != data.end() && key >= i->begin;
00259 }
00260 
00261 template <typename KeyType, typename ValType, ValType NullVal> inline 
00262 bool RangeMap<KeyType,ValType,NullVal>::intersects( KeyType start, KeyType count ) const
00263 {
00264   Range search = { start, count, NullVal };
00265   typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
00266   return i != data.end() && start + count > i->begin && i->begin+i->count > start;
00267 }
00268 
00269 template <typename KeyType, typename ValType, ValType NullVal>
00270 inline typename RangeMap<KeyType,ValType,NullVal>::iterator
00271 RangeMap<KeyType,ValType,NullVal>::erase( KeyType key, KeyType count )
00272 {
00273   Range search = { key, 1, NullVal };
00274   typename RangeList::iterator i, j;
00275   i = std::lower_bound( data.begin(), data.end(), search );
00276   
00277   if (i == data.end())
00278     return i;
00279   
00280   if (key > i->begin) {
00281     KeyType offset = key - i->begin;
00282       // special case - split existing entry
00283     if((offset + count) < i->count) {
00284       Range ins = { i->begin, offset, i->value };
00285       offset += count;
00286       i->begin += offset;
00287       i->value += offset;
00288       i->count -= offset;
00289       return data.insert( i, ins ) + 1;
00290     }
00291       // otherwise remove the latter part of i
00292     i->count = offset;
00293     ++i;
00294   }
00295   
00296     // remove any entries entirely convered by the input range
00297   for (j = i; j != data.end() && (j->begin + j->count) <= (key + count); ++j);
00298   i = data.erase(i,j);
00299   
00300     // remove beginning of last block
00301   if (i != data.end() && (key + count) >= i->begin) {
00302     KeyType offset = key + count - i->begin;
00303     i->begin += offset;
00304     i->value += offset;
00305     i->count -= offset;
00306   }
00307   
00308   return i;
00309 }
00310 
00311 } // namespace moab 
00312 
00313 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines