Leetcode 146 - LRU - warm up practice - add comment to help writing, and also set up a more meaningful test case with comment.

Leetcode146_LRU_warmup_June2_2016_B.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LRUCache_Warmup_SecondTime
{
    public class ListNode
    {
        public int key, val;
        public ListNode prev, next;

        public ListNode(int k, int v)
        {
            key = k;
            val = v;

            prev = null;
            next = null; 
        }
    }

    /*
     * Set up examination points to check: 
     * The most easily made bug - hashmap is out of sync with cache - queue - double linked list 
     */
    class LRUCache
    {
        private int capacity, size;
        private ListNode dummyHead, dummyTail;

        private Dictionary<int, ListNode> map;

        /*
         * constructor - 
         * a list of things to do:
         * 5 things to do:
         * 1. check capacity value - valid or not
         * 2. set cache size
         * 3. create dummy nodes
         * 4. set up double linked list - a queue
         * 5. create a hashmap variable 
         */
        public LRUCache(int capacity)
        {
            if (capacity < 0)
                return;

            this.capacity = capacity;
            size = 0;

            dummyHead = new ListNode(0, 0);
            dummyTail = new ListNode(0, 0); 

            // set up a emtpy list with dummy nodes
            dummyHead.next = dummyTail;
            dummyTail.prev = dummyHead; 

            // set up a map as welll 
            map = new Dictionary<int,ListNode>(); 
        }

        /*
         * Function spec
         * get function - more work than get - get and triggered actions
         * -- find the node, return val
         * -- next step, need to reposition the node in the queue - move to the tail
         * -- no change in dictionary variable
         * 
         * Assumption: 
         *  -1 - if the key is not found
         *  assuming that all value > 0
         */
        public int get(int key)
        {
            if (!map.ContainsKey(key))
            {
                return -1; 
            }

            ListNode target = map[key];
            remove(target);
            addToLast(target);

            return target.val; 
        }

        /*
         * Function spec:
         * 1. if the key exists, then do update of value - but more things to do
         *    step 1: remove the node first; 
         *    step 2: add to last one instead. 
         *    because the priority for eviction is changed, the node is least evictable, and then put 
         *    at the tail of queue - last out!
         *    
         * Dictionary - no need to change    
         */
        public void set(int key, int value)
        {
            if (map.ContainsKey(key))
            {
                ListNode target = map[key];
                target.val = value; // update the value 

                remove(target);
                addToLast(target);
            }
            else
            {
                // check capacity 
                if (size == capacity)
                {
                    // 1.  remove the head of queue
                    // 2.  remove it from dictionary as well
                    map.Remove(dummyHead.next.key);
                    remove(dummyHead.next);
                    size--;                                       
                }

                ListNode newNode = new ListNode(key, value);
                map.Add(key, newNode);
                addToLast(newNode); 
                size ++; 
            }
        }

        /*
         * Function spec:
         * insert a node between two nodes:
         * dummyTail.prev     and dummyTail
         * Need to take care of 4 links
         */
        private void addToLast(ListNode target)
        {
            target.next = dummyTail;
            target.prev = dummyTail.prev;

            dummyTail.prev.next = target;

            dummyTail.prev = target; 
        }

        /*
         * set up two nodes connections in double linked
         * target.prev    target.next
         * 
         * tip: no extra variable is needed 
         */
        private void remove(ListNode target)
        {
            target.next.prev = target.prev;
            target.prev.next = target.next; 
        }

        static void Main(string[] args)
        {
            LRUCache cache = new LRUCache(4);

            int[][] keyValuePair = new int[5][]{
                new int[2]{1,1}, 
                new int[2]{2,2},
                new int[2]{3,3}, 
                new int[2]{4,4}, 
                new int[2]{5,5}
            };

            for (int i = 0; i < cache.capacity; i++)
            {
                int key = keyValuePair[i][0];
                int value = keyValuePair[i][1];

                cache.set(key, value); 
            }

            int value_shouldbe1 = cache.get(1); 

            // add one more node into cache to push the cache to do eviction
            cache.set(keyValuePair[4][0], keyValuePair[4][1]);

            // key - 2 is evicted out from cache since line 179 - reach capacity 
            int value_shouldBeNonExisted = cache.get(2); 
        }
    }
}