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-2021 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  list.erase(it->second);
208  map.erase(it);
209  }
210  else
211  return it->second;
212  }
213  auto res = list.insert(pos, pair_t(std::move(key),std::move(value)));
214  map.emplace(&(res->first),res);
215  return res;
216  }
217 
218 
225  bool overwrite_existing = false)
226  {
227  insert(begin(), std::move(key), std::move(value), overwrite_existing);
228  }
229 
230 
231  pair_t& front() { return list.front(); }
232  pair_t const& front() const { return list.front(); }
233 
234 
235  pair_t& back() { return list.back(); }
236  pair_t const& back() const { return list.back(); }
237 
238 
245  void push_back(key_t key, value_t value, bool overwrite_existing = false)
246  {
247  insert(end(), std::move(key), std::move(value), overwrite_existing);
248  }
249 
250 
251  /* Erases the binding pointed at by given iterator.
252  * Does nothing if @pname{pos} is equal to {@link end()}.
253  * @return an iterator pointing to the next binding.
254  */
255  iterator
257  {
258  if (pos == this->cend())
259  return this->end();
260  map.erase(&(pos->first));
261  return list.erase(pos);
262  }
263 
264 
268  size_type
269  erase(key_t const& key)
270  {
271  auto it = map.find(&key);
272  if (it == map.end())
273  return 0;
274  const_iterator it2 = it->second; // Somehow this is required because
275  map.erase(it); // unordered_map tries to hash
276  list.erase(it2); // its key before erasing from iterator.
277  return 1;
278  }
279 
280 
284  value_t&
285  at (key_t const& key)
286  {
287  auto it = map.find(&key);
288  if (it != map.end())
289  return it->second->second;
290  std::stringstream ss;
291  ss << "This linked_map does not have a binding with key" << key << ".";
292  throw std::out_of_range(ss.str());
293  }
294 
295 
299  value_t const&
300  at (key_t const& key)
301  const
302  {
303  auto it = map.find(&key);
304  if (it != map.end())
305  return it->second->second;
306  std::stringstream ss;
307  ss << "This linked_map does not have a binding with key" << key << ".";
308  throw std::out_of_range(ss.str());
309  }
310 
311 
312 
321  value_t&
323  {
324  auto it = map.find(&key);
325  if (it != map.end())
326  return it->second->second;
327  list.emplace_back(pair_t(std::move(key),value_t()));
328  iterator x = --list.end();
329  map[&(x->first)] = x;
330  return x->second;
331  }
332 
333 
336  void
338  {
339  list.sort([](pair_t x,pair_t y){return (x.first < y.first);});
340  remap(false);
341  }
342 
343 
345  template <class Compare>
346  void sort(Compare comp)
347  {
348  list.sort(comp);
349  remap(false);
350  }
351 
352 
354 
355  linked_map_t(std::initializer_list<pair_t> l) : list(std::move(l))
356  {remap(true);}
357 
358  linked_map_t(std::list<pair_t> l) : list(std::move(l))
359  {remap(true);}
360 
362  : list(other.list), map() {remap(false);}
363 
365  : list(std::move(other.list)), map(std::move(other.map)) {}
366  // ^^^^^^^^^^^^^^^^^^^^^^^^
367  // This assumes that the iterators are still valid
368  // after moving a std::list
369 
370 
382  template<class O>
384  O&& container, // /!\ This is a universal reference, not a rvalue reference
385  typename std::enable_if<
386  is_iterable_with<O,init_pair_t>::value,bool>::type require_remap = true)
387  {
389  for (auto& pair : container) {
390  if (b) // This is clearly a case
391  list.push_back(pair); // where C17 `if constexpr` would
392  else // be beneficial.
393  list.push_back(std::move(pair)); //
394  }
395  remap(require_remap);
396  }
397 
398 
399 
404  bool operator!=(self_type_t const& other)
405  {return !( (*this) == other);}
406 
407 
416  bool operator==(self_type_t const& other) {
417  return this->equals_as_list(other);
418  }
419 
420 
427  template<typename KeyEquality = E, typename ValueEquality = std::equal_to<V>>
428  bool equals_as_list(self_type_t const& other) const
429  {
430  KeyEquality ke;
431  ValueEquality ve;
432  const_iterator it1 = begin();
433  const_iterator it2 = other.begin();
434  while (it1 != end() && it2 != other.end()) {
435  if (!ke(it1->first,it2->first))
436  return false;
437  if (!ve(it1->second,it2->second))
438  return false;
439  ++it1;
440  ++it2;
441  }
442  return (it1 == end() && it2 == other.end());
443  }
444 
454  template<typename ValueEquality = std::equal_to<V>>
455  bool equals_as_map(self_type_t const& other) const
456  {
457  ValueEquality ve;
458  if (this->size() != other.size())
459  return false;
460  const_iterator end = this->end();
461  for(pair_t const& pair: other) {
462  const_iterator it = this->find(pair.first);
463  if (it == end)
464  return false;
465  if (!ve(pair.second,it->second))
466  return false;
467  }
468  return true;
469  }
470 };
471 
472 
473 
474 } // end of namespace awali
475 
476 #endif
awali::linked_map_t::linked_map_t
linked_map_t(linked_map_t< key_t, value_t > &&other)
Definition: linked_map.hxx:364
is_iterable.hxx
awali::linked_map_t::end
iterator end() noexcept
Definition: linked_map.hxx:144
awali::linked_map_t::erase
size_type erase(key_t const &key)
Deletes the value bound to key.
Definition: linked_map.hxx:269
awali::linked_map_t::begin
const_iterator begin() const noexcept
Definition: linked_map.hxx:146
awali::linked_map_t::erase
iterator erase(const_iterator pos)
Definition: linked_map.hxx:256
awali::linked_map_t::push_front
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:224
awali
Main namespace of Awali.
Definition: ato.hh:22
awali::is_iterable_with
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
awali::linked_map_t::self_type_t
linked_map_t< K, V, H, E > self_type_t
Definition: linked_map.hxx:74
awali::linked_map_t::map
map_t map
Definition: linked_map.hxx:90
awali::linked_map_t::operator!=
bool operator!=(self_type_t const &other)
Returns true if this linked_map_t is different from other.
Definition: linked_map.hxx:404
awali::linked_map_t::max_size
size_type max_size() const noexcept
Definition: linked_map.hxx:121
awali::linked_map_t::pair_t
std::pair< key_t const, value_t > pair_t
Definition: linked_map.hxx:77
awali::linked_map_t::cend
const_iterator cend() const noexcept
Definition: linked_map.hxx:150
awali::linked_map_t::size_type
map_t::size_type size_type
Definition: linked_map.hxx:87
awali::linked_map_t::end
const_iterator end() const noexcept
Definition: linked_map.hxx:147
awali::linked_map_t
Implemention of a linked hash-map.
Definition: linked_map.hxx:72
awali::linked_map_t::linked_map_t
linked_map_t(std::list< pair_t > l)
Definition: linked_map.hxx:358
awali::linked_map_t::max_load_factor
float max_load_factor() const noexcept
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:135
awali::linked_map_t::value_t
V value_t
Definition: linked_map.hxx:76
awali::linked_map_t::max_bucket_count
size_type max_bucket_count() const noexcept
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:131
awali::linked_map_t::front
pair_t const & front() const
Definition: linked_map.hxx:232
awali::linked_map_t::cbegin
const_iterator cbegin() const noexcept
Definition: linked_map.hxx:149
awali::linked_map_t::iterator
std::list< pair_t >::iterator iterator
Definition: linked_map.hxx:81
awali::linked_map_t::linked_map_t
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:383
awali::linked_map_t::back
pair_t const & back() const
Definition: linked_map.hxx:236
awali::linked_map_t::list_t
std::list< pair_t > list_t
Definition: linked_map.hxx:80
awali::linked_map_t::count
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
awali::linked_map_t::linked_map_t
linked_map_t(std::initializer_list< pair_t > l)
Definition: linked_map.hxx:355
awali::linked_map_t::back
pair_t & back()
Definition: linked_map.hxx:235
awali::linked_map_t::map_t
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
awali::pointed_hash_t
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
awali::linked_map_t::value_type
pair_t value_type
Definition: linked_map.hxx:78
awali::linked_map_t::init_pair_t
std::pair< key_t, value_t > init_pair_t
Definition: linked_map.hxx:79
awali::pointed_equal_t::operator()
bool operator()(K *key1, K *key2) const noexcept
Definition: linked_map.hxx:49
awali::priority::value
static constexpr TOP< void > value
Definition: priority.hh:93
awali::linked_map_t::begin
iterator begin() noexcept
Definition: linked_map.hxx:143
awali::linked_map_t::max_load_factor
void max_load_factor(float x)
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:137
awali::linked_map_t::reserve
void reserve(size_type n)
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:141
awali::linked_map_t::linked_map_t
linked_map_t(linked_map_t< key_t, value_t > const &other)
Definition: linked_map.hxx:361
awali::json::node_t
Definition: node.hh:191
awali::linked_map_t::key_t
K key_t
Definition: linked_map.hxx:75
awali::linked_map_t::empty
bool empty() const noexcept
Returns if this linked_map_t is empty.
Definition: linked_map.hxx:116
awali::linked_map_t::bucket_count
size_type bucket_count() const noexcept
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:127
awali::linked_map_t::load_factor
float load_factor() const noexcept
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:133
awali::linked_map_t::clear
void clear() noexcept
Clears this linked_map_t.
Definition: linked_map.hxx:124
awali::linked_map_t::find
const_iterator find(key_t const &key) const
Returns the position corresponding to the binding of key.
Definition: linked_map.hxx:170
awali::linked_map_t::size
size_type size() const noexcept
Returns the number of bindings in this linked_map_t.
Definition: linked_map.hxx:119
awali::linked_map_t::const_iterator
std::list< pair_t >::const_iterator const_iterator
Definition: linked_map.hxx:82
awali::linked_map_t::remap
void remap(bool hard)
Recompute map from list.
Definition: linked_map.hxx:101
awali::sttc::pair
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
Definition: synchronizing_word.hh:266
awali::linked_map_t::list
list_t list
Definition: linked_map.hxx:91
awali::linked_map_t::sort
void sort()
Sort this linked_map_t by key assuming operator< exists on key_t.
Definition: linked_map.hxx:337
awali::linked_map_t::rehash
void rehash(size_type n)
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:139
awali::linked_map_t::equals_as_list
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:428
awali::linked_map_t::at
value_t const & at(key_t const &key) const
Access value bound to key.
Definition: linked_map.hxx:300
awali::pointed_equal_t
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
awali::linked_map_t::linked_map_t
linked_map_t()
Definition: linked_map.hxx:353
awali::linked_map_t::operator[]
value_t & operator[](key_t key)
Access, modify or set the value bound to key.
Definition: linked_map.hxx:322
awali::linked_map_t::operator==
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:416
awali::linked_map_t::insert
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
awali::pointed_hash_t::operator()
std::size_t operator()(K *key) const noexcept
Definition: linked_map.hxx:36
awali::linked_map_t::equals_as_map
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:455
awali::linked_map_t::bucket_size
size_type bucket_size(unsigned n) const noexcept
Accessor directly inherited from std::unordered_map.
Definition: linked_map.hxx:129
awali::linked_map_t::at
value_t & at(key_t const &key)
Access value bound to key.
Definition: linked_map.hxx:285
awali::linked_map_t::sort
void sort(Compare comp)
Sort this linked_map_t by given comparison.
Definition: linked_map.hxx:346
awali::linked_map_t::front
pair_t & front()
Definition: linked_map.hxx:231
awali::linked_map_t::find
iterator find(key_t const &key)
Returns the position corresponding to the binding of key.
Definition: linked_map.hxx:157
awali::linked_map_t::push_back
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:245