Sierra Toolkit  Version of the Day
VecMap.hpp
Go to the documentation of this file.
1 /*--------------------------------------------------------------------*/
2 /* Copyright 2002 Sandia Corporation. */
3 /* Under the terms of Contract DE-AC04-94AL85000, there is a */
4 /* non-exclusive license for use of this work by or on behalf */
5 /* of the U.S. Government. Export of this program may require */
6 /* a license from the United States Government. */
7 /*--------------------------------------------------------------------*/
14 #ifndef STK_UTIL_UTIL_vecmap_hpp
15 #define STK_UTIL_UTIL_vecmap_hpp
16 
17 #include <utility>
18 #include <functional>
19 #include <vector>
20 #include <algorithm>
21 
22 namespace sierra {
23 
59 template <class Key, class T, class Compare = std::less<Key> >
60 class vecmap {
61 public:
62  typedef Key key_type ;
63  typedef T mapped_type ;
64  typedef Compare key_compare ;
65 
66 private: // Hidden storage type
67  typedef std::vector< std::pair<const key_type,mapped_type> > storage ;
68 
69 public:
70  typedef typename storage::value_type value_type ;
71  typedef typename storage::allocator_type allocator_type ;
72  typedef typename allocator_type::reference reference ;
73  typedef typename allocator_type::const_reference const_reference ;
74  typedef typename allocator_type::pointer pointer ;
75  typedef typename allocator_type::const_pointer const_pointer ;
76  typedef typename storage::size_type size_type ;
77  typedef typename storage::difference_type difference_type ;
78  typedef typename storage::iterator iterator ;
79  typedef typename storage::const_iterator const_iterator ;
80  typedef typename storage::reverse_iterator reverse_iterator ;
81  typedef typename storage::const_reverse_iterator const_reverse_iterator ;
82 
83  typedef std::pair<key_type,mapped_type> value_type_unconst_key ;
84 
85 private: // key compare functors
86  class value_compare
87  : public std::binary_function<value_type,value_type,bool> {
88  private:
89  key_compare comp ;
90  public:
91  bool operator ()( const value_type & RHS , const value_type & LHS ) const
92  { return comp( RHS.first , LHS.first ); }
93  };
94 
95  class value_compare_key
96  : public std::binary_function<value_type,key_type,bool> {
97  private:
98  key_compare comp ;
99  public:
100  bool operator()( const value_type & RHS , const key_type & LHS ) const
101  { return comp( RHS.first , LHS ); }
102  };
103 
104  class value_compare_unconst_key
105  : public std::binary_function<value_type_unconst_key,key_type,bool> {
106  private:
107  key_compare comp ;
108  public:
109  bool operator()( const value_type_unconst_key & RHS , const key_type & LHS ) const
110  { return comp( RHS.first , LHS ); }
111  };
112 
113 private: // Object data
114  std::vector<value_type_unconst_key> Storage;
115  value_compare ValueComp ;
116  value_compare_key ValueKeyComp ;
117  value_compare_unconst_key UnconstValueKeyComp ;
118  key_compare KeyComp ;
119 
120 private:
121  storage & pub() {
122  char &i = reinterpret_cast<char&>(Storage);
123  return reinterpret_cast<storage&>(i);
124  }
125 
126  const storage & pub() const {
127  const char &i = reinterpret_cast<const char&>(Storage);
128  return reinterpret_cast<const storage&>(i);
129  }
130 
131  typedef typename std::vector<value_type_unconst_key>::iterator iterator_private ;
132 
133  static iterator_private & castit( iterator & i )
134  { return reinterpret_cast<iterator_private &>(i); }
135 
136  static iterator & castit( iterator_private & i )
137  { return reinterpret_cast<iterator &>(i); }
138 
139 public:
140  ~vecmap() {}
141 
142  vecmap() : Storage() {}
143 
144  vecmap( const vecmap<Key,T,Compare> & rhs ) : Storage(rhs.Storage) {}
145 
146  vecmap<Key,T,Compare> & operator = ( const vecmap<Key,T,Compare> & rhs ) {
147  Storage = rhs.Storage ;
148  return *this ;
149  }
150 
151  void swap( vecmap<Key,T,Compare> & v ) {
152  Storage.swap( v.Storage );
153  }
154 
155  iterator begin() { return pub().begin(); }
156  iterator end() { return pub().end(); }
157  const_iterator begin() const { return pub().begin(); }
158  const_iterator end() const { return pub().end(); }
159  reverse_iterator rbegin() { return pub().rbegin(); }
160  reverse_iterator rend() { return pub().rend(); }
161  const_reverse_iterator rbegin() const { return pub().rbegin(); }
162  const_reverse_iterator rend() const { return pub().rend(); }
163  bool empty() const { return Storage.empty(); }
164  size_type size() const { return Storage.size(); }
165  size_type max_size() const { return Storage.max_size(); }
166 
167 
168  typename std::vector<value_type_unconst_key>::iterator lower_bound_private_comp_( const key_type & k ) {
169  typename std::vector<value_type_unconst_key>::iterator __first = Storage.begin();
170  typename std::vector<value_type_unconst_key>::iterator __last = Storage.end();
171 
172 // difference_type __len = std::distance(__first, __last);
173  difference_type __len = __last - __first;
174  difference_type __half;
175  typename std::vector<value_type_unconst_key>::iterator __middle;
176 
177  while (__len > 0) {
178  __half = __len >> 1;
179  __middle = __first;
180 // std::advance(__middle, __half);
181  __middle += __half;
182  if (UnconstValueKeyComp(*__middle, k)) {
183  __first = __middle;
184  ++__first;
185  __len = __len - __half - 1;
186  }
187  else
188  __len = __half;
189  }
190  return __first;
191  }
192 
193  std::pair<iterator,bool> insert( const value_type & v ) {
194  typename std::vector<value_type_unconst_key>::iterator ip =
195  lower_bound_private_comp_(v.first);
196  // (ip-1)->first < v.first <= ip->first
197  const bool b = Storage.end() == ip || KeyComp( v.first , ip->first );
198  // b = v.first != ip->first
199  if ( b ) ip = Storage.insert(ip,value_type_unconst_key(v.first,v.second));
200  return std::pair<iterator,bool>( castit(ip), b );
201  }
202 
203  mapped_type & operator[]( const key_type & k ) {
204  typename std::vector<value_type_unconst_key>::iterator ip =
205  lower_bound_private_comp_(k);
206 
207  // (ip-1)->first < k <= ip->first
208  if ( Storage.end() == ip || KeyComp(k,ip->first) ) {
209  // k != ip->first => insert
210  ( ip = Storage.insert(ip,value_type_unconst_key()) )->first = k ;
211  }
212  return ip->second ;
213  }
214 
215  void erase( iterator i ) {
216  Storage.erase( castit(i) );
217  }
218 
219  void erase( iterator first , iterator last ) {
220  Storage.erase( castit(first), castit(last) );
221  }
222 
223  size_type erase( const key_type & k ) {
224  const typename std::vector<value_type_unconst_key>::iterator i =
225  lower_bound_private_comp_(k);
226  return KeyComp( k , i->first ) ? 0 : ( Storage.erase(i) , 1 );
227  }
228 
229  void clear() {
230  Storage.clear();
231  }
232 
233  key_compare key_comp() const { return KeyComp ; }
234 
235  value_compare value_comp() const { return ValueComp ; }
236 
237  iterator lower_bound( const key_type & k ) {
238  iterator __first = begin();
239  iterator __last = end();
240 
241 // difference_type __len = std::distance(__first, __last);
242  difference_type __len = __last - __first;
243  difference_type __half;
244  iterator __middle;
245 
246  while (__len > 0) {
247  __half = __len >> 1;
248  __middle = __first;
249 // std::advance(__middle, __half);
250  __middle += __half;
251  if (ValueKeyComp(*__middle, k)) {
252  __first = __middle;
253  ++__first;
254  __len = __len - __half - 1;
255  }
256  else
257  __len = __half;
258  }
259  return __first;
260  }
261 
262  const_iterator lower_bound( const key_type & k ) const {
263  const_iterator __first = begin();
264  const_iterator __last = end();
265 
266 // difference_type __len = std::distance(__first, __last);
267  difference_type __len = __last - __first;
268  difference_type __half;
269  const_iterator __middle;
270 
271  while (__len > 0) {
272  __half = __len >> 1;
273  __middle = __first;
274 // std::advance(__middle, __half);
275  __middle += __half;
276  if (ValueKeyComp(*__middle, k)) {
277  __first = __middle;
278  ++__first;
279  __len = __len - __half - 1;
280  }
281  else
282  __len = __half;
283  }
284  return __first;
285  }
286 
287  iterator upper_bound( const key_type & k ) {
288  iterator __first = begin();
289  iterator __last = end();
290 
291 // difference_type __len = std::distance(__first, __last);
292  difference_type __len = __last - __first;
293  difference_type __half;
294  iterator __middle;
295 
296  while (__len > 0) {
297  __half = __len >> 1;
298  __middle = __first;
299 // std::advance(__middle, __half);
300  __middle += __half;
301  if (__comp(k, *__middle))
302  __len = __half;
303  else {
304  __first = __middle;
305  ++__first;
306  __len = __len - __half - 1;
307  }
308  }
309  return __first;
310  }
311 
312 
313  const_iterator upper_bound( const key_type & k ) const {
314  const_iterator __first = begin();
315  const_iterator __last = end();
316 
317 // difference_type __len = std::distance(__first, __last);
318  difference_type __len = __last - __first;
319  difference_type __half;
320  const_iterator __middle;
321 
322  while (__len > 0) {
323  __half = __len >> 1;
324  __middle = __first;
325 // std::advance(__middle, __half);
326  __middle += __half;
327  if (__comp(k, *__middle))
328  __len = __half;
329  else {
330  __first = __middle;
331  ++__first;
332  __len = __len - __half - 1;
333  }
334  }
335  return __first;
336  }
337 
338 
339  iterator find( const key_type & k ) {
340  const iterator i = lower_bound(k);
341  return end() == i || KeyComp( k , i->first ) ? end() : i ;
342  }
343 
344  const_iterator find( const key_type & k ) const {
345  const const_iterator i = lower_bound(k);
346  return end() == i || KeyComp( k , i->first ) ? end() : i ;
347  }
348 
349  size_type count( const key_type & k ) const {
350  const const_iterator i = lower_bound(k);
351  return end() == i || KeyComp( k , i->first ) ? 0 : 1 ;
352  }
353 
354  //--------------------------------------------------------------------
355  // Is ok to get constant versions of the underlyingstorage
356 
357  operator const std::vector<value_type> & () const {
358  return * reinterpret_cast<const std::vector<value_type>*>( &Storage );
359  }
360 
361  operator const std::vector< std::pair<key_type,mapped_type> > & () const {
362  return Storage ;
363  }
364 
365  void reserve( size_type n ) {
366  Storage.reserve(n);
367  }
368 
369  bool operator == ( const vecmap<Key,T,Compare> & rhs ) const {
370  return Storage == rhs.Storage ;
371  }
372 
373  bool operator != ( const vecmap<Key,T,Compare> & rhs ) const {
374  return Storage != rhs.Storage ;
375  }
376 };
377 
378 } // namespace sierra
379 
380 #endif // STK_UTIL_UTIL_vecmap_hpp
Definition: Env.cpp:53
Vector-based std::map functionality.
Definition: VecMap.hpp:60