Mesh Oriented datABase  (version 5.5.1)
An array-based unstructured mesh library
RangeMap.hpp
Go to the documentation of this file.
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 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