using System;

using System.Collections.Generic;

using System.Security.Cryptography;

using System.Text;

​

namespace csharp_leetcode

{

    // https://leetcode.com/problems/lru-cache/

    public class LRUCache

    {

        private class Node

        {

            public Node(int i, int j) { key = i; val = j; }

            public int key { get; set; }

            public int val { get; set; }

        }

​

        Dictionary<int, LinkedListNode<Node>> dict = new Dictionary<int, LinkedListNode<Node>>(); // to quickly reach the node in linkedlist

        LinkedList<Node> lru = new LinkedList<Node>(); // to keep track of least recently used item list -> most recentyl used ..... least recently used

        int iCapacity = 0;

​

        public LRUCache(int capacity)

        {

            iCapacity = capacity;

        }

​

        public int Get(int key)

        {

            if (dict.ContainsKey(key))

            {

                Node nd = dict[key].Value;

                int val = dict[key].Value.val;

                // improve position on LRU catch

                lru.Remove(dict[key]); // O(1)

                this.LRU_AddToFirst(key, val);

                return val;

            }

            else

                return -1;

        }

​

        public void Put(int key, int value)

        {

            if (dict.ContainsKey(key))

            {

                dict[key].Value.val = value;

                // improve position on LRU catch

                lru.Remove(dict[key]); // O(1)

                this.LRU_AddToFirst(key, value);

            }

            else

            {

                if (lru != null && lru.Count == iCapacity) this.LRU_RemoveFromLast();

                this.LRU_AddToFirst(key, value);

            }

        }

        private void LRU_AddToFirst(int key, int value)

        {

            Node nd = new Node(key, value);

            LinkedListNode<Node> llnode = new LinkedListNode<Node>(nd);

            lru.AddFirst(llnode);

​

            if (dict.ContainsKey(key)) dict[key] = lru.First;

            else dict.Add(key, lru.First);

        }

        private void LRU_RemoveFromLast()

        {

            Node nd = lru.Last.Value;

            dict.Remove(nd.key);

            lru.RemoveLast();

        }

​

        public void debuglog()

        {

            Console.Write("dict: ");

            foreach (int key in dict.Keys)

            {

                Console.Write($"[{key}, {dict[key].Value.val}], ");

            }

            Console.WriteLine();

            Console.Write("LRU: ");

            foreach (Node nd in lru)

            {

                Console.Write($"{nd.key}:{nd.val} ");

            }

            Console.WriteLine();

        }

    }

​

    /**

    * Your LRUCache object will be instantiated and called as such:

    * LRUCache obj = new LRUCache(capacity);

    * int param_1 = obj.Get(key);

    * obj.Put(key,value);

    */

    public class LC_0146_lru_cache

    {

        public static void Main()

        {

            // Test Case 1

            //List<string> lstcmd = new List<string>() { "LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get" };

            //int[][] lstcmdval = { new int[] { 2 }, new int[] { 1, 1 }, new int[] { 2, 2 }, new int[] { 1 }, new int[] { 3, 3 }, new int[] { 2 }, new int[] { 4, 4 }, new int[] { 1 }, new int[] { 3 }, new int[] { 4 }};

​

            // Test Case 2 - failed

            //["LRUCache","put","put","put","put","get","get"]

            //[[2],[2,1],[1,1],[2,3],[4,1],[1],[2]]

            List<string> lstcmd = new List<string>() { "LRUCache", "put", "put", "put", "put", "get", "get" };

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

​

            LRUCache oLRUCache = null;

            for (int i = 0; i < lstcmd.Count; i++)

            {

                string cmd = lstcmd[i];

                int[] cmdval = lstcmdval[i];

                string tmpstr = (cmdval.Length > 1) ? $"{cmdval[0]}, {cmdval[1]}" : $"{cmdval[0]}";

                Console.WriteLine($"{cmd}, {tmpstr}");

                if (cmd == "LRUCache") oLRUCache = new LRUCache(cmdval[0]);

                else if (cmd == "get") Console.WriteLine(oLRUCache.Get(cmdval[0]));

                else if (cmd == "put") oLRUCache.Put(cmdval[0], cmdval[1]);

                oLRUCache.debuglog();

                Console.WriteLine();

            }

        }

    }

}

​

/*

146. LRU Cache

Medium

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity.

int get(int key) Return the value of the key if the key exists, otherwise return -1.

void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Follow up:

Could you do get and put in O(1) time complexity?

Example 1:

Input

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]

[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output

[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation

LRUCache lRUCache = new LRUCache(2);

lRUCache.put(1, 1); // cache is {1=1}

lRUCache.put(2, 2); // cache is {1=1, 2=2}

lRUCache.get(1);    // return 1

lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}

lRUCache.get(2);    // returns -1 (not found)

lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}

lRUCache.get(1);    // return -1 (not found)

lRUCache.get(3);    // return 3

lRUCache.get(4);    // return 4

Constraints:

1 <= capacity <= 3000

0 <= key <= 3000

0 <= value <= 10^4

At most 3 * 104 calls will be made to get and put.

*/