My Project
OrderedMap.hpp
1 /*
2  Copyright 2014 Statoil ASA.
3 
4  This file is part of the Open Porous Media project (OPM).
5 
6  OPM is free software: you can redistribute it and/or modify
7  it under the terms of the GNU General Public License as published by
8  the Free Software Foundation, either version 3 of the License, or
9  (at your option) any later version.
10 
11  OPM is distributed in the hope that it will be useful,
12  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  GNU General Public License for more details.
15 
16  You should have received a copy of the GNU General Public License
17  along with OPM. If not, see <http://www.gnu.org/licenses/>.
18  */
19 
20 #ifndef OPM_ORDERED_MAP_HPP
21 #define OPM_ORDERED_MAP_HPP
22 
23 #include <unordered_map>
24 #include <vector>
25 #include <string>
26 #include <stdexcept>
27 #include <iterator>
28 #include <sstream>
29 #include <set>
30 #include <cctype>
31 #include <algorithm>
32 
33 namespace Opm {
34 
35 namespace OrderedMapDetail
36 {
37 
38 template<class T, class A>
39 std::string
40 findSimilarStrings(std::string str,
41  const std::vector<std::pair<std::string, T>,A>& storage)
42 {
43  auto toUpper = [](const char c){ return std::toupper(c);};
44  std::transform(str.begin(), str.end(), str.begin(), toUpper);
45  std::set<std::string> alternatives;
46 
47  for(const auto& entry: storage)
48  {
49  std::string upper = entry.first;
50  std::transform(upper.begin(), upper.end(), upper.begin(),
51  toUpper);
52 
53  if(upper.find(str) != std::string::npos || str.find(upper) != std::string::npos)
54  {
55  alternatives.insert(entry.first);
56  }
57  }
58 
59  if (alternatives.empty())
60  {
61  return {};
62  }
63 
64  std::stringstream concated;
65  std::copy(alternatives.begin(), alternatives.end(),
66  std::ostream_iterator<std::string>(concated, ", "));
67  auto concatedStr = concated.str();
68  return concatedStr.substr(0, concatedStr.size()-2);
69 }
70 
71 template<std::size_t MAX_CHARS>
73 {
74 public:
75  std::size_t operator()(const std::string_view& key) const
76  {
77  return hasher(key.substr(0, MAX_CHARS));
78  }
79 private:
80  std::hash<std::string_view> hasher;
81 };
82 
83 
84 template<>
85 class TruncatedStringHash<std::string::npos> : public std::hash<std::string_view>
86 {};
87 
88 template<std::size_t MAX_CHARS>
90 {
91  bool operator()(const std::string& str1, const std::string& str2) const
92  {
93  return str1.substr(0, MAX_CHARS) == str2.substr(0, MAX_CHARS);
94  }
95 };
96 
97 template<>
98 struct TruncatedStringEquals<std::string::npos> : public std::equal_to<std::string>
99 {};
100 
101 } // end namespace detail
102 
113 template <typename T, std::size_t MAX_CHARS = std::string::npos>
114 class OrderedMap {
115 public:
116  using storage_type = typename std::vector<std::pair<std::string,T>>;
117  using index_type = typename std::unordered_map<std::string,std::size_t,
120  using iter_type = typename storage_type::iterator;
121  using const_iter_type = typename storage_type::const_iterator;
122 
123 private:
124  index_type m_map;
125  storage_type m_vector;
126 
127 public:
128 
129  OrderedMap() = default;
130 
131  OrderedMap(const index_type& index, const storage_type& storage)
132  : m_map(index)
133  , m_vector(storage)
134  {
135  }
136 
137  const index_type& getIndex() const { return m_map; }
138 
139  const storage_type& getStorage() const { return m_vector; }
140 
141  std::size_t count(const std::string& key) const {
142  return this->m_map.count(key);
143  }
144 
145 
146 
147  T& operator[](const std::string& key) {
148  if (this->count(key) == 0)
149  this->insert( std::make_pair(key, T()));
150 
151  return this->at(key);
152  }
153 
154 
155  std::size_t erase(const std::string& key) {
156  if (this->count(key) == 0)
157  return 0;
158 
159  std::size_t index = this->m_map.at(key);
160  this->m_map.erase(key);
161  this->m_vector.erase(this->m_vector.begin() + index);
162 
163  for (const auto& index_pair : this->m_map) {
164  auto target_index = index_pair.second;
165  if (target_index > index)
166  target_index--;
167 
168  this->m_map[index_pair.first] = target_index;
169  }
170  return 1;
171  }
172 
173 
174  void insert(std::pair<std::string,T> key_value_pair) {
175  if (this->count(key_value_pair.first) > 0) {
176  auto iter = m_map.find( key_value_pair.first );
177  size_t index = iter->second;
178  m_vector[index] = key_value_pair;
179  } else {
180  size_t index = m_vector.size();
181  this->m_map.emplace(key_value_pair.first, index);
182  this->m_vector.push_back( std::move( key_value_pair ) );
183  }
184  }
185 
186 
187  T& get(const std::string& key) {
188  auto iter = m_map.find( key );
189  if (iter == m_map.end())
190  {
191  using namespace std::string_literals;
192  auto startsWithSame = OrderedMapDetail::findSimilarStrings(key, m_vector);
193  if (!startsWithSame.empty())
194  {
195  startsWithSame = " Similar entries are "s +
196  startsWithSame + "."s;
197  }
198  throw std::invalid_argument("Key "s + key + " not found."s
199  + startsWithSame);
200  }
201  else {
202  size_t index = iter->second;
203  return iget(index);
204  }
205  }
206 
207 
208  T& iget(size_t index) {
209  if (index >= m_vector.size())
210  throw std::invalid_argument("Invalid index");
211  return m_vector[index].second;
212  }
213 
214  const T& get(const std::string& key) const {
215  const auto& iter = this->m_map.find( key );
216  if (iter == m_map.end())
217  {
218  auto startsWithSame = OrderedMapDetail::findSimilarStrings(key, m_vector);
219  if (!startsWithSame.empty())
220  {
221  startsWithSame = std::string(" Similar entries are ") +
222  startsWithSame + std::string(".");
223  }
224  using namespace std::string_literals;
225  throw std::invalid_argument("Key "s + key + " not found."s
226  + startsWithSame);
227  }
228  else {
229  size_t index = iter->second;
230  return iget(index);
231  }
232  }
233 
234 
235  const T& iget(size_t index) const {
236  if (index >= m_vector.size())
237  {
238  using namespace std::string_literals;
239  throw std::invalid_argument("Invalid index "s +
240  std::to_string(index) +
241  " is larger than container size"s);
242  }
243  return m_vector[index].second;
244  }
245 
246  const T& at(size_t index) const {
247  return this->iget(index);
248  }
249 
250  const T& at(const std::string& key) const {
251  return this->get(key);
252  }
253 
254  T& at(size_t index) {
255  return this->iget(index);
256  }
257 
258  T& at(const std::string& key) {
259  return this->get(key);
260  }
261 
262  size_t size() const {
263  return m_vector.size();
264  }
265 
266 
267  const_iter_type begin() const {
268  return m_vector.begin();
269  }
270 
271 
272  const_iter_type end() const {
273  return m_vector.end();
274  }
275 
276  iter_type begin() {
277  return m_vector.begin();
278  }
279 
280  iter_type end() {
281  return m_vector.end();
282  }
283 
284  iter_type find(const std::string& key) {
285  const auto map_iter = this->m_map.find(key);
286  if (map_iter == this->m_map.end())
287  return this->m_vector.end();
288 
289  return std::next(this->m_vector.begin(), map_iter->second);
290  }
291 
292  const_iter_type find(const std::string& key) const {
293  const auto map_iter = this->m_map.find(key);
294  if (map_iter == this->m_map.end())
295  return this->m_vector.end();
296 
297  return std::next(this->m_vector.begin(), map_iter->second);
298  }
299 
300  template<size_t n>
301  bool operator==(const OrderedMap<T,n>& data) const {
302  return this->getIndex() == data.getIndex() &&
303  this->getStorage() == data.getStorage();
304  }
305 
306  template<class Serializer>
307  void serializeOp(Serializer& serializer)
308  {
309  serializer(m_map);
310  serializer(m_vector);
311  }
312 };
313 }
314 
315 #endif
Definition: OrderedMap.hpp:73
A map with iteration in the order of insertion.
Definition: OrderedMap.hpp:114
Class for (de-)serializing.
Definition: Serializer.hpp:75
This class implements a small container which holds the transmissibility mulitpliers for all the face...
Definition: Exceptions.hpp:29