wilderfield
All Classes Files Functions
priority_map.hpp
Go to the documentation of this file.
1 // Copyright (c) [2024] [Bryan Wilder Field Lozano]
2 // Licensed under the MIT License. See LICENSE file in the project root for full
3 // license information.
4 
12 #ifndef INCLUDE_WILDERFIELD_PRIORITY_MAP_HPP_
13 #define INCLUDE_WILDERFIELD_PRIORITY_MAP_HPP_
14 
15 #include <algorithm>
16 #include <cstdint>
17 #include <functional>
18 #include <iterator>
19 #include <list>
20 #include <type_traits>
21 #include <unordered_map>
22 #include <unordered_set>
23 #include <utility>
24 
25 namespace wilderfield {
26 
39 template <typename KeyType, typename ValType,
40  typename Compare = std::greater<ValType>,
41  typename Hash = std::hash<KeyType>>
42 class PriorityMap final {
43  static_assert(std::is_arithmetic<ValType>::value,
44  "ValType must be a numeric type.");
45 
46  private:
47  Compare comp_;
48 
49  std::list<ValType> vals_;
50 
51  std::unordered_map<KeyType, typename std::list<ValType>::iterator, Hash>
52  keys_;
53 
54  std::unordered_map<ValType, std::unordered_set<KeyType>>
55  val_to_keys_;
56 
57  // Private member functions
58 
59  // Insert new key
60  void Insert(const KeyType& key, const ValType& new_val);
61 
62  // Update Key with Val
63  // This function can be used for increment, decrement, or assigning a new val
64  void Update(const KeyType& key, const ValType& new_val);
65 
66  // Get the value associated with a key.
67  ValType val(const KeyType& key) const { return *(keys_.at(key)); }
68 
69  public:
70  std::size_t Size() const {
71  return keys_.size();
72  }
73 
74  bool Empty() const {
75  return keys_.empty();
76  }
77 
78  std::size_t Count(const KeyType& key) const {
79  return keys_.count(key);
80  }
81 
82  std::pair<KeyType, ValType> Top()
83  const;
84 
85  std::size_t Erase(
86  const KeyType& key);
88 
89  void Pop();
90 
91  class Proxy;
92  Proxy operator[](const KeyType& key);
93 
94  // Proxy class to handle the increment operation.
95  class Proxy {
96  private:
97  PriorityMap* pm;
98  KeyType key;
99 
100  public:
101  Proxy(PriorityMap* pm, const KeyType& key) : pm(pm), key(key) {}
102 
103  Proxy& operator++() {
104  pm->Update(key, pm->val(key) + 1);
105  return *this;
106  }
107 
108  Proxy operator++(int) {
109  Proxy temp = *this;
110  ++(*this);
111  return temp;
112  }
113 
114  Proxy& operator--() {
115  pm->Update(key, pm->val(key) - 1);
116  return *this;
117  }
118 
119  Proxy operator--(int) {
120  Proxy temp = *this;
121  --(*this);
122  return temp;
123  }
124 
125  void operator=(const ValType& val) { pm->Update(key, val); }
126 
127  operator ValType() const { return pm->val(key); }
128  };
129 };
130 
131 // Out-of-line implementation of PriorityMap methods
132 
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); // For now avoid memory bloat
140  vals_.erase(old_it);
141  }
142  }
143  return keys_.erase(key);
144 }
145 
146 template <typename KeyType, typename ValType, typename Compare, typename Hash>
148  const {
149  if (vals_.empty()) {
150  throw std::out_of_range("Can't access top on an empty PriorityMap.");
151  }
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.");
155  }
156  // Return a pair consisting of one of the keys and the value.
157  return {*(val_to_keys_.at(val).begin()), val};
158 }
159 
160 template <typename KeyType, typename ValType, typename Compare, typename Hash>
162  if (vals_.empty()) {
163  throw std::out_of_range("Can't pop from empty PriorityMap.");
164  }
165 
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.");
169  }
170  KeyType key = *(val_to_keys_[*old_it].begin());
171 
172  val_to_keys_[*old_it].erase(key);
173  keys_.erase(key);
174 
175  // Remove node if it's empty
176  if (val_to_keys_[*old_it].empty()) {
177  val_to_keys_.erase(*old_it); // For now avoid memory bloat
178  vals_.erase(old_it);
179  }
180 }
181 
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);
187 
188  // True if minHeap
189  if (comp_(0, 1)) {
190  // Linear search towards end
191  auto insertion_point = std::find_if(
192  vals_.begin(), vals_.end(), [&](const auto val) { return val >= 0; });
193 
194  if (insertion_point == vals_.end() || (*insertion_point) != 0) {
195  insertion_point = vals_.insert(insertion_point, 0);
196  }
197 
198  keys_[key] = insertion_point;
199  } else { // maxHeap
200  // Linear search towards begin
201  auto insertion_point =
202  std::find_if(vals_.rbegin(), vals_.rend(),
203  [&](const auto val) { return val >= 0; });
204 
205  if (insertion_point == vals_.rend() || (*insertion_point) != 0) {
206  auto newIt = vals_.insert(insertion_point.base(), 0);
207  keys_[key] = newIt;
208  } else {
209  keys_[key] = std::next(insertion_point).base();
210  }
211  }
212  }
213 
214  Update(key, new_val);
215 }
216 
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];
221 
222  // Save Old Value
223  ValType oldVal = *old_it;
224 
225  if (oldVal == new_val) return;
226 
227  // Remove the key from the old association
228  keys_.erase(key);
229  val_to_keys_[oldVal].erase(key);
230 
231  // Make new association
232  val_to_keys_[new_val].insert(key);
233 
234  // True if minHeap and oldVal < new_val or if maxHeap and oldVal > new_val
235  if (comp_(oldVal, new_val)) {
236  // Linear search towards end
237  auto insertion_point =
238  std::find_if(old_it, vals_.end(), [&](const auto val) {
239  if (comp_(1, 0)) {
240  return val <= new_val;
241  }
242  return val >= new_val;
243  });
244 
245  if (insertion_point == vals_.end() || (*insertion_point) != new_val) {
246  insertion_point = vals_.insert(insertion_point, new_val);
247  }
248 
249  keys_[key] = insertion_point;
250  } else { // minHeap and oldVal > new_val or maxHeap and oldVal < new_val
251  // Need to search in reverse
252  typename std::list<ValType>::reverse_iterator old_rit(
253  old_it); // old_rit will point one element closer to begin
254 
255  // Linear search towards begin
256  auto insertion_point =
257  std::find_if(old_rit, vals_.rend(), [&](const auto val) {
258  if (comp_(0, 1)) {
259  return val <= new_val;
260  }
261  return val >= new_val;
262  });
263 
264  if (insertion_point == vals_.rend() || (*insertion_point) != new_val) {
265  auto newIt = vals_.insert(insertion_point.base(), new_val);
266  keys_[key] = newIt;
267  keys_[key] = std::next(insertion_point).base();
268  } else {
269  keys_[key] = std::next(insertion_point).base();
270  }
271  }
272 
273  // Remove the old node if it's empty
274  if (val_to_keys_[oldVal].empty()) {
275  val_to_keys_.erase(*old_it); // For now avoid memory bloat
276  vals_.erase(old_it);
277  }
278 }
279 
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) {
283  // If the key doesn't exist, create a new node with value 0
284  if (keys_.find(key) == keys_.end()) {
285  Insert(key, 0);
286  }
287  return Proxy(this, key);
288 }
289 
290 } // namespace wilderfield
291 
292 #endif // INCLUDE_WILDERFIELD_PRIORITY_MAP_HPP_
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