 |
Mesh Oriented datABase
(version 5.5.1)
An array-based unstructured mesh library
|
|
Mesh Oriented datABase
(version 5.5.1)
An array-based unstructured mesh library
|
1 /*
2 * MOAB, a Mesh-Oriented datABase, is a software component for creating,
3 * storing and accessing finite element mesh data.
4 *
5 * Copyright 2004 Sandia Corporation. Under the terms of Contract
6 * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government
7 * retains certain rights in this software.
8 *
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public
11 * License as published by the Free Software Foundation; either
12 * version 2.1 of the License, or (at your option) any later version.
13 *
14 */
15
16 /**\file RangeMap.hpp
17 *\author Jason Kraftcheck (kraftche@cae.wisc.edu)
18 *\date 2007-04-25
19 */
20
21 #ifndef MOAB_RANGE_MAP_HPP
22 #define MOAB_RANGE_MAP_HPP
23
24 #include <vector>
25 #include <algorithm>
26
27 namespace moab
28 {
29
30 /**\brief Map ranges of values
31 *
32 * This class provides a map between ranges of values, such as
33 * a map between file IDs and EntityHandles. It is intended
34 * for use in situations where there are relatively few insertions
35 * of large contiguous ranges of values.
36 */
37 template < typename KeyType, typename ValType, ValType NullVal = 0 >
38 class RangeMap
39 {
40 public:
41 typedef KeyType key_type;
42 typedef ValType value_type;
43
44 struct Range
45 {
46 KeyType begin, count;
47 ValType value;
48 bool operator<( const Range& other ) const
49 {
50 return begin + count <= other.begin;
51 } // equal if overlapping!
52 };
53 typedef typename std::vector< Range > RangeList;
54 typedef typename RangeList::const_iterator iterator;
55 typedef typename RangeList::const_iterator const_iterator;
56
57 inline bool empty() const
58 {
59 return data.empty();
60 }
61
62 inline const Range& back() const
63 {
64 return data.back();
65 }
66 inline const Range& front() const
67 {
68 return data.front();
69 }
70
71 /**\brief Insert mapping between range of keys and range of values
72 *
73 * Insert mapping from [first_key, first_key+count) to [first_val, first_val+count)
74 *
75 * Input range of keys many not overlap any other input range. If it does overlap
76 * an existing range, the second value of the pair will be returned as false
77 * and the iterator will point to (one of) the overlapping ranges.
78 */
79 inline std::pair< iterator, bool > insert( KeyType first_key, ValType first_val, KeyType count );
80
81 /**\brief Insert mapping between range of keys and range of values
82 *
83 * Insert mapping from [first_key, first_key+count) to [first_val, first_val+count)
84 *
85 * Input range of keys many not overlap any other input range. If it does overlap
86 * an existing range, the second value of the pair will be returned as false
87 * and the iterator will point to (one of) the overlapping ranges.
88 */
89 inline bool merge( const RangeMap< KeyType, ValType, NullVal >& other );
90
91 /** Find the value corresponding to the specified key. Returns NullVal if not found */
92 inline ValType find( KeyType key ) const;
93
94 /** Find the value corresponding to the specified key. Returns false if not found */
95 inline bool find( KeyType key, ValType& val_out ) const;
96
97 /** Check if range contains key */
98 inline bool exists( KeyType key ) const;
99
100 /** Check if range contains key */
101 inline bool intersects( KeyType start, KeyType count ) const;
102
103 /** Remove a block of values */
104 inline iterator erase( KeyType beg, KeyType count );
105
106 inline unsigned num_ranges() const
107 {
108 return data.size();
109 }
110
111 inline iterator begin() const
112 {
113 return data.begin();
114 }
115 inline iterator end() const
116 {
117 return data.end();
118 }
119 inline iterator lower_bound( KeyType key ) const
120 {
121 Range b = { key, 1, NullVal };
122 return std::lower_bound( begin(), end(), b );
123 }
124 static inline iterator lower_bound( iterator s, iterator e, KeyType key )
125 {
126 Range b = { key, 1, NullVal };
127 return std::lower_bound( s, e, b );
128 }
129 inline iterator upper_bound( KeyType key ) const
130 {
131 Range b = { key, 1, NullVal };
132 return std::upper_bound( begin(), end(), b );
133 }
134 static inline iterator upper_bound( iterator s, iterator e, KeyType key )
135 {
136 Range b = { key, 1, NullVal };
137 return std::upper_bound( s, e, b );
138 }
139 inline std::pair< iterator, iterator > equal_range( KeyType key ) const
140 {
141 Range b = { key, 1, NullVal };
142 return std::equal_range( begin(), end(), b );
143 }
144
145 inline void clear()
146 {
147 data.clear();
148 }
149
150 protected:
151 RangeList data;
152 };
153
154 template < typename KeyType, typename ValType, ValType NullVal >
155 inline std::pair< typename RangeMap< KeyType, ValType, NullVal >::iterator, bool > RangeMap<
156 KeyType,
157 ValType,
158 NullVal >::insert( KeyType first_key, ValType first_val, KeyType count )
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 }
213
214 template < typename KeyType, typename ValType, ValType NullVal >
215 inline bool RangeMap< KeyType, ValType, NullVal >::merge( const RangeMap< KeyType, ValType, NullVal >& other )
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 }
253
254 template < typename KeyType, typename ValType, ValType NullVal >
255 inline ValType RangeMap< KeyType, ValType, NullVal >::find( KeyType key ) const
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 }
263
264 template < typename KeyType, typename ValType, ValType NullVal >
265 inline bool RangeMap< KeyType, ValType, NullVal >::find( KeyType key, ValType& val ) const
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 }
278
279 template < typename KeyType, typename ValType, ValType NullVal >
280 inline bool RangeMap< KeyType, ValType, NullVal >::exists( KeyType key ) const
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 }
286
287 template < typename KeyType, typename ValType, ValType NullVal >
288 inline bool RangeMap< KeyType, ValType, NullVal >::intersects( KeyType start, KeyType count ) const
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 }
294
295 template < typename KeyType, typename ValType, ValType NullVal >
296 inline typename RangeMap< KeyType, ValType, NullVal >::iterator RangeMap< KeyType, ValType, NullVal >::erase(
297 KeyType key,
298 KeyType count )
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 }
340
341 } // namespace moab
342
343 #endif
1.9.1.