Python - DLL and Hash Table


  • 0
    S
    class CacheNode(object):
        def __init__(self,key):
            self.key  = key
            self.prev = None
            self.next = None
    
    class CacheList(object):
        def __init__(self):
            self.head = None
            self.tail = None
            self.len  = 0
        
        def __enqueue__(self,cache_node):
            if cache_node:
                self.len += 1
                if self.tail is None:
                    self.head = self.tail = cache_node
                else:
                    cache_node.prev = self.tail
                    self.tail.next  = cache_node
                    self.tail       = self.tail.next
                
        
        def __popfirst__(self):
            nodex = None
            if self.head:
                nodex     = self.head
                self.head = self.head.next
                if nodex.next:
                    nodex.next.prev = None
                nodex.prev = nodex.next = None
                self.len -= 1
            return nodex
        
        def __poplast__(self):
            nodex = None
            if self.tail:
                nodex     = self.tail
                self.tail = self.tail.prev
                if nodex.prev:
                    nodex.prev.next = None
                nodex.prev = nodex.next = None
                self.len -= 1
            return nodex
        
        def __pop__(self,cache_node):
            if self.tail is cache_node:
                return self.__poplast__()
            if self.head is cache_node:
                return self.__popfirst__()
            prev,cache_node.prev = cache_node.prev, None
            next,cache_node.next = cache_node.next, None
            if prev:
                prev.next = next
            if next:
                next.prev = prev
            self.len -= 1
            return cache_node
        
        def __len__(self):
            return self.len
                
            
    class LRUCache(object):
    
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.kvstore  = dict()
            self.capacity = capacity
            self.list     = CacheList()
            
    
        def get(self, key):
            """
            :type key: int
            :rtype: int
            """
            value = -1
            
            if self.capacity > 0:        
                value,cache_node = self.kvstore.get(key,(-1,None))
                if value != -1: # if item is in kvstore
                    self.list.__pop__(cache_node)
                    self.list.__enqueue__(cache_node)
    
            return value
            
    
        def put(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: void
            """
            if self.capacity > 0:
                if key in self.kvstore:
                    ovalue,cache_node = self.kvstore[key]
                    self.list.__pop__(cache_node)
                    cache_node.value  = value
                else:
                    if self.list.__len__()  == self.capacity:
                        cache_node = self.list.__popfirst__()
                        self.kvstore.pop(cache_node.key)
    
                    cache_node = CacheNode(key)
                    
                self.kvstore[key] = (value, cache_node)
                self.list.__enqueue__(cache_node)
    # Your LRUCache object will be instantiated and called as such:
    # obj = LRUCache(capacity)
    # param_1 = obj.get(key)
    # obj.put(key,value)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.