map_vector.h
Go to the documentation of this file.
1 #ifndef cetlib_map_vector_h
2 #define cetlib_map_vector_h
3 
4 // ======================================================================
5 // map_vector: A map mimicking a sparse vector interface
6 //
7 // Integer subscripting is unsupported and yields a compilation failure.
8 // ======================================================================
9 
10 #include "cetlib_except/exception.h"
11 
12 #include <algorithm>
13 #include <iosfwd>
14 #include <vector>
15 
16 namespace cet {
17  class map_vector_key;
18 
19  bool operator==(map_vector_key const&, map_vector_key const&) noexcept;
20  bool operator!=(map_vector_key const&, map_vector_key const&) noexcept;
21  bool operator<(map_vector_key const&, map_vector_key const&) noexcept;
22  bool operator>(map_vector_key const&, map_vector_key const&) noexcept;
23  bool operator<=(map_vector_key const&, map_vector_key const&) noexcept;
24  bool operator>=(map_vector_key const&, map_vector_key const&) noexcept;
25 
26  std::ostream& operator<<(std::ostream&, map_vector_key const&);
27 
28  template <class Value>
29  class map_vector;
30 }
31 
32 // ======================================================================
33 
35 public:
36  // c'tors:
37  constexpr map_vector_key() noexcept : key_{-1ul} {}
38  explicit map_vector_key(int key);
39  constexpr explicit map_vector_key(unsigned const key) noexcept : key_{key} {}
40  constexpr explicit map_vector_key(unsigned long key) noexcept;
41 
42  // observers:
43  constexpr unsigned long
44  asInt() const noexcept
45  {
46  return key_;
47  }
48  constexpr unsigned long
49  asUint() const noexcept
50  {
51  return key_;
52  }
53  void ensure_valid() const;
54 
55 private:
56  unsigned long key_;
57 
58 }; // map_vector_key
59 
61 {
62  if (key < 0) {
63  throw cet::exception("InvalidKey")
64  << "Negative key " << key << " not valid for map_vector_key.";
65  }
66 }
67 
68 constexpr cet::map_vector_key::map_vector_key(unsigned long const key) noexcept
69  : key_{key}
70 {}
71 
72 inline void
74 {
75  if (key_ == static_cast<unsigned long>(-1)) { // Invalid key
76  throw cet::exception("InvalidKey")
77  << "Attempt to use an invalid cet::map_vector_key.";
78  }
79 }
80 
81 // ======================================================================
82 
83 template <class Value>
84 class cet::map_vector {
85 public:
86  // types:
88  using mapped_type = Value;
89  using value_type = std::pair<key_type, mapped_type>;
90  using impl_type = std::vector<value_type>;
91 
92  using size_type = typename impl_type::size_type;
93  using difference_type = typename impl_type::difference_type;
94 
95  using iterator = typename impl_type::iterator;
97  using reverse_iterator = typename impl_type::reverse_iterator;
98  using const_reverse_iterator = typename impl_type::const_reverse_iterator;
99 
100  using allocator_type = typename impl_type::allocator_type;
101  using pointer = typename allocator_type::pointer;
102  using const_pointer = typename allocator_type::const_pointer;
103  using reference = typename allocator_type::reference;
104  using const_reference = typename allocator_type::const_reference;
105 
106  // c'tors:
107  map_vector() = default;
108 
109  template <class InIter>
110  map_vector(InIter const b, InIter const e)
111  {
112  insert(b, e);
113  }
114 
115  // use compiler-generated copy c'tor, copy assignment, and d'tor
116 
117  // properties:
118  bool
119  empty() const noexcept
120  {
121  return v_.empty();
122  }
123  size_type
124  size() const noexcept
125  {
126  return v_.size();
127  }
128  size_type
129  max_size() const noexcept
130  {
131  return v_.max_size();
132  }
133  size_type
134  capacity() const noexcept
135  {
136  return v_.capacity();
137  }
138 
140  get_allocator() const noexcept
141  {
142  return v_.get_allocator();
143  }
144 
145  // observers:
146  value_type const& front() const;
147  value_type const& back() const;
148 
149  // To be used in case map_vectors must be concatenated, and not
150  // merged.
151  size_t
152  delta() const
153  {
154  return v_.empty() ? 0 : 1 + v_.back().first.asInt();
155  }
156 
157  bool has(key_type key) const;
158 
159  iterator find(key_type key);
160  const_iterator find(key_type key) const;
161  const_iterator findOrThrow(key_type key) const;
162 
163  mapped_type* getOrNull(key_type key);
164  mapped_type const* getOrNull(key_type key) const;
165 
166  mapped_type& getOrThrow(key_type key);
167  mapped_type const& getOrThrow(key_type key) const;
168 
169  mapped_type& operator[](key_type key);
170  mapped_type const& operator[](key_type key) const { return getOrThrow(key); }
171  mapped_type const&
172  at(key_type key) const
173  {
174  return getOrThrow(key);
175  }
176 
177  // iterators:
178  iterator
179  begin() noexcept
180  {
181  return v_.begin();
182  }
184  begin() const noexcept
185  {
186  return v_.begin();
187  }
188 
189  iterator
190  end() noexcept
191  {
192  return v_.end();
193  }
195  end() const noexcept
196  {
197  return v_.end();
198  }
199 
201  rbegin() noexcept
202  {
203  return v_.rbegin();
204  }
206  rbegin() const noexcept
207  {
208  return v_.rbegin();
209  }
210 
212  rend() noexcept
213  {
214  return v_.rend();
215  }
217  rend() const noexcept
218  {
219  return v_.rend();
220  }
221 
223  cbegin() const noexcept
224  {
225  return v_.cbegin();
226  }
228  cend() const noexcept
229  {
230  return v_.cend();
231  }
233  crbegin() const
234  {
235  return v_.crbegin();
236  }
238  crend() const noexcept
239  {
240  return v_.crend();
241  }
242 
243  // mutators:
244  void
245  clear() noexcept
246  {
247  v_.clear();
248  }
249 
250  void
252  {
253  v_.reserve(n);
254  }
255 
256  void
258  {
259  v_.swap(other.v_);
260  }
261 
262  std::pair<iterator, bool> insert(value_type const& x);
263 
264  // The insert function template merges the incoming entries with the
265  // current collection. It is the responsibility of the user to
266  // ensure that the incoming entries are sorted. Duplicate entries
267  // will be removed.
268  template <class InIter>
269  void insert(InIter b, InIter e);
270 
271  // The append function template simply inserts the incoming entries
272  // at the end of the current collection. It is the responsibility
273  // of the user to ensure that the incoming entries are sorted and
274  // that the keys are disjoint and greater than those in the current
275  // collection.
276  template <class InIter>
277  void append(InIter b, InIter e);
278 
279  // MUST UPDATE WHEN CLASS IS CHANGED!
280  static short
282  {
283  return 10;
284  }
285 
286 private:
287  impl_type v_{};
288 
289  bool class_invariant() const;
290 
291  static bool lt(value_type const&, value_type const&) noexcept;
292  static bool eq(value_type const&, value_type const&) noexcept;
293 
294 }; // map_vector<>
295 
296 // ======================================================================
297 // additional map_vector_key implementation
298 
299 // ----------------------------------------------------------------------
300 // comparisons:
301 
302 inline bool
303 cet::operator==(map_vector_key const& k1, map_vector_key const& k2) noexcept
304 {
305  return k1.asInt() == k2.asInt();
306 }
307 
308 inline bool
309 cet::operator!=(map_vector_key const& k1, map_vector_key const& k2) noexcept
310 {
311  return k1.asInt() != k2.asInt();
312 }
313 
314 inline bool
315 cet::operator<(map_vector_key const& k1, map_vector_key const& k2) noexcept
316 {
317  return k1.asInt() < k2.asInt();
318 }
319 
320 inline bool
321 cet::operator>(map_vector_key const& k1, map_vector_key const& k2) noexcept
322 {
323  return k1.asInt() > k2.asInt();
324 }
325 
326 inline bool
327 cet::operator<=(map_vector_key const& k1, map_vector_key const& k2) noexcept
328 {
329  return k1.asInt() <= k2.asInt();
330 }
331 
332 inline bool
333 cet::operator>=(map_vector_key const& k1, map_vector_key const& k2) noexcept
334 {
335  return k1.asInt() >= k2.asInt();
336 }
337 
338 // ----------------------------------------------------------------------
339 // output:
340 
341 inline std::ostream&
342 cet::operator<<(std::ostream& os, cet::map_vector_key const& key)
343 {
344  return os << key.asInt();
345 }
346 
347 // ======================================================================
348 // additional map_vector<> implementation
349 
350 // ----------------------------------------------------------------------
351 // observers:
352 
353 template <class Value>
356 {
357  if (v_.empty())
358  throw cet::exception("map_vector::front") << "container is empty!\n";
359  return v_.front();
360 }
361 
362 template <class Value>
365 {
366  if (v_.empty())
367  throw cet::exception("map_vector::back") << "container is empty!\n";
368  return v_.back();
369 }
370 
371 template <class Value>
372 bool
374 {
375  value_type const v{key, mapped_type{}};
376  return std::binary_search(v_.begin(), v_.end(), v, lt);
377 }
378 
379 template <class Value>
382 {
383  value_type const v{key, mapped_type{}};
384  auto const begin = v_.begin(), end = v_.end();
385  auto it = std::lower_bound(begin, end, v, lt);
386  if (it != end && it->first != key)
387  it = end;
388  return it;
389 }
390 
391 template <class Value>
394 {
395  value_type const v{key, mapped_type{}};
396  auto const begin = v_.cbegin(), end = v_.cend();
397  auto it = std::lower_bound(begin, end, v, lt);
398  if (it != end && it->first != key)
399  it = end;
400  return it;
401 }
402 
403 template <class Value>
406 {
407  auto p = find(key);
408  if (p == v_.cend())
409  throw cet::exception("map_vector::getOrThrow")
410  << "out of range (no such key): " << key.asInt() << std::endl;
411 
412  return p;
413 }
414 
415 template <class Value>
416 Value*
418 {
419  auto it = find(key);
420  return it == v_.end() ? nullptr : &it->second;
421 }
422 
423 template <class Value>
424 Value const*
426 {
427  auto it = find(key);
428  return it == v_.cend() ? nullptr : &it->second;
429 }
430 
431 template <class Value>
432 Value&
434 {
435  auto* p = getOrNull(key);
436  if (p == nullptr)
437  throw cet::exception("map_vector::getOrThrow")
438  << "out of range (no such key): " << key.asInt() << std::endl;
439 
440  return *p;
441 }
442 
443 template <class Value>
444 Value const&
446 {
447  auto const* p = getOrNull(key);
448  if (p == nullptr)
449  throw cet::exception("map_vector::getOrThrow")
450  << "out of range (no such key): " << key.asInt() << std::endl;
451 
452  return *p;
453 }
454 
455 template <class Value>
457 {
458  value_type const v{key, mapped_type{}};
459  auto const begin = v_.begin(), end = v_.end();
460  auto it = std::lower_bound(begin, end, v, lt);
461  if (it == end || it->first != key)
462  it = v_.insert(it, std::move(v));
463  return it->second;
464 }
465 
466 // ----------------------------------------------------------------------
467 // mutators:
468 
469 template <class Value>
472 {
473  v.first.ensure_valid();
474  auto const begin = v_.begin(), end = v_.end();
475  auto it = std::lower_bound(begin, end, v, lt);
476  if (it == end || it->first != v.first)
477  return std::make_pair(v_.insert(it, v), true);
478  return std::make_pair(it, false);
479 }
480 
481 template <class Value>
482 template <class InIter>
483 void
484 cet::map_vector<Value>::insert(InIter const b, InIter const e)
485 {
486  std::for_each(b, e, [](auto const& pr) { return pr.first.ensure_valid(); });
488  result.reserve(size() + std::distance(b, e));
489  std::merge(v_.cbegin(), v_.cend(), b, e, back_inserter(result), lt);
490  auto new_end = std::unique(result.begin(), result.end(), eq);
491  result.erase(new_end, result.end());
492  result.shrink_to_fit();
493  v_.swap(result);
494 }
495 
496 template <class Value>
497 template <class InIter>
498 void
499 cet::map_vector<Value>::append(InIter const b, InIter const e)
500 {
501  std::for_each(b, e, [](auto const& pr) { return pr.first.ensure_valid(); });
502  v_.insert(v_.cend(), b, e);
503  assert(class_invariant());
504 }
505 
506 // ----------------------------------------------------------------------
507 // helpers:
508 
509 template <class Value>
510 bool
512 {
513  return std::is_sorted(v_.begin(), v_.end(), lt);
514 }
515 
516 // ======================================================================
517 
518 template <class Value>
519 bool
520 cet::map_vector<Value>::lt(value_type const& v1, value_type const& v2) noexcept
521 {
522  return v1.first < v2.first;
523 }
524 
525 template <class Value>
526 bool
527 cet::map_vector<Value>::eq(value_type const& v1, value_type const& v2) noexcept
528 {
529  return v1.first == v2.first;
530 }
531 
532 // ======================================================================
533 #endif /* cetlib_map_vector_h */
534 
535 // Local variables:
536 // mode: c++
537 // End:
end
while True: pbar.update(maxval-len(onlies[E][S])) #print iS, "/", len(onlies[E][S]) found = False for...
reverse_iterator rbegin() noexcept
Definition: map_vector.h:201
bool empty() const noexcept
Definition: map_vector.h:119
intermediate_table::iterator iterator
constexpr map_vector_key(unsigned const key) noexcept
Definition: map_vector.h:39
allocator_type get_allocator() const noexcept
Definition: map_vector.h:140
constexpr unsigned long asUint() const noexcept
Definition: map_vector.h:49
static QCString result
constexpr bool operator>=(exempt_ptr< E >, exempt_ptr< E >)
Definition: exempt_ptr.h:279
size_type capacity() const noexcept
Definition: map_vector.h:134
const_reverse_iterator rend() const noexcept
Definition: map_vector.h:217
std::ostream & operator<<(std::ostream &, map_vector_key const &)
Definition: map_vector.h:342
const_iterator cend() const noexcept
Definition: map_vector.h:228
std::vector< value_type > impl_type
Definition: map_vector.h:90
void swap(map_vector< mapped_type > &other)
Definition: map_vector.h:257
std::pair< key_type, mapped_type > value_type
Definition: map_vector.h:89
bool has(key_type key) const
Definition: map_vector.h:373
iterator find(key_type key)
Definition: map_vector.h:381
iterator end() noexcept
Definition: map_vector.h:190
std::pair< iterator, bool > insert(value_type const &x)
Definition: map_vector.h:471
STL namespace.
intermediate_table::const_iterator const_iterator
map_vector(InIter const b, InIter const e)
Definition: map_vector.h:110
const_iterator end() const noexcept
Definition: map_vector.h:195
typename allocator_type::reference reference
Definition: map_vector.h:103
constexpr map_vector_key() noexcept
Definition: map_vector.h:37
typename impl_type::const_reverse_iterator const_reverse_iterator
Definition: map_vector.h:98
size_t delta() const
Definition: map_vector.h:152
void clear() noexcept
Definition: map_vector.h:245
typename impl_type::allocator_type allocator_type
Definition: map_vector.h:100
typename allocator_type::const_reference const_reference
Definition: map_vector.h:104
Value mapped_type
Definition: map_vector.h:88
decltype(auto) constexpr size(T &&obj)
ADL-aware version of std::size.
Definition: StdUtils.h:92
typename impl_type::reverse_iterator reverse_iterator
Definition: map_vector.h:97
static bool lt(value_type const &, value_type const &) noexcept
Definition: map_vector.h:520
const_iterator begin() const noexcept
Definition: map_vector.h:184
typename impl_type::size_type size_type
Definition: map_vector.h:92
const double e
size_type max_size() const noexcept
Definition: map_vector.h:129
mapped_type & operator[](key_type key)
Definition: map_vector.h:456
constexpr bool operator<(exempt_ptr< E >, exempt_ptr< E >)
Definition: exempt_ptr.h:256
typename impl_type::difference_type difference_type
Definition: map_vector.h:93
def key(type, name=None)
Definition: graph.py:13
std::void_t< T > n
void append(InIter b, InIter e)
Definition: map_vector.h:499
def move(depos, offset)
Definition: depos.py:107
typename allocator_type::const_pointer const_pointer
Definition: map_vector.h:102
typename allocator_type::pointer pointer
Definition: map_vector.h:101
constexpr bool operator<=(exempt_ptr< E >, exempt_ptr< E >)
Definition: exempt_ptr.h:272
impl_type v_
Definition: map_vector.h:287
bool class_invariant() const
Definition: map_vector.h:511
p
Definition: test.py:223
constexpr bool operator==(exempt_ptr< E >, exempt_ptr< E >) noexcept
Definition: exempt_ptr.h:211
void reserve(size_type const n)
Definition: map_vector.h:251
value_type const & front() const
Definition: map_vector.h:355
constexpr bool operator>(exempt_ptr< E >, exempt_ptr< E >)
Definition: exempt_ptr.h:265
double distance(double x1, double y1, double z1, double x2, double y2, double z2)
reverse_iterator rend() noexcept
Definition: map_vector.h:212
mapped_type const & operator[](key_type key) const
Definition: map_vector.h:170
constexpr bool operator!=(exempt_ptr< E >, exempt_ptr< E >) noexcept
Definition: exempt_ptr.h:218
typename impl_type::iterator iterator
Definition: map_vector.h:95
iterator begin() noexcept
Definition: map_vector.h:179
value_type const & back() const
Definition: map_vector.h:364
const_reverse_iterator crbegin() const
Definition: map_vector.h:233
unsigned long key_
Definition: map_vector.h:56
const_reverse_iterator rbegin() const noexcept
Definition: map_vector.h:206
static bool * b
Definition: config.cpp:1043
constexpr unsigned long asInt() const noexcept
Definition: map_vector.h:44
static bool eq(value_type const &, value_type const &) noexcept
Definition: map_vector.h:527
list x
Definition: train.py:276
void ensure_valid() const
Definition: map_vector.h:73
decltype(auto) constexpr begin(T &&obj)
ADL-aware version of std::begin.
Definition: StdUtils.h:72
mapped_type const & at(key_type key) const
Definition: map_vector.h:172
const_iterator findOrThrow(key_type key) const
Definition: map_vector.h:405
mapped_type & getOrThrow(key_type key)
Definition: map_vector.h:433
static short Class_Version()
Definition: map_vector.h:281
size_type size() const noexcept
Definition: map_vector.h:124
const_reverse_iterator crend() const noexcept
Definition: map_vector.h:238
typename impl_type::const_iterator const_iterator
Definition: map_vector.h:96
const_iterator cbegin() const noexcept
Definition: map_vector.h:223
cet::coded_exception< error, detail::translate > exception
Definition: exception.h:33
QTextStream & endl(QTextStream &s)
mapped_type * getOrNull(key_type key)
Definition: map_vector.h:417