【C#】使っていない順に自動で破棄してくれるDictionaryクラス

# 概要

使っていない順に自動で破棄してくれるDictionaryクラス「AutoDisposedDictionary」を作りました。
通常のDictionaryと同じように使えます。
要素が指定数を超えたら、使っていない順に指定数破棄されます。
System.Collectionsのインターフェイスを色々と実装したのは初めてなので、不具合や修正案をコメントしていただけると助かります。

# コード

https://github.com/yamara-mh/CodeStorage/blob/main/Codes/AutoDisposedDictionary.cs

``` AutoDisposedDictionary.cs
using System.Collections.Generic;
using System.Linq;
using System;
using System.Collections;

namespace Yamara
{
    public class AutoDisposedDictionary<TKey, TValue> :
        ICollection<KeyValuePair<TKey, TValue>>,
        IEnumerable,
        IDictionary<TKey, TValue>,
        IReadOnlyCollection<KeyValuePair<TKey, TValue>>,
        IReadOnlyDictionary<TKey, TValue>
    {
        public int MaxItemsCount { get; private set; }
        public int AutoDisposeCount;

        private Dictionary<TKey, TValue> _items;
        private Dictionary<TKey, uint> _history;
        private uint _historyCount;
        private Action<TValue> _disposeAction;

        public AutoDisposedDictionary(int maxItemsCount, int autoDisposeCount, Action<TValue> disposeAction = null)
        {
            if (maxItemsCount >= 1)
            {
                MaxItemsCount = maxItemsCount;
                _items = new Dictionary<TKey, TValue>(maxItemsCount);
                _history = new Dictionary<TKey, uint>(maxItemsCount);
            }
            else
            {
                MaxItemsCount = int.MaxValue;
                _items = new Dictionary<TKey, TValue>();
                _history = new Dictionary<TKey, uint>();
            }

            AutoDisposeCount = autoDisposeCount;
        }

        public int Count => _items.Count;
        public bool IsReadOnly => false;
        public ICollection<TKey> Keys => _items.Keys;
        public ICollection<TValue> Values => _items.Values;
        IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys => Keys;
        IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values => Values;
        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() => _items.GetEnumerator();
        IEnumerator IEnumerable.GetEnumerator() => _items.GetEnumerator();

        public bool ContainsKey(TKey key) => _items.ContainsKey(key);

        public bool Contains(KeyValuePair<TKey, TValue> item)
            => _items.ContainsKey(item.Key) && EqualityComparer<TValue>.Default.Equals(_items[item.Key], item.Value);

        public TValue this[TKey key]
        {
            get
            {
                SetHistoryCount(key);
                return _items[key];
            }
            set
            {
                SetHistoryCount(key);
                _items[key] = value;
            }
        }

        public void SetMaxItemsCount(int maxItemsCount)
        {
            if (_items.Count > maxItemsCount) RemoveInUnusedOrder(_items.Count - maxItemsCount);
            MaxItemsCount = maxItemsCount;
        }

#region Add & Get & Copy

        public void Add(TKey key, TValue item)
        {
            _items.Add(key, item);
            SetHistoryCount(key);
            if (_items.Count > MaxItemsCount) RemoveInUnusedOrder(AutoDisposeCount);
        }

        public bool TryAdd(TKey key, TValue item)
        {
            if (ContainsKey(key)) return false;
            _items.Add(key, item);
            SetHistoryCount(key);
            if (_items.Count > MaxItemsCount) RemoveInUnusedOrder(AutoDisposeCount);
            return true;
        }

        public void Add(KeyValuePair<TKey, TValue> item)
        {
            _items.Add(item.Key, item.Value);
            SetHistoryCount(item.Key);
            if (_items.Count > MaxItemsCount) RemoveInUnusedOrder(AutoDisposeCount);
        }

        public void AddRange(IEnumerable<KeyValuePair<TKey, TValue>> pairs)
            => pairs.ToList().ForEach(pair => Add(pair.Key, pair.Value));

        public bool TryGetValue(TKey key, out TValue value)
        {
            if (_items.ContainsKey(key))
            {
                SetHistoryCount(key);
                value = _items[key];
                return true;
            }
            value = default;
            return false;
        }

        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            if (arrayIndex >= _items.Count)
            {
                array = new KeyValuePair<TKey, TValue>[0];
                return;
            }
            array = new KeyValuePair<TKey, TValue>[_items.Count - arrayIndex];

            var list = _items.Skip(arrayIndex).ToList();
            Enumerable.Range(0, list.Count).ToList().ForEach(i => array[i] = list[i]);
        }

        private void SetHistoryCount(TKey key)
        {
            _history[key] = ++_historyCount;
            if (_historyCount == uint.MaxValue)
            {
                _historyCount = 0;
                foreach (var k in _history.OrderBy(kv => kv.Value).Select(kv => kv.Key))
                {
                    _history[k] = ++_historyCount;
                }
            }
        }

        #endregion

#region Remove & Clear

        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            if (_items.Contains(item))
            {
                RemoveProcess(item.Key);
                return true;
            }
            return false;
        }
        
        public bool Remove(TKey key)
        {
            if (_items.ContainsKey(key))
            {
                RemoveProcess(key);
                return true;
            }
            return false;
        }

        public void RemoveRange(IEnumerable<TKey> keys) => keys.ToList().ForEach(key => Remove(key));

        public void RemoveInUnusedOrder(int removeCount)
        {
            _history
                .OrderBy(item => item.Value)
                .Take(Math.Min(Math.Max(removeCount, 0), _items.Count))
                .ToList()
                .ForEach(item => RemoveProcess(item.Key));
        }

        public void RemoveInUnusedOrder(double removeRate)
            => RemoveInUnusedOrder((int)Math.Round(_items.Count * removeRate));

        private void RemoveProcess(TKey key)
        {
            _disposeAction?.Invoke(_items[key]);
            _items.Remove(key);
            _history.Remove(key);
        }

        public void Clear()
        {
            _items.Clear();
            _history.Clear();
            _historyCount = 0;
        }

#endregion

    }
}
```

# 詳細説明
public な関数や変数の中から、説明が必要そうなものの詳細を書きました。

|関数・変数|説明|
|-|-|
|public AutoDisposedCache(<br>int maxItemsCount, <br>int autoDisposeCount, <br>Action<T> disposeAction = null)|コンストラクタです。<br>maxItemsCountには最大保持数、<br>autoDisposeCountには最大保持数を超えた際に自動で破棄する数、<br>disposeActionには要素を破棄する際の処理を入れてください。|
|public void RemoveInUnusedOrder(<br>int removeCount)|利用していない順に要素を並べ、先頭からremoveCount個破棄します。|
|public void RemoveInUnusedOrder(<br>double removeRate)|利用していない順に要素を並べ、先頭から[要素数 * removeRate]個破棄します。|
|public void SetMaxItems(int maxItems)|最大保持数を指定します。現在より小さい値を入れると、利用していない順に溢れた数だけ要素を破棄します。|
|public int AutoDisposeCount|自動破棄時の破棄数を指定します。|

# 使っていない順の求め方メモ
AutoDisposedDictionary では、要素を保持するDictionaryとは別に、使われた順を記録する履歴Dictionaryを用意しています。
また、要素を追加・取得する度に+1される _historyCount も用意しています。
要素の追加・取得に合わせて履歴Dictionaryに _historyCount の値を記録することで、利用されないほど値が小さくなる履歴Dictionaryが出来上がります。
その履歴Dictionaryを昇順にソートすれば、使っていない順が求められます。

### オーバーフロー対策

uint _historyCount をインクリメントし続けるとオーバーフローします。
@albireo さんのコメントをもとに、_historyCount が uint.MaxValue になったら _historyCount を0に、履歴Dictionaryの Value を1からの連番で付け直すようにしました。