CBMC
forward_list_as_map.h
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module: util
4 
5 Author: Romain Brenguier, romain.brenguier@diffblue.com
6 
7 \*******************************************************************/
8 
9 #ifndef CPROVER_UTIL_FORWARD_LIST_AS_MAP_H
10 #define CPROVER_UTIL_FORWARD_LIST_AS_MAP_H
11 
12 #include <algorithm>
13 #include <forward_list>
14 
15 #include "as_const.h"
16 #include "narrow.h"
17 
19 template <typename keyt, typename mappedt>
20 // requires DefaultConstructible<mappedt>
21 class forward_list_as_mapt : public std::forward_list<std::pair<keyt, mappedt>>
22 {
23 public:
24  using implementationt = typename std::forward_list<std::pair<keyt, mappedt>>;
25  using const_iterator = typename implementationt::const_iterator;
26  using iterator = typename implementationt::iterator;
27 
29  {
30  }
31 
32  forward_list_as_mapt(std::initializer_list<std::pair<keyt, mappedt>> list)
33  : implementationt(std::move(list))
34  {
35  }
36 
37  void remove(const keyt &name)
38  {
39  const_iterator it = this->lower_bound(name);
40 
41  if(it != this->end() && it->first == name)
42  {
43  iterator before = this->before_begin();
44  while(std::next(before) != it)
45  ++before;
46  this->erase_after(before);
47  }
48  }
49 
50  const const_iterator find(const keyt &name) const
51  {
52  const_iterator it = lower_bound(name);
53 
54  if(it == this->end() || it->first != name)
55  return this->end();
56 
57  return it;
58  }
59 
60  iterator add(const keyt &name)
61  {
62  iterator it = mutable_lower_bound(name);
63 
64  if(it == this->end() || it->first != name)
65  {
66  iterator before = this->before_begin();
67  while(std::next(before) != it)
68  ++before;
69  it = this->emplace_after(before, name, mappedt());
70  }
71 
72  return it;
73  }
74 
75  mappedt &operator[](const keyt &name)
76  {
77  return add(name)->second;
78  }
79 
80  mappedt &add(const keyt &name, mappedt irep)
81  {
82  iterator it = mutable_lower_bound(name);
83 
84  if(it == this->end() || it->first != name)
85  {
86  iterator before = this->before_begin();
87  while(std::next(before) != it)
88  ++before;
89  it = this->emplace_after(before, name, std::move(irep));
90  }
91  else
92  it->second = std::move(irep);
93 
94  return it->second;
95  }
96 
97  std::size_t size() const
98  {
99  return narrow<std::size_t>(std::distance(this->begin(), this->end()));
100  }
101 
102 private:
103  static bool order(const std::pair<keyt, mappedt> &a, const keyt &b)
104  {
105  return a.first < b;
106  }
107 
108  const_iterator lower_bound(const keyt &id) const
109  {
110  return std::lower_bound(this->begin(), this->end(), id, order);
111  }
112 
114  {
115  return std::lower_bound(this->begin(), this->end(), id, order);
116  }
117 };
118 
119 #endif // CPROVER_UTIL_FORWARD_LIST_AS_MAP_H
Implementation of map-like interface using a forward list.
void remove(const keyt &name)
const const_iterator find(const keyt &name) const
iterator mutable_lower_bound(const keyt &id)
std::size_t size() const
forward_list_as_mapt(std::initializer_list< std::pair< keyt, mappedt >> list)
typename std::forward_list< std::pair< keyt, mappedt > > implementationt
typename implementationt::iterator iterator
mappedt & add(const keyt &name, mappedt irep)
iterator add(const keyt &name)
const_iterator lower_bound(const keyt &id) const
typename implementationt::const_iterator const_iterator
mappedt & operator[](const keyt &name)
static bool order(const std::pair< keyt, mappedt > &a, const keyt &b)