Cache

LRU

Single process version:

LRUCache (Dictionary wrapper):
  - Action filters:
    - On Get:
      - Mark entry access
    - On Put (AddOrUpdate):
      - Remove the least recently used
       
  - Least recently used:
    - Tracking: 
      - With use of auxiliary doubly linked list (var orderByAccessView) and dictionary (var keyToOrderByAccess)
	- On Get (TrackAccess):
 	  - Retrieve entry from keyToOrderByAccess 		  
 	  - Move node in entriesByAccessView to the top
        - On Put (TrackAccess):
 	  - Ensure entry in keyToEntriesByAccess
 	  - Move node in entriesByAccessView to the top (TrackAccess)
	  - If entry is new:
	    - If new size exceeds required (EnsureSize):
 	      - Retrieve last node from entriesByAccessView (var leastRecentlyUsed)
 	      - Remove(leastRecentlyUsed)
	    - Insert a new item
        - On Remove (StopTracking):
          - Retrieve entry from keyToEntriesByAccess and remove it
          - Remove node from entriesByAccessView
          - Remove entry from the dictionary itself
Costs:
  - Get: 
    - Time: O(1)  
  - Put:
    - Time: O(1)  
    
Tests:
LRUCache cache = new LRUCache(capacity: 2);

cache.Put(1, 1);
cache.Put(2, 2);
cache.Get(1);       // returns 1
cache.Put(3, 3);    // evicts key 2
cache.Get(2);       // returns -1 (not found)
cache.Put(4, 4);    // evicts key 1
cache.Get(1);       // returns -1 (not found)
cache.Get(3);       // returns 3
cache.Get(4);       // returns 4