Leetcode 146 - LRU - warm up practice - a lot of things are new to me! Add a lot of comment.

Leetcode146_LRU_warmup_June2_2016.cs

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

namespace LRUCache_Warmup_June2_2016
{
    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; 
        }
    }

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

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

            for (int i = 0; i < 4; i++)
            {
                cache.set(keyValuePair[i][0], keyValuePair[i][1]); 
            }

            // cache is setup as a queue, the head of queue will be removed if capacity is reached, now the order from head to tail is 1, 2, 3, 4, 5
            int value = cache.get(1);  // 1 is visited, then, 1 will be reposition to the end. 

            // set fifth node in the array, evoking LRU cache to do eviction of head of queue
            cache.set(keyValuePair[4][0], keyValuePair[4][1]);

            int value_shouldbe_1         = cache.get(1);  //return 1
            int value_shouldbe_negative1 = cache.get(2);  // not found, return -1
            int value_shouldbe_1_aswell  = cache.get(3);  // return 3

            ListNode newNode = new ListNode(1, 10);
            cache.set(1, 10); 
            int value_shouldbe_10 = cache.get(1); 

        }

        private int capacity, size;
        private ListNode dummyHead, dummyTail;

        private Dictionary<int, ListNode> map;

        public bool arugmentOk = true;

        /*
         * Talk about design quickly here:
         * To find a key, using hashmap, find O(1) time; 
         * To visit a node, and then, need to remove the node, since double linked list, 
         * find time is P(1), remove time is also O(1), reconstruct the links of prev, next two nodes. 
         * Add visited node to the head of linked list, head of queue - O(1) time as well. 
         * 
         * cache is a queue, remove from the head, add to last one. 
         * if the node is visited, then, remove the visited node first, then add to the end 
         * of queue. 
         */
        public LRUCache(int capacity)
        {
            if (capacity <= 0)
                return;

            this.capacity = capacity;
            size = 0;

            // set up dummyHead, dummyTail
            dummyHead = new ListNode(0, 0);
            dummyTail = new ListNode(0, 0);

            // for an empty double linked list, please connect dummyHead to dummyTail
            // It is much easy to handle empty list, and also insertion/ deletion. 
            dummyTail.prev = dummyHead;
            dummyHead.next = dummyHead;

            // set up a map for O(1) access to find the key 
            map = new Dictionary<int, ListNode>(); 
        }

        /*
         * Function spec:
         * 
         * get  method 
         * -- find the node, return val, 
         * -- and then, need to reposition the node in the queue
         * 
         * 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 <- tricky part
         * <- need to remove the node first, 
         * <- add to last one instead. 
         * In other words, reposition the node, and also update the value 
         * 2. if the capacity is reached, then remove the tail of queue first, 
         * add a new node to the end of queue. 
         * 
         * Bugs to avoid, share tips:  
         * 1. remove a node, also need to update hashMap on that. Remove the node from the dictionary. 
         * 2. If the node is repositioned in the queue, no need to update dictionary. 
         */
        public void set(int key, int value)
        {
            if (map.ContainsKey(key))
            {
                ListNode target = map[key];
                target.val = value;

                // since the node will be removed first, but add as well. No need to update dictionary. 
                remove(target);
                addToLast(target);
            }
            else
            {   // double check, which node to remove, dummyHead.next.key ? not tail?
                // cache is a queue, remove from the head, add to last one. 
                // if the node is visited, then, remove the visited node first, then add to the end of queue. 
                // remove a node, also, need to remove it from HashMap 
                if (size == capacity)
                {
                    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; 

            // need to reset dummyTail.prev
            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; 
        }
    }
}