מריה בוטוסוב

יש לממש LRU Cache ע''י שימוש במבנה מהיר שיאפשר גישה מהירה ועידכון מהיר. חשוב ש cache מוגבל בגודלו ופריטים שלא ניגשו אליהם הרבה זמן ימחקו ראשונים.

public class LRUCache {
    int maxCapacity = 0;
    LinkedList lst = new LinkedList();
    Dictionary<int, Node> cache = new Dictionary<int, Node>();
 
    public LRUCache(int capacity) {
        maxCapacity = capacity;
    }
    
    public int Get(int key) {
        if(!cache.ContainsKey(key))
            return -1;       
        lst.SetHead(cache[key]);            
        return cache[key].Value;
             
    }
    
    public void Put(int key, int value) {            
        if(!cache.ContainsKey(key)) {
            if(cache.Count() == maxCapacity)
                evictLeastRecent();
            
            Node node = new Node(key, value);
            cache.Add(key, node); 
            lst.SetHead(node);
        }
        else {
            Node node = cache[key];
            node.Value = value;
            lst.SetHead(node);
        }
    }
    
    private void evictLeastRecent() {
        int key = lst.Tail.Key;
        lst.RemoveTail();
        cache.Remove(key);
    }
    
    public class LinkedList {
        public Node Tail;
        public Node Head;
        
        public void SetHead(Node node) {                        
            if(Head == node) return;
            if(Head == null) {
                Head = Tail =  node;
            } else if (Head == Tail) {
                Tail.Prev = node;
                Head = node;
                Head.Next = Tail;            
            } else {
                if(Tail == node)
                    RemoveTail();
                node.RemoveRelations();
                Head.Prev = node;
                node.Next = Head;
                Head = node;                
            } 
        }
        
        public void RemoveTail() {                
            if (Tail == null) return;
            if(Head == Tail) {
                Head = Tail  =  null;
            }
            else {
                Tail = Tail.Prev;
                Tail.Next = null;
            }
        }
    }
    
    public class Node {
        public Node Next;
        public Node Prev;
        public int Key;
        public int Value;
        
        public Node(int key, int value) {
            this.Key = key;
            this.Value = value;
        }
        
        public void RemoveRelations() {
            if(Prev != null)
                Prev.Next  = Next;
            if(Next != null)
                Next.Prev = Prev;
            Next = null;
            Prev = null;
        }
    }
}