Branch data Line data Source code
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 ([email protected])
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 : 1388 : 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 : 1352549 : bool operator<( const Range& other ) const
49 : : {
50 : 1352549 : 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 : 236 : inline bool empty() const
58 : : {
59 : 236 : return data.empty();
60 : : }
61 : :
62 : 170 : inline const Range& back() const
63 : : {
64 : 170 : 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 : 9378 : inline iterator begin() const
112 : : {
113 : 9378 : return data.begin();
114 : : }
115 : 31720 : inline iterator end() const
116 : : {
117 : 31720 : return data.end();
118 : : }
119 : 8396 : inline iterator lower_bound( KeyType key ) const
120 : : {
121 : 8396 : Range b = { key, 1, NullVal };
122 [ + - ][ + - ]: 8396 : return std::lower_bound( begin(), end(), b );
[ + - ]
123 : : }
124 : 7172 : static inline iterator lower_bound( iterator s, iterator e, KeyType key )
125 : : {
126 : 7172 : Range b = { key, 1, NullVal };
127 [ + - ]: 7172 : 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 : 149 : inline void clear()
146 : : {
147 : 149 : data.clear();
148 : 149 : }
149 : :
150 : : protected:
151 : : RangeList data;
152 : : };
153 : :
154 : : template < typename KeyType, typename ValType, ValType NullVal >
155 : 3114 : inline std::pair< typename RangeMap< KeyType, ValType, NullVal >::iterator, bool > RangeMap<
156 : : KeyType, ValType, NullVal >::insert( KeyType first_key, ValType first_val, KeyType count )
157 : : {
158 : 3114 : Range block = { first_key, count, first_val };
159 [ + - ]: 3114 : typename RangeList::iterator i = std::lower_bound( data.begin(), data.end(), block );
160 : :
161 [ + - ][ + + ]: 3114 : if( i == data.end() )
162 : : {
163 [ + - ][ + + ]: 3112 : if( i != data.begin() )
164 : : {
165 [ + - ]: 3004 : --i;
166 [ + - ][ + - ]: 3004 : if( i->begin + i->count == first_key && i->value + i->count == first_val )
[ + + ][ + - ]
[ + - ][ - + ]
[ - + ]
167 : : {
168 [ # # ]: 0 : i->count += count;
169 [ # # ]: 0 : return std::pair< iterator, bool >( i, true );
170 : : }
171 : : }
172 [ + - ]: 3112 : data.push_back( block );
173 [ + - ][ + - ]: 3112 : return std::pair< iterator, bool >( data.end() - 1, true );
174 : : }
175 : :
176 [ + - ][ - + ]: 2 : if( i->begin < first_key + count ) return std::pair< iterator, bool >( i, false );
[ # # ]
177 : :
178 [ + - ][ - + ]: 2 : if( i->begin == first_key + count && i->value == first_val + count )
[ # # ][ # # ]
[ - + ]
179 : : {
180 [ # # ]: 0 : i->begin = first_key;
181 [ # # ]: 0 : i->value = first_val;
182 [ # # ]: 0 : i->count += count;
183 [ # # ][ # # ]: 0 : if( i != data.begin() )
184 : : {
185 [ # # ]: 0 : count = i->count;
186 [ # # ]: 0 : --i;
187 [ # # ][ # # ]: 0 : if( i->begin + i->count == first_key && i->value + i->count == first_val )
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ]
188 : : {
189 [ # # ]: 0 : i->count += count;
190 [ # # ]: 0 : ++i;
191 [ # # ]: 0 : i = data.erase( i );
192 [ # # ]: 0 : --i;
193 : : }
194 : : }
195 [ # # ]: 0 : return std::pair< iterator, bool >( i, true );
196 : : }
197 : :
198 [ + - ][ + - ]: 2 : if( i != data.begin() )
199 : : {
200 [ + - ]: 2 : --i;
201 [ + - ][ + - ]: 2 : if( i->begin + i->count == first_key && i->value + i->count == first_val )
[ - + ][ # # ]
[ # # ][ # # ]
[ - + ]
202 : : {
203 [ # # ]: 0 : i->count += count;
204 [ # # ]: 0 : return std::pair< iterator, bool >( i, true );
205 : : }
206 [ + - ]: 2 : ++i;
207 : : }
208 : :
209 [ + - ][ + - ]: 3114 : return std::pair< iterator, bool >( data.insert( i, block ), true );
210 : : }
211 : :
212 : : template < typename KeyType, typename ValType, ValType NullVal >
213 : 3 : inline bool RangeMap< KeyType, ValType, NullVal >::merge( const RangeMap< KeyType, ValType, NullVal >& other )
214 : : {
215 : : // grow map sufficiently to hold new ranges
216 [ + - ]: 3 : RangeList new_data;
217 [ + - ]: 3 : new_data.reserve( other.data.size() + data.size() );
218 : :
219 : : // merge
220 : 3 : typename RangeList::const_iterator i = other.data.begin();
221 [ + - ]: 3 : typename RangeList::const_iterator j = data.begin();
222 : 3 : typename RangeList::const_iterator k;
223 [ + - ][ + + ]: 14 : while( i != other.data.end() || j != data.end() )
[ + - ][ + + ]
[ + + ][ + - ]
[ + + # #
# # ]
224 : : {
225 [ + - ][ + - ]: 11 : if( j != data.end() && ( i == other.data.end() || j->begin < i->begin ) )
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + +
# # # # ]
226 : : {
227 : 8 : k = j;
228 [ + - ]: 8 : ++j;
229 : : }
230 [ + - ][ + - ]: 3 : else if( i != other.data.end() )
231 : : {
232 : 3 : k = i;
233 [ + - ]: 3 : ++i;
234 : : }
235 : :
236 : : // check if we need to merge with the end of the previous block
237 [ + + ]: 11 : if( new_data.empty() )
238 [ + - ][ + - ]: 3 : new_data.push_back( *k );
239 [ + - ][ + - ]: 8 : else if( new_data.back().begin + new_data.back().count > k->begin )
[ + - ][ - + ]
240 : 0 : return false;
241 [ + - ][ + - ]: 16 : else if( new_data.back().begin + new_data.back().count == k->begin &&
[ + - ][ + - ]
[ - + ][ - + ]
242 [ + - ][ + - ]: 8 : new_data.back().value + new_data.back().count == k->value )
[ + - ]
243 [ # # ][ # # ]: 0 : new_data.back().count += k->count;
244 : : else
245 [ + - ][ + - ]: 8 : new_data.push_back( *k );
246 : : }
247 : :
248 : 3 : data.swap( new_data );
249 : 3 : return true;
250 : : }
251 : :
252 : : template < typename KeyType, typename ValType, ValType NullVal >
253 : 306547 : inline ValType RangeMap< KeyType, ValType, NullVal >::find( KeyType key ) const
254 : : {
255 : 306547 : Range search = { key, 1, NullVal };
256 [ + - ]: 306547 : typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
257 [ + - ][ + + ]: 306547 : if( i == data.end() || i->begin > key ) return NullVal;
[ + - ][ + + ]
[ + - ][ + + ]
[ # # ]
258 : :
259 [ + - ][ + - ]: 306547 : return i->value + key - i->begin;
260 : : }
261 : :
262 : : template < typename KeyType, typename ValType, ValType NullVal >
263 : 0 : inline bool RangeMap< KeyType, ValType, NullVal >::find( KeyType key, ValType& val ) const
264 : : {
265 : 0 : Range search = { key, 1, NullVal };
266 [ # # ]: 0 : typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
267 [ # # ][ # # ]: 0 : if( i == data.end() || i->begin > key )
[ # # ][ # # ]
[ # # ]
[ # # # # ]
268 : : {
269 : 0 : val = NullVal;
270 : 0 : return false;
271 : : }
272 : :
273 [ # # ][ # # ]: 0 : val = i->value + key - i->begin;
274 : 0 : return true;
275 : : }
276 : :
277 : : template < typename KeyType, typename ValType, ValType NullVal >
278 : 0 : inline bool RangeMap< KeyType, ValType, NullVal >::exists( KeyType key ) const
279 : : {
280 : 0 : Range search = { key, 1, NullVal };
281 [ # # ]: 0 : typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
282 [ # # ][ # # ]: 0 : return i != data.end() && key >= i->begin;
[ # # ][ # # ]
[ # # ][ # # ]
283 : : }
284 : :
285 : : template < typename KeyType, typename ValType, ValType NullVal >
286 : 0 : inline bool RangeMap< KeyType, ValType, NullVal >::intersects( KeyType start, KeyType count ) const
287 : : {
288 : 0 : Range search = { start, count, NullVal };
289 [ # # ]: 0 : typename RangeList::const_iterator i = std::lower_bound( data.begin(), data.end(), search );
290 [ # # ][ # # ]: 0 : return i != data.end() && start + count > i->begin && i->begin + i->count > start;
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ]
291 : : }
292 : :
293 : : template < typename KeyType, typename ValType, ValType NullVal >
294 : 0 : inline typename RangeMap< KeyType, ValType, NullVal >::iterator RangeMap< KeyType, ValType, NullVal >::erase(
295 : : KeyType key, KeyType count )
296 : : {
297 : 0 : Range search = { key, 1, NullVal };
298 : 0 : typename RangeList::iterator i, j;
299 [ # # ]: 0 : i = std::lower_bound( data.begin(), data.end(), search );
300 : :
301 [ # # ][ # # ]: 0 : if( i == data.end() ) return i;
[ # # ]
302 : :
303 [ # # ][ # # ]: 0 : if( key > i->begin )
304 : : {
305 [ # # ]: 0 : KeyType offset = key - i->begin;
306 : : // special case - split existing entry
307 [ # # ][ # # ]: 0 : if( ( offset + count ) < i->count )
308 : : {
309 [ # # ][ # # ]: 0 : Range ins = { i->begin, offset, i->value };
310 : 0 : offset += count;
311 [ # # ]: 0 : i->begin += offset;
312 [ # # ]: 0 : i->value += offset;
313 [ # # ]: 0 : i->count -= offset;
314 [ # # ][ # # ]: 0 : return data.insert( i, ins ) + 1;
[ # # ]
315 : : }
316 : : // otherwise remove the latter part of i
317 [ # # ]: 0 : i->count = offset;
318 [ # # ]: 0 : ++i;
319 : : }
320 : :
321 : : // remove any entries entirely convered by the input range
322 [ # # ][ # # ]: 0 : for( j = i; j != data.end() && ( j->begin + j->count ) <= ( key + count ); ++j )
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ]
[ # # # # ]
323 : : ;
324 [ # # ]: 0 : i = data.erase( i, j );
325 : :
326 : : // remove beginning of last block
327 [ # # ][ # # ]: 0 : if( i != data.end() && ( key + count ) >= i->begin )
[ # # ][ # # ]
[ # # ]
[ # # # # ]
328 : : {
329 [ # # ]: 0 : KeyType offset = key + count - i->begin;
330 [ # # ]: 0 : i->begin += offset;
331 [ # # ]: 0 : i->value += offset;
332 [ # # ]: 0 : i->count -= offset;
333 : : }
334 : :
335 [ # # ]: 0 : return i;
336 : : }
337 : :
338 : : } // namespace moab
339 : :
340 : : #endif
|
