Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- var LFUCache = function(capacity) {
- // max capacity
- this.maxCap = capacity;
- // current capacity
- this.currentCap = 0;
- // cache
- this.cache = {};
- // value
- // frequency
- // Least amount accessed
- this.leastFrequentAccessedAmount = 0;
- // this.secondLeastFrequentAccessedAmount = 0;
- // Frequency lookup object
- this.frequency = {};
- // array of values
- };
- LFUCache.prototype.get = function(key) {
- if (this.cache[key]) {
- this._updateFrequency(this.cache[key]);
- return this.cache[key].value;
- } else {
- return -1
- }
- };
- LFUCache.prototype.put = function(key, value) {
- // look up key and value first
- if (this.maxCap > 0) {
- if (this.cache[key]) {
- this.cache[key].value = value;
- this._updateFrequency(this.cache[key]);
- } else {
- if (this.currentCap === this.maxCap) {
- this.cache[this.frequency[this.leastFrequentAccessedAmount][0]] = null;
- this.frequency[this.leastFrequentAccessedAmount].splice(0, 1);
- } else {
- this.currentCap++;
- }
- this.cache[key] = {
- value,
- frequency: 0,
- keyName: key
- };
- if (this.frequency[0]) {
- this.frequency[0].push(key);
- } else {
- this.frequency[0] = [key];
- }
- this.leastFrequentAccessedAmount = 0;
- }
- }
- };
- LFUCache.prototype._updateFrequency = function(key) {
- let freq = this.frequency[key.frequency];
- for (var i = 0; i < freq.length; i++) {
- if (freq[i] === key.keyName) {
- freq.splice(i, 1);
- }
- }
- if (key.frequency === this.leastFrequentAccessedAmount && this.frequency[key.frequency].length === 0) {
- this.leastFrequentAccessedAmount++;
- }
- key.frequency++;
- if (this.frequency[key.frequency]) {
- this.frequency[key.frequency].push(key.keyName);
- } else {
- this.frequency[key.frequency] = [key.keyName]
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement