12 #ifndef INCLUDE_WILDERFIELD_PRIORITY_MAP_HPP_
13 #define INCLUDE_WILDERFIELD_PRIORITY_MAP_HPP_
20 #include <type_traits>
21 #include <unordered_map>
22 #include <unordered_set>
25 namespace wilderfield {
39 template <
typename KeyType,
typename ValType,
40 typename Compare = std::greater<ValType>,
41 typename Hash = std::hash<KeyType>>
43 static_assert(std::is_arithmetic<ValType>::value,
44 "ValType must be a numeric type.");
49 std::list<ValType> vals_;
51 std::unordered_map<KeyType, typename std::list<ValType>::iterator, Hash>
54 std::unordered_map<ValType, std::unordered_set<KeyType>>
60 void Insert(
const KeyType& key,
const ValType& new_val);
64 void Update(
const KeyType& key,
const ValType& new_val);
67 ValType val(
const KeyType& key)
const {
return *(keys_.at(key)); }
78 std::size_t
Count(
const KeyType& key)
const {
79 return keys_.count(key);
82 std::pair<KeyType, ValType>
Top()
92 Proxy operator[](
const KeyType& key);
103 Proxy& operator++() {
104 pm->Update(key, pm->val(key) + 1);
108 Proxy operator++(
int) {
114 Proxy& operator--() {
115 pm->Update(key, pm->val(key) - 1);
119 Proxy operator--(
int) {
125 void operator=(
const ValType& val) { pm->Update(key, val); }
127 operator ValType()
const {
return pm->val(key); }
133 template <
typename KeyType,
typename ValType,
typename Compare,
typename Hash>
135 if (keys_.find(key) != keys_.end()) {
136 auto old_it = keys_[key];
137 val_to_keys_[*old_it].erase(key);
138 if (val_to_keys_[*old_it].empty()) {
139 val_to_keys_.erase(*old_it);
143 return keys_.erase(key);
146 template <
typename KeyType,
typename ValType,
typename Compare,
typename Hash>
150 throw std::out_of_range(
"Can't access top on an empty PriorityMap.");
152 const auto val = vals_.front();
153 if (val_to_keys_.at(val).empty()) {
154 throw std::logic_error(
"Inconsistent state: Val with no keys.");
157 return {*(val_to_keys_.at(val).begin()), val};
160 template <
typename KeyType,
typename ValType,
typename Compare,
typename Hash>
163 throw std::out_of_range(
"Can't pop from empty PriorityMap.");
166 auto old_it = vals_.begin();
167 if (val_to_keys_[*old_it].empty()) {
168 throw std::logic_error(
"Inconsistent state: Val with no keys.");
170 KeyType key = *(val_to_keys_[*old_it].begin());
172 val_to_keys_[*old_it].erase(key);
176 if (val_to_keys_[*old_it].empty()) {
177 val_to_keys_.erase(*old_it);
182 template <
typename KeyType,
typename ValType,
typename Compare,
typename Hash>
184 const KeyType& key,
const ValType& new_val) {
185 if (keys_.find(key) == keys_.end()) {
186 val_to_keys_[0].insert(key);
191 auto insertion_point = std::find_if(
192 vals_.begin(), vals_.end(), [&](
const auto val) { return val >= 0; });
194 if (insertion_point == vals_.end() || (*insertion_point) != 0) {
195 insertion_point = vals_.insert(insertion_point, 0);
198 keys_[key] = insertion_point;
201 auto insertion_point =
202 std::find_if(vals_.rbegin(), vals_.rend(),
203 [&](
const auto val) { return val >= 0; });
205 if (insertion_point == vals_.rend() || (*insertion_point) != 0) {
206 auto newIt = vals_.insert(insertion_point.base(), 0);
209 keys_[key] = std::next(insertion_point).base();
214 Update(key, new_val);
217 template <
typename KeyType,
typename ValType,
typename Compare,
typename Hash>
218 void PriorityMap<KeyType, ValType, Compare, Hash>::Update(
219 const KeyType& key,
const ValType& new_val) {
220 auto old_it = keys_[key];
223 ValType oldVal = *old_it;
225 if (oldVal == new_val)
return;
229 val_to_keys_[oldVal].erase(key);
232 val_to_keys_[new_val].insert(key);
235 if (comp_(oldVal, new_val)) {
237 auto insertion_point =
238 std::find_if(old_it, vals_.end(), [&](
const auto val) {
240 return val <= new_val;
242 return val >= new_val;
245 if (insertion_point == vals_.end() || (*insertion_point) != new_val) {
246 insertion_point = vals_.insert(insertion_point, new_val);
249 keys_[key] = insertion_point;
252 typename std::list<ValType>::reverse_iterator old_rit(
256 auto insertion_point =
257 std::find_if(old_rit, vals_.rend(), [&](
const auto val) {
259 return val <= new_val;
261 return val >= new_val;
264 if (insertion_point == vals_.rend() || (*insertion_point) != new_val) {
265 auto newIt = vals_.insert(insertion_point.base(), new_val);
267 keys_[key] = std::next(insertion_point).base();
269 keys_[key] = std::next(insertion_point).base();
274 if (val_to_keys_[oldVal].empty()) {
275 val_to_keys_.erase(*old_it);
280 template <
typename KeyType,
typename ValType,
typename Compare,
typename Hash>
281 typename PriorityMap<KeyType, ValType, Compare, Hash>::Proxy
282 PriorityMap<KeyType, ValType, Compare, Hash>::operator[](
const KeyType& key) {
284 if (keys_.find(key) == keys_.end()) {
287 return Proxy(
this, key);
Definition: priority_map.hpp:95
Priority map class.
Definition: priority_map.hpp:42
std::size_t Count(const KeyType &key) const
Returns the count of a particular key in the map.
Definition: priority_map.hpp:78
std::size_t Erase(const KeyType &key)
Definition: priority_map.hpp:134
std::pair< KeyType, ValType > Top() const
Returns the top element (key-value pair) in the priority map.
Definition: priority_map.hpp:147
std::size_t Size() const
Returns the number of unique keys in the priority map.
Definition: priority_map.hpp:70
bool Empty() const
Checks whether the priority map is empty.
Definition: priority_map.hpp:74
void Pop()
Removes the top element from the priority map.
Definition: priority_map.hpp:161