LruCache.cs

namespace Cs.Core.Core
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    // 참고 : https://www.geeksforgeeks.org/lru-cache-implementation/
    public sealed class LruCache<TKey, TElement>
    {
        private readonly LinkedList<(TKey Key, TElement Value)> timeline = new LinkedList<(TKey, TElement)>();
        private readonly Dictionary<TKey, LinkedListNode<(TKey, TElement)>> index;

        public LruCache(int maxCount)
        {
            this.index = new Dictionary<TKey, LinkedListNode<(TKey, TElement)>>(maxCount);
            this.MaxCount = maxCount;
        }

        public int Count => this.timeline.Count;
        public IEnumerable<TElement> Values => this.timeline.Select(e => e.Value);
        public int MaxCount { get; }

        public bool TryGetValue(TKey key, out TElement result)
        {
            bool exist = this.index.TryGetValue(key, out var node);
            if (exist == false)
            {
                result = default;
                return false;
            }

            result = node.Value.Item2;
            this.timeline.Remove(node);
            this.timeline.AddFirst(node);
            return true;
        }

        //// 값이 없으면 insert하지만, 존재한다면 touch만 한다.
        public bool Insert(TKey key, TElement element)
        {
            bool insert = false;
            if (this.index.TryGetValue(key, out var node) == false) //// 기존에 값이 존재하지 않음.
            {
                while (this.timeline.Count >= this.MaxCount) //// delete least recently used element
                {
                    var outTarget = this.timeline.Last;
                    this.timeline.RemoveLast();
                    this.index.Remove(outTarget.Value.Key);
                }

                node = new LinkedListNode<(TKey, TElement)>((key, element));
                this.index.Add(key, node);
                insert = true;
            }
            else
            {
                this.timeline.Remove(node);
            }

            this.timeline.AddFirst(node);
            return insert;
        }

        //// 값이 없으면 insert, 존재하면 update.
        public bool Upsert(TKey key, TElement element)
        {
            bool insert = false;
            if (this.index.TryGetValue(key, out var node) == false) //// 기존에 값이 존재하지 않음.
            {
                while (this.timeline.Count >= this.MaxCount) //// delete least recently used element
                {
                    var outTarget = this.timeline.Last;
                    this.timeline.RemoveLast();
                    this.index.Remove(outTarget.Value.Key);
                }

                insert = true;
            }
            else
            {
                this.timeline.Remove(node);
            }

            node = new LinkedListNode<(TKey, TElement)>((key, element));
            this.timeline.AddFirst(node);
            this.index[key] = node;
            return insert;
        }
    }
}