Data Structures and Algorithms (Python implementation)

LRU Cache.py

# Author: John Ifegwu
import time
import math

class Node:
    
    def __init__(self, key, value, weight):
        self.key = key
        self.value = value
        self.weight = weight
        self.setLastAccessTime()
        
    def setLastAccessTime(self):
        self.lastAccessTime = time.time()
    
    def getScore(self):
        curTime = time.time()
        if self.lastAccessTime != curTime:
            return self.weight / (curTime - self.lastAccessTime)
        else:
            return self.weight / -100


class LRUCache:
    
    def __init__(self, capacity):
        self.capacity = capacity
        self.count = 0
        self.map = {}
    
    #This method works in O(n)
    def getLeastScoredKey(self):
        #gets least Scored Key.
        tempScore = 0
        score = 0
        key = 0
        for n in self.map.values():
            tempScore = n.getScore()
            if score == 0:
                score = tempScore
                key = n.key
            elif score > tempScore:
                score = tempScore
                key = n.key
        return key
   
    #This method works in O(n)    
    def deleteExcesses(self):
        self.map.pop(self.getLeastScoredKey())
    
    #This method works in O(1) 
    def get(self, key):
        if self.map.get(key) != None:
            node = self.map.get(key)
            #update access time
            node.setLastAccessTime()
            return node.value
        else:
            return -1
    
    #This method works in O(1) 
    def put(self, key, value, weight):
        if self.map.get(key) != None:
            #update records
            node = self.map.get(key)
            node.value = value
            node.weight = weight 
            node.setLastAccessTime()
        else:
            #add new record
            node = Node(key, value, weight)
            self.map.update({key:node})
            if self.count < self.capacity:
                self.count += 1
            else:
                self.deleteExcesses()
    
    #this method is just for demonstration purpose
    def printMap(self):
        for n in self.map.values():
            print("Key: {0} Value: {1}".format(n.key, n.value))


cache = LRUCache(2)
print("Adding Key 1 and Key 2 details.")
cache.put(1, 100, 0.1)
cache.put(2, 200, 0.2)
cache.printMap()
print("")

print("adding next will delete  key 1")
cache.put(3, 300, 0.3)
cache.printMap()
print("")

print("adding next will delete key 2")
cache.put(4, 400, 0.4)
cache.printMap()

print("\nUpdating key 4 with the value 500")
cache.put(4, 500, 0.5)

print("\n executing get for key 1, 2, 3 and 4")

print(" Key 1 returned: {0} \n Key 2 returned: {1} \n Key 3 returned: {2} \n Key 4 returned: {3}".format(cache.get(1), cache.get(2), cache.get(3), cache.get(4)))