// 1. Page is present in the cache - If the page is already present in the cache, we move the page to the start of the list.

// 2. Page is not present in the cache - If the page is not present in the cache, we add the page to the list. 

// How to add a page to the list:

//    a. If the cache is not full, add the new page to the start of the list.

//    b. If the cache is full, remove the last node of the linked list and move the new page to the start of the list.

​

​

using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        int cacheSize = 4;

        var cache = new LRUCache(cacheSize);

        cache.accessPage(4);

        cache.printCacheState();

        cache.accessPage(2);

        cache.printCacheState();

        cache.accessPage(1);

        cache.printCacheState();

        cache.accessPage(1);

        cache.printCacheState();

        cache.accessPage(4);

        cache.printCacheState();

        cache.accessPage(3);

        cache.printCacheState();

        cache.accessPage(7);

        cache.printCacheState();

        cache.accessPage(8);

        cache.printCacheState();

        cache.accessPage(3);

        cache.printCacheState();

    }

}

​

public class LRUCache{

    private DoublyLinkedList pageList;

    private Dictionary<int, Node> pageMap;

    private int cacheSize;

    public LRUCache(int cacheSize){

        this.cacheSize = cacheSize;

        this.pageList = new DoublyLinkedList(cacheSize);

        this.pageMap = new Dictionary<int, Node>();

    }

    public void accessPage(int pageNum){

        Node pageNode = null;

        if(pageMap.ContainsKey(pageNum)){

            pageNode = pageMap[pageNum];

            pageList.moveToStart(pageNode);

        }else{

            pageNode = new Node(pageNum);

            if(pageList.currSize == pageList.size){

                pageList.removeLast();

                pageMap.Remove(pageNum);

            }

            pageNode = pageList.addNode(pageNode);

            pageMap.Add(pageNum, pageNode);

        }

    }

    public void printCacheState(){

        if(pageList.head == null) {

            return;

        }

        Node tmp = pageList.head;

        while(tmp != null) {

            if(tmp.prev != null){ Console.Write("(prev:" + tmp.prev.pageNumber + ") "); }

            Console.Write(tmp.pageNumber + " ");

            if(tmp.next != null){ Console.Write("(next:" + tmp.next.pageNumber + ") "); }

            tmp = tmp.next;

        }

        Console.WriteLine("");

        if(pageList.head != null) { Console.WriteLine("head:" + pageList.head.pageNumber);}

        if(pageList.tail != null) { Console.WriteLine("tail:" + pageList.tail.pageNumber);}

        //if(pageList.head != null) { Console.WriteLine("size:" + pageList.size);}

        //if(pageList.tail != null) { Console.WriteLine("currSize:" + pageList.currSize);}

    }

}

​

public class DoublyLinkedList{

    public int size;

    public int currSize;

    public Node head;

    public Node tail;

    public DoublyLinkedList(int cacheSize){

        this.size = cacheSize;

    }

    public void removeLast(){

        if(tail != null){

            var tailPrev = tail.prev;

            if(tailPrev != null)

            {

                tailPrev.next = null;

                tail = tailPrev;

                if(currSize > 0){

                    currSize -= 1;

                }

            }

        }

    }

    public void moveToStart(Node node){

        if(head == node)

            return;

        if(tail == node){

            tail = node.prev;

        }

        var prev = node.prev;

        var next = node.next;

        if(prev != null){

            prev.next = next;

        }

        if(next != null){

            next.prev = prev;

        }

        if(head != null){

            node.prev = null;

            node.next = head;

        }

        head = node;

        head.next.prev = node;

        //if(tail != null) { Console.WriteLine("move to start tail:" + tail.pageNumber); }

    }

    public Node addNode(Node node){

        currSize++;

        if(head == null){

            head = node;

            tail = node;

        }else{

            node.next = head;

            node.next.prev = node;

            head = node;

        }

        return node;

    }

}

​

public class Node{

    public int pageNumber;

    public Node next;

    public Node prev;

    public Node(){}

    public Node(int pageNum){

        this.pageNumber = pageNum;

    }

}