1//! @file cache.hpp
2//! @author ryftchen
3//! @brief The declarations (cache) in the data structure module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2026 ryftchen. All rights reserved.
6
7#pragma once
8
9#include <list>
10#include <map>
11#include <numeric>
12#include <optional>
13#include <unordered_map>
14#include <vector>
15
16//! @brief The data structure module.
17namespace data_structure // NOLINT(modernize-concat-nested-namespaces)
18{
19//! @brief Cache-related functions in the data structure module.
20namespace cache
21{
22//! @brief Brief function description.
23//! @return function description (module_function)
24inline static const char* description() noexcept
25{
26 return "DS_CACHE";
27}
28extern const char* version() noexcept;
29
30//! @brief The FIFO (first in first out) cache replacement policy.
31//! @tparam Key - type of cache key
32//! @tparam Value - type of value stored in the cache
33template <typename Key, typename Value>
34class FIFO
35{
36public:
37 //! @brief Construct a new FIFO object.
38 //! @param capacity - maximum number of elements the cache can hold
39 //! @param maxLoadFactor - maximum load factor for the internal hash map
40 explicit FIFO(const std::size_t capacity, const float maxLoadFactor = 1.0F);
41
42 //! @brief Insert or update an element by using the value by key.
43 //! @param key - key associated with the value
44 //! @param value - value to be inserted or updated
45 void insert(const Key& key, Value value);
46 //! @brief Insert a range of key-value pairs.
47 //! @tparam Range - type of range of key-value pairs
48 //! @param keyValueRange - range of key-value pairs to insert
49 //! @return number of elements inserted
50 template <typename Range>
51 std::size_t insertRange(Range&& keyValueRange);
52 //! @brief Erase an element by key.
53 //! @param key - key of the element to remove
54 //! @return be found and erased or not
55 bool erase(const Key& key);
56 //! @brief Erase a range of elements by using iterators.
57 //! @tparam Iterator - type of pair iterator
58 //! @param begin - iterator to the beginning of pairs
59 //! @param end - iterator to the ending of pairs
60 //! @return number of elements successfully erased
61 template <typename Iterator>
62 std::size_t erase(Iterator begin, const Iterator end);
63 //! @brief Erase a range of elements by using a range of keys.
64 //! @tparam Range - type of range of keys
65 //! @param keyRange - range of keys to be erased
66 //! @return number of elements successfully erased
67 template <typename Range>
68 std::size_t eraseRange(const Range& keyRange);
69 //! @brief Find a value by key.
70 //! @param key - key to search for
71 //! @return optional value
72 std::optional<Value> find(const Key& key);
73 //! @brief Find a range of values by keys by using iterators.
74 //! @tparam Iterator - type of pair iterator
75 //! @param begin - iterator to the beginning of pairs
76 //! @param end - iterator to the ending of pairs
77 //! @param distance - optional pre-allocation hint for result container size
78 //! @return container of key-optional-value pairs
79 template <typename Iterator>
80 auto find(Iterator begin, const Iterator end, const std::size_t distance = 0)
81 -> std::vector<std::pair<Key, std::optional<Value>>>;
82 //! @brief Find a range of values by keys by using a range of keys.
83 //! @tparam Range - type of range of keys
84 //! @param keyRange - range of keys to be searched
85 //! @return container of key-optional-value pairs
86 template <typename Range>
87 auto findRange(const Range& keyRange) -> std::vector<std::pair<Key, std::optional<Value>>>;
88 //! @brief Resolve values for a range of keys in-place by using iterators.
89 //! @tparam Iterator - type of pair iterator
90 //! @param begin - iterator to the beginning of pairs
91 //! @param end - iterator to the ending of pairs
92 template <typename Iterator>
93 void resolveRange(Iterator begin, const Iterator end);
94 //! @brief Resolve values for a range of keys in-place by using a range of key-optional-value pairs.
95 //! @tparam Range - type of range of key-optional-value pairs
96 //! @param keyOptValueRange - range of key-optional-value pairs to resolve
97 template <typename Range>
98 void resolveRange(Range& keyOptValueRange);
99
100 //! @brief Check whether any elements do not exist in the cache.
101 //! @return any elements do not exist or exist
102 [[nodiscard]] bool empty() const;
103 //! @brief Get the number of elements currently in the cache.
104 //! @return number of used slots
105 [[nodiscard]] std::size_t size() const;
106 //! @brief Get the total capacity of the cache.
107 //! @return maximum number of elements the cache can hold
108 [[nodiscard]] std::size_t capacity() const;
109
110private:
111 struct Element;
112 //! @brief Alias for the iterator of the internal FIFO list.
113 using FIFOIter = typename std::list<Element>::iterator;
114 //! @brief Alias for the iterator of the internal hash map.
115 using KeyedIter = typename std::unordered_map<Key, FIFOIter>::iterator;
116 //! @brief Element metadata.
117 struct Element
118 {
119 //! @brief Optional iterator pointing to the key in the hash map.
120 std::optional<KeyedIter> keyedPosition{};
121 //! @brief The value stored in the element.
122 Value value{};
123 };
124
125 //! @brief The ordering of the FIFO queue of elements.
126 std::list<Element> fifoList{};
127 //! @brief Hash map for fast key-to-element lookup.
128 std::unordered_map<Key, FIFOIter> keyedElements{};
129 //! @brief Number of elements.
130 std::size_t usedSize{0};
131
132 //! @brief Operation of inserting or updating.
133 //! @param key - key associated with the value
134 //! @param value - value to be inserted or updated
135 void doInsertOrUpdate(const Key& key, Value&& value);
136 //! @brief Operation of inserting.
137 //! @param key - key associated with the value
138 //! @param value - value to be inserted
139 void doInsert(const Key& key, Value&& value);
140 //! @brief Operation of updating.
141 //! @param keyedPos - iterator to the element in the hash map
142 //! @param value - value to be updated
143 void doUpdate(const KeyedIter keyedPos, Value&& value);
144 //! @brief Operation of erasing.
145 //! @param fifoPos - iterator to the element in the FIFO list
146 void doErase(const FIFOIter fifoPos);
147 //! @brief Operation of finding.
148 //! @param key - key to search for
149 //! @return optional value
150 std::optional<Value> doFind(const Key& key);
151};
152
153template <typename Key, typename Value>
154FIFO<Key, Value>::FIFO(const std::size_t capacity, const float maxLoadFactor) : fifoList{capacity}
155{
156 keyedElements.max_load_factor(maxLoadFactor);
157 keyedElements.reserve(capacity);
158}
159
160template <typename Key, typename Value>
161void FIFO<Key, Value>::insert(const Key& key, Value value)
162{
163 doInsertOrUpdate(key, value: std::move(value));
164}
165
166template <typename Key, typename Value>
167template <typename Range>
168std::size_t FIFO<Key, Value>::insertRange(Range&& keyValueRange)
169{
170 auto&& range = std::forward<Range>(keyValueRange);
171 std::size_t inserted = 0;
172 for (auto& [key, value] : range)
173 {
174 doInsertOrUpdate(key, value: std::move(value));
175 ++inserted;
176 }
177 return inserted;
178}
179
180template <typename Key, typename Value>
181bool FIFO<Key, Value>::erase(const Key& key)
182{
183 if (const auto keyedPos = keyedElements.find(key); keyedPos != keyedElements.cend())
184 {
185 doErase(fifoPos: keyedPos->second);
186 return true;
187 }
188 return false;
189}
190
191template <typename Key, typename Value>
192template <typename Iterator>
193std::size_t FIFO<Key, Value>::erase(Iterator begin, const Iterator end)
194{
195 std::size_t erased = 0;
196 while (begin != end)
197 {
198 if (const auto keyedPos = keyedElements.find(*begin); keyedPos != keyedElements.cend())
199 {
200 ++erased;
201 doErase(fifoPos: keyedPos->second);
202 }
203 ++begin;
204 }
205 return erased;
206}
207
208template <typename Key, typename Value>
209template <typename Range>
210std::size_t FIFO<Key, Value>::eraseRange(const Range& keyRange)
211{
212 return erase(std::cbegin(keyRange), std::cend(keyRange));
213}
214
215template <typename Key, typename Value>
216std::optional<Value> FIFO<Key, Value>::find(const Key& key)
217{
218 return doFind(key);
219}
220
221template <typename Key, typename Value>
222template <typename Iterator>
223auto FIFO<Key, Value>::find(Iterator begin, const Iterator end, const std::size_t distance)
224 -> std::vector<std::pair<Key, std::optional<Value>>>
225{
226 std::vector<std::pair<Key, std::optional<Value>>> result{};
227 if (distance > 0)
228 {
229 result.reserve(distance);
230 }
231 while (begin != end)
232 {
233 result.emplace_back(*begin, doFind(key: *begin));
234 ++begin;
235 }
236 return result;
237}
238
239template <typename Key, typename Value>
240template <typename Range>
241auto FIFO<Key, Value>::findRange(const Range& keyRange) -> std::vector<std::pair<Key, std::optional<Value>>>
242{
243 return find(std::cbegin(keyRange), std::cend(keyRange), std::size(keyRange));
244}
245
246template <typename Key, typename Value>
247template <typename Iterator>
248void FIFO<Key, Value>::resolveRange(Iterator begin, const Iterator end)
249{
250 while (begin != end)
251 {
252 auto& [key, optValue] = *begin;
253 optValue = doFind(key);
254 ++begin;
255 }
256}
257
258template <typename Key, typename Value>
259template <typename Range>
260void FIFO<Key, Value>::resolveRange(Range& keyOptValueRange)
261{
262 return resolveRange(std::begin(keyOptValueRange), std::end(keyOptValueRange));
263}
264
265template <typename Key, typename Value>
266bool FIFO<Key, Value>::empty() const
267{
268 return usedSize == 0;
269}
270
271template <typename Key, typename Value>
272std::size_t FIFO<Key, Value>::size() const
273{
274 return usedSize;
275}
276
277template <typename Key, typename Value>
278std::size_t FIFO<Key, Value>::capacity() const
279{
280 return fifoList.size();
281}
282
283template <typename Key, typename Value>
284void FIFO<Key, Value>::doInsertOrUpdate(const Key& key, Value&& value)
285{
286 if (const auto keyedPos = keyedElements.find(key); keyedPos != keyedElements.cend())
287 {
288 doUpdate(keyedPos, value: std::move(value));
289 }
290 else
291 {
292 doInsert(key, value: std::move(value));
293 }
294}
295
296template <typename Key, typename Value>
297void FIFO<Key, Value>::doInsert(const Key& key, Value&& value)
298{
299 fifoList.splice(fifoList.cend(), fifoList, fifoList.cbegin());
300 auto lastElemPos = std::prev(fifoList.end());
301 auto& elem = *lastElemPos;
302 if (elem.keyedPosition.has_value())
303 {
304 keyedElements.erase(elem.keyedPosition.value());
305 }
306 else
307 {
308 ++usedSize;
309 }
310
311 elem.value = std::move(value);
312 elem.keyedPosition = keyedElements.emplace(key, lastElemPos).first;
313}
314
315template <typename Key, typename Value>
316void FIFO<Key, Value>::doUpdate(const KeyedIter keyedPos, Value&& value)
317{
318 auto& elem = *keyedPos->second;
319 elem.value = std::move(value);
320}
321
322template <typename Key, typename Value>
323void FIFO<Key, Value>::doErase(const FIFOIter fifoPos)
324{
325 auto& elem = *fifoPos;
326 if (fifoPos != fifoList.cbegin())
327 {
328 fifoList.splice(fifoList.cbegin(), fifoList, fifoPos);
329 }
330 if (elem.keyedPosition.has_value())
331 {
332 keyedElements.erase(elem.keyedPosition.value());
333 elem.keyedPosition = std::nullopt;
334 }
335
336 --usedSize;
337}
338
339template <typename Key, typename Value>
340std::optional<Value> FIFO<Key, Value>::doFind(const Key& key)
341{
342 if (const auto keyedPos = keyedElements.find(key); keyedPos != keyedElements.cend())
343 {
344 const auto& elem = *keyedPos->second;
345 return std::make_optional(elem.value);
346 }
347 return std::nullopt;
348}
349
350//! @brief The LFU (least frequently used) cache replacement policy.
351//! @tparam Key - type of cache key
352//! @tparam Value - type of value stored in the cache
353template <typename Key, typename Value>
354class LFU
355{
356public:
357 //! @brief Construct a new LFU object.
358 //! @param capacity - maximum number of elements the cache can hold
359 //! @param maxLoadFactor - maximum load factor for the internal hash map
360 explicit LFU(const std::size_t capacity, const float maxLoadFactor = 1.0F);
361
362 //! @brief Insert or update an element by using the value by key.
363 //! @param key - key associated with the value
364 //! @param value - value to be inserted or updated
365 void insert(const Key& key, Value value);
366 //! @brief Insert a range of key-value pairs.
367 //! @tparam Range - type of range of key-value pairs
368 //! @param keyValueRange - range of key-value pairs to insert
369 //! @return number of elements inserted
370 template <typename Range>
371 std::size_t insertRange(Range&& keyValueRange);
372 //! @brief Erase an element by key.
373 //! @param key - key of the element to remove
374 //! @return be found and erased or not
375 bool erase(const Key& key);
376 //! @brief Erase a range of elements by using a range of keys.
377 //! @tparam Range - type of range of keys
378 //! @param keyRange - range of keys to be erased
379 //! @return number of elements successfully erased
380 template <typename Range>
381 std::size_t eraseRange(const Range& keyRange);
382 //! @brief Find a value by key.
383 //! @param key - key to search for
384 //! @param peek - whether peek
385 //! @return optional value
386 std::optional<Value> find(const Key& key, const bool peek = false);
387 //! @brief Find a value with refcount by key.
388 //! @param key - key to search for
389 //! @param peek - whether peek
390 //! @return optional value with refcount
391 auto findWithRefcount(const Key& key, const bool peek = false) -> std::optional<std::pair<Value, std::size_t>>;
392 //! @brief Find a range of values by keys by using a range of keys.
393 //! @tparam Range - type of range of keys
394 //! @param keyRange - range of keys to be searched
395 //! @param peek - whether peek
396 //! @return container of key-optional-value pairs
397 template <typename Range>
398 auto findRange(const Range& keyRange, const bool peek = false) -> std::vector<std::pair<Key, std::optional<Value>>>;
399 //! @brief Resolve values for a range of keys in-place by using a range of key-optional-value pairs.
400 //! @tparam Range - type of range of key-optional-value pairs
401 //! @param keyOptValueRange - range of key-optional-value pairs to resolve
402 //! @param peek - whether peek
403 template <typename Range>
404 void resolveRange(Range& keyOptValueRange, const bool peek = false);
405
406 //! @brief Check whether any elements do not exist in the cache.
407 //! @return any elements do not exist or exist
408 [[nodiscard]] bool empty() const;
409 //! @brief Get the number of elements currently in the cache.
410 //! @return number of used slots
411 [[nodiscard]] std::size_t size() const;
412 //! @brief Get the total capacity of the cache.
413 //! @return maximum number of elements the cache can hold
414 [[nodiscard]] std::size_t capacity() const;
415
416private:
417 struct Element;
418 //! @brief Alias for the iterator of the internal open slot list.
419 using OpenSlotIter = typename std::list<Element>::iterator;
420 //! @brief Alias for the iterator of the internal LFU list.
421 using LFUIter = typename std::multimap<std::size_t, OpenSlotIter>::iterator;
422 //! @brief Alias for the iterator of the internal hash map.
423 using KeyedIter = typename std::unordered_map<Key, OpenSlotIter>::iterator;
424 //! @brief Element metadata.
425 struct Element
426 {
427 //! @brief Iterator pointing to the key in the hash map.
428 KeyedIter keyedPosition{};
429 //! @brief Iterator pointing to the LFU list.
430 LFUIter lfuPosition{};
431 //! @brief The value stored in the element.
432 Value value{};
433 };
434
435 //! @brief The open list of unused slots for elements.
436 std::list<Element> openSlotList{};
437 //! @brief The end of the open list. It is used to pull open slots from.
438 typename std::list<Element>::iterator openSlotListEnd{};
439 //! @brief The sorted map stores the number of times each element has been used.
440 std::multimap<std::size_t, OpenSlotIter> lfuList{};
441 //! @brief Hash map for fast key-to-element lookup.
442 std::unordered_map<Key, OpenSlotIter> keyedElements{};
443 //! @brief Number of elements.
444 std::size_t usedSize{0};
445
446 //! @brief Operation of inserting or updating.
447 //! @param key - key associated with the value
448 //! @param value - value to be inserted or updated
449 void doInsertOrUpdate(const Key& key, Value&& value);
450 //! @brief Operation of inserting.
451 //! @param key - key associated with the value
452 //! @param value - value to be inserted
453 void doInsert(const Key& key, Value&& value);
454 //! @brief Operation of updating.
455 //! @param keyedPos - iterator to the element in the hash map
456 //! @param value - value to be updated
457 void doUpdate(const KeyedIter keyedPos, Value&& value);
458 //! @brief Operation of erasing.
459 //! @param openSlotPos - iterator to the element in the open slot list
460 void doErase(const OpenSlotIter openSlotPos);
461 //! @brief Operation of finding.
462 //! @param key - key to search for
463 //! @param peek - whether peek
464 //! @return optional value
465 std::optional<Value> doFind(const Key& key, const bool peek);
466 //! @brief Operation of finding with refcount.
467 //! @param key - key to search for
468 //! @param peek - whether peek
469 //! @return optional value with refcount
470 auto doFindWithRefcount(const Key& key, const bool peek) -> std::optional<std::pair<Value, std::size_t>>;
471 //! @brief Operation of accessing.
472 //! @param elem - element to be accessed
473 void doAccess(Element& elem);
474 //! @brief Operation of pruning.
475 void doPrune();
476};
477
478template <typename Key, typename Value>
479LFU<Key, Value>::LFU(const std::size_t capacity, const float maxLoadFactor) :
480 openSlotList{capacity}, openSlotListEnd{openSlotList.begin()}
481{
482 keyedElements.max_load_factor(maxLoadFactor);
483 keyedElements.reserve(capacity);
484}
485
486template <typename Key, typename Value>
487void LFU<Key, Value>::insert(const Key& key, Value value)
488{
489 doInsertOrUpdate(key, value: std::move(value));
490}
491
492template <typename Key, typename Value>
493template <typename Range>
494std::size_t LFU<Key, Value>::insertRange(Range&& keyValueRange)
495{
496 auto&& range = std::forward<Range>(keyValueRange);
497 std::size_t inserted = 0;
498 for (auto& [key, value] : range)
499 {
500 doInsertOrUpdate(key, value: std::move(value));
501 ++inserted;
502 }
503 return inserted;
504}
505
506template <typename Key, typename Value>
507bool LFU<Key, Value>::erase(const Key& key)
508{
509 if (const auto keyedPos = keyedElements.find(key); keyedPos != keyedElements.cend())
510 {
511 doErase(openSlotPos: keyedPos->second);
512 return true;
513 }
514 return false;
515}
516
517template <typename Key, typename Value>
518template <typename Range>
519std::size_t LFU<Key, Value>::eraseRange(const Range& keyRange)
520{
521 std::size_t erased = 0;
522 for (const auto& key : keyRange)
523 {
524 if (const auto keyedPos = keyedElements.find(key); keyedPos != keyedElements.cend())
525 {
526 ++erased;
527 doErase(openSlotPos: keyedPos->second);
528 }
529 }
530 return erased;
531}
532
533template <typename Key, typename Value>
534std::optional<Value> LFU<Key, Value>::find(const Key& key, const bool peek)
535{
536 return doFind(key, peek);
537}
538
539template <typename Key, typename Value>
540auto LFU<Key, Value>::findWithRefcount(const Key& key, const bool peek) -> std::optional<std::pair<Value, std::size_t>>
541{
542 return doFindWithRefcount(key, peek);
543}
544
545template <typename Key, typename Value>
546template <typename Range>
547auto LFU<Key, Value>::findRange(const Range& keyRange, const bool peek)
548 -> std::vector<std::pair<Key, std::optional<Value>>>
549{
550 std::vector<std::pair<Key, std::optional<Value>>> result{};
551 result.reserve(std::size(keyRange));
552 for (const auto& key : keyRange)
553 {
554 result.emplace_back(key, doFind(key, peek));
555 }
556 return result;
557}
558
559template <typename Key, typename Value>
560template <typename Range>
561void LFU<Key, Value>::resolveRange(Range& keyOptValueRange, const bool peek)
562{
563 for (auto& [key, optValue] : keyOptValueRange)
564 {
565 optValue = doFind(key, peek);
566 }
567}
568
569template <typename Key, typename Value>
570bool LFU<Key, Value>::empty() const
571{
572 return usedSize == 0;
573}
574
575template <typename Key, typename Value>
576std::size_t LFU<Key, Value>::size() const
577{
578 return usedSize;
579}
580
581template <typename Key, typename Value>
582std::size_t LFU<Key, Value>::capacity() const
583{
584 return openSlotList.size();
585}
586
587template <typename Key, typename Value>
588void LFU<Key, Value>::doInsertOrUpdate(const Key& key, Value&& value)
589{
590 if (const auto keyedPos = keyedElements.find(key); keyedPos != keyedElements.cend())
591 {
592 doUpdate(keyedPos, value: std::move(value));
593 }
594 else
595 {
596 doInsert(key, value: std::move(value));
597 }
598}
599
600template <typename Key, typename Value>
601void LFU<Key, Value>::doInsert(const Key& key, Value&& value)
602{
603 if (usedSize >= openSlotList.size())
604 {
605 doPrune();
606 }
607
608 const auto keyedPos = keyedElements.emplace(key, openSlotListEnd).first;
609 const auto lfuPos = lfuList.emplace(1, openSlotListEnd);
610 auto& elem = *openSlotListEnd;
611 elem.value = std::move(value);
612 elem.keyedPosition = keyedPos;
613 elem.lfuPosition = lfuPos;
614
615 ++openSlotListEnd;
616 ++usedSize;
617}
618
619template <typename Key, typename Value>
620void LFU<Key, Value>::doUpdate(const KeyedIter keyedPos, Value&& value)
621{
622 auto& elem = *keyedPos->second;
623 elem.value = std::move(value);
624
625 doAccess(elem);
626}
627
628template <typename Key, typename Value>
629void LFU<Key, Value>::doErase(const OpenSlotIter openSlotPos)
630{
631 auto& elem = *openSlotPos;
632 if (openSlotPos != std::prev(openSlotListEnd))
633 {
634 openSlotList.splice(openSlotListEnd, openSlotList, openSlotPos);
635 }
636 --openSlotListEnd;
637
638 keyedElements.erase(elem.keyedPosition);
639 lfuList.erase(elem.lfuPosition);
640 --usedSize;
641}
642
643template <typename Key, typename Value>
644std::optional<Value> LFU<Key, Value>::doFind(const Key& key, const bool peek)
645{
646 if (const auto keyedPos = keyedElements.find(key); keyedPos != keyedElements.cend())
647 {
648 auto& elem = *keyedPos->second;
649 if (!peek)
650 {
651 doAccess(elem);
652 }
653 return std::make_optional(elem.value);
654 }
655 return std::nullopt;
656}
657
658template <typename Key, typename Value>
659auto LFU<Key, Value>::doFindWithRefcount(const Key& key, const bool peek)
660 -> std::optional<std::pair<Value, std::size_t>>
661{
662 if (const auto keyedPos = keyedElements.find(key); keyedPos != keyedElements.cend())
663 {
664 auto& elem = *keyedPos->second;
665 if (!peek)
666 {
667 doAccess(elem);
668 }
669 return std::make_optional(std::make_pair(elem.value, elem.lfuPosition->first));
670 }
671 return std::nullopt;
672}
673
674template <typename Key, typename Value>
675void LFU<Key, Value>::doAccess(Element& elem)
676{
677 const auto refcount = elem.lfuPosition->first;
678 lfuList.erase(elem.lfuPosition);
679 elem.lfuPosition = lfuList.emplace(refcount + 1, elem.keyedPosition->second);
680}
681
682template <typename Key, typename Value>
683void LFU<Key, Value>::doPrune()
684{
685 if (usedSize > 0)
686 {
687 doErase(openSlotPos: lfuList.cbegin()->second);
688 }
689}
690
691//! @brief The LRU (least recently used) cache replacement policy.
692//! @tparam Key - type of cache key
693//! @tparam Value - type of value stored in the cache
694template <typename Key, typename Value>
695class LRU
696{
697public:
698 //! @brief Construct a new LRU object.
699 //! @param capacity - maximum number of elements the cache can hold
700 //! @param maxLoadFactor - maximum load factor for the internal hash map
701 explicit LRU(const std::size_t capacity, const float maxLoadFactor = 1.0F);
702
703 //! @brief Insert or update an element by using the value by key.
704 //! @param key - key associated with the value
705 //! @param value - value to be inserted or updated
706 void insert(const Key& key, Value value);
707 //! @brief Insert a range of key-value pairs.
708 //! @tparam Range - type of range of key-value pairs
709 //! @param keyValueRange - range of key-value pairs to insert
710 //! @return number of elements inserted
711 template <typename Range>
712 std::size_t insertRange(Range&& keyValueRange);
713 //! @brief Erase an element by key.
714 //! @param key - key of the element to remove
715 //! @return be found and erased or not
716 bool erase(const Key& key);
717 //! @brief Erase a range of elements by using a range of keys.
718 //! @tparam Range - type of range of keys
719 //! @param keyRange - range of keys to be erased
720 //! @return number of elements successfully erased
721 template <typename Range>
722 std::size_t eraseRange(const Range& keyRange);
723 //! @brief Find a value by key.
724 //! @param key - key to search for
725 //! @param peek - whether peek
726 //! @return optional value
727 std::optional<Value> find(const Key& key, const bool peek = false);
728 //! @brief Find a range of values by keys by using a range of keys.
729 //! @tparam Range - type of range of keys
730 //! @param keyRange - range of keys to be searched
731 //! @param peek - whether peek
732 //! @return container of key-optional-value pairs
733 template <typename Range>
734 auto findRange(const Range& keyRange, const bool peek = false) -> std::vector<std::pair<Key, std::optional<Value>>>;
735 //! @brief Resolve values for a range of keys in-place by using a range of key-optional-value pairs.
736 //! @tparam Range - type of range of key-optional-value pairs
737 //! @param keyOptValueRange - range of key-optional-value pairs to resolve
738 //! @param peek - whether peek
739 template <typename Range>
740 void resolveRange(Range& keyOptValueRange, const bool peek = false);
741
742 //! @brief Check whether any elements do not exist in the cache.
743 //! @return any elements do not exist or exist
744 [[nodiscard]] bool empty() const;
745 //! @brief Get the number of elements currently in the cache.
746 //! @return number of used slots
747 [[nodiscard]] std::size_t size() const;
748 //! @brief Get the total capacity of the cache.
749 //! @return maximum number of elements the cache can hold
750 [[nodiscard]] std::size_t capacity() const;
751
752private:
753 //! @brief Alias for the iterator of the internal LRU list.
754 using LRUIter = std::list<std::size_t>::iterator;
755 //! @brief Alias for the iterator of the internal hash map.
756 using KeyedIter = typename std::unordered_map<Key, std::size_t>::iterator;
757 //! @brief Element metadata.
758 struct Element
759 {
760 //! @brief Iterator pointing to the key in the hash map.
761 KeyedIter keyedPosition{};
762 //! @brief Iterator pointing to the LRU list.
763 LRUIter lruPosition;
764 //! @brief The value stored in the element.
765 Value value{};
766 };
767
768 //! @brief The main store for the key-value pairs.
769 std::vector<Element> elements{};
770 //! @brief The sorted list stores the index of each element.
771 std::list<std::size_t> lruList;
772 //! @brief The end of the LRU list. It is used to denote how many elements are in use.
773 LRUIter lruListEnd;
774 //! @brief Hash map for fast key-to-element lookup.
775 std::unordered_map<Key, std::size_t> keyedElements{};
776 //! @brief Number of elements.
777 std::size_t usedSize{0};
778
779 //! @brief Operation of inserting or updating.
780 //! @param key - key associated with the value
781 //! @param value - value to be inserted or updated
782 void doInsertOrUpdate(const Key& key, Value&& value);
783 //! @brief Operation of inserting.
784 //! @param key - key associated with the value
785 //! @param value - value to be inserted
786 void doInsert(const Key& key, Value&& value);
787 //! @brief Operation of updating.
788 //! @param keyedPos - iterator to the element in the hash map
789 //! @param value - value to be updated
790 void doUpdate(const KeyedIter keyedPos, Value&& value);
791 //! @brief Operation of erasing.
792 //! @param elemIdx - index of element
793 void doErase(const std::size_t elemIdx);
794 //! @brief Operation of finding.
795 //! @param key - key to search for
796 //! @param peek - whether peek
797 //! @return optional value
798 std::optional<Value> doFind(const Key& key, const bool peek);
799 //! @brief Operation of accessing.
800 //! @param elem - element to be accessed
801 void doAccess(Element& elem);
802 //! @brief Operation of pruning.
803 void doPrune();
804};
805
806template <typename Key, typename Value>
807LRU<Key, Value>::LRU(const std::size_t capacity, const float maxLoadFactor) : elements{capacity}, lruList(capacity)
808{
809 std::iota(first: lruList.begin(), last: lruList.end(), value: 0);
810 lruListEnd = lruList.begin();
811
812 keyedElements.max_load_factor(maxLoadFactor);
813 keyedElements.reserve(capacity);
814}
815
816template <typename Key, typename Value>
817void LRU<Key, Value>::insert(const Key& key, Value value)
818{
819 doInsertOrUpdate(key, value: std::move(value));
820}
821
822template <typename Key, typename Value>
823template <typename Range>
824std::size_t LRU<Key, Value>::insertRange(Range&& keyValueRange)
825{
826 auto&& range = std::forward<Range>(keyValueRange);
827 std::size_t inserted = 0;
828 for (auto& [key, value] : range)
829 {
830 doInsertOrUpdate(key, value: std::move(value));
831 ++inserted;
832 }
833 return inserted;
834}
835
836template <typename Key, typename Value>
837bool LRU<Key, Value>::erase(const Key& key)
838{
839 if (const auto keyedPos = keyedElements.find(key); keyedPos != keyedElements.cend())
840 {
841 doErase(elemIdx: keyedPos->second);
842 return true;
843 }
844 return false;
845}
846
847template <typename Key, typename Value>
848template <typename Range>
849std::size_t LRU<Key, Value>::eraseRange(const Range& keyRange)
850{
851 std::size_t erased = 0;
852 for (const auto& key : keyRange)
853 {
854 if (const auto keyedPos = keyedElements.find(key); keyedPos != keyedElements.cend())
855 {
856 ++erased;
857 doErase(elemIdx: keyedPos->second);
858 }
859 }
860 return erased;
861}
862
863template <typename Key, typename Value>
864std::optional<Value> LRU<Key, Value>::find(const Key& key, const bool peek)
865{
866 return doFind(key, peek);
867}
868
869template <typename Key, typename Value>
870template <typename Range>
871auto LRU<Key, Value>::findRange(const Range& keyRange, const bool peek)
872 -> std::vector<std::pair<Key, std::optional<Value>>>
873{
874 std::vector<std::pair<Key, std::optional<Value>>> result{};
875 result.reserve(std::size(keyRange));
876 for (const auto& key : keyRange)
877 {
878 result.emplace_back(key, doFind(key, peek));
879 }
880 return result;
881}
882
883template <typename Key, typename Value>
884template <typename Range>
885void LRU<Key, Value>::resolveRange(Range& keyOptValueRange, const bool peek)
886{
887 for (auto& [key, optValue] : keyOptValueRange)
888 {
889 optValue = doFind(key, peek);
890 }
891}
892
893template <typename Key, typename Value>
894bool LRU<Key, Value>::empty() const
895{
896 return usedSize == 0;
897}
898
899template <typename Key, typename Value>
900std::size_t LRU<Key, Value>::size() const
901{
902 return usedSize;
903}
904
905template <typename Key, typename Value>
906std::size_t LRU<Key, Value>::capacity() const
907{
908 return elements.size();
909}
910
911template <typename Key, typename Value>
912void LRU<Key, Value>::doInsertOrUpdate(const Key& key, Value&& value)
913{
914 if (const auto keyedPos = keyedElements.find(key); keyedPos != keyedElements.cend())
915 {
916 doUpdate(keyedPos, value: std::move(value));
917 }
918 else
919 {
920 doInsert(key, value: std::move(value));
921 }
922}
923
924template <typename Key, typename Value>
925void LRU<Key, Value>::doInsert(const Key& key, Value&& value)
926{
927 if (usedSize >= elements.size())
928 {
929 doPrune();
930 }
931
932 const auto elemIdx = *lruListEnd;
933 const auto keyedPos = keyedElements.emplace(key, elemIdx).first;
934 auto& elem = elements[elemIdx];
935 elem.value = std::move(value);
936 elem.lruPosition = lruListEnd;
937 elem.keyedPosition = keyedPos;
938
939 ++lruListEnd;
940 ++usedSize;
941
942 doAccess(elem);
943}
944
945template <typename Key, typename Value>
946void LRU<Key, Value>::doUpdate(const KeyedIter keyedPos, Value&& value)
947{
948 auto& elem = elements[keyedPos->second];
949 elem.value = std::move(value);
950
951 doAccess(elem);
952}
953
954template <typename Key, typename Value>
955void LRU<Key, Value>::doErase(const std::size_t elemIdx)
956{
957 auto& elem = elements[elemIdx];
958 if (elem.lruPosition != std::prev(x: lruListEnd))
959 {
960 lruList.splice(lruListEnd, lruList, elem.lruPosition);
961 }
962 --lruListEnd;
963
964 keyedElements.erase(elem.keyedPosition);
965 --usedSize;
966}
967
968template <typename Key, typename Value>
969std::optional<Value> LRU<Key, Value>::doFind(const Key& key, const bool peek)
970{
971 if (const auto keyedPos = keyedElements.find(key); keyedPos != keyedElements.cend())
972 {
973 const std::size_t elemIdx = keyedPos->second;
974 auto& elem = elements[elemIdx];
975 if (!peek)
976 {
977 doAccess(elem);
978 }
979 return std::make_optional(elem.value);
980 }
981 return std::nullopt;
982}
983
984template <typename Key, typename Value>
985void LRU<Key, Value>::doAccess(Element& elem)
986{
987 lruList.splice(lruList.cbegin(), lruList, elem.lruPosition);
988}
989
990template <typename Key, typename Value>
991void LRU<Key, Value>::doPrune()
992{
993 if (usedSize > 0)
994 {
995 doErase(elemIdx: lruList.back());
996 }
997}
998} // namespace cache
999} // namespace data_structure
1000