Last active
November 18, 2020 09:53
-
-
Save johnifegwu/63e1e51eff38f4e83e15e946611ed819 to your computer and use it in GitHub Desktop.
Data Structures and Algorithms (Java Implementation)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.sql.Timestamp; | |
import java.util.*; | |
import java.lang.Math; | |
//Author: John Ifegwu | |
class Node { | |
int key; | |
int value; | |
Timestamp lastAccessTime; | |
double weight; | |
public Node(int key, int value, double weight) | |
{ | |
this.key = key; | |
this.value = value; | |
this.weight = weight; | |
setAccessTime(); | |
} | |
public void setAccessTime() | |
{ | |
Date dt = new Date(); | |
Timestamp ts = new Timestamp(dt.getTime()); | |
this.lastAccessTime = ts; | |
} | |
public double getScore() | |
{ | |
Date dt = new Date(); | |
if (dt != this.lastAccessTime) | |
{ | |
return this.weight / (dt.getTime() -this.lastAccessTime.getTime()); | |
}else | |
{ | |
return this.weight / -100; | |
} | |
} | |
} | |
class LRUCache { | |
private HashMap<Integer, Node> map; | |
private int capicity, count; | |
public LRUCache(int capacity) | |
{ | |
this.capicity = capacity; | |
map = new HashMap<>(); | |
count = 0; | |
} | |
//This method works in O(n) | |
//Removes excesses | |
public void deleteExcess() | |
{ | |
map.remove(getLeastScoredKey()); | |
} | |
//This method works in O(n) | |
// Gets the least Scored key. | |
int getLeastScoredKey() | |
{ | |
double tempScore = 0; | |
double score = 0; | |
int key = 0; | |
for (Node n : map.values()) | |
{ | |
tempScore = n.getScore(); | |
if (score == 0) | |
{ | |
score = tempScore; | |
key = n.key; | |
} | |
else if (score > tempScore) | |
{ | |
score = tempScore; | |
key = n.key; | |
} | |
} | |
return key; | |
} | |
// This method works in O(1) | |
public int get(int key) | |
{ | |
if (map.get(key) != null) { | |
Node node = map.get(key); | |
//Update access time. | |
node.setAccessTime(); | |
int result = node.value; | |
System.out.println("Got the value : " + | |
result + " for the key: " + key); | |
return result; | |
} | |
else | |
{ | |
System.out.println(""); | |
System.out.println("Did not get any value" + | |
" for the key: " + key); | |
return -1; | |
} | |
} | |
// This method works in O(1) | |
public void put(int key, int value, double weight) | |
{ | |
//Update cache if key exist. | |
//Otherwise add new and delete excesses if needs be. | |
System.out.println(""); | |
System.out.println("Going to set the (key, "+ | |
"value, weight) : (" + key + ", " + value + ", " + weight + ")"); | |
if (map.get(key) != null) { | |
Node node = map.get(key); | |
node.value = value; | |
node.weight = weight; | |
//Update access time. | |
node.setAccessTime(); | |
} | |
else | |
{ | |
Node node = new Node(key, value, weight); | |
map.put(key, node); | |
if (count < capicity) { | |
count++; | |
} | |
else | |
{ | |
//Remove excesses | |
deleteExcess(); | |
} | |
} | |
} | |
} | |
public class lunchLRUCache { | |
public static void main(String[] args) | |
{ | |
System.out.println(""); | |
System.out.println("Testing the LRU Cache Implementation"); | |
LRUCache cache = new LRUCache(2); | |
// We will store a key (1) with value 100 in the cache. | |
cache.put(1, 100, 0.1); | |
// We will store a key (2) with value 200 in the cache. | |
cache.put(2, 200, 0.1); | |
System.out.println(""); | |
System.out.println("Value for the key: 1 is " + cache.get(1)); // returns 100 | |
// We will store a key (5) with value 500 in the cache. | |
// this will remove key 1 from the cache. | |
cache.put(5, 500, 0.1); | |
System.out.println(""); | |
System.out.println("Value for the key: 1 is " + cache.get(1)); // returns -1 (not found) | |
// We will store a key (3) with value 300 in the cache. | |
// this will remove key 2 from the cache. | |
cache.put(3, 300, 0.1); | |
System.out.println("Value for the key: 2 is " + cache.get(2)); // returns -1 (not found) | |
System.out.println(""); | |
System.out.println("Value for the key: 5 is " + cache.get(5)); // returns 500 | |
System.out.println("Value for the key: 3 is " + cache.get(3)); // return 300 | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment