Advertisement
Catsher

LRU Cache C#

Mar 30th, 2025
581
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 4.99 KB | None | 0 0
  1. public class LRUCache
  2. {
  3.     public int Capacity { get; set; }
  4.  
  5.     public int _count = 0;
  6.     public int Count => _count;
  7.  
  8.     private Dictionary<int, OurNode<(int, int)>> KeyAndLinkToNode { get; set; } = [];
  9.     private OurLinkedList<(int, int)> Queue { get; set; } = new();
  10.  
  11.     public LRUCache(int capacity)
  12.     {
  13.         Capacity = capacity;
  14.     }
  15.  
  16.     public int Get(int key)
  17.     {
  18.         if (!KeyAndLinkToNode.TryGetValue(key, out var nodeWithValue))
  19.         {
  20.             return -1;
  21.         }
  22.         var finalValue = nodeWithValue.Value.Item2;
  23.  
  24.  
  25.         if (Count == 0)
  26.             throw new InvalidOperationException("ЧЛЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕН");
  27.         else if (Count == 1)
  28.         {
  29.  
  30.         }
  31.         else if (nodeWithValue.Previous is null)
  32.         {
  33.             Queue.First = Queue.First.Next;
  34.             Queue.Last.Next = nodeWithValue;
  35.             Queue.Last = nodeWithValue;
  36.         }
  37.         else if (nodeWithValue.Next is null)
  38.         {
  39.  
  40.         }
  41.         else
  42.         {
  43.             nodeWithValue.Previous.Next = nodeWithValue.Next;
  44.             Queue.Last.Next = nodeWithValue;
  45.         }
  46.  
  47.        
  48.  
  49.         Console.WriteLine(finalValue);
  50.         return finalValue;
  51.     }
  52.  
  53.     public void Put(int key, int value)
  54.     {
  55.         if (KeyAndLinkToNode.ContainsKey(key))
  56.         {
  57.             var nodeToUpdate = KeyAndLinkToNode[key];
  58.             nodeToUpdate.Value = (nodeToUpdate.Value.Item1, value);
  59.  
  60.             if (Count == 0)
  61.                 throw new InvalidOperationException("ЧЛЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕН");
  62.             else if (Count == 1)
  63.             {
  64.  
  65.             }
  66.             else if (nodeToUpdate.Previous is null)
  67.             {
  68.                 Queue.First = Queue.First.Next;
  69.                 Queue.Last.Next = nodeToUpdate;
  70.                 Queue.Last = nodeToUpdate;
  71.             }
  72.             else if (nodeToUpdate.Next is null)
  73.             {
  74.  
  75.             }
  76.             else
  77.             {
  78.                 nodeToUpdate.Previous.Next = nodeToUpdate.Next;
  79.                 Queue.Last.Next = nodeToUpdate;
  80.             }
  81.  
  82.             return;
  83.         }
  84.  
  85.         if (Count == Capacity)
  86.         {
  87.             var deletedNode = Queue.First;
  88.             Queue.RemoveFirst();
  89.  
  90.             KeyAndLinkToNode.Remove(deletedNode!.Value.Item1);
  91.             _count -= 1;
  92.         }
  93.  
  94.         Queue.AddLast((key, value));
  95.         var node = Queue.Last;
  96.         KeyAndLinkToNode[key] = node;
  97.         _count += 1;
  98.     }
  99.  
  100.     public class OurLinkedList<T>
  101.     {
  102.         private int _count;
  103.  
  104.         public OurNode<T> First { get; set; }
  105.         public OurNode<T> Last { get; set; }
  106.         public int Count => _count;
  107.  
  108.         // Добавление элемента в начало списка
  109.         public void AddFirst(T value)
  110.         {
  111.             OurNode<T> newNode = new OurNode<T>(value);
  112.  
  113.             if (First == null)
  114.             {
  115.                 First = newNode;
  116.                 Last = newNode;
  117.             }
  118.             else
  119.             {
  120.                 newNode.Next = First;
  121.                 First.Previous = newNode;
  122.                 First = newNode;
  123.             }
  124.  
  125.             _count++;
  126.         }
  127.  
  128.         // Удаление первого элемента списка
  129.         public void RemoveFirst()
  130.         {
  131.             if (First == null)
  132.                 throw new InvalidOperationException("The list is empty.");
  133.  
  134.             if (First == Last)
  135.             {
  136.                 First = null;
  137.                 Last = null;
  138.             }
  139.             else
  140.             {
  141.                 First = First.Next;
  142.                 First.Previous = null;
  143.             }
  144.  
  145.             _count--;
  146.         }
  147.  
  148.         // Добавление элемента в конец списка
  149.         public void AddLast(T value)
  150.         {
  151.             OurNode<T> newNode = new OurNode<T>(value);
  152.  
  153.             if (Last == null)
  154.             {
  155.                 First = newNode;
  156.                 Last = newNode;
  157.             }
  158.             else
  159.             {
  160.                 newNode.Previous = Last;
  161.                 Last.Next = newNode;
  162.                 Last = newNode;
  163.             }
  164.  
  165.             _count++;
  166.         }
  167.  
  168.         // Удаление последнего элемента списка
  169.         public void RemoveLast()
  170.         {
  171.             if (Last == null)
  172.                 throw new InvalidOperationException("The list is empty.");
  173.  
  174.             if (First == Last)
  175.             {
  176.                 First = null;
  177.                 Last = null;
  178.             }
  179.             else
  180.             {
  181.                 Last = Last.Previous;
  182.                 Last.Next = null;
  183.             }
  184.  
  185.             _count--;
  186.         }
  187.     }
  188.  
  189.     public class OurNode<T>
  190.     {
  191.         public T Value { get; set; }
  192.         public OurNode<T> Previous { get; set; }
  193.         public OurNode<T> Next { get; set; }
  194.  
  195.         public OurNode(T value)
  196.         {
  197.             Value = value;
  198.         }
  199.     }
  200. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement