Awali
Another Weighted Automata library
linkedhashmap.hh
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_MISC_LINKEDHASHMAP_HH
18 #define AWALI_MISC_LINKEDHASHMAP_HH
19 
20 #include<unordered_map>
21 #include<vector>
22 
23 namespace awali {
24  namespace sttc {
25  namespace internal {
26  /* This structure provides the minimal amount of services which is required by hopcroft algorithm:
27  * - random access in (amortized) constant time
28  * - iteration over keys in linear time
29  */
30  template<typename K, typename V>
31  struct linked_hash_map {
32  private:
33  std::unordered_map<K,V> map_;
34  std::vector<K> list_;
35  public:
36  const std::vector<K>& domain() const {
37  return list_;
38  }
39 
40  V& operator[](const K& k) {
41  if(map_.count(k)==0)
42  list_.emplace_back(k);
43  return map_[k];
44  }
45 
46  unsigned count(const K& k) const {
47  return map_.count(k);
48  }
49 
50  void clear() {
51  map_.clear();
52  list_.clear();
53  }
54  };
55 
56  template<typename K, typename V>
58  private:
59  const linked_hash_map<K,V>& map_;
60  typename std::vector<K>::const_iterator current_;
61  public:
63  map_(map),
64  current_(map.domain().begin())
65  {}
66 
67  lhm_values_const_iterator(linked_hash_map<K,V>& map, typename std::vector<K>::const_iterator& current) :
68  map_(map),
69  current_(current)
70  {}
71 
72  const V& operator*() const {
73  return map_[*current_];
74  }
75 
77  ++current_;
78  }
79 
81  return current_==it.current_;
82  }
83 
85  return current_!=it.current_;
86  }
87  };
88 
89  template<typename K, typename V>
90  struct lhm_values {
91  private:
92  const linked_hash_map<K,V>& map_;
94  public:
96  map_(map)
97  {}
98 
99  iterator begin() const {
100  return iterator(map_);
101  }
102 
103  iterator end() const {
104  return iterator(map_, map_.domain().end());
105  }
106  };
107  }
108  }
109 }
110 #endif
automaton_t domain(transducer_t tdc)
Returns the automaton corresponding to the second tape of the transducer.
auto map(const std::tuple< Ts... > &ts, Fun f) -> decltype(map_tuple_(f, ts, make_index_sequence< sizeof...(Ts)>()))
Map a function on a tuple, return tuple of the results.
Definition: tuple.hh:134
Main namespace of Awali.
Definition: ato.hh:22
lhm_values_const_iterator & operator++()
Definition: linkedhashmap.hh:76
lhm_values_const_iterator(linked_hash_map< K, V > &map)
Definition: linkedhashmap.hh:62
lhm_values_const_iterator & operator!=(const lhm_values_const_iterator &it) const
Definition: linkedhashmap.hh:84
lhm_values_const_iterator & operator==(const lhm_values_const_iterator &it) const
Definition: linkedhashmap.hh:80
lhm_values_const_iterator(linked_hash_map< K, V > &map, typename std::vector< K >::const_iterator &current)
Definition: linkedhashmap.hh:67
const V & operator*() const
Definition: linkedhashmap.hh:72
Definition: linkedhashmap.hh:90
lhm_values(linked_hash_map< K, V > &map)
Definition: linkedhashmap.hh:95
iterator begin() const
Definition: linkedhashmap.hh:99
iterator end() const
Definition: linkedhashmap.hh:103
Definition: linkedhashmap.hh:31
unsigned count(const K &k) const
Definition: linkedhashmap.hh:46
const std::vector< K > & domain() const
Definition: linkedhashmap.hh:36
V & operator[](const K &k)
Definition: linkedhashmap.hh:40
void clear()
Definition: linkedhashmap.hh:50