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