Awali
Another Weighted Automata library
linked_map.hxx
Go to the documentation of this file.
1 // This file is part of Awali.
2 // Copyright 2016-2022 Sylvain Lombardy, Victor Marsault, Jacques Sakarovitch
3 //
4 // Awali is a free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 
17 #ifndef AWALI_LINKED_MAP_HXX
18 #define AWALI_LINKED_MAP_HXX
19 
21 
22 #include <unordered_map>
23 #include <list>
24 #include <stdexcept>
25 #include <sstream>
26 
27 namespace awali {
28 
33 template <typename K, typename H = std::hash<K>>
34 class pointed_hash_t : protected H {
35 public:
36  std::size_t operator()(K* key) const noexcept {
37  return (key == nullptr) ? 0 : H::operator()(*key);
38  }
39 };
40 
46 template <typename K, typename E = std::equal_to<K>>
47 class pointed_equal_t : protected E {
48 public:
49  bool operator()(K* key1, K* key2) const noexcept {
50  return (key1 == nullptr || key2 == nullptr) ? (key1 == key2)
51  : E::operator()(*key1,*key2);
52  }
53 };
54 
55 
70 template <typename K, typename V,
71  typename H = std::hash<K>, typename E = std::equal_to<K>>
72 class linked_map_t {
73 public:
75  typedef K key_t;
76  typedef V value_t;
77  typedef std::pair<key_t const,value_t> pair_t;
78  typedef pair_t value_type;
79  typedef std::pair<key_t,value_t> init_pair_t;
80  typedef std::list<pair_t> list_t;
81  typedef typename std::list<pair_t>::iterator iterator;
82  typedef typename std::list<pair_t>::const_iterator const_iterator;
83  typedef std::unordered_map< key_t const*,
84  iterator,
87  typedef typename map_t::size_type size_type;
88 
89 protected:
92 
101  void remap(bool hard) {
102  map.clear();
103  map.reserve(list.size());
104  for(auto it = list.begin(); it != list.end(); it++) {
105  if (hard) {
106  auto x = map.find(&(it->first));
107  if (x != map.end())
108  erase(x->second);
109  }
110  map[&(it->first)]=it;
111  }
112  }
113 
114 public:
116  bool empty() const noexcept { return list.empty(); }
117 
119  size_type size() const noexcept { return list.size(); }
120 
121  size_type max_size() const noexcept { return map.max_size(); }
122 
124  void clear() noexcept { map.clear(); list.clear(); }
125 
127  size_type bucket_count() const noexcept {return map.bucket_count();}
129  size_type bucket_size(unsigned n) const noexcept {return map.bucket_size(n);}
131  size_type max_bucket_count() const noexcept {return map.max_bucket_count();}
133  float load_factor() const noexcept {return map.load_factor();}
135  float max_load_factor() const noexcept {return map.max_load_factor();}
137  void max_load_factor(float x) {map.max_load_factor(x);}
139  void rehash(size_type n) {map.rehash(n);}
141  void reserve(size_type n) {map.reserve(n);}
142 
143  iterator begin() noexcept {return list.begin();}
144  iterator end() noexcept {return list.end();}
145 
146  const_iterator begin() const noexcept {return cbegin();}
147  const_iterator end() const noexcept {return cend();}
148 
149  const_iterator cbegin() const noexcept {return list.cbegin();}
150  const_iterator cend() const noexcept {return list.cend();}
151 
152 
156  iterator
157  find(key_t const& key)
158  {
159  auto res = map.find(&key);
160  if (res == map.end())
161  return list.end();
162  else
163  return res->second;
164  }
165 
170  find(key_t const& key)
171  const
172  {
173  auto res = map.find(&key);
174  if (res == map.end())
175  return list.cend();
176  else
177  return res->second;
178  }
179 
180 
183  size_type count(key_t const& key)
184  const
185  {
186  return map.find(&key) != map.end();
187  }
188 
189 
190 
191 
192 
202  bool overwrite_existing = false)
203  {
204  auto it = map.find(&key);
205  if (it != map.end()) {
206  if (overwrite_existing) {
207  auto list_it = it->second;
208  map.erase(it);
209  list.erase(list_it);
210  }
211  else
212  return it->second;
213  }
214  auto res = list.emplace(pos, std::move(key),std::move(value));
215  map.emplace(&(res->first),res);
216  return res;
217  }
218 
219 
226  bool overwrite_existing = false)
227  {
228  insert(begin(), std::move(key), std::move(value), overwrite_existing);
229  }
230 
231 
232  pair_t& front() { return list.front(); }
233  pair_t const& front() const { return list.front(); }
234 
235 
236  pair_t& back() { return list.back(); }
237  pair_t const& back() const { return list.back(); }
238 
239 
246  void push_back(key_t key, value_t value, bool overwrite_existing = false)
247  {
248  insert(end(), std::move(key), std::move(value), overwrite_existing);
249  }
250 
251 
252  /* Erases the binding pointed at by given iterator.
253  * Does nothing if @pname{pos} is equal to {@link end()}.
254  * @return an iterator pointing to the next binding.
255  */
256  iterator
258  {
259  if (pos == this->cend())
260  return this->end();
261  map.erase(&(pos->first));
262  return list.erase(pos);
263  }
264 
265 
269  size_type
270  erase(key_t const& key)
271  {
272  auto it = map.find(&key);
273  if (it == map.end())
274  return 0;
275  const_iterator it2 = it->second; // Somehow this is required because
276  map.erase(it); // unordered_map tries to hash
277  list.erase(it2); // its key before erasing from iterator.
278  return 1;
279  }
280 
281 
285  value_t&
286  at (key_t const& key)
287  {
288  auto it = map.find(&key);
289  if (it != map.end())
290  return it->second->second;
291  std::stringstream ss;
292  ss << "This linked_map does not have a binding with key" << key << ".";
293  throw std::out_of_range(ss.str());
294  }
295 
296 
300  value_t const&
301  at (key_t const& key)
302  const
303  {
304  auto it = map.find(&key);
305  if (it != map.end())
306  return it->second->second;
307  std::stringstream ss;
308  ss << "This linked_map does not have a binding with key" << key << ".";
309  throw std::out_of_range(ss.str());
310  }
311 
312 
313 
322  value_t&
324  {
325  auto it = map.find(&key);
326  if (it != map.end())
327  return it->second->second;
328  list.emplace_back(std::move(key),value_t());
329  iterator x = --list.end();
330  map[&(x->first)] = x;
331  return x->second;
332  }
333 
334 
337  void
339  {
340  list.sort([](pair_t x,pair_t y){return (x.first < y.first);});
341  remap(false);
342  }
343 
344 
346  template <class Compare>
347  void sort(Compare comp)
348  {
349  list.sort(comp);
350  remap(false);
351  }
352 
353 
355 
356  linked_map_t(std::initializer_list<pair_t> l) : list(std::move(l))
357  {remap(true);}
358 
359  linked_map_t(std::list<pair_t> l) : list(std::move(l))
360  {remap(true);}
361 
363  : list(other.list), map() {remap(false);}
364 
366  : list(std::move(other.list)), map(std::move(other.map)) {}
367  // ^^^^^^^^^^^^^^^^^^^^^^^^
368  // This assumes that the iterators are still valid
369  // after moving a std::list
370 
371 
383  template<class O>
385  O&& container, // /!\ This is a universal reference, not a rvalue reference
386  typename std::enable_if<
387  is_iterable_with<O,init_pair_t>::value,bool>::type require_remap = true)
388  {
390  for (auto& pair : container) {
391  if (b) // This is clearly a case
392  list.push_back(pair); // where C17 `if constexpr` would
393  else // be beneficial.
394  list.push_back(std::move(pair)); //
395  }
396  remap(require_remap);
397  }
398 
399 
400 
405  bool operator!=(self_type_t const& other)
406  {return !( (*this) == other);}
407 
408 
417  bool operator==(self_type_t const& other) {
418  return this->equals_as_list(other);
419  }
420 
421 
428  template<typename KeyEquality = E, typename ValueEquality = std::equal_to<V>>
429  bool equals_as_list(self_type_t const& other) const
430  {
431  KeyEquality ke;
432  ValueEquality ve;
433  const_iterator it1 = begin();
434  const_iterator it2 = other.begin();
435  while (it1 != end() && it2 != other.end()) {
436  if (!ke(it1->first,it2->first))
437  return false;
438  if (!ve(it1->second,it2->second))
439  return false;
440  ++it1;
441  ++it2;
442  }
443  return (it1 == end() && it2 == other.end());
444  }
445 
455  template<typename ValueEquality = std::equal_to<V>>
456  bool equals_as_map(self_type_t const& other) const
457  {
458  ValueEquality ve;
459  if (this->size() != other.size())
460  return false;
461  const_iterator end = this->end();
462  for(pair_t const& pair: other) {
463  const_iterator it = this->find(pair.first);
464  if (it == end)
465  return false;
466  if (!ve(pair.second,it->second))
467  return false;
468  }
469  return true;
470  }
471 };
472 
473 
474 
475 } // end of namespace awali
476 
477 #endif
Implemention of a linked hash-map.
Definition: linked_map.hxx:72
size_type max_bucket_count() const noexcept
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:131
linked_map_t(std::initializer_list< pair_t > l)
Definition: linked_map.hxx:356
list_t list
Definition: linked_map.hxx:91
std::list< pair_t >::iterator iterator
Definition: linked_map.hxx:81
void push_front(key_t key, value_t value, bool overwrite_existing=false)
Inserts a new key/value binding at the front of this linked_map_t; deletes existing binding for key p...
Definition: linked_map.hxx:225
size_type count(key_t const &key) const
Returns the number of binding associated with key, that is 0 or 1.
Definition: linked_map.hxx:183
size_type erase(key_t const &key)
Deletes the value bound to key.
Definition: linked_map.hxx:270
std::pair< key_t const, value_t > pair_t
Definition: linked_map.hxx:77
map_t::size_type size_type
Definition: linked_map.hxx:87
iterator insert(const_iterator pos, key_t key, value_t value, bool overwrite_existing=false)
Inserts a new key/value binding before pos; deletes existing binding for key prior to insertion if ov...
Definition: linked_map.hxx:201
bool equals_as_map(self_type_t const &other) const
Returns true if the bindings in this linked_map_t are exactly those in other, when considered as maps...
Definition: linked_map.hxx:456
bool empty() const noexcept
Returns if this linked_map_t is empty.
Definition: linked_map.hxx:116
bool operator==(self_type_t const &other)
Returns true if this linked_map_t is equal to other, when both are considered as lists of pairs.
Definition: linked_map.hxx:417
pair_t & front()
Definition: linked_map.hxx:232
iterator begin() noexcept
Definition: linked_map.hxx:143
value_t & operator[](key_t key)
Access, modify or set the value bound to key.
Definition: linked_map.hxx:323
size_type size() const noexcept
Returns the number of bindings in this linked_map_t.
Definition: linked_map.hxx:119
const_iterator begin() const noexcept
Definition: linked_map.hxx:146
const_iterator find(key_t const &key) const
Returns the position corresponding to the binding of key.
Definition: linked_map.hxx:170
std::list< pair_t > list_t
Definition: linked_map.hxx:80
linked_map_t(linked_map_t< key_t, value_t > const &other)
Definition: linked_map.hxx:362
bool operator!=(self_type_t const &other)
Returns true if this linked_map_t is different from other.
Definition: linked_map.hxx:405
linked_map_t(O &&container, typename std::enable_if< is_iterable_with< O, init_pair_t >::value, bool >::type require_remap=true)
Universal constructor to build a linked_map_t from any kind of iterable containing std::pair<std::str...
Definition: linked_map.hxx:384
const_iterator cbegin() const noexcept
Definition: linked_map.hxx:149
void reserve(size_type n)
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:141
linked_map_t(std::list< pair_t > l)
Definition: linked_map.hxx:359
void remap(bool hard)
Recompute map from list.
Definition: linked_map.hxx:101
pair_t const & front() const
Definition: linked_map.hxx:233
void max_load_factor(float x)
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:137
void sort(Compare comp)
Sort this linked_map_t by given comparison.
Definition: linked_map.hxx:347
bool equals_as_list(self_type_t const &other) const
Returns true if this linked_map_t is equal to other, when both are considered as lists of pairs.
Definition: linked_map.hxx:429
linked_map_t< K, V, H, E > self_type_t
Definition: linked_map.hxx:74
std::unordered_map< key_t const *, iterator, pointed_hash_t< key_t const, H >, pointed_equal_t< key_t const, E > > map_t
Definition: linked_map.hxx:86
V value_t
Definition: linked_map.hxx:76
float max_load_factor() const noexcept
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:135
std::pair< key_t, value_t > init_pair_t
Definition: linked_map.hxx:79
map_t map
Definition: linked_map.hxx:90
const_iterator cend() const noexcept
Definition: linked_map.hxx:150
pair_t const & back() const
Definition: linked_map.hxx:237
value_t & at(key_t const &key)
Access value bound to key.
Definition: linked_map.hxx:286
float load_factor() const noexcept
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:133
std::list< pair_t >::const_iterator const_iterator
Definition: linked_map.hxx:82
void sort()
Sort this linked_map_t by key assuming operator< exists on key_t.
Definition: linked_map.hxx:338
size_type bucket_size(unsigned n) const noexcept
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:129
iterator find(key_t const &key)
Returns the position corresponding to the binding of key.
Definition: linked_map.hxx:157
K key_t
Definition: linked_map.hxx:75
iterator erase(const_iterator pos)
Definition: linked_map.hxx:257
pair_t & back()
Definition: linked_map.hxx:236
pair_t value_type
Definition: linked_map.hxx:78
linked_map_t(linked_map_t< key_t, value_t > &&other)
Definition: linked_map.hxx:365
value_t const & at(key_t const &key) const
Access value bound to key.
Definition: linked_map.hxx:301
void rehash(size_type n)
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:139
void clear() noexcept
Clears this linked_map_t.
Definition: linked_map.hxx:124
void push_back(key_t key, value_t value, bool overwrite_existing=false)
Inserts a new key/value binding at the back of this linked_map_t; deletes existing binding for key pr...
Definition: linked_map.hxx:246
size_type bucket_count() const noexcept
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:127
const_iterator end() const noexcept
Definition: linked_map.hxx:147
size_type max_size() const noexcept
Definition: linked_map.hxx:121
linked_map_t()
Definition: linked_map.hxx:354
iterator end() noexcept
Definition: linked_map.hxx:144
This class takes a type E that computes equality for type K and allows to compute equality for type K...
Definition: linked_map.hxx:47
bool operator()(K *key1, K *key2) const noexcept
Definition: linked_map.hxx:49
This class takes a hasher for type K and makes a hasher for type K const* that hash the pointed value...
Definition: linked_map.hxx:34
std::size_t operator()(K *key) const noexcept
Definition: linked_map.hxx:36
static constexpr TOP< void > value
Definition: priority.hh:93
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
Definition: synchronizing_word.hh:266
Main namespace of Awali.
Definition: ato.hh:22
decltype(internal::is_iterable_aux2< T, X >(priority::value)) is_iterable_with
Trait to test whether type T can be iterated over and assign its values to type X.
Definition: is_iterable.hxx:97