FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
algorithm-examples/cpp-algorithm/src/hashtable/isbn_cache.h at main · codejsha/algorithm-examples · GitHub
codejsha
/
algorithm-examples
Public
Notifications
You must be signed in to change notification settings
Fork
0
Star
2
Code
Issues
0
Pull requests
0
Discussions
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Discussions
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
algorithm-examples
/
cpp-algorithm
/
src
/
hashtable
/
isbn_cache.h
Copy path
More file actions
More file actions
Latest commit
History
History
History
103 lines (93 loc) · 2.78 KB
Breadcrumbs
algorithm-examples
/
cpp-algorithm
/
src
/
hashtable
/
isbn_cache.h
Copy path
File metadata and controls
103 lines (93 loc) · 2.78 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#
ifndef
CPP_ALGORITHM_ISBN_CACHE_H
#
define
CPP_ALGORITHM_ISBN_CACHE_H
#
include
<
list
>
#
include
<
string
>
#
include
<
unordered_map
>
namespace
IsbnCache
{
/*
*
* \brief Least recently used cache for ISBNs.
*/
class
LruCache
{
public:
LruCache
(
size_t
capacity) {}
explicit
LruCache
(
int
capacity)
: capacity_(capacity) {}
/*
*
* \brief Lookup ISBN in cache.
* \param isbn the ISBN to search for
* \return price if the ISBN is in the cache, -1 otherwise
*/
int
Lookup
(
const
std::string& isbn)
{
if
(
auto
it = price_table_.
find
(isbn); it == price_table_.
end
())
{
return
-
1
;
}
else
{
auto
price = it->
second
.
second
;
MoveToFront
(isbn, it);
return
price;
}
}
/*
*
* \brief Insert an ISBN into the cache.
* \param isbn the ISBN to insert
* \param price the price of the book
*/
void
Insert
(
const
std::string& isbn,
int
price)
{
if
(
auto
it = price_table_.
find
(isbn); it != price_table_.
end
())
{
MoveToFront
(isbn, it);
}
else
{
if
(price_table_.
size
() == capacity_)
{
price_table_.
erase
(lru_queue_.
back
());
lru_queue_.
pop_back
();
}
lru_queue_.
emplace_front
(isbn);
price_table_[isbn] = {lru_queue_.
begin
(), price};
}
}
/*
*
* \brief Erase an ISBN from the cache.
* \param isbn the ISBN to erase
* \return true if the ISBN was in the cache, false otherwise
*/
bool
Erase
(
const
std::string& isbn)
{
if
(
auto
it = price_table_.
find
(isbn); it == price_table_.
end
())
{
return
false
;
}
else
{
lru_queue_.
erase
(it->
second
.
first
);
price_table_.
erase
(it);
return
true
;
}
}
private:
using
Table = std::unordered_map<std::string, std::pair<std::list<std::string>::iterator,
int
>>;
/*
*
* \brief Move an ISBN to the front of the queue.
* \param isbn the ISBN to move
* \param it the iterator to the ISBN in the queue
*/
void
MoveToFront
(
const
std::string& isbn,
const
Table::iterator& it)
{
lru_queue_.
erase
(it->
second
.
first
);
lru_queue_.
emplace_front
(isbn);
it->
second
.
first
= lru_queue_.
begin
();
}
int
capacity_;
Table price_table_;
std::list<std::string> lru_queue_;
};
}
#
endif
Back
|
FazBrowse Home
|
New Git URL